Shay Moran

Conference publications

• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
  Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran
  NeurIPS 2024
• Universal Rates for Active Learning
  Steve Hannneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas
  NeurIPS 2024
• Improved Sample Complexity for Multiclass PAC Learning
  Steve Hannneke, Shay Moran, and Qiang Zhang
  NeurIPS 2024
• Learning-Augmented Algorithms with Explicit Predictors
  Marek Elias, Haim Kaplan, Yishay Mansour, and Shay Moran
  NeurIPS 2024
• Fast Rates for Bandit PAC Multiclass Classification
  Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran
  NeurIPS 2024
• Credit Attribution and Stable Compression
  Roi Livni, Shay Moran, Kobbi Nissim, and Chirag Pabbaraju
  NeurIPS 2024
• Ramsey Theorems for Trees and a General `Private Learning Implies Online Learning' Theorem
  Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari
  FOCS 2024
• Local Borsuk-Ulam, Stability, and Replicability
  Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff
  STOC 2024
• The Real Price of Bandit Information in Multiclass Classification
  Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran
  COLT 2024
• List Sample Compression and Uniform Convergence
  Steve Hanneke, Shay Moran, Tom Waknine
  COLT 2024
• Learnability Gaps of Strategic Classification
  Lee Cohen, Yishay Mansour, Shay Moran, Han Shao
  COLT 2024
• Dual VC Dimension Obstructs Sample Compression by Embeddings
  Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, and Amir Yehudayoff
  COLT 2024
• A Theory of Interpretable Approximations
  Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen
  COLT 2024
• A Unified Characterization of Private Learnability via Graph Theory
  Noga Alon, Shay Moran, Hilla Schefler, and Amir Yehudayoff
  COLT 2024
• Replicability and stability in learning
  Zachary Chase, Shay Moran, and Amir Yehudayoff
  FOCS 2023
• Adversarial Resilience in Sequential Prediction via Abstention
  Surbhi Goel, Steve Hanneke, Shay Moran, Abhishek Shetty
  NeurIPS 2023
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
  Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran
  NeurIPS 2023
• A Trichotomy for Transductive Learning
  Steve Hanneke, Shay Moran, and Jonathan Shafer (should also be here the humble Zachary Chase!)
  NeurIPS 2023
• On Differentially Private Online Prediction
  Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, and Uri Stemmer
  NeurIPS 2023
• The Bayesian Stability Zoo
  Shay Moran, Jonathan Shafer, and Hilla Schefler
  NeurIPS 2023
• Improper Multiclass Boosting
  Nataly Brukhim, Steve Hanneke, and Shay Moran
  COLT 2023
• Multiclass Online Learning and Uniform Convergence
  Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Amber Tewari
  COLT 2023
• Universal Rates for Multiclass Learning
  Steve Hanneke, Shay Moran, and Qian Zhang
  COLT 2023
• Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
  Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran
  COLT 2023
• List Online Learning
  Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili
  COLT 2023
• Fine-Grained Distribution-Dependent Learning Curves
  Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin
  COLT 2023
• Statistical Indistinguishability of Learning Algorithms
  Alkis Kalavasis, Amin Karbasi, Shay Moran, Grigoris Velegkas
  ICML 2023
• Universal Rates for Interactive Learning
  Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas
  NeurIPS 2022
  Oral Presentation
• On Optimal Learning Under Targeted Data Poisoning
  Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran
  NeurIPS 2022
  Oral Presentation
• Integral Probability Metrics PAC-Bayes Bounds
  Ron Amit, Baruch Epstein, Ron Meir, and Shay Moran
  NeurIPS 2022
• A Characterization of Multiclass Learnability
  Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff
  FOCS 2022
  Invited to FOCS special issue of SICOMP
  Invited talk at TCS+ 2022
• Monotone Learning
  Olivier Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, and Uri Stemmer
  COLT 2022
• A Resiliant Distributed Boosting Algorithm
  Yuval FIlmus, Idan Mehalel, Shay Moran
  ICML 2022
• Active Learning with Label Comparisons
  Gal Elidan, Amir Globerson, Shay Moran, and Gal Yona
  UAI 2022
• Uniform Brackets, Containers, and Combinatorial Macbeath Regions
  Kunal Dutta, Arijit Ghosh, and Shay Moran
  ITCS 2022
• Towards a Unified Information-Theoretic Framework for Generalization
  Mahdi Haghifam, Gintare Karolina Dzuigaite, Shay Moran, and Daniel M. Roy
  NeurIPS 2021
  Spotlight Presentation
• Multiclass Boosting and the Cost of Weak Learning
  Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E. Schapire
  NeurIPS 2021
• A Theory of PAC Learnability of Partial Concept Classes
  Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran
  FOCS 2021
• Statistically Near-Optimal Hypothesis Selection
  Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, and Shay Moran
  FOCS 2021
• Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
  Steve Hanneke, Roi Livni, and Shay Moran
  COLT 2021
  Best Paper Runner-up
• Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
  Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh R. Saxena
  COLT 2021
• Boosting Simple Learners
  Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran
  STOC 2021
• Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
  Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev
  STOC 2021
  Invited and accepted to STOC special issue of SICOMP
• A Theory of Universal Learning
  Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff
  STOC 2021
  Invited talk at TCS+ 2021
  Invited to HALG 2022
• The entropy of lies: playing twenty questions with a liar
  Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran
  ITCS 2021
• Learning from Mixtures of Private and Public Populations
  Raef Bassily, Shay Moran, and Anupama Nandi
  NeurIPS 2020
• A Limitation of the PAC-Bayes Framework
  Roi Livni and Shay Moran
  NeurIPS 2020
• Online Agnostic Boosting via Regret Minimization
  Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran
  NeurIPS 2020
• Synthetic Data Generators - Sequential and Private
  Olivier Bousquet, Roi Livni, and Shay Moran
  NeurIPS 2020
• An Equivalence Between Private Classification and Online Prediction
  Mark Bun, Roi Livni, and Shay Moran
  FOCS 2020
  Best Paper Award
  Invited to JACM
  Invited talk at TCS+ 2020
  Plenary talk at TPDP 2020
  Invited to HALG 2021
• Private Query Release Assisted by Public Data
  Raef Bassily, Albert Cheu, Shay Moran, Alexander Nikolov, Jonathan Ullman, and Zhiwey Steven Wu
  ICML 2020
  Plenary talk at TPDP 2020
• Proper Learning, Helly Number, and an Optimal SVM Bound
  Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy
  COLT 2020
  Best Paper Award
  Invited to Journal of Mathematical Statistics and Learning
  Invited to HALG 2021
• Closure Properties for Private Classification and Online Prediction
  Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer
  COLT 2020, TPDP 2020
• On the Perceptron's Compression
  Shay Moran, Ido Nachum, Itai Panasoff, and Amir Yehudayoff
  CiE 2020
• An adaptive nearest neighbor rule for classification
  Akshay Balsubramani, Sanjoy Dasgupta, Yoav Freund, and Shay Moran
  NeurIPS 2019
  Spotlight Presentation
• Private Learning implies Online Learning: An Efficient Reduction
  Alon Gonen, Elad Hazan, and Shay Moran
  NeurIPS 2019
  Spotlight Presentation
• Limits of Private Learning with Access to Public Data
  Noga Alon, Raef Bassily, and Shay Moran
  NeurIPS 2019
• Learning to Screen
  Alon Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, and Shay Moran
  NeurIPS 2019
• Private Centerpoints and Learning of Halfspaces
  Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer
  COLT 2019
• The Optimal Approximation Factor in Density Estimation
  Olivier Bousquet, Daniel Kane, and Shay Moran
  COLT 2019
• On Communication Complexity of Classification Problems
  Daniel Kane, Roi Livni, Shay Moran, and Amir Yehudayoff
  COLT 2019
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
  Jeremie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth
  ICALP 2019
• Private PAC learning implies finite Littlestone dimension
  Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
  STOC 2019
  Plenary presentation at the "Theory and Practice of Differential Privacy 2018" workshop
• On weak epsilon-nets and the Radon number
  Shay Moran and Amir Yehudayoff
  SoCG 2019
  Invited and accepted to a special issue of Discrete & Computational Geometry (DCG)
• Generalized comparison trees for point-location problems
  Daniel Kane, Shachar Lovett, and Shay Moran
  ICALP 2018
• Are Two (Samples) Really Better Than One? On The Non-Asymptotic Performance of Empirical Revenue Maximization
  Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, and Shay Moran
  EC 2018
• Near-optimal linear decision trees for k-SUM and related problems
  Daniel Kane, Shachar Lovett, and Shay Moran
  STOC 2018
  Invited to STOC special issue of SICOMP (declined in favor of J. ACM)
  Invited talks at TCS+ 2018 and HALG 2019
• Learners that Leak Little Information
  Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff
  ALT 2018
• Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
  Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, and Amir Yehudayoff
  NIPS 2017
  Spotlight Presentation
• Active classification with comparison queries
  Daniel Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang
  FOCS 2017
• Twenty (simple) questions
  Yuval Dagan, Ariel Gabizon, Yuval Filmus, and Shay Moran
  STOC 2017
  Invited to HALG 2018
• On statistical learning via the lens of compression
  Ofir David, Shay Moran, and Amir Yehudayoff
  NIPS 2016
  Full oral presentation
• Labeled compression schemes for extremal classes
  Shay Moran and Manfred K. Warmuth
  ALT 2016
• Fooling Pairs in Randomized Communication Complexity
  Shay Moran, Makrand Sinha, and Amir Yehudayoff
  SIROCCO 2016
• Hitting set for hypergraphs of low VC-dimension
  Karl Bringmann, László Kozma, Shay Moran, and N.S. Narayanaswami
  ESA 2016
• Shattered Sets and the Hilbert Function
  Shay Moran and Cyrus Rashtchian
  MFCS 2016
• Sign rank, VC dimension and spectral gaps
  Noga Alon, Shay Moran, and Amir Yehudayoff
  COLT 2016
• Node-balancing by edge-increments
  Friedrich Eisenbrand, Shay Moran, Rom Pinchasi, and Martin Skutella
  ESA 2015
• Teaching and compressing for low VC dimension
  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff
  FOCS 2015
  Invited to FOCS special issue of SICOMP (declined in favor of J.ACM)
  The conference version combines two separate papers:
  Teaching and compressing for low VC dimension
  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff
  Sample compression schemes for VC classes
  Shay Moran and Amir Yehudayoff
• Internal compression of protocols to entropy
  Balthazar Bauer, Shay Moran, and Amir Yehudayoff
  RANDOM 2015
• Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  ICALP 2014
• Direct sum fails for zero error average communication
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  ITCS 2014
  Invited to a special issue of Algorithmica