[edit]
[edit]
Editors: Gergely Neu, Lorenzo Rosasco
Conference on Learning Theory 2023: Preface
; 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]
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。