Conference on Learning Theory 2023: Preface

Gergely Neu, Lorenzo Rosasco; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:i-i

[abs][Download PDF]

Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality

Alireza Mousavi-Hosseini, Tyler K. Farghly, Ye He, Krishna Balasubramanian, Murat A. Erdogdu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1-35

[abs][Download PDF]

Improved Discretization Analysis for Underdamped Langevin Monte Carlo

Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, Murat A. Erdogdu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:36-71

[abs][Download PDF]

The One-Inclusion Graph Algorithm is not Always Optimal

Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:72-88

[abs][Download PDF]

Beyond Uniform Smoothness: A Stopped Analysis of Adaptive SGD

Matthew Faw, Litu Rout, Constantine Caramanis, Sanjay Shakkottai; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:89-160

[abs][Download PDF]

Convergence of AdaGrad for Non-convex Objectives: Simple Proofs and Relaxed Assumptions

Bohan Wang, Huishuai Zhang, Zhiming Ma, Wei Chen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:161-190

[abs][Download PDF]

Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problems

Yunwen Lei; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:191-227

[abs][Download PDF]

The Sample Complexity of Approximate Rejection Sampling With Applications to Smoothed Online Learning

Adam Block, Yury Polyanskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:228-273

[abs][Download PDF]

Online Learning and Solving Infinite Games with an ERM Oracle

Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, Maxwell K. Fishelson; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:274-324

[abs][Download PDF]

Online Learning in Dynamically Changing Environments

Changlong Wu, Ananth Grama, Wojciech Szpankowski; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:325-358

[abs][Download PDF]

Accelerated Riemannian Optimization: Handling Constraints with a Prox to Bound Geometric Penalties

David Martínez-Rubio, Sebastian Pokutta; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:359-393

[abs][Download PDF]

Bregman Deviations of Generic Exponential Families

Sayak Ray Chowdhury, Patrick Saux, Odalric Maillard, Aditya Gopalan; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:394-449

[abs][Download PDF]

Bagging is an Optimal PAC Learner

Kasper Green Larsen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:450-468

[abs][Download PDF]

Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix

Julia Gaudio, Nirmit Joshi; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:469-510

[abs][Download PDF]

Find a witness or shatter: the landscape of computable PAC learning.

Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas, Tomasz Steifer; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:511-524

[abs][Download PDF]

Proper Losses, Moduli of Convexity, and Surrogate Regret Bounds

Han Bao; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:525-547

[abs][Download PDF]

Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for Non-Spherical Gaussian Mixtures

Rares-Darius Buhai, David Steurer; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:548-611

[abs][Download PDF]

Online Reinforcement Learning in Stochastic Continuous-Time Systems

Mohamad Kazem Shirani Faradonbeh, Mohamad Sadegh Shirani Faradonbeh; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:612-656

[abs][Download PDF]

Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm

Fang Kong, Canzhe Zhao, Shuai Li; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:657-673

[abs][Download PDF]

Private Online Prediction from Experts: Separations and Faster Rates

Hilal Asi, Vitaly Feldman, Tomer Koren, Kunal Talwar; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:674-699

[abs][Download PDF]

Improved Bounds for Multi-task Learning with Trace Norm Regularization

Weiwei Liu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:700-714

[abs][Download PDF]

Local Glivenko-Cantelli

Doron Cohen, Aryeh Kontorovich; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:715-715

[abs][Download PDF]

Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach.

Giacomo Greco, Maxence Noble, Giovanni Conforti, Alain Durmus; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:716-746

[abs][Download PDF]

Multitask Learning via Shared Features: Algorithms and Hardness

Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, Lydia Zakynthinou; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:747-772

[abs][Download PDF]

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension

Yuval Filmus, Steve Hanneke, Idan Mehalel, Shay Moran; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:773-836

[abs][Download PDF]

Uniqueness of BP fixed point for the Potts model and applications to community detection

Yuzhou Gu, Yury Polyanskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:837-884

[abs][Download PDF]

Weak Recovery Threshold for the Hypergraph Stochastic Block Model

Yuzhou Gu, Yury Polyanskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:885-920

[abs][Download PDF]

Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression

Gabriel Arpino, Ramji Venkataramanan; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:921-986

[abs][Download PDF]

VO$Q$L: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

Alekh Agarwal, Yujia Jin, Tong Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:987-1063

[abs][Download PDF]

On Testing and Learning Quantum Junta Channels

Zongbo Bao, Penghui Yao; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1064-1094

[abs][Download PDF]

Repeated Bilateral Trade Against a Smoothed Adversary

Nicolò Cesa-Bianchi, Tommaso R. Cesari, Roberto Colomboni, Federico Fusco, Stefano Leonardi; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1095-1130

[abs][Download PDF]

On the Existence of a Complexity in Fixed Budget Bandit Identification

Rémy Degenne; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1131-1154

[abs][Download PDF]

Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron

Weihang Xu, Simon Du; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1155-1198

[abs][Download PDF]

From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networks

Luca Arnaboldi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1199-1227

[abs][Download PDF]

Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold

Sholom Schechtman, Daniil Tiapkin, Michael Muehlebach, Éric Moulines; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1228-1258

[abs][Download PDF]

Projection-free Online Exp-concave Optimization

Dan Garber, Ben Kretzu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1259-1284

[abs][Download PDF]

A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs

Dirk van der Hoeven, Lukas Zierahn, Tal Lancewicki, Aviv Rosenberg, Nicolò Cesa-Bianchi; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1285-1321

[abs][Download PDF]

Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory

Andrew J. Wagenmaker, Dylan J. Foster; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1322-1472

[abs][Download PDF]

Improved dimension dependence of a proximal algorithm for sampling

Jiaojiao Fan, Bo Yuan, Yongxin Chen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1473-1521

[abs][Download PDF]

Private Covariance Approximation and Eigenvalue-Gap Bounds for Complex Gaussian Perturbations

Oren Mangoubi, Nisheeth K. Vishnoi; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1522-1587

[abs][Download PDF]

Exponential Hardness of Reinforcement Learning with Linear Function Approximation

Sihan Liu, Gaurav Mahajan, Daniel Kane, Shachar Lovett, Gellért Weisz, Csaba Szepesvári; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1588-1617

[abs][Download PDF]

Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Making

Adam Block, Max Simchowitz, Alexander Rakhlin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1618-1665

[abs][Download PDF]

Learning and Testing Latent-Tree Ising Models Efficiently

Vardis Kandiros, Constantinos Daskalakis, Yuval Dagan, Davin Choo; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1666-1729

[abs][Download PDF]

Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets

Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1730-1773

[abs][Download PDF]

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling

Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1774-1790

[abs][Download PDF]

Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms

Osama A Hanna, Lin Yang, Christina Fragouli; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1791-1821

[abs][Download PDF]

Quantum Channel Certification with Incoherent Measurements

Omar Fawzi, Nicolas Flammarion, Aurélien Garivier, Aadil Oufkir; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1822-1884

[abs][Download PDF]

List Online Classification

Shay Moran, Ohad Sharon, Iska Tsubari, Sivan Yosebashvili; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1885-1913

[abs][Download PDF]

InfoNCE Loss Provably Learns Cluster-Preserving Representations

Advait Parulekar, Liam Collins, Karthikeyan Shanmugam, Aryan Mokhtari, Sanjay Shakkottai; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1914-1961

[abs][Download PDF]

Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergence

Ruichen Jiang, Qiujiang Jin, Aryan Mokhtari; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1962-1992

[abs][Download PDF]

Exploring Local Norms in Exp-concave Statistical Learning

Nikita Puchkin, Nikita Zhivotovskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1993-2013

[abs][Download PDF]

Learning Hidden Markov Models Using Conditional Samples

Gaurav Mahajan, Sham Kakade, Akshay Krishnamurthy, Cyril Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2014-2066

[abs][Download PDF]

A Second-Order Method for Stochastic Bandit Convex Optimisation

Tor Lattimore, András György; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2067-2094

[abs][Download PDF]

A Lower Bound for Linear and Kernel Regression with Adaptive Covariates

Tor Lattimore; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2095-2113

[abs][Download PDF]

Provable Benefits of Representational Transfer in Reinforcement Learning

Alekh Agarwal, Yuda Song, Wen Sun, Kaiwen Wang, Mengdi Wang, Xuezhou Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2114-2187

[abs][Download PDF]

Geodesically convex $M$-estimation in metric spaces

Victor-Emmanuel Brunel; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2188-2210

[abs][Download PDF]

Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise

Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2211-2239

[abs][Download PDF]

Tighter PAC-Bayes Bounds Through Coin-Betting

Kyoungseok Jang, Kwang-Sung Jun, Ilja Kuzborskij, Francesco Orabona; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2240-2264

[abs][Download PDF]

Inference on Strongly Identified Functionals of Weakly Identified Functions

Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, Masatoshi Uehara; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2265-2265

[abs][Download PDF]

Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise

Zijian Liu, Jiawei Zhang, Zhengyuan Zhou; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2266-2290

[abs][Download PDF]

Minimax Instrumental Variable Regression and $L_2$ Convergence Guarantees without Identification or Closedness

Andrew Bennett, Nathan Kallus, Xiaojie Mao, Whitney Newey, Vasilis Syrgkanis, Masatoshi Uehara; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2291-2318

[abs][Download PDF]

SQ Lower Bounds for Learning Mixtures of Separated and Bounded Covariance Gaussians

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2319-2349

[abs][Download PDF]

Allocating Divisible Resources on Arms with Unknown and Random Rewards

Wenhao Li, Ningyuan Chen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2350-2351

[abs][Download PDF]

Semi-Random Sparse Recovery in Nearly-Linear Time

Jonathan Kelner, Jerry Li, Allen X. Liu, Aaron Sidford, Kevin Tian; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2352-2398

[abs][Download PDF]

Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler

Sivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen, Kevin Tian; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2399-2439

[abs][Download PDF]

Detection-Recovery Gap for Planted Dense Cycles

Cheng Mao, Alexander S. Wein, Shenduo Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2440-2481

[abs][Download PDF]

Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap

Raef Bassily, Cristóbal Guzmán, Michael Menart; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2482-2508

[abs][Download PDF]

Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling

Jason Altschuler, Kunal Talwar; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2509-2510

[abs][Download PDF]

A Pretty Fast Algorithm for Adaptive Private Mean Estimation

Rohith Kuditipudi, John Duchi, Saminul Haque; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2511-2551

[abs][Download PDF]

SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics

Emmanuel Abbe, Enric Boix Adserà, Theodor Misiakiewicz; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2552-2623

[abs][Download PDF]

Optimal Scoring Rules for Multi-dimensional Effort

Jason D. Hartline, Liren Shan, Yingkai Li, Yifan Wu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2624-2650

[abs][Download PDF]

Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation

Qiwen Cui, Kaiqing Zhang, Simon Du; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2651-2652

[abs][Download PDF]

Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds

Shinji Ito, Kei Takemura; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2653-2677

[abs][Download PDF]

On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring

Dean Foster, Dylan J. Foster, Noah Golowich, Alexander Rakhlin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2678-2792

[abs][Download PDF]

Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation

Yuanhao Wang, Qinghua Liu, Yu Bai, Chi Jin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2793-2848

[abs][Download PDF]

Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures

Wai Ming Tai, Bryon Aragam; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2849-2849

[abs][Download PDF]

Information-Directed Selection for Top-Two Algorithms

Wei You, Chao Qin, Zihao Wang, Shuoguang Yang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2850-2851

[abs][Download PDF]

Accelerated and Sparse Algorithms for Approximate Personalized PageRank and Beyond

David Martínez-Rubio, Elias Wirth, Sebastian Pokutta; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2852-2876

[abs][Download PDF]

Toward L_∞Recovery of Nonlinear Functions: A Polynomial Sample Complexity Bound for Gaussian Random Fields

Kefan Dong, Tengyu Ma; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2877-2918

[abs][Download PDF]

Self-Directed Linear Classification

Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2919-2947

[abs][Download PDF]

On the Lower Bound of Minimizing Polyak-Łojasiewicz functions

Pengyun Yue, Cong Fang, Zhouchen Lin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2948-2968

[abs][Download PDF]

Curvature and complexity: Better lower bounds for geodesically convex optimization

Christopher Criscitiello, Nicolas Boumal; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:2969-3013

[abs][Download PDF]

A Nearly Tight Bound for Fitting an Ellipsoid to Gaussian Random Points

Daniel Kane, Ilias Diakonikolas; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3014-3028

[abs][Download PDF]

Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems

Stefan Tiegel; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3029-3064

[abs][Download PDF]

Testing of Index-Invariant Properties in the Huge Object Model

Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, Sayantan Sen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3065-3136

[abs][Download PDF]

Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs

Michał Dereziński; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3137-3172

[abs][Download PDF]

Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization

Spencer Frei, Gal Vardi, Peter Bartlett, Nathan Srebro; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3173-3228

[abs][Download PDF]

Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints

Ankit Pensia, Amir Reza Asadi, Varun Jog, Po-Ling Loh; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3229-3230

[abs][Download PDF]

Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization

David Gamarnik, Eren C. Kizildağ, Will Perkins, Changji Xu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3231-3263

[abs][Download PDF]

Intrinsic dimensionality and generalization properties of the R-norm inductive bias

Navid Ardeshir, Daniel J. Hsu, Clayton H. Sanford; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3264-3303

[abs][Download PDF]

Improved Dynamic Regret for Online Frank-Wolfe

Yuanyu Wan, Lijun Zhang, Mingli Song; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3304-3327

[abs][Download PDF]

Online Nonconvex Optimization with Limited Instantaneous Oracle Feedback

Ziwei Guan, Yi Zhou, Yingbin Liang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3328-3355

[abs][Download PDF]

Tackling Combinatorial Distribution Shift: A Matrix Completion Perspective

Max Simchowitz, Abhishek Gupta, Kaiqing Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3356-3468

[abs][Download PDF]

The $k$-Cap Process on Geometric Random Graphs

Mirabel E. Reid, Santosh S. Vempala; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3469-3509

[abs][Download PDF]

Efficient Algorithms for Sparse Moment Problems without Separation

Zhiyuan Fan, Jian Li; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3510-3565

[abs][Download PDF]

From Pseudorandomness to Multi-Group Fairness and Back

Cynthia Dwork, Daniel Lee, Huijia Lin, Pranay Tankala; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3566-3614

[abs][Download PDF]

A new ranking scheme for modern data and its application to two-sample hypothesis testing

Doudou Zhou, Hao Chen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3615-3668

[abs][Download PDF]

Linearization Algorithms for Fully Composite Optimization

Maria-Luiza Vladarean, Nikita Doikov, Martin Jaggi, Nicolas Flammarion; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3669-3695

[abs][Download PDF]

Near Optimal Heteroscedastic Regression with Symbiotic Learning

Aniket Das, Dheeraj M. Nagaraj, Praneeth Netrapalli, Dheeraj Baby; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3696-3757

[abs][Download PDF]

Approximately Stationary Bandits with Knapsacks

Giannis Fikioris, Éva Tardos; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3758-3782

[abs][Download PDF]

Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models

Yuchen Wu, Kangjie Zhou; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3783-3820

[abs][Download PDF]

Causal Matrix Completion

Anish Agarwal, Munther Dahleh, Devavrat Shah, Dennis Shen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3821-3826

[abs][Download PDF]

A High-dimensional Convergence Theorem for U-statistics with Applications to Kernel-based Testing

Kevin H. Huang, Xing Liu, Andrew Duncan, Axel Gandy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3827-3918

[abs][Download PDF]

Asymptotic confidence sets for random linear programs

Shuyu Liu, Florentina Bunea, Jonathan Niles-Weed; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3919-3940

[abs][Download PDF]

Algorithmically Effective Differentially Private Synthetic Data

Yiyun He, Roman Vershynin, Yizhe Zhu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3941-3968

[abs][Download PDF]

Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient

Dylan J. Foster, Noah Golowich, Yanjun Han; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:3969-4043

[abs][Download PDF]

Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions

Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, David Steurer; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4044-4071

[abs][Download PDF]

Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms

Aniket Das, Dheeraj M. Nagaraj, Anant Raj; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4072-4129

[abs][Download PDF]

The Expressive Power of Tuning Only the Normalization Layers

Angeliki Giannou, Shashank Rajput, Dimitris Papailiopoulos; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4130-4131

[abs][Download PDF]

Precise Asymptotic Analysis of Deep Random Feature Models

David Bosch, Ashkan Panahi, Babak Hassibi; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4132-4179

[abs][Download PDF]

The Complexity of Markov Equilibrium in Stochastic Games

Constantinos Daskalakis, Noah Golowich, Kaiqing Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4180-4234

[abs][Download PDF]

Near-optimal fitting of ellipsoids to random points

Aaron Potechin, Paxton M. Turner, Prayaag Venkat, Alexander S. Wein; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4235-4295

[abs][Download PDF]

Entropic characterization of optimal rates for learning Gaussian mixtures

Zeyu Jia, Yury Polyanskiy, Yihong Wu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4296-4335

[abs][Download PDF]

Minimizing Dynamic Regret on Geodesic Metric Spaces

Zihao Hu, Guanghui Wang, Jacob D. Abernethy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4336-4383

[abs][Download PDF]

Sharp analysis of EM for learning mixtures of pairwise differences

Abhishek Dhawan, Cheng Mao, Ashwin Pananjady; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4384-4428

[abs][Download PDF]

Zeroth-order Optimization with Weak Dimension Dependency

Pengyun Yue, Long Yang, Cong Fang, Zhouchen Lin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4429-4472

[abs][Download PDF]

Quasi-Newton Steps for Efficient Online Exp-Concave Optimization

Zakaria Mhammedi, Khashayar Gatmiry; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4473-4503

[abs][Download PDF]

Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators

Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh Vempala; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4504-4569

[abs][Download PDF]

Deterministic Nonsmooth Nonconvex Optimization

Michael Jordan, Guy Kornowski, Tianyi Lin, Ohad Shamir, Manolis Zampetakis; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4570-4597

[abs][Download PDF]

Backward Feature Correction: How Deep Learning Performs Deep (Hierarchical) Learning

Zeyuan Allen-Zhu, Yuanzhi Li; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4598-4598

[abs][Download PDF]

Differentially Private and Lazy Online Convex Optimization

Naman Agarwal, Satyen Kale, Karan Singh, Abhradeep Thakurta; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4599-4632

[abs][Download PDF]

Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regression

Aleksandrs Slivkins, Karthik Abinav Sankararaman, Dylan J Foster; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4633-4656

[abs][Download PDF]

Law of Large Numbers for Bayesian two-layer Neural Network trained with Variational Inference

Arnaud Descours, Tom Huix, Arnaud Guillin, Manon Michel, Éric Moulines, Boris Nectoux; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4657-4695

[abs][Download PDF]

Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal

Moïse Blanchard, Junhui Zhang, Patrick Jaillet; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4696-4736

[abs][Download PDF]

Sparse PCA Beyond Covariance Thresholding

Gleb Novikov; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4737-4776

[abs][Download PDF]

Finite-Sample Symmetric Mean Estimation with Fisher Information Rate

Shivam Gupta, Jasper C. H. Lee, Eric Price; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4777-4830

[abs][Download PDF]

Fast Algorithms for a New Relaxation of Optimal Transport

Moses Charikar, Beidi Chen, Christopher Ré, Erik Waingarten; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4831-4862

[abs][Download PDF]

Generalization Guarantees via Algorithm-dependent Rademacher Complexity

Sarah Sachs, Tim van Erven, Liam Hodgkinson, Rajiv Khanna, Umut Şimşekli; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4863-4880

[abs][Download PDF]

Shortest Program Interpolation Learning

Naren Sarayu Manoj, Nathan Srebro; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4881-4901

[abs][Download PDF]

$\ell_p$-Regression in the Arbitrary Partition Model of Communication

Yi Li, Honghao Lin, David Woodruff; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4902-4928

[abs][Download PDF]

On Classification-Calibration of Gamma-Phi Losses

Yutong Wang, Clayton Scott; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4929-4951

[abs][Download PDF]

Generalization Error Bounds for Noisy, Iterative Algorithms via Maximal Leakage

Ibrahim Issa, Amedeo Roberto Esposito, Michael Gastpar; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4952-4976

[abs][Download PDF]

Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency

Heyang Zhao, Jiafan He, Dongruo Zhou, Tong Zhang, Quanquan Gu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4977-5020

[abs][Download PDF]

PAC Verification of Statistical Algorithms

Saachi Mutreja, Jonathan Shafer; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5021-5043

[abs][Download PDF]

Active Coverage for PAC Reinforcement Learning

Aymen Al-Marjani, Andrea Tirinzoni, Emilie Kaufmann; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5044-5109

[abs][Download PDF]

Ticketed Learning–Unlearning Schemes

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, Chiyuan Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5110-5139

[abs][Download PDF]

Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

Mahdi Soltanolkotabi, Dominik Stöger, Changzhi Xie; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5140-5142

[abs][Download PDF]

U-Calibration: Forecasting for an Unknown Agent

Bobby Kleinberg, Renato Paes Leme, Jon Schneider, Yifeng Teng; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5143-5145

[abs][Download PDF]

STay-ON-the-Ridge: Guaranteed Convergence to Local Minimax Equilibrium in Nonconvex-Nonconcave Games

Constantinos Daskalakis, Noah Golowich, Stratis Skoulakis, Emmanouil Zampetakis; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5146-5198

[abs][Download PDF]

Empirical Bayes via ERM and Rademacher complexities: the Poisson model

Soham Jana, Yury Polyanskiy, Anzo Z. Teh, Yihong Wu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5199-5235

[abs][Download PDF]

Kernelized Diffusion Maps

Loucas Pillaud-Vivien, Francis Bach; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5236-5259

[abs][Download PDF]

Statistical and Computational Limits for Tensor-on-Tensor Association Detection

Ilias Diakonikolas, Daniel M. Kane, Yuetian Luo, Anru Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5260-5310

[abs][Download PDF]

Sparsity-aware generalization theory for deep neural networks

Ramchandran Muthukumar, Jeremias Sulam; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5311-5342

[abs][Download PDF]

Is Planted Coloring Easier than Planted Clique?

Pravesh Kothari, Santosh S Vempala, Alexander S Wein, Jeff Xu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5343-5372

[abs][Download PDF]

Moments, Random Walks, and Limits for Spectrum Approximation

Yujia Jin, Christopher Musco, Aaron Sidford, Apoorv Vikram Singh; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5373-5394

[abs][Download PDF]

Minimax optimal testing by classification

Patrik R. Gerber, Yanjun Han, Yury Polyanskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5395-5432

[abs][Download PDF]

Improper Multiclass Boosting

Nataly Brukhim, Steve Hanneke, Shay Moran; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5433-5452

[abs][Download PDF]

Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions

Ilias Diakonikolas, Sushrut Karmalkar, Jong Ho Park, Christos Tzamos; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5453-5475

[abs][Download PDF]

Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes

Zihan Zhang, Qiaomin Xie; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5476-5477

[abs][Download PDF]

The Aggregation–Heterogeneity Trade-off in Federated Learning

Xuyang Zhao, Huiyuan Wang, Wei Lin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5478-5502

[abs][Download PDF]

A Blackbox Approach to Best of Both Worlds in Bandits and Beyond

Chris Dann, Chen-Yu Wei, Julian Zimmert; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5503-5570

[abs][Download PDF]

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization

Alexandros Hollender, Emmanouil Zampetakis; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5571-5572

[abs][Download PDF]

Sharp thresholds in inference of planted subgraphs

Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5573-5577

[abs][Download PDF]

Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions

Gavin Brown, Samuel Hopkins, Adam Smith; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5578-5579

[abs][Download PDF]

Learning Narrow One-Hidden-Layer ReLU Networks

Sitan Chen, Zehao Dou, Surbhi Goel, Adam Klivans, Raghu Meka; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5580-5614

[abs][Download PDF]

Universal Rates for Multiclass Learning

Steve Hanneke, Shay Moran, Qian Zhang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5615-5681

[abs][Download PDF]

Multiclass Online Learning and Uniform Convergence

Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, Ambuj Tewari; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5682-5696

[abs][Download PDF]

Local Risk Bounds for Statistical Aggregation

Jaouad Mourtada, Tomas Vaškevičius, Nikita Zhivotovskiy; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5697-5698

[abs][Download PDF]

The Implicit Bias of Batch Normalization in Linear Models and Two-layer Linear Convolutional Neural Networks

Yuan Cao, Difan Zou, Yuanzhi Li, Quanquan Gu; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5699-5753

[abs][Download PDF]

On a Class of Gibbs Sampling over Networks

Bo Yuan, Jiaojiao Fan, Jiaming Liang, Andre Wibisono, Yongxin Chen; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5754-5780

[abs][Download PDF]

Limits of Model Selection under Transfer Learning

Steve Hanneke, Samory Kpotufe, Yasaman Mahdaviyeh; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5781-5812

[abs][Download PDF]

Bandit Learnability can be Undecidable

Steve Hanneke, Liu Yang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5813-5849

[abs][Download PDF]

Detection-Recovery and Detection-Refutation Gaps via Reductions from Planted Clique

Guy Bresler, Tianze Jiang; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5850-5889

[abs][Download PDF]

Fine-Grained Distribution-Dependent Learning Curves

Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, Ilya Tolstikhin; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5890-5924

[abs][Download PDF]

Efficient median of means estimator

Stanislav Minsker; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5925-5933

[abs][Download PDF]

Open problem: log(n) factor in "Local Glivenko-Cantelli"

Doron Cohen, Aryeh Kontorovich; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5934-5936

[abs][Download PDF]

Open Problem: Learning sparse linear concepts by priming the features

Manfred K. Warmuth, Ehsan Amid; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5937-5942

[abs][Download PDF]

Open Problem: The Sample Complexity of Multi-Distribution Learning for VC Classes

Pranjal Awasthi, Nika Haghtalab, Eric Zhao; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5943-5949

[abs][Download PDF]

Open Problem: Polynomial linearly-convergent method for g-convex optimization?

Christopher Criscitiello, David Martínez-Rubio, Nicolas Boumal; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5950-5956

[abs][Download PDF]

Open Problem: Is There a First-Order Method that Only Converges to Local Minimax Optima?

Jiseok Chae, Kyuwon Kim, Donghwan Kim; Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:5957-5964

[abs][Download PDF]