
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

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

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

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

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

On Linear Stochastic Approximation: Finegrained PolyakRuppert and NonAsymptotic Concentration
We undertake a precise study of the asymptotic and nonasymptotic proper...
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

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

On the Computational Complexity of HighDimensional Bayesian Variable Selection
We study the computational complexity of Markov chain Monte Carlo (MCMC)...
read it

Newton Sketch: A Lineartime Optimization Algorithm with LinearQuadratic Convergence
We propose a randomized secondorder method for optimization known as th...
read it

Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
Data in the form of pairwise comparisons arises in many domains, includi...
read it

Optimal prediction for sparse linear models? Lower bounds for coordinateseparable Mestimators
For the problem of highdimensional sparse linear regression, it is know...
read it

Distributed Estimation of Generalized Matrix Rank: Efficient Algorithms and Lower Bounds
We study the following generalized matrix rank estimation problem: given...
read it

Randomized sketches for kernels: Fast and optimal nonparametric regression
Kernel ridge regression (KRR) is a standard method for performing nonpa...
read it

Support recovery without incoherence: A case for nonconvex regularization
We demonstrate that the primaldual witness proof method may be used to ...
read it

Iterative Hessian sketch: Fast and accurate solution approximation for constrained leastsquares
We study randomized sketching methods for approximately solving leastsq...
read it

Statistical guarantees for the EM algorithm: From population to samplebased analysis
We develop a general framework for proving rigorous guarantees on the pe...
read it

The geometry of kernelized spectral clustering
Clustering of data sets is a standard problem in many areas of science a...
read it

Randomized Sketches of Convex Programs with Sharp Guarantees
Random projection (RP) is a classical technique for reducing storage and...
read it

Optimal rates for zeroorder convex optimization: the power of two function evaluations
We consider derivativefree algorithms for stochastic and nonstochastic...
read it

Early stopping and nonparametric regression: An optimal datadependent stopping rule
The strategy of early stopping is a regularization technique based on ch...
read it

Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
We establish optimal convergence rates for a decompositionbased scalabl...
read it

Regularized Mestimators with nonconvexity: Statistical and algorithmic theory for local optima
We provide novel theoretical results regarding local optima of regulariz...
read it

Belief Propagation for Continuous State Spaces: Stochastic MessagePassing with Quantitative Guarantees
The sumproduct or belief propagation (BP) algorithm is a widely used me...
read it

Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
We investigate the relationship between the structure of a discrete grap...
read it

Privacy Aware Learning
We study statistical risk minimization problems under a privacy model in...
read it

Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions
We develop and analyze stochastic optimization algorithms for problems i...
read it

Stochastic Belief Propagation: A LowComplexity Alternative to the SumProduct Algorithm
The sumproduct or belief propagation (BP) algorithm is a widelyused me...
read it

Highdimensional regression with noisy and missing data: Provable guarantees with nonconvexity
Although the standard formulations of prediction problems involve fully...
read it