- Corrupted Learning Dynamics in Games
Taira Tsuchiya (The University of Tokyo); Shinji Ito (The University of Tokyo and RIKEN); Haipeng Luo (University of Southern California)
- A Theory of Learning with Autoregressive Chain of Thought
Nirmit Joshi (Toyota Technological Institute at Chicago); Nathan Srebro (Toyota Technological Institute at Chicago); Gal Vardi (Weizmann Institute of Science); Adam Block (Microsoft Research); Surbhi Goel (University of Pennsylvania); Zhiyuan Li (Toyota Technological Institute at Chicago); Theodor Misiakiewicz (Yale University)
- Anytime Acceleration of Gradient Descent
Zihan Zhang (Princeton University); Jason Lee (Princeton University); Simon Du (University of Washington); Yuxin Chen (University of Pennsylvania)
- Deterministic Apple Tasting
Zachary Chase (University of California San Diego); Idan Mehalel (Technion)
- Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality
Andre Wibisono (Yale University)
- On the Convergence of Min-Max Langevin Dynamics and Algorithm
Yang Cai (Yale University); Siddharth Mitra (Yale University); Xiuyuan Wang (Yale University); Andre Wibisono (Yale University)
- Generation through the lens of learning theory
Vinod Raman (University of Michigan); Ambuj Tewari (University of Michigan); Jiaxun Li (University of Michigan)
- Optimal Differentially Private Sampling of Unbounded Gaussians
Valentio Iverson (University of Waterloo); Gautam Kamath (University of Waterloo); Argyris Mouzakis (University of Waterloo)
- Recovering Labels from Crowdsourced Data: an Optimal and Polynomial-Time Method
Emmanuel Pilliat (ENSAI)
- Approximating the total variation distance between spin systems
Weiming Feng (The University of Hong Kong); Hongyang Liu (Nanjing University); Minji Yang (The University of Hong Kong)
- Statistical and Computational Limits of Detecting Arbitrary Planted Subgraphs in Random Graphs
Dor Elimelech (Tel Aviv University); Wasim Huleihel (Tel Aviv University)
- The Oracle Complexity of Simplex-based Matrix Games: Linear Separability and Nash Equilibria
Guy Kornowski (Weizmann Institute of Science); Ohad Shamir (Weizmann Institute of Science)
- Low-dimensional adaptation of diffusion models: Convergence in total variation
Jiadong Liang (University of Pennsylvania); Zhihan Huang (University of Pennsylvania); Yuxin Chen (University of Pennsylvania)
- Robust random graph matching in dense graphs via vector approximate message passing
Zhangsong Li (Peking University)
- Compression Barriers in Autoregressive Transformers
Themistoklis Haris (Boston University); Krzysztof Onak (Boston University)
- Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimization
Chandan Tankala (University of Oregon); Dheeraj Nagaraj (Google Research); Anant Raj (Indian Institute of Science)
- Structure-agnostic Optimality of Doubly Robust Learning for Treatment Effect Estimation
JIKAI JIN (Stanford University); Vasilis Syrgkanis (Stanford University)
- Sparsity-Based Interpolation of External, Internal and Swap Regret
Zhou Lu (Princeton University); Y. Jennifer Sun (Princeton University); Zhiyu Zhang (Harvard University)
- A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
Hang Du (MIT); Shuyang Gong (Peking University ); Jiaming Xu (Duke University )
- Some easy optimization problems have the overlap-gap property
Shuangping Li (Stanford University); Tselil Schramm (Stanford University)
- Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Φ-Mutual Information
Siddharth Mitra (Yale University); Andre Wibisono (Yale University); Jiaming Liang (University of Rochester)
- A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions
Junfan Li (Harbin Institute of Technology, Shenzhen); Shizhong Liao (Tianjin University); Zenglin Xu (Fudan University); Liqiang Nie (Harbin Institute of Technology, Shenzhen)
- What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness
Yang Cai (Yale University); Alkis Kalavasis (Yale University); Katerina Mamali (Yale University); Anay Mehrotra (Yale University); Manolis Zampetakis (Yale University)
- Fast and Multiphase Rates for Nearest Neighbor Classifiers
Pengkun Yang (Tsinghua University); Jingzhao Zhang (Tsinghua University)
- Improved Algorithms for Effective Resistance Computation on Graphs
Yichun Yang (Beijing Institute of Technology); Rong-Hua Li (Beijing Institute of Technology); Meihao Liao (Beijing Institute of Technology); Guoren Wang (Beijing Institute of Technology)
- Depth Separations in Neural Networks: Separating the Dimension from the Accuracy
Itay Safran (Purdue University); Daniel Reichman (WPI); Paul Valiant (Purdue University)
- Of Dice and Games: A Theory of Generalized Boosting
Marco Bressan (University of Milan); Nataly Brukhim (Princeton); Nicolò Cesa-Bianchi (University of Milan); Emmanuel Esposito (University of Milan); Yishay Mansour (Tel Aviv University and Google Research); Shay Moran (Technion and Google Research); Maximilian Thiessen (TU Wien)
- Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
Minhui Jiang (ETH Zürich); Yuansi Chen (ETH Zürich)
- Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black (UC San Diego); Arya Mazumdar (UC San Diego); Barna Saha (UC San Diego); Yinzhan Xu (UC San Diego)
- The Pitfalls of Imitation Learning When Actions Are Continuous
Daniel Pfrommer (Massachusetts Institute of Technology); Max Simchowitz (Carnegie Mellon University); Ali Jadbabaie (Massachusetts Institute of Technology)
- Gradient Methods with Online Scaling
Wenzhi Gao (Stanford University); Ya-Chi Chu (Stanford University); Yinyu Ye (Stanford University); Madeleine Udell (Stanford University)
- Data-dependent Bounds with $T$-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits using Stability-Penalty Matching
Quan Nguyen (University of Victoria); Shinji Ito (The University of Tokyo/RIKEN); Junpei Komiyama (New York University/RIKEN); Nishant Mehta (University of Victoria)
- Improved Margin Generalization Bounds for Voting Classifiers
Mikael Møller Høgsgaard (Aarhus University); Kasper Green Larsen (Aarhus University)
- Complexity of Injectivity and Verification of ReLU Neural Networks
Moritz Grillo (Technische Universität Berlin); Vincent Froese (Technische Universität Berlin); Martin Skutella ( Technische Universität Berlin)
- Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes
Victor S. Portella (University of São Paulo); Nick Harvey (University of British Columbia)
- Stability and List-Replicability for Agnostic Learners
Ari Blondal (McGill University); Shan Gao (McGill University); Hamed Hatami (McGill University); Pooya Hatami (Ohio State University)
- Quantum State and Unitary Learning Implies Circuit Lower Bounds
Daniel Liang (Portland State University); Nai-Hui Chia (Rice University); Fang Song (Portland State University)
- Learning Constant-Depth Circuits in Malicious Noise Models
Adam Klivans (University of Texas at Austin); Konstantinos Stavropoulos (University of Texas at Austin); Arsen Vasilyan (University of Texas at Austin)
- Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity
Dominik Stöger (KU Eichstätt-Ingolstadt); Yizhe Zhu (USC)
- Testing (Conditional) Mutual Information
Jan Seyfried (Centre for Quantum Technologies, National University of Singapore); Sayantan Sen (Centre for Quantum Technologies, National University of Singapore); Marco Tomamichel (Department of Electrical and Computer Engineering & Centre for Quantum Technologies, National University of Singapore)
- Logarithmic Width Suffices for Robust Memorization
Amitsour Egosi (Weizmann Institute of Science ); Gilad Yehudai (Weizmann Institute of Science); Ohad Shamir (Weizmann Institute of Science)
- The Adaptive Complexity of Finding a Stationary Point
Huanjian Zhou (The University of Tokyo/RIKEN); Andi Han (RIKEN); Akiko Takeda (The University of Tokyo/RIKEN); Masashi Sugiyama (RIKEN/The University of Tokyo)
- Multi-Pass Memory Lower Bounds for Learning Problems
Qian Li (Shenzhen Research Institute of Big Data); Shuo Wang (MIT); Jiapeng Zhang (University of Southern California)
- Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(\epsilon^{-4/7})$ Second-Order Oracle Complexity
Lesi Chen (Tsinghua University); Chengchang Liu (The Chinese University of Hong Kong); Luo Luo (Fudan University); Jingzhao Zhang (Tsinghua University)
- Blackwell's Approachability with Approximation Algorithms
Dan Garber (Technion); Mhna Massalha (Technion)
- Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery
Filip Kovačević (IST Austria); Yihan Zhang (IST Austria); Marco Mondelli (IST Austria)
- Testing Juntas and Junta Subclasses with Relative Error
Rocco Servedio (Columbia University); Xi Chen (Columbia University); William Pires (Columbia University); Toniann Pitassi (Columbia University)
- Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play
John Lazarsfeld (SUTD); Georgios Piliouras (Google Deepmind); Ryann Sim (SUTD); Andre Wibisono (Yale)
- Universal rates of ERM for agnostic learning
Steve Hanneke (Purdue University); Mingyue Xu (Purdue University)
- Model predictive control is almost optimal for restless bandits
Dheeraj Narasimha (INRIA); Nicolas Gast (INRIA)
- Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorization
Yu-Han WU (Sorbonne University); Pierre Marion (EPFL); Gérard Biau (Sorbonne Université); Claire Boyer (Université Paris-Saclay)
- Span-Agnostic Optimal Sample Complexity for Average-Reward RL
Matthew Zurek (UW-Madison); Yudong Chen (UW-Madison)
- Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks
- Accelerating Proximal Gradient Descent via Silver Stepsizes
Jinho Bok (University of Pennsylvania); Jason Altschuler (University of Pennsylvania)
- Lower Bounds for Greedy Teaching Set Constructions
Spencer Compton (Stanford University); Chirag Pabbaraju (Stanford University); Nikita Zhivotovskiy (UC Berkeley)
- Experimental Design for Semiparametric Bandits
Seok Jin Kim (Columbia University); Gi-Soo Kim (UNIST); Min-hwan Oh (Seoul National University)
- Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification
Dhruv Rohatgi (Massachusetts Institute of Technology); Adam Block (Columbia University); Audrey Huang (University of Illinois Urbana-Champaign); Akshay Krishnamurthy (Microsoft Research); Dylan Foster (Microsoft Research)
- Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy
Fan Chen (MIT); Alexander Rakhlin (MIT)
- Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
Ainesh Bakshi (MIT); Vincent Cohen-Addad (Google Research); Sam Hopkins (MIT); Rajesh Jayaram (Google Research); Silvio Lattanzi (Google Research)
- Learning Partitions with Optimal Query and Round Complexities
Hadley Black (UC San Diego); Arya Mazumdar (UC San Diego); Barna Saha (UC San Diego)
- Improved Offline Contextual Bandits with Second-Order Bounds and Beyond with Betting and Freezing
Jongha Ryu (Massachusetts Institute of Technology); Jeongyeol Kwon (University of Wisconsin-Madison); Benjamin Koppe (Cornell University); Kwang-Sung Jun (University of Arizona)
- The Role of Environment Access in Agnostic Reinforcement Learning
Akshay Krishnamurthy (Microsoft Research); Gene Li (TTIC); Ayush Sekhari (MIT)
- Learning sparse generalized linear models with binary outcome via iterative hard thresholding
Namiko Matsumoto (UC San Diego); Arya Mazumdar (University of California, San Diego)
- Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications
Yizhou Xu (EPFL); Antoine Maillard (INRIA); FLORENT KRZAKALA (EPFL); Lenka Zdeborova (EPFL)
- Sharper Bounds for Chebyshev Moment Matching, with Applications
Cameron Musco (UMass Amherst); Christopher Musco (New York University); Lucas Rosenblatt (New York University); Apoorv Vikram Singh (New York University)
- Non-Euclidean High-Order Smooth Convex Optimization
Juan Pablo Contreras (Universidad Católica de Chile); Cristóbal Guzmán (Universidad Católica de Chile); David Martínez-Rubio (ZIB)
- Predicting quantum channels over general product distributions
Sitan Chen (Harvard); Jaume de dios Pont (ETH); Jun-Ting Hsieh (CMU); Hsin-Yuan Huang (Caltech); Jane Lange (MIT); Jerry Li (-)
- PREM: Privately Answering Statistical Queries with Relative Error
Badih Ghazi (Google); Cristóbal Guzmán (Institute for Mathematical and Computational Engineering, Pontificia Universidad Cat\'olica de Chile ); Pritish Kamath (Google); Alexander Knop (Google); Ravi Kumar (Google); Pasin Manurangsi (Google); Sushant Sachdeva (University of Toronto)
- Truthfulness of Decision-Theoretic Calibration Measures
Mingda Qiao (Massachusetts Institute of Technology); Eric Zhao (UC Berkeley)
- Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning
Dhruv Rohatgi (Massachusetts Institute of Technology); Dylan Foster (Microsoft Research)
- Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers
Kean Chen (University of Pennsylvania); Qisheng Wang (University of Edinburgh)
- A Distributional-Lifting Theorem for PAC Learning
Guy Blanc (Stanford); Jane Lange (MIT); Carmen Strassle (Stanford); Li-Yang Tan (Stanford)
- Better private distribution testing by leveraging unverified auxiliary data
Maryam Aliakbarpour (Rice University); Arnav Burudgunte (Purdue University); Clément Canonne (University of Sydney); Ronitt Rubinfeld (MIT)
- Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
Antoine Moulin (Universitat Pompeu Fabra); Gergely Neu (Universitat Pompeu Fabra); Luca Viano (EPFL)
- Bayes correlated equilibria, no-regret dynamics in Bayesian games, and the price of anarchy
Kaito Fujii (National Institute of Informatics)
- Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
Yuzhou Gu (New York University); Xin Li (Johns Hopkins University); Yinzhan Xu (University of California, San Diego)
- Learning DNF through Generalized Fourier Representations
Mohsen Heidari (Indiana University); Roni Khardon (Indiana University)
- Improved algorithms for learning quantum Hamiltonians, via flat polynomials
Shyam Narayanan (Massachusetts Institute of Technology)
- Learning shallow quantum circuits with many-qubit gates
Francisca Vasconcelos (UC Berkeley); Hsin-Yuan Huang (Caltech)
- Time-Uniform, Self-Normalized Concentration for Vector-Valued Processes
Justin Whitehouse (Carnegie Mellon University); Aaditya Ramdas (Carnegie Mellon University); Steven Wu (Carnegie Mellon University)
- Rate-Preserving Reductions for Blackwell Approachability
Christoph Dann (Google); Yishay Mansour (Google); Mehryar Mohri (Google); Jon Schneider (Google); Balasubramanian Sivan (Google)
- Orthogonal Causal Calibration
Justin Whitehouse (Stanford University); Vasilis Syrgkanis (Stanford); Bryan Wilder (Carnegie Mellon University); Chris Jung (Meta); Steven Wu (Carnegie Mellon University)
- Computing High-dimensional Confidence Sets for Arbitrary Distributions
Chao Gao (University of Chicago); Liren Shan (Toyota Technological Institute, Chicago); Vaidehi Srinivas (Northwestern University); Aravindan Vijayaraghavan (Northwestern University)
- Universal Rates for Multiclass Learning with Bandit Feedback
Steve Hanneke (Purdue University); Amirreza Shaeiri (Purdue University); Qian Zhang (Purdue University)
- DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
Jerry Chee (Cornell University); Arturs Backurs (Microsoft Research); Rainie Heck (University of Washington); Li Zhang (Microsoft); Janardhan Kulkarni (Microsoft Research); Thomas Rothvoss (University of Washington); Sivakanth Gopi (Microsoft Research)
- Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
Anxin Guo (Northwestern University); Aravindan Vijayaraghavan (Northwestern University)
- Community detection with the Bethe-Hessian
Ludovic Stephan (Univ Rennes, Ensai, CNRS, CREST); Yizhe Zhu (University of Southern California)
- Online Covariance Estimation in Nonsmooth Stochastic Approximation
Liwei Jiang (Georgia Institute of Technology); Abhishek Roy (Texas A&M University); Krishna Balasubramanian (University of California, Davis); Damek Davis (University of Pennsylvania); Dmitriy Drusvyatskiy (University of Washington); Sen Na (Georgia Institute of Technology)
- Towards Fair Representation: Clustering and Consensus
Diptarka Chakraborty (National University of Singapore); Debarati Das (Pennsylvania State University); Kushagra Chatterjee (National University of Singapore); Tien Long Nguyen (Pennsylvania State University); Romina Nobahari (Sharif University of Technology)
- Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
Thanasis Pittas (University of Wisconsin-Madison); Ankit Pensia (Simons Institute for the Theory of Computing)
- Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries
Arnab Maiti (University of Washington); Zhiyuan Fan (Massachusetts Institute of Technology); Gabriele Farina (Massachusetts Institute of Technology); Kevin Jamieson (University of Washington); Lillian Ratliff (University of Washington)
- Simplifying Adversarially Robust PAC Learning with Tolerance
Hassan Ashtiani (McMaster University); Vinayak Pathak (Layer6 AI); Ruth Urner (York University)
- Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
Dmitriy Kunisky (Johns Hopkins University)
- Robust Algorithms for Recovering Planted $r$-Colorable Graphs
Anand Louis (Indian Institute of Science); Rameesh Paul (Indian Institute of Science); Prasad Raghavendra (University of California, Berkeley)
- Optimal Low degree hardness for Broadcasting on Trees
Han Huang (University of Missouri); Elchanan Mossel (MIT)
- Are all models wrong? Fundamental limits in distribution-free empirical model falsification
Manuel Mueller (University of Cambridge); Yuetian Luo (University of Chicago); Rina Foygel Barber (University of Chicago)
- Regret Bounds for Robust Online Decision Making
Alexander Appel (Computational Rational Agents Laboratory, Ashgro); Vanessa Kosoy (Technion - Israel Institute of Technology)
- Linear Convergence of Diffusion Models Under the Manifold Hypothesis
Peter Potaptchik (Oxford); Iskander Azangulov (Oxford); George Deligiannidis (Oxford)
- Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback
Shinji Ito (The University of Tokyo); Haipeng Luo (University of Southern California); Taira Tsuchiya (The University of Tokyo); Yue Wu (University of Southern California)
- An Uncertainty Principle for Linear Recurrent Neural Networks
Alexandre François (National Institute for Research in Digital Science and Technology); Francis Bach (INRIA); Antonio Orvieto (ELLIS Institute)
- Optimistic Q-learning for average reward and episodic reinforcement learning
Priyank Agrawal (Columbia University); Shipra Agrawal (Columbia University)
- Linear Bandits on Ellipsoids: Minimax Optimal Algorithms
Raymond Zhang (CentraleSupelec); Hédi Hadiji (CentraleSupelec); Richard Combes (CentraleSupelec)
- Non-Monetary Mechanism Design without Distributional Information: Using Scarce Audits Wisely
Yan Dai (ORC, MIT); Moise Blanchard (Columbia University); Patrick Jaillet (MIT)
- Information-theoretic reduction of deep neural networks to linear models in the overparametrized proportional regime
Francesco Camilli (Abdus Salam International Centre for Theoretical Physics (ICTP)); Daria Tieplova (Abdus Salam International Centre for Theoretical Physics (ICTP)); Jean Barbier ( Abdus Salam International Centre for Theoretical Physics (ICTP)); Eleonora Bergamin (International School for Advanced Studies)
- The late-stage training dynamics of (stochastic) subgradient descent on homogeneous neural networks
Sholom Schechtman (Télécom SudParis); Nicolas Schreuder (DIBRIS, MALGA)
- Computational Intractability of Strategizing against Online Learners
Yuval Dagan (-MIT); Angelos Assos (MIT); Nived Rajaraman (UC Berkeley)
- Learning general Gaussian mixtures with efficient score matching
Sitan Chen (Harvard University); Vasilis Kontonis (University of Texas Austin); Kulin Shah (University of Texas Austin)
- Data Selection for ERMs
Steve Hanneke (Purdue University); Shay Moran (Technion and Google Research); Alexander Shlimovich (Technion); Amir Yehudayoff (Technion and Copenhagen University)
- Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions
Samuel Baguley (Hasso Plattner Institute); Andreas Göbel (Hasso Plattner Institute); Marcus Pappik (Hasso Plattner Institute); Leon Schiller (Hasso Plattner Institute)
- Learning Augmented Graph k-Clustering
Kijun Shin (Seoul National University); Chenglin Fan (Seoul National University)
- Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity
Bo Li (HKUST); Wei Wang (HKUST); Peng Ye (HKUST)
- Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on $\so(d)$
Amit Daniely (Hebrew University)
- On the query complexity of sampling from non-log-concave distributions
Yuchen He (Shanghai Jiao Tong University); Chihao Zhang (Shanghai Jiao Tong University)
- Logarithmic regret of exploration in average reward Markov decision processes
Victor Boone (Université Grenoble Alpes); Bruno Gaujal (Inria)
- Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments
Yuanyu Wan (Zhejiang University)
- Algorithms for Sparse LPN and LSPN Against Low-noise
Xue Chen (University of Science and Technology of China); Zhaienhe Zhou (University of Science and Technology of China ); Wenxuan Shu (University of Science and Technology of China)
- Optimal Online Bookmaking For Any Number of Outcomes
Hadar Tal (The Hebrew University of Jerusalem); Oron Sabag (The Hebrew University of Jerusalem)
- From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs
Cynthia Dwork (Harvard University); Chris Hays (Massachusetts Institute of Technology); Nicole Immorlica (Microsoft Research); Juan C. Perdomo (Harvard University); Pranay Tankala (Harvard University)
- Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
Guy Bresler (Massachusetts Institute of Technology); Alina Harbuzova (Massachusetts Institute of Technology)
- Efficiently learning and sampling multimodal distributions with data-based initialization
Frederic Koehler (Stanford); Holden Lee (Johns Hopkins University); Thuy-Duong Vuong (UC Berkeley)
- On the Hardness of Bandit Learning
Nataly Brukhim (Institute of Advanced Studies); Aldo Pacchiano (Broad Institute of MIT and Harvard, Boston University); Miroslav Dudik (Microsoft); Robert Schapire (Microsoft)
- Thompson Sampling for Bandit Convex Optimisation
Alireza Bakhtiari (University of Alberta); Tor Lattimore (DeepMind); Csaba Szepesvari (Google DeepMind and University of Alberta)
- Spherical Dimension
Bogdan Chornomaz (Technion); Shay Moran (-); Tom Waknine (Technion)
- Learning Algorithms in the Limit
Hristo Papazov (EPFL); Nicolas Flammarion (EPFL)
- Identifiability and Estimation in High-Dimenisonal Nonparametric Latent Structure Models
Yichen Lyu (Tsinghua University); Pengkun Yang (Tsinghua University)
- Learning Compositional Functions with Transformers from Easy-to-Hard Data
Zixuan Wang (Princeton University); Eshaan Nichani (Princeton University); Alberto Bietti (Flatiron Institute); Alex Damian (Princeton University); Daniel Hsu (Columbia University); Jason Lee (Princeton University); Denny Wu (New York University and Flatiron Institute)
- Heavy-tailed Estimation is Easier than Adversarial Contamination
Yeshwanth Cherapanamjeri (MIT); Daniel Lee (MIT)
- Low-dimensional functions are efficiently learnable under randomly biased distributions
Elisabetta Cornacchia (Inria); Dan Mikulincer (University of Washington); Elchanan Mossel (MIT)
- Faster Acceleration for Steepest Descent
Site Bai (Purdue University); Brian Bullins (Purdue University)
- Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization
Ruichen Jiang (UT Austin); Devyani Maladkar (UT Austin); Aryan Mokhtari (UT Austin)
- Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient Algorithms
Lukas Hintze (University of Hamburg); Lena Krieg (TU Dortmund University); Olga Scheftelowitsch (TU Dortmund); Haodong Zhu (Eindhoven University of Technology)
- Spike-and-Slab Posterior Sampling in High Dimensions
Yusong Zhu ( University of Texas at Austin); Syamantak Kumar (University of Texas at Austin); Purnamrita Sarkar (University of Texas at Austin ); Kevin Tian (University of Texas at Austin)
- Learning Intersections of Two Margin Halfspaces under Factorizable Distributions
Ilias Diakonikolas (UW-Madison); Mingchen Ma (UW-Madison); Lisheng Ren (UW-Madison); Christos Tzamos (University of Athens)
- Market Making without Regret
Nicolò Cesa-Bianchi (University of Milan); Tom Cesari (University of Ottawa); Roberto Colomboni (Politecnico di Milano); Luigi Foscari (University of Milan); Vinayak Pathak (Independent)
- Sample Efficient Downstream Swap Regret and Omniprediction for Non-Linear Losses
Jiuyao Lu (University of Pennsylvania); Aaron Roth (University of Pennsylvania); Mirah Shi (University of Pennsylvania)
- Faster Algorithms for Agnostically Learning Disjunctions and their Implications
Ilias Diakonikolas (University of Wisconsin-Madison); Daniel M. Kane (University of California San Diego); Lisheng Ren (University of Wisconsin-Madison)
- Can a calibration metric be both testable and actionable?
Raphael Rossellini (University of Chicago); Jake Soloff (University of Chicago); Rina Foygel Barber (University of Chicago); Zhimei Ren (University of Pennsylvania ); Rebecca Willett (University of Chicago)
- The Planted Spanning Tree Problems: Exact Overlap Characterization via Local Weak Convergence
Mehrdad Moharrami (University of Iowa); Cris Moore (Santa Fe Institute); Jiaming Xu (Duke University)
- Quantifying Overfitting along the Regularization Path for Two-Part-Code MDL in Supervised Classification
Xiaohan Zhu (University of Chicago); Nathan Srebro (Toyota Technological Institute at Chicago)
- The Fundamental Limits of Recovering Planted Subgraphs
Daniel Lee (Massachusetts Institute of Technology); Francisco Pernice (Massachusetts Institute of Technology); Amit Rajaraman (Massachusetts Institute of Technology); Ilias Zadik (Yale)
- Language Model Reinforcement Learning: Exploration and the Computational Role of the Base Model
Dylan Foster (Microsoft Research); Zakaria Mhammedi (Google Research); Dhruv Rohatgi (Massachusetts Institute of Technology)
- Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystrom Method
Sachin Garg (University of Michigan); Michal Derezinski (University of Michigan)
- Computing Optimal Regularizers for Online Linear Optimization
Khashayar Gatmiry (MIT); Jon Schneider (Google); Stefanie Jegelka (MIT)
- Gap in Gaussian RKHS and Neural Networks: An infinite sample asymptotic
Akash Kumar (University of California San Diego); Rahul Parhi (University of California San Diego); Misha Belkin ( University of California San Diego)
- Computable learning of natural hypothesis classes
Syed Akbari (University of Michigan); Matthew Harrison-Trainor (University of Illinois Chicago)
- Learning Mixtures of Gaussians Using Diffusion Models
Khashayar Gatmiry (Massachusetts Institute of Technology); Holden Lee (John Hopkins University); Jonathan A. Kelner (Massachusetts Institute of Technology)
- Proofs as Explanations: Short Certificates for Reliable Predictions
Avrim Blum (Toyota Technological Institute at Chicago); Steve Hanneke (Purdue University); Chirag Pabbaraju (Stanford University); Donya Saless (Toyota Technological Institute at Chicago)
- Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts
Pan Peng (University of Science and Technology of China); Hangyu Xu (University of Science and Technology of China)
- "All-Something-Nothing" Phase Transitions in Planted k-Factor Recovery
Julia Gaudio (Northwestern University); Colin Sandon (EPFL); Jiaming Xu (Duke University); Dana Yang (Cornell University)
- A Fine-grained Characterization of PAC Learnability
Marco Bressan (University of Milan); Nataly Brukhim (Princeton); Nicolò Cesa-Bianchi (University of Milan); Emmanuel Esposito (University of Milan); Yishay Mansour (Tel Aviv University and Google Research); Shay Moran (Technion and Google Research); Maximilian Thiessen (TU Wien)
- Robustly Learning Monotone Generalized Linear Models via Data Augmentation
Ilias Diakonikolas (University of Wisconsin-Madison); Jelena Diakonikolas (University of Wisconsin-Madison ); Puqian Wang (University of Wisconsin-Madison); Nikos Zarifis (University of Wisconsin-Madison )
- New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
El Mehdi Saad (Paris Saclay University); Wei-Cheng Lee (KAUST); Francesco Orabona (KAUST)
- How to safely discard features based on aggregate SHAP values
Robi Bhattacharjee (University of Tuebingen); Karolin Frohnapel (University of Tuebingen); Ulrike Luxburg (University of Tuebingen)
- Universality of High-Dimensional Logistic Regression and a Novel CGMT under Block Dependence with Applications to Data Augmentation
Matthew Esmaili Mallory (Harvard University); Kevin Han Huang (UCL); Morgane Austern (Harvard University)
- Estimating stationary mass, frequency by frequency
Milind Nakul (Georgia Institue of Technology); Vidya Muthukumar (Georgia Institute of Technology); Ashwin Pananjady (Georgia Institute of Technology)
- Metric Clustering and Graph Optimization Problems using Weak Comparison Oracles
Syamantak Das (IIIT-Delhi); Sainyam Galhotra (Cornell University); Wen-Zhi Li (Cornell University); Rahul Raychaudhury (Duke University); Stavros Sintos (University of Illinois Chicago)
- The Space Complexity of Learning-Unlearning Algorithms
Yeshwanth Cherapanamjeri (MIT); Sumegha Garg (Rutgers University); Ayush Sekhari (CORNELL UNIVERSITY); Abhishek Shetty (MIT); Nived Rajaraman (UC Berkeley)
- Online Scheduling and Learning with Delays
Alexander Ryabchenko (University of Toronto); Idan Attias (TTIC); Daniel Roy (University of Toronto)
- Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
Zakaria Mhammedi (MIT)
- Local Regularizers Are Not Transductive Learners
Sky Jafar (University High School); Julian Asilis (University of Southern California); Shaddin Dughmi (University of Southern California)
- Private List Learnability vs. Online List Learnability
Steve Hanneke (Purdue University); Shay Moran (Technion); Hilla Schefler (Technion); Iska Tsubari (Technion)
- Decision Making in Hybrid Environments: A Model Aggregation Approach
Haolin Liu (University of Virginia); Chen-Yu Wei (University of Virginia); Julian Zimmert (Google)
- The Sample Complexity of Simple Binary Hypothesis Testing: Tight Bounds with Sequential Interactivity and Information Constraints
Hadi Kazemi (University of Cambridge); Ankit Pensia (UC Berkeley); Varun Jog (University of Cambridge)
- Online Convex Optimization with a Separation Oracle
Zakaria Mhammedi (MIT)
- Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials
August Chen (Cornell University); Karthik Sridharan (Cornell University)
- Optimal Scheduling of Dynamic Transport
Panagiotis Tsimpos (Massachusetts Institute of Technology); Zhi Ren (Massachusetts Institute of Technology); Jakob Zech (Heidelberg University); Youssef Marzouk (Massachusetts Institute of Technology)
- Towards Fundamental Limits for Active Multi-distribution Learning
Yihan Zhou (The University of Texas at Austin); Chicheng Zhang (University of Arizona)
- Exploring Facets of Language Generation in the Limit
Moses Charikar (Stanford University); Chirag Pabbaraju (Stanford University)
- A Theory of Self-Directed Online Learning Rates
Pramith Devulapalli (Purdue University); Steve Hanneke (Purdue University); Amirreza Shaeiri (Purdue University)
- Low-rank fine-tuning lies between lazy training and feature learning
Arif Kerem Dayi (Harvard University); Sitan Chen (Harvard University)
- Stochastic block models with many communities and the Kesten--Stigum bound
Byron Chin (MIT); Elchanan Mossel (MIT); Youngtak Sohn (Brown University); Alexander Wein (UC Davis)
- On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy
Zeyu Jia (MIT); Yury Polyanskiy (MIT); Alexander Rakhlin (MIT)
- Trade-offs in Data Memorization: Learn More to Remember Less
Vitaly Feldman (Apple); Guy Kornowski (Weizmann Institute of Science); Xin Lyu (UC Berkeley)
- Generalization error bound for denoising score matching under relaxed manifold assumption
Konstantin Yakovlev (HSE University); Nikita Puchkin (HSE University)
- Alternating Regret for Online Convex Optimization
Soumita Hait (USC); Ping Li (University of Science and Technology of China); Haipeng Luo (USC); Mengxiao Zhang (University of Southern California)
- Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
Guy Bresler (Massachusetts Institute of Technology); Chenghao Guo (Massachusetts Institute of Technology); Yury Polyanskiy (Massachusetts Institute of Technology); Andrew Yao (Massachusetts Institute of Technology)
- Mean-field neural network beyond finite time horizon
Margalit Glasgow (MIT); Joan Bruna (NYU); Denny Wu (NYU)