ML Anthology

COLT 2025

182 papers

“All-Something-Nothing” Phase Transitions in Planted $k$-Factor Recovery (Extended Abstract) Julia Gaudio, Colin Sandon, Jiaming Xu, Dana Yang
PDF
A Distributional-Lifting Theorem for PAC Learning Guy Blanc, Jane Lange, Carmen Strassle, Li-Yang Tan
PDF
A Fine-Grained Characterization of PAC Learnability Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen
PDF
A Gap Between the Gaussian RKHS and Neural Networks: An Infinite-Center Asymptotic Analysis Akash Kumar, Rahul Parhi, Mikhail Belkin
PDF
A Polynomial-Time Algorithm for Online Sparse Linear Regression with Improved Regret Bound Under Weaker Conditions Junfan Li, Shizhong Liao, Zenglin Xu, Liqiang Nie
PDF
A Proof of the Changepoint Detection Threshold Conjecture in Preferential Attachment Models Hang Du, Shuyang Gong, Jiaming Xu
PDF
A Theory of Learning with Autoregressive Chain of Thought Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, Nathan Srebro
PDF
Accelerating Proximal Gradient Descent via Silver Stepsizes Jinho Bok, Jason M. Altschuler
PDF
Agnostic Learning of Arbitrary ReLU Activation Under Gaussian Marginals Anxin Guo, Aravindan Vijayaraghavan
PDF
Algorithms for Sparse LPN and LSPN Against Low-Noise (extended Abstract) Xue Chen, Wenxuan Shu, Zhaienhe Zhou
PDF
Alternating Regret for Online Convex Optimization Soumita Hait, Ping Li, Haipeng Luo, Mengxiao Zhang
PDF
An Uncertainty Principle for Linear Recurrent Neural Networks Alexandre François, Antonio Orvieto, Francis Bach
PDF
Anytime Acceleration of Gradient Descent Zihan Zhang, Jason Lee, Simon Du, Yuxin Chen
PDF
Approximating the Total Variation Distance Between Spin Systems Weiming Feng, Hongyang Liu, Minji Yang
PDF
Are All Models Wrong? Fundamental Limits in Distribution-Free Empirical Model Falsification Manuel M. Müller, Yuetian Luo, Rina Foygel Barber
PDF
Bayes Correlated Equilibria, No-Regret Dynamics in Bayesian Games, and the Price of Anarchy Kaito Fujii
PDF
Better Private Distribution Testing by Leveraging Unverified Auxiliary Data Maryam Aliakbarpour, Arnav Burudgunte, Clément Canonne, Ronitt Rubinfeld
PDF
Beyond Propagation of Chaos: A Stochastic Algorithm for Mean Field Optimization Chandan Tankala, Dheeraj Nagaraj, Anant Raj
PDF
Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks Omar Montasser, Abhishek Shetty, Nikita Zhivotovskiy
PDF
Black-Box Reductions for Decentralized Online Convex Optimization in Changing Environments Yuanyu Wan
PDF
Blackwell’s Approachability with Approximation Algorithms Dan Garber, Massalha Mhna
PDF
Can a Calibration Metric Be Both Testable and Actionable? Raphael Rossellini, Jake A. Soloff, Rina Foygel Barber, Zhimei Ren, Rebecca Willett
PDF
Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-Offs Alexander Ryabchenko, Idan Attias, Daniel M. Roy
PDF
Characterizing Dependence of Samples Along the Langevin Dynamics and Algorithms via Contraction of $φ$-Mutual Information (Extended Abstract) Jiaming Liang, Siddharth Mitra, Andre Wibisono
PDF
Community Detection with the Bethe-Hessian Ludovic Stephan, Yizhe Zhu
PDF
Complexity of Injectivity and Verification of ReLU Neural Networks (Extended Abstract) Vincent Froese, Moritz Grillo, Martin Skutella
PDF
Compression Barriers in Autoregressive Transformers Themistoklis Haris, Krzysztof Onak
PDF
Computable Learning of Natural Hypothesis Classes Syed Akbari, Matthew Harrison-Trainor
PDF
Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation Guy Bresler, Alina Harbuzova
PDF
Computational Intractability of Strategizing Against Online Learners Angelos Assos, Yuval Dagan, Nived Rajaraman
PDF
Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning Under Misspecification (extended Abstract) Dhruv Rohatgi, Adam Block, Audrey Huang, Akshay Krishnamurthy, Dylan J. Foster
PDF
Computing High-Dimensional Confidence Sets for Arbitrary Distributions Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan
PDF
Computing Optimal Regularizers for Online Linear Optimization Khashayar Gatmiry, Jon Schneider, Stefanie Jegelka
PDF
Conference on Learning Theory 2025: Preface Nika Haghtalab, Ankur Moitra
PDF
Corrupted Learning Dynamics in Games Taira Tsuchiya, Shinji Ito, Haipeng Luo
PDF
Data Selection for ERMs Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff
PDF
Data-Dependent Bounds with $t$-Optimal Best-of-Both-Worlds Guarantees in Multi-Armed Bandits Using Stability-Penalty Matching Quan Nguyen, Shinji Ito, Junpei Komiyama, Mehta Nishant
PDF
Decision Making in Changing Environments: Robustness, Query-Based Learning, and Differential Privacy Fan Chen, Alexander Rakhlin
PDF
Decision Making in Hybrid Environments: A Model Aggregation Approach Haolin Liu, Chen-Yu Wei, Zimmert Julian
PDF
Depth Separations in Neural Networks: Separating the Dimension from the Accuracy Itay Safran, Daniel Reichman, Paul Valiant
PDF
Detecting Arbitrary Planted Subgraphs in Random Graphs Dor Elimelech, Wasim Huleihel
PDF
Deterministic Apple Tasting Zachary Chase, Idan Mehalel
PDF
Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts Pan Peng, Hangyu Xu
PDF
DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory Jerry Chee, Arturs Backurs, Rainie Heck, Li Zhang, Janardhan Kulkarni, Thomas Rothvoss, Sivakanth Gopi
PDF
Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversaries Arnab Maiti, Zhiyuan Fan, Kevin Jamieson, Lillian J. Ratliff, Gabriele Farina
PDF
Efficiently Learning and Sampling Multimodal Distributions with Data-Based Initialization Frederic Koehler, Holden Lee, Thuy-Duong Vuong
PDF
Estimating Stationary Mass, Frequency by Frequency Milind Nakul, Vidya Muthukumar, Ashwin Pananjady
PDF
Existence of Adversarial Examples for Random Convolutional Networks via Isoperimetric Inequalities on $\mathbb{SO}(d)$ Amit Daniely
PDF
Experimental Design for Semiparametric Bandits Seok-Jin Kim, Gi-Soo Kim, Min-hwan Oh
PDF
Exploring Facets of Language Generation in the Limit Moses Charikar, Chirag Pabbaraju
PDF
Fast and Furious Symmetric Learning in Zero-Sum Games: Gradient Descent as Fictitious Play John Lazarsfeld, Georgios Piliouras, Ryann Sim, Andre Wibisono
PDF
Fast and Multiphase Rates for Nearest Neighbor Classifiers Pengkun Yang, Jingzhao Zhang
PDF
Faster Acceleration for Steepest Descent Cedar Site Bai, Brian Bullins
PDF
Faster Algorithms for Agnostically Learning Disjunctions and Their Implications Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
PDF
Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method Sachin Garg, Michał Dereziński
PDF
From Fairness to Infinity: Outcome-Indistinguishable (Omni)Prediction in Evolving Graphs Cynthia Dwork, Chris Hays, Nicole Immorlica, Juan C. Perdomo, Pranay Tankala
PDF
Fundamental Limits of Matrix Sensing: Exact Asymptotics, Universality, and Applications Yizhou Xu, Antoine Maillard, Lenka Zdeborová, Florent Krzakala
PDF
Generalization Error Bound for Denoising Score Matching Under Relaxed Manifold Assumption Konstantin Yakovlev, Nikita Puchkin
PDF
Generation Through the Lens of Learning Theory Vinod Raman, Jiaxun Li, Ambuj Tewari
PDF
Gradient Methods with Online Scaling Wenzhi Gao, Ya-Chi Chu, Yinyu Ye, Madeleine Udell
PDF
Heavy-Tailed Estimation Is Easier than Adversarial Contamination Yeshwanth Cherapanamjeri, Daniel Lee
PDF
How to Safely Discard Features Based on Aggregate SHAP Values Robi Bhattacharjee, Karolin Frohnapfel, Ulrike Luxburg
PDF
Identifiability and Estimation in High-Dimensional Nonparametric Latent Structure Models Yichen Lyu, Pengkun Yang
PDF
Improved Algorithms for Effective Resistance Computation on Graphs Yang Yichun, Li Rong-Hua, Liao Meihao, Wang Guoren
PDF
Improved Algorithms for Learning Quantum Hamiltonians, via Flat Polynomials Shyam Narayanan
PDF
Improved Margin Generalization Bounds for Voting Classifiers Mikael Høgsgaard Møller, Kasper Green Larsen
PDF
Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing J. Jon Ryu, Jeongyeol Kwon, Benjamin Koppe, Kwang-Sung Jun
PDF
Improved Sample Upper and Lower Bounds for Trace Estimation of Quantum State Powers Kean Chen, Qisheng Wang
PDF
Information-Theoretic Reduction of Deep Neural Networks to Linear Models in the Overparametrized Proportional Regime Francesco Camilli, Daria Tieplova, Eleonora Bergamin, Jean Barbier
PDF
Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback Shinji Ito, Haipeng Luo, Taira Tsuchiya, Yue Wu
PDF
Is a Good Foundation Necessary for Efficient Reinforcement Learning? the Computational Role of the Base Model in Exploration Dylan J Foster, Zakaria Mhammedi, Dhruv Rohatgi
PDF
Learning Algorithms in the Limit Hristo Papazov, Nicolas Flammarion
PDF
Learning Augmented Graph $k$-Clustering Chenglin Fan, Kijun Shin
PDF
Learning Compositional Functions with Transformers from Easy-to-Hard Data Zixuan Wang, Eshaan Nichani, Alberto Bietti, Alex Damian, Daniel Hsu, Jason D Lee, Denny Wu
PDF
Learning Constant-Depth Circuits in Malicious Noise Models Adam Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
PDF
Learning DNF Through Generalized Fourier Representations Mohsen Heidari, Roni Khardon
PDF
Learning General Gaussian Mixtures with Efficient Score Matching Sitan Chen, Vasilis Kontonis, Kulin Shah
PDF
Learning Intersections of Two Margin Halfspaces Under Factorizable Distributions Ilias Diakonikolas, Ma Mingchen, Ren Lisheng, Tzamos Christos
PDF
Learning Mixtures of Gaussians Using Diffusion Models Khashayar Gatmiry, Jonathan Kelner, Holden Lee
PDF
Learning Partitions with Optimal Query and Round Complexities Hadley Black, Arya Mazumdar, Barna Saha
PDF
Learning Shallow Quantum Circuits with Many-Qubit Gates Francisca Vasconcelos, Hsin-Yuan Huang
PDF
Learning Sparse Generalized Linear Models with Binary Outcomes via Iterative Hard Thresholding Namiko Matsumoto, Arya Mazumdar
PDF
Linear Bandits on Ellipsoids: Minimax Optimal Algorithms Raymond Zhang, Hadiji Hédi, Combes Richard
PDF
Linear Convergence of Diffusion Models Under the Manifold Hypothesis Peter Potaptchik, Iskander Azangulov, George Deligiannidis
PDF
Local Regularizers Are Not Transductive Learners Sky Jafar, Julian Asilis, Shaddin Dughmi
PDF
Logarithmic Regret of Exploration in Average Reward Markov Decision Processes Victor Boone, Bruno Gaujal
PDF
Logarithmic Width Suffices for Robust Memorization Amitsour Egosi, Gilad Yehudai, Ohad Shamir
PDF
Low Coordinate Degree Algorithms II: Categorical Signals and Generalized Stochastic Block Models Dmitriy Kunisky
PDF
Low-Dimensional Adaptation of Diffusion Models: Convergence in Total Variation (extended Abstract) Jiadong Liang, Zhihan Huang, Yuxin Chen
PDF
Low-Dimensional Functions Are Efficiently Learnable Under Randomly Biased Distributions Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel
PDF
Low-Rank Fine-Tuning Lies Between Lazy Training and Feature Learning Arif Kerem Dayi, Sitan Chen
PDF
Lower Bounds for Greedy Teaching Set Constructions Spencer Compton, Chirag Pabbaraju, Nikita Zhivotovskiy
PDF
Lower Bounds for Private Estimation of Gaussian Covariance Matrices Under All Reasonable Parameter Regimes Victor S. Portella, Nicholas J. A. Harvey
PDF
Market Making Without Regret Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Luigi Foscari, Vinayak Pathak
PDF
Mean-Field Analysis of Polynomial-Width Two-Layer Neural Network Beyond Finite Time Horizon Margalit Glasgow, Denny Wu, Joan Bruna
PDF
Metric Clustering and Graph Optimization Problems Using Weak Comparison Oracles Rahul Raychaudhury, Wen-Zhi Li, Syamantak Das, Sainyam Galhotra, Stavros Sintos
PDF
Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams Ainesh Bakshi, Vincent Cohen-Addad, Rajesh Jayaram, Samuel B. Hopkins, Silvio Lattanzi
PDF
Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality (Extended Abstract) Andre Wibisono
PDF
Model Predictive Control Is Almost Optimal for Restless Bandits Nicolas "Gast, Dheeraj" Narasimha
PDF
Multi-Pass Memory Lower Bounds for Learning Problems Qian Li, Shuo Wang, Jiapeng Zhang
PDF
Necessary and Sufficient Oracles: Toward a Computational Taxonomy for Reinforcement Learning Dhruv Rohatgi, Dylan J. Foster
PDF
New Lower Bounds for Non-Convex Stochastic Optimization Through Divergence Decomposition El Mehdi Saad, Wei-Cheng Lee, Francesco Orabona
PDF
Noisy Group Testing in the Linear Regime: Exact Thresholds and Efficient Lukas Hintze, Lena Krieg, Olga Scheftelowitsch, Haodong Zhu
PDF
Non-Convex Matrix Sensing: Breaking the Quadratic Rank Barrier in the Sample Complexity Extended Abstract Dominik Stöger, Yizhe Zhu
PDF
Non-Euclidean High-Order Smooth Convex Optimization Extended Abstract Juan Pablo Contreras, Cristóbal Guzmán, David Martı́nez-Rubio
PDF
Non-Monetary Mechanism Design Without Distributional Information: Using Scarce Audits Wisely (Extended Abstract) Yan Dai, Moïse Blanchard, Patrick Jaillet
PDF
Of Dice and Games: A Theory of Generalized Boosting Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen
PDF
On the Convergence of Min-Max Langevin Dynamics and Algorithm Yang Cai, Siddharth Mitra, Xiuyuan Wang, Andre Wibisono
PDF
On the Hardness of Bandit Learning Nataly Brukhim, Aldo Pacchiano, Miroslav Dudik, Robert Schapire
PDF
On the Minimax Regret of Sequential Probability Assignment via Square-Root Entropy Zeyu Jia, Alexander Rakhlin, Yury Polyanskiy
PDF
On the Query Complexity of Sampling from Non-Log-Concave Distributions (extended Abstract) Yuchen He, Chihao Zhang
PDF
Online Convex Optimization with a Separation Oracle Zakaria Mhammedi
PDF
Online Covariance Estimation in Nonsmooth Stochastic Approximation Liwei Jiang, Abhishek Roy, Krishnakumar Balasubramanian, Damek Davis, Dmitriy Drusvyatskiy, Sen Na
PDF
Open Problem: Data Selection for Regression Tasks Steve Hanneke, Shay Moran, Alexander Shlimovich, Amir Yehudayoff
PDF
Open Problem: Fixed-Parameter Tractability of Zonotope Problems Vincent Froese, Moritz Grillo, Christoph Hertrich, Martin Skutella
PDF
Open Problem: Optimal Instance-Dependent Sample Complexity for Finding Nash Equilibrium in Two Player Zero-Sum Matrix Games Arnab Maiti
PDF
Open Problem: Regret Minimization in Heavy-Tailed Bandits with Unknown Distributional Parameters Gianmarco Genalti, Alberto Maria Metelli
PDF
Open Problem: Structure-Agnostic Minimax Risk for Partial Linear Model Yihong Gu
PDF
Optimal Differentially Private Sampling of Unbounded Gaussians Valentio Iverson, Gautam Kamath, Argyris Mouzakis
PDF
Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu
PDF
Optimal Online Bookmaking for Any Number of Outcomes Hadar Tal, Oron Sabag
PDF
Optimal Robust Estimation Under Local and Global Corruptions: Stronger Adversary and Smaller Error Thanasis Pittas, Ankit Pensia
PDF
Optimal Scheduling of Dynamic Transport Panos Tsimpos, Ren Zhi, Jakob Zech, Youssef Marzouk
PDF
Optimistic Q-Learning for Average Reward and Episodic Reinforcement Learning Extended Abstract Priyank Agrawal, Shipra Agrawal
PDF
Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning Antoine Moulin, Gergely Neu, Luca Viano
PDF
Optimization, Isoperimetric Inequalities, and Sampling via Lyapunov Potentials August Y Chen, Karthik Sridharan
PDF
Orthogonal Causal Calibration (Extended Abstract) Justin Whitehouse, Christopher Jung, Vasilis Syrgkanis, Bryan Wilder, Zhiwei Steven Wu
PDF
Partial and Exact Recovery of a Random Hypergraph from Its Graph Projection Guy Bresler, Chenghao Guo, Yury Polyanskiy, Andrew Yao
PDF
Polynomial Low Degree Hardness for Broadcasting on Trees (Extended Abstract) Han Huang, Elchanan Mossel
PDF
Predicting Quantum Channels over General Product Distributions Sitan Chen, Jaume de Dios Pont, Jun-Ting Hsieh, Hsin-Yuan Huang, Jane Lange, Jerry Li
PDF
PREM: Privately Answering Statistical Queries with Relative Error Badih Ghazi, Cristóbal Guzmán, Pritish Kamath, Alexander Knop, Ravi Kumar, Pasin Manurangsi, Sushant Sachdeva
PDF
Private List Learnability vs. Online List Learnability Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari
PDF
Private Realizable-to-Agnostic Transformation with Near-Optimal Sample Complexity Bo Li, Wei Wang, Peng Ye
PDF
Proofs as Explanations: Short Certificates for Reliable Predictions Avrim Blum, Steve Hanneke, Chirag Pabbaraju, Donya Saless
PDF
Provable Complexity Improvement of AdaGrad over SGD: Upper and Lower Bounds in Stochastic Non-Convex Optimization Ruichen Jiang, Devyani Maladkar, Aryan Mokhtari
PDF
Quantifying Overfitting Along the Regularization Path for Two-Part-Code MDL in Supervised Classification Xiaohan Zhu, Nathan Srebro
PDF
Quantum State and Unitary Learning Implies Circuit Lower Bounds Nai-Hui Chia, Daniel Liang, Fang Song
PDF
Rate-Preserving Reductions for Blackwell Approachability Christoph Dann, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan
PDF
Recovering Labels from Crowdsourced Data: An Optimal and Polynomial-Time Method Emmanuel Pilliat
PDF
Regret Bounds for Robust Online Decision Making Alexander Appel, Vanessa Kosoy
PDF
Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis Minhui Jiang, Yuansi Chen
PDF
Robust Algorithms for Recovering Planted $r$-Colorable Graphs Anand Louis, Rameesh Paul, Prasad Raghavendra
PDF
Robust Random Graph Matching in Gaussian Models via Vector Approximate Message Passing Zhangsong Li
PDF
Robustly Learning Monotone Generalized Linear Models via Data Augmentation Nikos Zarifis, Puqian Wang, Ilias Diakonikolas, Jelena Diakonikolas
PDF
Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions Zakaria Mhammedi
PDF
Sample Efficient Omniprediction and Downstream Swap Regret for Non-Linear Losses Jiuyao Lu, Aaron Roth, Mirah Shi
PDF
Sharper Bounds for Chebyshev Moment Matching, with Applications Cameron Musco, Christopher Musco, Lucas Rosenblatt, Apoorv Vikram Singh
PDF
Simplifying Adversarially Robust PAC Learning with Tolerance Hassan Ashtiani, Vinayak Pathak, Ruth Urner
PDF
Solving Convex-Concave Problems with $\mathcal{O}(\epsilon^{-4/7})$ Second-Order Oracle Complexity Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang
PDF
Some Easy Optimization Problems Have the Overlap-Gap Property Shuangping Li, Tselil Schramm
PDF
Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL Matthew Zurek, Yudong Chen
PDF
Sparsity-Based Interpolation of External, Internal and Swap Regret Zhou Lu, Y Jennifer Sun, Zhiyu Zhang
PDF
Spectral Estimators for Multi-Index Models: Precise Asymptotics and Optimal Weak Recovery Filip Kovačević, Zhang Yihan, Marco Mondelli
PDF
Spherical Dimension Bogdan Chornomaz, Shay Moran, Tom Waknine
PDF
Spike-and-Slab Posterior Sampling in High Dimensions Symantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu
PDF
Stability and List-Replicability for Agnostic Learners Ari Blondal, Gao Shan, Hamed Hatami, Pooya Hatami
PDF
Stochastic Block Models with Many Communities and the Kesten–Stigum Bound - Extended Abstract Byron Chin, Elchanan Mossel, Youngtak Sohn, Alexander S. Wein
PDF
Structure-Agnostic Optimality of Doubly Robust Learning for Treatment Effect Estimation (Extended Abstract) Jikai Jin, Vasilis Syrgkanis
PDF
Taking a Big Step: Large Learning Rates in Denoising Score Matching Prevent Memorization Yu-Han Wu, Pierre Marion, Gérard Biau, Claire Boyer
PDF
Testing (Conditional) Mutual Information - Extended Abstract Jan Seyfried, Sayantan Sen, Marco Tomamichel
PDF
Testing Juntas and Junta Subclasses with Relative Error Xi Chen, William Pires, Toniann Pitassi, R. A. Servedio
PDF
Testing Thresholds and Spectral Properties of High-Dimensional Random Toroidal Graphs via Edgeworth-Style Expansions Samuel Baguley, Andreas Göbel, Marcus Pappik, Leon Schiller
PDF
The Adaptive Complexity of Finding a Stationary Point Zhou Huanjian, Han Andi, Takeda Akiko, Sugiyama Masashi
PDF
The Fundamental Limits of Recovering Planted Subgraphs (extended Abstract) Daniel Z. Lee, Francisco Pernice, Amit Rajaraman, Ilias Zadik
PDF
The Late-Stage Training Dynamics of (stochastic) Subgradient Descent on Homogeneous Neural Networks Sholom Schechtman, Nicolas Schreuder
PDF
The Oracle Complexity of Simplex-Based Matrix Games: Linear Separability and Nash Equilibria Guy Kornowski, Ohad Shamir
PDF
The Pitfalls of Imitation Learning When Actions Are Continuous Max Simchowitz, Daniel Pfrommer, Ali Jadbabaie
PDF
The Planted Spanning Tree Problems: Exact Overlap Characterization via Local Weak Convergence Extended Abstract Mehrdad Moharrami, Cristopher Moore, Jiaming Xu
PDF
The Role of Environment Access in Agnostic Reinforcement Learning (Extended Abstract) Akshay Krishnamurthy, Gene Li, Ayush Sekhari
PDF
The Sample Complexity of Distributed Simple Binary Hypothesis Testing Under Information Constraints Hadi Kazemi, Ankit Pensia, Jog Varun
PDF
The Space Complexity of Learning-Unlearning Algorithms (extended Abstract) Yeshwanth Cherapanamjeri, Sumegba Garg, Nived Rajaraman, Ayush Sekhari, Abhishek Shetty
PDF
Thompson Sampling for Bandit Convex Optimisation Alireza Bakhtiari, Tor Lattimore, Csaba Szepesvári
PDF
Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold Yuzhou Gu, Xin Li, Yinzhan Xu
PDF
Time-Uniform Self-Normalized Concentration for Vector-Valued Processes (Extended Abstract) Justin Whitehouse, Zhiwei Steven Wu, Aaditya Ramdas
PDF
Towards Fair Representation: Clustering and Consensus Diptarka Chakraborty, Kushagra Chatterjee, Debarati Das, Tien Long Nguyen, Romina Nobahari
PDF
Towards Fundamental Limits for Active Multi-Distribution Learning Chicheng Zhang, Yihan Zhou
PDF
Trade-Offs in Data Memorization via Strong Data Processing Inequalities Vitaly Feldman, Guy Kornowski, Xin Lyu
PDF
Truthfulness of Decision-Theoretic Calibration Measures Mingda Qiao, Eric Zhao
PDF
Universal Rates for Multiclass Learning with Bandit Feedback Steve Hanneke, Amirreza Shaeiri, Qian Zhang
PDF
Universal Rates of ERM for Agnostic Learning Steve Hanneke, Mingyue Xu
PDF
Universality of High-Dimensional Logistic Regression and a Novel CGMT Under Dependence with Applications to Data Augmentation Matthew Esmaili Mallory, Kevin Han Huang, Morgane Austern
PDF
What Makes Treatment Effects Identifiable? Characterizations and Estimators Beyond Unconfoundedness (Extended Abstract) Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, Manolis Zampetakis
PDF