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 (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)
    • 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)