[edit]
[edit]
Editors: Mikhail Belkin, Samory Kpotufe
Filter Authors: Filter Titles:
Conference on Learning Theory 2021: Post-conference Preface
; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:i-iii
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Deterministic Finite-Memory Bias Estimation
Tomer Berg, Or Ordentlich, Ofer Shayevitz; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:566-585
[abs][Download PDF]
Online Learning from Optimal Actions
Omar Besbes, Yuri Fonseca, Ilan Lobel; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:586-586
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Fast Rates for Structured Prediction
Vivien A Cabannes, Francis Bach, Alessandro Rudi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:823-865
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Black-Box Control for Linear Dynamical Systems
Xinyi Chen, Elad Hazan; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1114-1143
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Quantifying Variational Approximation for Log-Partition Function
Romain Cosson, Devavrat Shah; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1330-1357
[abs][Download PDF]
From Local Pseudorandom Generators to Hardness of Learning
Amit Daniely, Gal Vardi; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1358-1394
[abs][Download PDF]
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
[abs][Download PDF]
Weak learning convex sets under normal distributions
Anindya De, Rocco Servedio; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1399-1428
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
The Sample Complexity of Robust Covariance Testing
Ilias Diakonikolas, Daniel M. Kane; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1511-1521
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Kernel Thinning
Raaz Dwivedi, Lester Mackey; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1753-1753
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Adaptivity in Adaptive Submodularity
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1823-1846
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Sequential prediction under log-loss and misspecification
Meir Feder, Yury Polyanskiy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:1937-1964
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Frank-Wolfe with a Nearest Extreme Point Oracle
Dan Garber, Noam Wolf; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2103-2132
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Differentially Private Nonparametric Regression Under a Growth Condition
Noah Golowich; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2149-2192
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Reduced-Rank Regression with Operator Norm Error
Praneeth Kacham, David Woodruff; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2679-2716
[abs][Download PDF]
(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
[abs][Download PDF]
The Sparse Vector Technique, Revisited
Haim Kaplan, Yishay Mansour, Uri Stemmer; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2747-2776
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
On the Minimal Error of Empirical Risk Minimization
Gil Kur, Alexander Rakhlin; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2849-2852
[abs][Download PDF]
**Paper retracted by author request (see pdf for retraction notice from the authors)** 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
[abs][Download PDF]
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
[abs][Download PDF]
Improved Regret for Zeroth-Order Stochastic Convex Bandits
Tor Lattimore, Andras Gyorgy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2938-2964
[abs][Download PDF]
Mirror Descent and the Information Ratio
Tor Lattimore, Andras Gyorgy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:2965-2992
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Approximation Algorithms for Socially Fair Clustering
Yury Makarychev, Ali Vakilian; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3246-3264
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
A Theory of Heuristic Learnability
Mikito Nanashima; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3483-3525
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Exponential savings in agnostic active learning through abstention
Nikita Puchkin, Nikita Zhivotovskiy; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3806-3832
[abs][Download PDF]
Exponential Weights Algorithms for Selective Learning
Mingda Qiao, Gregory Valiant; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3833-3858
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
Johnson-Lindenstrauss Transforms with Best Confidence
Maciej Skorski; Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3989-4007
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
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
[abs][Download PDF]
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。