[edit]

Volume 134: Conference on Learning Theory, 15-19 August 2021, Boulder, Colorado, USA

[edit]

Editors: Mikhail Belkin, Samory Kpotufe

[bib][citeproc]

Conference on Learning Theory 2021: Post-conference Preface

Mikhail Belkin, Kpotufe Samory; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:i-iii

Stochastic block model entropy and broadcasting on trees with survey

Emmanuel Abbe, Elisabetta Cornacchia, Yuzhou Gu, Yury Polyanskiy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1-25

Regret Minimization in Heavy-Tailed Bandits

Shubhada Agrawal, Sandeep K. Juneja, Wouter M. Koolen; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:26-62

SGD Generalizes Better Than GD (And Regularization Doesn’t Help)

Idan Amir, Tomer Koren, Roi Livni; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:63-92

The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications for Profile Maximum Likelihood

Nima Anari, Moses Charikar, Kirankumar Shiragur, Aaron Sidford; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:93-158

Learning in Matrix Games can be Arbitrarily Complex

Gabriel P. Andrade, Rafael Frongillo, Georgios Piliouras; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:159-185

Functions with average smoothness: structure, algorithms, and learning

Yair Ashlagi, Lee-Ad Gottlieb, Aryeh Kontorovich; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:186-236

Adversarially Robust Low Dimensional Representations

Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:237-325

The Last-Iterate Convergence Rate of Optimistic Mirror Descent in Stochastic Variational Inequalities

Waïss Azizian, Franck Iutzeler, Jérôme Malick, Panayotis Mertikopoulos; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:326-358

Optimal Dynamic Regret in Exp-Concave Online Learning

Dheeraj Baby, Yu-Xiang Wang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:359-409

Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs

Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, Alex Wein; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:410-473

Non-Euclidean Differentially Private Stochastic Convex Optimization

Raef Bassily, Cristobal Guzman, Anupama Nandi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:474-499

Reconstructing weighted voting schemes from partial information about their power indices

Huck Bennett, Anindya De, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:500-565

Deterministic Finite-Memory Bias Estimation

Tomer Berg, Or Ordentlich, Ofer Shayevitz; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:566-585

Online Learning from Optimal Actions

Omar Besbes, Yuri Fonseca, Ilan Lobel; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:586-586

Majorizing Measures, Sequential Complexities, and Online Learning

Adam Block, Yuval Dagan, Alexander Rakhlin; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:587-590

Robust learning under clean-label attack

Avrim Blum, Steve Hanneke, Jian Qian, Han Shao; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:591-634

Rank-one matrix estimation: analytic time evolution of gradient descent dynamics

Antoine Bodin, Nicolas Macris; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:635-678

Multiplayer Bandit Learning, from Competition to Cooperation

Simina Branzei, Yuval Peres; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:679-723

Near Optimal Distributed Learning of Halfspaces with Two Parties

Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:724-758

Near-Optimal Entrywise Sampling of Numerically Sparse Matrices

Vladimir Braverman, Robert Krauthgamer, Aditya R. Krishnan, Shay Sapir; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:759-773

Statistical Query Algorithms and Low Degree Tests Are Almost Equivalent

Matthew S Brennan, Guy Bresler, Sam Hopkins, Jerry Li, Tselil Schramm; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:774-774

Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries

Marco Bressan, Nicoló Cesa-Bianchi, Silvio Lattanzi, Andrea Paudice; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:775-803

A Law of Robustness for Two-Layers Neural Networks

Sebastien Bubeck, Yuanzhi Li, Dheeraj M Nagaraj; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:804-820

Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions

Sebastien Bubeck, Thomas Budzinski, Mark Sellke; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:821-822

Fast Rates for Structured Prediction

Vivien A Cabannes, Francis Bach, Alessandro Rudi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:823-865

Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

Yair Carmon, Arun Jambulapati, Yujia Jin, Aaron Sidford; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:866-882

Optimizing Optimizers: Regret-optimal gradient descent algorithms

Philippe Casgrain, Anastasis Kratsios; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:883-926

When does gradient descent with logistic loss interpolate using deep networks with smoothed ReLU activations?

Niladri S. Chatterji, Philip M. Long, Peter Bartlett; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:927-1027

Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints

Wei-Ning Chen, Peter Kairouz, Ayfer Ozgur; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1028-1059

Learning and testing junta distributions with sub cube conditioning

Xi Chen, Rajesh Jayaram, Amit Levi, Erik Waingarten; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1060-1113

Black-Box Control for Linear Dynamical Systems

Xinyi Chen, Elad Hazan; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1114-1143

Query complexity of least absolute deviation regression via robust uniform convergence

Xue Chen, Michal Derezinski; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1144-1179

Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition

Liyu Chen, Haipeng Luo, Chen-Yu Wei; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1180-1215

Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications

Liyu Chen, Haipeng Luo, Chen-Yu Wei; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1216-1259

Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, Philippe Rigollet; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1260-1300

Online Markov Decision Processes with Aggregate Bandit Feedback

Alon Cohen, Haim Kaplan, Tomer Koren, Yishay Mansour; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1301-1329

Quantifying Variational Approximation for Log-Partition Function

Romain Cosson, Devavrat Shah; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1330-1357

From Local Pseudorandom Generators to Hardness of Learning

Amit Daniely, Gal Vardi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1358-1394

A Statistical Taylor Theorem and Extrapolation of Truncated Densities

Constantinos Daskalakis, Vasilis Kontonis, Christos Tzamos, Emmanouil Zampetakis; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1395-1398

Weak learning convex sets under normal distributions

Anindya De, Rocco Servedio; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1399-1428

Learning sparse mixtures of permutations from noisy information

Anindya De, Ryan O’Donnell, Rocco Servedio; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1429-1466

Sparse sketches with small inversion bias

Michal Derezinski, Zhenyu Liao, Edgar Dobriban, Michael Mahoney; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1467-1510

The Sample Complexity of Robust Covariance Testing

Ilias Diakonikolas, Daniel M. Kane; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1511-1521

Agnostic Proper Learning of Halfspaces under Gaussian Marginals

Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1522-1551

The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, Nikos Zarifis; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1552-1584

Boosting in the Presence of Massart Noise

Ilias Diakonikolas, Russell Impagliazzo, Daniel M. Kane, Rex Lei, Jessica Sorrell, Christos Tzamos; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1585-1644

Outlier-Robust Learning of Ising Models Under Dobrushin’s Condition

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart, Yuxin Sun; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1645-1682

Random Coordinate Langevin Monte Carlo

Zhiyan Ding, Qin Li, Jianfeng Lu, Stephen J Wright; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1683-1710

On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning

Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Hoi-To Wai; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1711-1752

Kernel Thinning

Raaz Dwivedi, Lester Mackey; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1753-1753

Non-asymptotic approximations of neural networks by Gaussian processes

Ronen Eldan, Dan Mikulincer, Tselil Schramm; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1754-1775

On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness

Murat A Erdogdu, Rasa Hosseinzadeh; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1776-1822

Adaptivity in Adaptive Submodularity

Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1823-1846

Concentration of Non-Isotropic Random Tensors with Applications to Learning and Empirical Risk Minimization

Mathieu Even, Laurent Massoulie; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1847-1886

Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks

Cong Fang, Jason Lee, Pengkun Yang, Tong Zhang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1887-1936

Sequential prediction under log-loss and misspecification

Meir Feder, Yury Polyanskiy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1937-1964

Convergence rates and approximation results for SGD and its continuous-time counterpart

Xavier Fontaine, Valentin De Bortoli, Alain Durmus; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1965-2058

Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

Dylan Foster, Alexander Rakhlin, David Simchi-Levi, Yunzong Xu; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2059-2059

Efficient Algorithms for Learning from Coarse Labels

Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, Christos Tzamos; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2060-2079

Impossibility of Partial Recovery in the Graph Alignment Problem

Luca Ganassali, Laurent Massoulie, Marc Lelarge; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2080-2102

Frank-Wolfe with a Nearest Extreme Point Oracle

Dan Garber, Noam Wolf; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2103-2132

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

Badih Ghazi, Ravi Kumar, Pasin Manurangsi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2133-2146

Survival of the strictest: Stable and unstable equilibria under regularized learning with partial information

Angeliki Giannou, Emmanouil Vasileios Vlatakis-Gkaragkounis, Panayotis Mertikopoulos; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2147-2148

Differentially Private Nonparametric Regression Under a Growth Condition

Noah Golowich; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2149-2192

Source Identification for Mixtures of Product Distributions

Spencer Gordon, Bijan H Mazaheri, Yuval Rabani, Leonard Schulman; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2193-2216

PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes

Peter Grunwald, Thomas Steinke, Lydia Zakynthinou; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2217-2247

Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora’s Problem

Chenghao Guo, Zhiyi Huang, Zhihao Gavin Tang, Xinzhi Zhang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2248-2288

Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games

Steve Hanneke, Roi Livni, Shay Moran; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2289-2314

Shape Matters: Understanding the Implicit Bias of the Noise Covariance

Jeff Z. HaoChen, Colin Wei, Jason Lee, Tengyu Ma; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2315-2357

Bounded Memory Active Learning through Enriched Queries

Max Hopkins, Daniel Kane, Shachar Lovett, Michal Moshkovitz; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2358-2387

Adaptive Learning in Continuous Games: Optimal Regret Bounds and Convergence to Nash Equilibrium

Yu-Guan Hsieh, Kimon Antonakopoulos, Panayotis Mertikopoulos; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2388-2422

On the Approximation Power of Two-Layer Networks of Random ReLUs

Daniel Hsu, Clayton H Sanford, Rocco Servedio, Emmanouil Vasileios Vlatakis-Gkaragkounis; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2423-2461

Fast Rates for the Regret of Offline Reinforcement Learning

Yichun Hu, Nathan Kallus, Masatoshi Uehara; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2462-2462

Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates

De Huang, Jonathan Niles-Weed, Rachel Ward; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2463-2498

Group testing and local search: is there a computational-statistical gap?

Fotis Iliopoulos, Ilias Zadik; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2499-2551

Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds

Shinji Ito; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2552-2583

Double Explore-then-Commit: Asymptotic Optimality and Beyond

Tianyuan Jin, Pan Xu, Xiaokui Xiao, Quanquan Gu; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2584-2633

Moment Multicalibration for Uncertainty Estimation

Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, Rakesh Vohra; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2634-2678

Reduced-Rank Regression with Operator Norm Error

Praneeth Kacham, David Woodruff; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2679-2716

(Nearly) Dimension Independent Private ERM with AdaGrad Rates\{via Publicly Estimated Subspaces

Peter Kairouz, Monica Ribero Diaz, Keith Rush, Abhradeep Thakurta; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2717-2746

The Sparse Vector Technique, Revisited

Haim Kaplan, Yishay Mansour, Uri Stemmer; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2747-2776

Asymptotically Optimal Information-Directed Sampling

Johannes Kirschner, Tor Lattimore, Claire Vernade, Csaba Szepesvari; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2777-2821

Hypothesis testing with low-degree polynomials in the Morris class of exponential families

Dmitriy Kunisky; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2822-2848

On the Minimal Error of Empirical Risk Minimization

Gil Kur, Alexander Rakhlin; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2849-2852

Nonparametric Regression with Shallow Overparameterized Neural Networks Trained by GD with Early Stopping

Ilja Kuzborskij, Csaba Szepesvari; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2853-2890

Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning

Andrew Lamperski; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2891-2937

Improved Regret for Zeroth-Order Stochastic Convex Bandits

Tor Lattimore, Andras Gyorgy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2938-2964

Mirror Descent and the Information Ratio

Tor Lattimore, Andras Gyorgy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2965-2992

Structured Logconcave Sampling with a Restricted Gaussian Oracle

Yin Tat Lee, Ruoqi Shen, Kevin Tian; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2993-3050

Stochastic Approximation for Online Tensorial Independent Component Analysis

Chris Junchi Li, Michael Jordan; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3051-3106

Softmax Policy Gradient Methods Can Take Exponential Time to Converge

Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, Yuxin Chen; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3107-3110

Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing

Yi Li, David Woodruff, Taisuke Yasuda; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3111-3195

A Priori Generalization Analysis of the Deep Ritz Method for Solving High Dimensional Elliptic Partial Differential Equations

Yulong Lu, Jianfeng Lu, Min Wang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3196-3241

Corruption-robust exploration in episodic reinforcement learning

Thodoris Lykouris, Max Simchowitz, Alex Slivkins, Wen Sun; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3242-3245

Approximation Algorithms for Socially Fair Clustering

Yury Makarychev, Ali Vakilian; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3246-3264

The Connection Between Approximation, Depth Separation and Learnability in Neural Networks

Eran Malach, Gilad Yehudai, Shai Shalev-Schwartz, Ohad Shamir; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3265-3295

Random Graph Matching with Improved Noise Robustness

Cheng Mao, Mark Rudelson, Konstantin Tikhomirov; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3296-3329

Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions

Saeed Masoudian, Yevgeny Seldin; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3330-3350

Learning with invariances in random features and kernel models

Song Mei, Theodor Misiakiewicz, Andrea Montanari; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3351-3418

Learning to Sample from Censored Markov Random Fields

Ankur Moitra, Elchanan Mossel, Colin P Sandon; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3419-3451

Adversarially Robust Learning with Unknown Perturbation Sets

Omar Montasser, Steve Hanneke, Nathan Srebro; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3452-3482

A Theory of Heuristic Learnability

Mikito Nanashima; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3483-3525

Information-Theoretic Generalization Bounds for Stochastic Gradient Descent

Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, Daniel M. Roy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3526-3545

It was “all” for “nothing”: sharp phase transitions for noiseless discrete channels

Jonathan Niles-Weed, Ilias Zadik; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3546-3547

SGD in the Large: Average-case Analysis, Asymptotics, and Stepsize Criticality

Courtney Paquette, Kiwon Lee, Fabian Pedregosa, Elliot Paquette; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3548-3626

Provable Memorization via Deep Neural Networks using Sub-linear Parameters

Sejun Park, Jaeho Lee, Chulhee Yun, Jinwoo Shin; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3627-3661

Towards a Query-Optimal and Time-Efficient Algorithm for Clustering with a Faulty Oracle

Pan Peng, Jiapeng Zhang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3662-3680

Towards a Dimension-Free Understanding of Adaptive Linear Control

Juan C Perdomo, Max Simchowitz, Alekh Agarwal, Peter Bartlett; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3681-3770

Learning from Censored and Dependent Data: The case of Linear Dynamics

Orestis Plevrakis; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3771-3787

Adaptive Discretization for Adversarial Lipschitz Bandits

Chara Podimata, Alex Slivkins; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3788-3805

Exponential savings in agnostic active learning through abstention

Nikita Puchkin, Nikita Zhivotovskiy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3806-3832

Exponential Weights Algorithms for Selective Learning

Mingda Qiao, Gregory Valiant; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3833-3858

Average-Case Communication Complexity of Statistical Problems

Cyrus Rashtchian, David Woodruff, Peng Ye, Hanlin Zhu; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3859-3886

Learning to Stop with Surprisingly Few Samples

Daniel Russo, Assaf Zeevi, Tianyi Zhang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3887-3888

The Effects of Mild Over-parameterization on the Optimization Landscape of Shallow ReLU Neural Networks

Itay M Safran, Gilad Yehudai, Ohad Shamir; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3889-3934

Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball

Othmane Sebbouh, Robert M Gower, Aaron Defazio; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3935-3971

Lazy OCO: Online Convex Optimization on a Switching Budget

Uri Sherman, Tomer Koren; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3972-3988

Johnson-Lindenstrauss Transforms with Best Confidence

Maciej Skorski; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3989-4007

Efficient Bandit Convex Optimization: Beyond Linear Losses

Arun Sai Suggala, Pradeep Ravikumar, Praneeth Netrapalli; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4008-4067

On Empirical Bayes Variational Autoencoder: An Excess Risk Bound

Rong Tang, Yun Yang; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4068-4125

Machine Unlearning via Algorithmic Stability

Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi, Raman Arora; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4126-4142

A Dimension-free Computational Upper-bound for Smooth Optimal Transport Estimation

Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, Francois-Xavier Vialard; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4143-4173

Robust Online Convex Optimization in the Presence of Outliers

Tim van Erven, Sarah Sachs, Wouter M Koolen, Wojciech Kotlowski; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4174-4194

Size and Depth Separation in Approximating Benign Functions with Neural Networks

Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4195-4223

Implicit Regularization in ReLU Networks with the Square Loss

Gal Vardi, Ohad Shamir; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4224-4258

Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games

Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, Haipeng Luo; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4259-4299

Non-stationary Reinforcement Learning without Prior Knowledge: an Optimal Black-box Approach

Chen-Yu Wei, Haipeng Luo; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4300-4354

On Query-efficient Planning in MDPs under Linear Realizability of the Optimal State-value Function

Gellert Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, Csaba Szepesvari; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4355-4385

The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication

Blake E Woodworth, Brian Bullins, Ohad Shamir, Nathan Srebro; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4386-4437

Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap

Haike Xu, Tengyu Ma, Simon Du; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4438-4472

Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation

Andrea Zanette, Ching-An Cheng, Alekh Agarwal; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4473-4525

Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov Noise

Chicheng Zhang, Yinan Li; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4526-4527

Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizon

Zihan Zhang, Xiangyang Ji, Simon Du; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4528-4531

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes

Dongruo Zhou, Quanquan Gu, Csaba Szepesvari; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4532-4576

A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network

Mo Zhou, Rong Ge, Chi Jin; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4577-4632

Benign Overfitting of Constant-Stepsize SGD for Linear Regression

Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, Sham Kakade; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4633-4635

Open Problem: Are all VC-classes CPAC learnable?

Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David, Tosca Lechner, Ruth Urner; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4636-4641

Open Problem: Is There an Online Learning Algorithm That Learns Whenever Online Learning Is Possible?

Steve Hanneke; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4642-4646

Open Problem: Tight Online Confidence Intervals for RKHS Elements

Sattar Vakili, Jonathan Scarlett, Tara Javidi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4647-4652

Open Problem: Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?

Chulhee Yun, Suvrit Sra, Ali Jadbabaie; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:4653-4658

subscribe via RSS