
ROOTSGD: Sharp Nonasymptotics and Asymptotic Efficiency in a Single Algorithm
The theory and practice of stochastic optimization has focused on stocha...
read it

Revisiting complexity and the biasvariance tradeoff
The recent success of highdimensional models, such as deep neural netwo...
read it

Instability, Computational Efficiency and Statistical Accuracy
Many statistical estimators are defined as the fixed point of a datadep...
read it

FedSplit: An algorithmic framework for fast federated optimization
Motivated by federated learning, we consider the hubandspoke model of ...
read it

Lower bounds in multiple testing: A framework based on derandomized proxies
The large bulk of work in multiple testing has focused on specifying pro...
read it

On Linear Stochastic Approximation: Finegrained PolyakRuppert and NonAsymptotic Concentration
We undertake a precise study of the asymptotic and nonasymptotic proper...
read it

Is Temporal Difference Learning Optimal? An InstanceDependent Analysis
We address the problem of policy evaluation in discounted Markov decisio...
read it

Sampling for Bayesian Mixture Models: MCMC with PolynomialTime Mixing
We study the problem of sampling from the power posterior distribution i...
read it

An Efficient Sampling Algorithm for Nonsmooth Composite Potentials
We consider the problem of sampling from a density of the form p(x) ∝(f...
read it

Value function estimation in Markov reward processes: Instancedependent ℓ_∞bounds for policy evaluation
Markov reward processes (MRPs) are used to model stochastic phenomena ar...
read it

A Diffusion Process Perspective on Posterior Contraction Rates for Parameters
We show that diffusion processes can be exploited to study the posterior...
read it

HighOrder Langevin Diffusion Yields an Accelerated MCMC Algorithm
We propose a Markov chain Monte Carlo (MCMC) algorithm based on thirdor...
read it

Improved Bounds for Discretization of Langevin Diffusions: NearOptimal Rates without Convexity
We present an improved analysis of the EulerMaruyama discretization of ...
read it

Variancereduced Qlearning is minimax optimal
We introduce and analyze a form of variancereduced Qlearning. For γdi...
read it

Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multistep gradients
Hamiltonian Monte Carlo (HMC) is a stateoftheart Markov chain Monte C...
read it

Stochastic approximation with conecontractive operators: Sharp ℓ_∞bounds for Qlearning
Motivated by the study of Qlearning algorithms in reinforcement learnin...
read it

Challenges with EM in application to weakly identifiable mixture models
We study a class of weakly identifiable locationscale mixture models fo...
read it

DerivativeFree Methods for Policy Optimization: Guarantees for Linear Quadratic Systems
We study derivativefree methods for policy optimization over the class ...
read it

Singularity, Misspecification, and the Convergence Rate of EM
A line of recent work has characterized the behavior of the EM algorithm...
read it

LShapley and CShapley: Efficient Model Interpretation for Structured Data
We study instancewise feature importance scoring as a method for model i...
read it

Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
Many applications, including rank aggregation, crowdlabeling, and graph...
read it

Convergence guarantees for a class of nonconvex and nonsmooth optimization problems
We consider the problem of finding critical points of functions that are...
read it

From Gauss to Kolmogorov: Localized Measures of Complexity for Ellipses
The Gaussian width is a fundamental quantity in probability, statistics ...
read it

Breaking the 1/√(n) Barrier: Faster Rates for Permutationbased Models in Polynomial Time
Many applications, including rank aggregation and crowdlabeling, can be...
read it

Learning to Explain: An InformationTheoretic Perspective on Model Interpretation
We introduce instancewise feature selection as a methodology for model i...
read it

Logconcave sampling: MetropolisHastings algorithms are fast!
We consider the problem of sampling from a strongly logconcave density ...
read it

Approximate Ranking from Pairwise Comparisons
A common problem in machine learning is to rank a set of n items based o...
read it

The local geometry of testing in ellipses: Tight control via localized Kolmogorov widths
We study the local geometry of testing a mean vector within a highdimen...
read it

The local geometry of testing in ellipses: Tight control via localized Kolomogorov widths
We study the local geometry of testing a mean vector within a highdimen...
read it

Fast MCMC sampling algorithms on polytopes
We propose and analyze two new MCMC sampling algorithms, the Vaidya walk...
read it

Online control of the false discovery rate with decaying memory
In the online multiple testing problem, pvalues corresponding to differ...
read it

DAGGER: A sequential algorithm for FDR control on DAGs
We propose a topdown algorithm for multiple testing on directed acyclic...
read it

Low Permutationrank Matrices: Structural Properties and Noisy Completion
We consider the problem of noisy matrix completion, in which the goal is...
read it

Worstcase vs Averagecase Design for Estimation from Fixed Pairwise Comparisons
Pairwise comparison data arises in many domains, including tournament ra...
read it

Early stopping for kernel boosting algorithms: A general analysis with localized complexities
Early stopping of iterative algorithms is a widelyused form of regulari...
read it

Kernel Feature Selection via Conditional Covariance Minimization
We propose a framework for feature selection that employs kernelbased m...
read it

A framework for MultiA(rmed)/B(andit) testing with online FDR control
We propose an alternative framework to existing setups for controlling f...
read it

Denoising Linear Models with Permuted Data
The multivariate linear regression model with shuffled data and additive...
read it

A unified treatment of multiple testing with prior knowledge using the pfilter
A significant literature studies ways of employing prior knowledge to im...
read it

Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
We provide two fundamental results on the population (infinitesample) l...
read it

Linear Regression with an Unknown Permutation: Statistical and Computational Limits
Consider a noisy linear observation model with an unknown permutation, b...
read it

A Permutationbased Model for Crowd Labeling: Optimal Estimation and Robustness
The aggregation and denoising of crowd labeled data is a task that has g...
read it

Active Ranking from Pairwise Comparisons and when Parametric Assumptions Don't Help
We consider sequential or active ranking of a set of n items based on no...
read it

On kernel methods for covariates that are rankings
Permutationvalued features arise in a variety of applications, either i...
read it

Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
We study methods for aggregating pairwise comparison data in order to es...
read it

Asymptotic behavior of ℓ_pbased Laplacian regularization in semisupervised learning
Given a weighted graph with N vertices, consider a realvalued regressio...
read it

Simple, Robust and Optimal Ranking from Pairwise Comparisons
We consider data in the form of pairwise comparisons of n items, with th...
read it

Statistical and Computational Guarantees for the BaumWelch Algorithm
The Hidden Markov Model (HMM) is one of the mainstays of statistical mod...
read it

Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
There are various parametric models for analyzing pairwise comparison da...
read it

Fast lowrank estimation by projected gradient descent: General statistical and algorithmic guarantees
Optimization problems with rank constraints arise in many applications, ...
read it