Accepted papers

  • Locally Private Hypothesis Selection
    Sivakanth Gopi, Gautam Kamath, Janardhan D Kulkarni, Aleksandar Nikolov, Steven Wu, Huanyu Zhang
  • Differentially Private Mean Estimation of Heavy-Tailed Distributions
    Gautam Kamath, Vikrant Singhal, Jonathan Ullman
  • An O(m/eps^3.5)-Cost Algorithm for Semidefinite Programs with Diagonal Constraints
    Swati Padmanabhan, Yin Tat Lee
  • Adaptive Submodular Maximization under Stochastic Item Costs
    Srinivasan Parthasarathy
  • Gradient descent algorithms for Bures-Wasserstein barycenters
    Sinho Chewi, Philippe Rigollet, Tyler Maunu, Austin Stromme
  • On the gradient complexity of linear regression
    Elad Hazan, Mark Braverman, Max Simchowitz, Blake E Woodworth
  • Improper Learning for Non-Stochastic Control
    Max Simchowitz, Karan Singh, Elad Hazan
  • Root-n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
    Kefan Dong, Jian Peng, Yining Wang, Yuan Zhou
  • No-Regret Prediction in Marginally Stable Systems
    Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang
  • Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities
    Jelena Diakonikolas
  • PAC learning with stable and private predictions
    Yuval Dagan, Vitaly Feldman
  • Learning a Single Neuron with Gradient Methods
    Gilad Yehudai, Ohad Shamir
  • Universal Approximation with Deep Narrow Networks
    Patrick Kidger, Terry J Lyons
  • Asymptotic Errors for High-Dimensional Convex Penalized Linear Regression beyond Gaussian Matrices
    Alia Abbara, Florent Krzakala, Cedric Gerbelot
  • On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems
    Dan Garber
  • From Nesterov's Estimate Sequence to Riemannian Acceleration
    Kwangjun Ahn, Suvrit Sra
  • Selfish Robustness and Equilibria in Multi-Player Bandits
    Etienne Boursier, Vianney Perchet
  • How Good is SGD with Random Shuffling?
    Itay M Safran, Ohad Shamir
  • Exploration by Optimisation in Partial Monitoring
    Tor Lattimore, Csaba Szepesvari
  • Extending Learnability to Auxiliary-Input Cryptographic Primitives and Meta-PAC Learning
    Mikito Nanashima
  • Noise-tolerant, Reliable Active Classification with Comparison Queries
    Max Hopkins, Shachar Lovett, Daniel Kane, Gaurav Mahajan
  • Sharper Bounds for Uniformly Stable Algorithms
    Olivier Bousquet, Yegor Klochkov, Nikita Zhivotovskiy
  • Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
    Alekh Agarwal, Sham Kakade, Jason Lee, Gaurav Mahajan
  • Consistent recovery threshold of hidden nearest neighbor graphs
    Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang
  • High probability guarantees for stochastic convex optimization
    Damek Davis, Dmitriy Drusvyatskiy
  • Information Directed Sampling for Linear Partial Monitoring
    Johannes Kirschner, Tor Lattimore, Andreas Krause
  • ID3 Learns Juntas for Smoothed Product Distributions
    Eran Malach, Amit Daniely, Alon Brutzkus
  • Tight Lower Bounds for Combinatorial Multi-Armed Bandits
    Nadav Merlis, Shie Mannor
  • Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
    Jayadev Acharya, Clement L Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi
  • Reasoning About Generalization via Conditional Mutual Information
    Thomas Steinke, Lydia Zakynthinou
  • A Greedy Anytime Algorithm for Sparse PCA
    Dan Vilenchik, Adam Soffer, Guy Holtzman
  • Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
    Yin Tat Lee, Ruoqi Shen, Kevin Tian
  • Provably Efficient Reinforcement Learning with Linear Function Approximation
    Chi Jin, Zhuoran Yang, Zhaoran Wang, Michael Jordan
  • A Fast Spectral Algorithm for Mean Estimation with Sub-Gaussian Rates
    Zhixian Lei, Kyle Luh, Prayaag Venkat, Fred Zhang
  • How to trap a gradient flow
    Dan Mikulincer, Sebastien Bubeck
  • Near-Optimal Algorithms for Minimax Optimization
    Tianyi Lin, Chi Jin, Michael Jordan
  • Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal
    Alekh Agarwal, Sham Kakade, Lin Yang
  • Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
    Maksim Kaledin, Eric Moulines, Alexey Naumov, Vladislav Tadic, Hoi-To Wai
  • Fast Rates for Online Prediction with Abstention
    Gergely Neu, Nikita Zhivotovskiy
  • Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
    YICHUN HU, Nathan Kallus, Xiaojie Mao
  • Data-driven confidence bands for distributed nonparametric regression
    Valeriy Avanesov
  • Tsallis-INF for Decoupled Exploration and Exploitation in Multi-armed Bandits
    Chloé Rouyer, Yevgeny Seldin
  • Pan-Private Uniformity Testing
    Kareem Amin, Matthew Joseph, Jieming Mao
  • ODE-Inspired Analysis for the Biological Version of Oja’s Rule in Solving Streaming PCA
    Mien Brabeeba Wang, Chi-Ning Chou
  • Complexity Guarantees for Polyak Steps with Momentum
    Mathieu Barre, Adrien B Taylor, Alexandre d'Aspremont
  • Calibrated Surrogate Losses for Adversarially Robust Classification
    Han Bao, Clayton Scott, Masashi Sugiyama
  • Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
    Oliver Hinder, Aaron Sidford, Nimit S Sohoni
  • Faster Projection-free Online Learning
    Edgar Minasyan, Elad Hazan
  • Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
    Sebastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke
  • Coordination without communication: optimal regret in two players multi-armed bandits
    Sebastien Bubeck, Thomas Budzinski
  • EM Algorithm is Sample-Optimal for Learning Mixtures of Well-Separated Gaussians
    Jeongyeol Kwon, Constantine Caramanis
  • Online Learning with Vector Costs and Bandits with Knapsacks
    Thomas Kesselheim, Sahil Singla
  • Better Algorithms for Estimating Non-Parametric Models in Crowd-Sourcing and Rank Aggregation
    Allen X Liu, Ankur Moitra
  • Nearly Non-Expansive Bounds for Mahalanobis Hard Thresholding
    Xiaotong Yuan, Ping Li
  • Learning Halfspaces with Massart Noise Under Structured Distributions
    Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis
  • Rigorous Guarantees for Tyler's M-Estimator via Quantum Expansion
    William C Franks, Ankur Moitra
  • Active Learning for Identification of Linear Dynamical Systems
    Andrew J Wagenmaker, Kevin Jamieson
  • Bounds in query learning
    Hunter S Chase, James Freitag
  • Active Local Learning
    Arturs Backurs, Avrim Blum, Neha Gupta
  • Kernel and Rich Regimes in Overparametrized Models
    Blake E Woodworth, Suriya Gunasekar, Jason Lee, Edward Moroshko, Pedro Henrique Pamplona Savarese, Itay Golan, Daniel Soudry, Nathan Srebro
  • Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
    Qiaomin Xie, Yudong Chen, Zhaoran Wang, Zhuoran Yang
  • Finite-Time Analysis of Asynchronous Stochastic Approximation and $Q$-Learning
    Guannan Qu, Adam Wierman
  • Parallels Between Phase Transitions and Circuit Complexity?
    Colin P Sandon, Ankur Moitra, Elchanan Mossel
  • Hierarchical Clustering: A 0.585 Revenue Approximation
    Noga Alon, Yossi Azar, Danny Vainstein
  • Gradient descent follows the regularization path for general losses
    Ziwei Ji, Miroslav Dudik, Robert Schapire, Matus Telgarsky
  • Bessel Smoothing and Multi-Distribution Property Estimation
    Yi Hao, Ping Li
  • Privately Learning Thresholds: Closing the Exponential Gap
    Uri Stemmer, Moni Naor, Haim Kaplan, Yishay Mansour, Katrina Ligett
  • Pessimism About Unknown Unknowns Inspires Conservatism
    Michael K Cohen, Marcus Hutter
  • The Influence of Shape Constraints on the Thresholding Bandit Problem
    James Cheshire, Pierre Menard, Alexandra Carpentier
  • Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent
    James P Bailey, Gauthier Gidel, Georgios Piliouras
  • Efficient and robust algorithms for adversarial linear contextual bandits
    Gergely Neu, Julia Olkhovskaya
  • Non-asymptotic Analysis for Nonparametric Testing
    Yun Yang, Zuofeng Shang, Guang Cheng
  • Tree-projected gradient descent for estimating gradient-sparse parameters on graphs
    Sheng Xu, Zhou Fan, Sahand Negahban
  • Covariance-adapting algorithm for semi-bandits with application to sparse rewards
    Pierre Perrault, Vianney Perchet, Michal Valko
  • Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems
    Noah Golowich, Sarath Pattathil, Constantinos Daskalakis, Asuman Ozdaglar
  • A Corrective View of Neural Networks: Representation, Memorization and Learning
    Dheeraj M Nagaraj, Guy Bresler
  • Learning Entangled Single-Sample Gaussians in the Subset-of-Signals Model
    Yingyu Liang, Hui Yuan
  • Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss
    Lénaïc Chizat, Francis Bach
  • Dimension-Free Bounds for Chasing Convex Functions
    Guru Guruganesh, Anupam Gupta, Charles Argue
  • Optimal group testing
    Oliver Gebhard, Philipp Loick, Maximilian Hahn-Klimroth, Amin Coja-Oghlan
  • On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
    Gil Kur, Alexander Rakhlin, Adityanand Guntuboyina
  • A Nearly Optimal Variant of the Perceptron Algorithm for the Uniform Distribution on the Unit Sphere
    Marco Schmalhofer
  • A Closer Look at Small-loss Bounds for Bandits with Graph Feedback
    Chung-Wei Lee, Haipeng Luo, Mengxiao Zhang
  • Extrapolating the profile of a finite population
    Yihong Wu, Yury Polyanskiy, Soham Jana
  • Balancing Gaussian vectors in high dimension
    Paxton M Turner, Raghu Meka, Philippe Rigollet
  • On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
    Tengyuan Liang, Alexander Rakhlin, Xiyu Zhai
  • From tree matching to sparse graph alignment
    Luca Ganassali, Laurent Massoulie
  • Estimating Principal Components under Adversarial Perturbations
    Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
  • Logistic Regression Regret: What’s the Catch?
    Gil I Shamir
  • Efficient, Noise-Tolerant, and Private Learning via Boosting
    Mark Bun, Marco L Carmosino, Jessica Sorrell
  • Highly smooth minimization of non-smooth problems
    Brian Bullins
  • Proper Learning, Helly Number, and an Optimal SVM Bound
    Olivier Bousquet, Steve Hanneke, Shay Moran, Nikita Zhivotovskiy
  • Efficient Parameter Estimation of Truncated Boolean Product Distributions
    Dimitris Fotakis, Alkis Kalavasis, Christos Tzamos
  • Estimation and Inference with Trees and Forests in High Dimensions
    Vasilis Syrgkanis, Emmanouil Zampetakis
  • Closure Properties for Private Classification and Online Prediction
    Noga Alon, Amos Beimel, Shay Moran, Uri Stemmer
  • New Potential-Based Bounds for Prediction with Expert Advice
    Vladimir A Kobzar, Robert Kohn, Zhilei Wang
  • Distributed Signal Detection under Communication Constraints
    Jayadev Acharya, Clement L Canonne, Himanshu Tyagi
  • Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
    Antonio Blanca, Zongchen Chen, Eric Vigoda, Daniel Stefankovic
  • Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
    Ilias Diakonikolas, Daniel M Kane, Vasilis Kontonis, Nikos Zarifis
  • Costly Zero Order Oracles
    Renato Paes Leme, Jon Schneider
  • Precise Tradeoffs in Adversarial Training for Linear Regression
    Adel Javanmard, Mahdi Soltanolkotabi, Hamed Hassani
  • Approximate is Good Enough: Probabilistic Variants of Dimensional and Margin Complexity
    Pritish Kamath, Omar Montasser, Nathan Srebro
  • Wasserstein Control of Mirror Langevin Monte Carlo
    Kelvin Shuangjian Zhang, Gabriel Peyré, Jalal Fadili, Marcelo Pereyra
  • The estimation error of general first order methods
    Michael V Celentano, Andrea Montanari, Yuchen Wu
  • Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations
    Yossi Arjevani, Yair Carmon, John Duchi, Dylan Foster, Ayush Sekhari, Karthik Sridharan
  • Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
    Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant
  • Free Energy Wells and Overlap Gap Property in Sparse PCA
    Ilias Zadik, Alexander S. Wein, Gerard Ben Arous
  • Robust causal inference under covariate shift via worst-case subpopulation treatment effects
    Sookyo Jeong, Hongseok Namkoong
  • Winnowing with Gradient Descent
    Ehsan Amid, Manfred K. Warmuth
  • Embedding Dimension of Polyhedral Losses
    Jessica J Finocchiaro, Rafael Frongillo, Bo Waggoner
  • List Decodable Subspace Recovery
    Morris Yau, Prasad Raghavendra
  • Approximation Schemes for ReLU Regression
    Ilias Diakonikolas, Surbhi Goel, Sushrut Karmalkar, Adam Klivans, Mahdi Soltanolkotabi
  • Learning Over-parametrized Two-layer ReLU Neural Networks beyond NTK
    Yuanzhi Li, Tengyu Ma, Hongyang R Zhang
  • Fine-grained Analysis for Linear Stochastic Approximation with Averaging: Polyak-Ruppert, Non-asymptotic Concentration and Beyond
    Wenlong Mou, Chris Junchi Li, Martin Wainwright, Peter Bartlett, Michael Jordan
  • Learning Polynomials in Few Relevant Dimensions
    Sitan Chen, Raghu Meka
  • Efficient improper learning for online logistic regression
    Pierre Gaillard, Rémi Jézéquel, Alessandro Rudi
  • Lipschitz and Comparator-Norm Adaptivity in Online Learning
    Zakaria Mhammedi, Wouter M Koolen
  • Information Theoretic Optimal Learning of Gaussian Graphical Models
    Sidhant Misra, Marc D Vuffray, Andrey Lokhov
  • Reducibility and Statistical-Computational Gaps from Secret Leakage
    Matthew S Brennan, Guy Bresler
  • Taking a hint: How to leverage loss predictors in contextual bandits?
    Chen-Yu Wei, Haipeng Luo, Alekh Agarwal