Accepted Papers

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-Dimensional 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 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 (Google Research)
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 (Google Research)
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)
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)