For authors

Uniform concentration and symmetrization for weak interactions

Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks

The Relative Complexity of Maximum Likelihood Estimation, MAP Estimation, and Sampling

Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm

Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate

An Optimal High-Order Tensor Method for Convex Optimization

Testing Identity of Multidimensional Histograms

Improved Path-length Regret Bounds for Bandits

Sorted Top-k in Rounds

Privately Learning High-Dimensional Distributions

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time

On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA

Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits

Lower Bounds for Parallel and Randomized Convex Optimization

Learning Two Layer Rectified Neural Networks in Polynomial Time

Stochastic Gradient Descent Learns State Equations with Nonlinear Activations

Learning Ising Models with Independent Failures

The Gap Between Model-Based and Model-Free Methods on the Linear Quadratic Regulator: An Asymptotic Viewpoint

Tight analyses for non smooth stochastic gradient descent

Estimating the Mixing Time of Ergodic Markov Chains

Sharp Analysis for Nonconvex SGD Escaping from Saddle Points

Reasoning in Bayesian Opinion Exchange Networks Is PSPACE-Hard

Learning in Non-convex Games with an Optimization Oracle

Depth Separations in Neural Networks: What is Actually Being Separated?

Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds

A Universal Algorithm for Variational Inequalities Adaptive to Smoothness and Noise

Multi-armed Bandit Problems with Strategic Arms

Distribution-Dependent Analysis of Gibbs-ERM Principle

Sample complexity of partition identification using multi-armed bandits

The Optimal Approximation Factor in Density Estimation

Planting trees in graphs, and finding them back

Fast determinantal point processes via distortion-free intermediate sampling

Is your function low dimensional?

Accuracy-Memory Tradeoffs and Phase Transitions in Belief Propagation

Making the Last Iterate of SGD Information Theoretically Optimal

Sharp Theoretical Analysis for Nonparametric Testing under Random Projection

Robustness of spectral methods for community detection

An Information-Theoretic Approach to Minimax Regret in Partial Monitoring

Global Convergence of the EM Algorithm for Mixtures of Two Component Linear Regression

Near-optimal method for highly smooth convex optimization

Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature

Learning to Prune: Speeding up Repeated Computations

Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon

On Communication Complexity of Classification Problems

Theoretical guarantees for sampling and inference in generative models with latent diffusions

Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit

Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem

Combinatorial Algorithms for Optimal Design

Minimax experimental design: Bridging the gap between statistical and worst-case approaches to least squares regression

Budgeted Kernelized Bandits for Large Scale Gaussian Process Optimization

Combining Online Learning Guarantees

Estimation of smooth densities in Wasserstein distance

Artificial Constraints and Hints for Unbounded Online Learning

Inference under Local Constraints: Lower Bounds from Chi-Square Contractions

Communication and Memory Efficient Testing of Discrete Distributions

Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

Learning rates for Gaussian mixtures under group invariance

Optimal Tensor Methods in Smooth Convex and Uniformly Convex Optimization

Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting

Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches

A Robust Spectral Algorithm for Overcomplete Tensor Decomposition

Discrepancy, Coresets, and Sketches in Machine Learning

When can unlabeled data improve the learning rate?

Beyond Least-Squares: Fast Rates for Regularized Empirical Risk Minimization through Self-Concordance

A Theory of Selective Prediction

Reconstructing Trees from Traces

Solving Empirical Risk Minimization in the Current Matrix Multiplication Time

Nonconvex sampling with the Metropolis-adjusted Langevin algorithm

Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization

On Mean Estimation for General Norms with Statistical Queries

Maximum Entropy Distributions: Bit Complexity and Stability

Classification with unknown class conditional label noise on non-compact feature spaces

Testing Markov Chains Without Hitting

Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning

Sum-of-squares meets square loss: Fast rates for agnostic tensor completion

A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free

Statistical Learning with a Nuisance Component

Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness

Affine Invariant Covariance Estimation for Heavy-Tailed Distributions

Learning Linear Dynamical Systems with Semi-Parametric Least Squares

Non-asymptotic Analysis of Biased Stochastic Approximation Scheme

Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression

On the Performance of Thompson Sampling on Logistic Bandits

Lower Bounds for Locally Private Estimation via Communication Complexity

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models

Space lower bounds for linear prediction

Testing Mixtures of Discrete Distributions

Universality of Computational Lower Bounds for Submatrix Detection

How Hard is Robust Mean Estimation?

Approximate Guarantees for Dictionary Learning

Private Center Points and Learning of Halfspaces

Fast Mean Estimation with Sub-Gaussian Rates

Better Algorithms for Stochastic Bandits with Adversarial Corruptions

Sample-Optimal Low-Rank Approximation of Distance Matrices

High probability generalization bounds for uniformly stable algorithms with nearly optimal rate

Computational Limitations in Robust Classification and Win-Win Results

The implicit bias of gradient descent on nonseparable data

Bandit Principal Component Analysis

A near-optimal algorithm for approximating the John Ellipsoid

Pure Entropic Regularization for MTS

Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT

Achieving the Bayes Error Rate in Stochastic Block Model by SDP, Robustly

Adaptively Tracking the Best Bandit Arm with an Unknown Number of Distribution Changes

VC Classes are Adversarially Robustly Learnable, but Only Improperly

The Complexity of Making the Gradient Small in Stochastic Convex Optimization

Towards Testing Monotonicity of Distributions Over General Posets

On the Computational Power of Online Gradient Descent

How do infinite width bounded norm networks look in function space?

Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Games

Active Regression via Linear-Sample Sparsification

Faster Algorithms for High-Dimensional Robust Covariance Estimation

Parameter-free Online Convex Optimization with Sub-Exponential Noise

Computationally and Statistically Efficient Truncated Regression

Lipschitz Adaptivity with Multiple Learning Rates in Online Learning

The All-or-Nothing Phenomenon in Sparse Linear Regression

A Rank-1 Sketch for Matrix Multiplicative Weights

Optimal Learning for Mallows Block Model

Generalization and learning under Dobrushin's condition