SGHMC improves sampling and optimization under local conditions.
problem Nonconvex optimization and sampling under local conditions.
method Nonasymptotic analysis of SGHMC convergence.
result SGHMC provides high-precision results uniformly in iterations.
We establish the first nonasymptotic error bounds for Kaplan-Meier-based nearest neighbor and kernel survival probability estimators where feature vectors reside in metric spaces. Our bounds imply rates of strong consistency for these nonparametric estimators and, up to a log factor, match an existing lower bound for c…
Gradient descent optimally trains RNNs without overparameterization.
problem Training recurrent neural networks (RNNs) with gradient descent.
method Nonasymptotic analysis of gradient descent for RNNs with diagonal weight matrices.
result Gradient descent can achieve optimality in RNNs with a network size scaling logarithmically with the number of samples.
New confidence intervals improve treatment effect estimation in randomized experiments.
problem Improving confidence intervals for treatment effects in randomized experiments.
method Systematic exploitation of negative dependence or variance adaptivity.
result Achieved nonasymptotic confidence intervals with the same effective sample size as asymptotic ones.
Stochastic Gradient Langevin Dynamics (SGLD) is a popular variant of Stochastic Gradient Descent, where properly scaled isotropic Gaussian noise is added to an unbiased estimate of the gradient at each iteration. This modest change allows SGLD to escape local minima and suffices to guarantee asymptotic convergence to g…
Study shows generative priors improve rank-one matrix recovery with optimal sample complexity.
problem Recovering a rank-one signal matrix from noisy data with additional prior information.
method Analysis of a nonlinear least squares objective with a favorable global optimization landscape.
result Established optimal sample complexity for generative priors in rank-one matrix recovery.
New framework robustifies loss functions with quantiles for outlier resistance.
problem Widespread outliers in big data affect statistical estimation and inference.
method Introduces a framework connecting to trimming, scalable algorithms, and new techniques.
result Robust estimators achieve minimax rate optimality in regression, classification, and neural networks.
ROOT-SGD solves convex optimization problems with optimal nonasymptotic and near-optimal asymptotic performance.
problem Solving strongly convex and smooth unconstrained optimization problems using stochastic first-order algorithms.
method ROOT-SGD: Recursive One-Over-T SGD, averaging past stochastic gradients.
result Achieves state-of-the-art performance in both nonasymptotic and asymptotic senses.
The paper improves nonparametric confidence bands for band-limited functions.
problem Constructing nonparametric simultaneous confidence bands with nonasymptotic and distribition-free guarantees.
method Based on Paley-Wiener reproducing kernel Hilbert spaces, the paper relaxes assumptions, improves noise estimation, and tightens constraints.
result Enhanced confidence bands with improved efficiency and tighter constraints.
Sampling from various kinds of distributions is an issue of paramount importance in statistics since it is often the key ingredient for constructing estimators, test procedures or confidence intervals. In many situations, the exact sampling from a given distribution is impossible or computationally expensive and, there…
This paper tightens the law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
problem Developing nonasymptotic concentration bounds for empirical KL_inf with optimal constants and rates.
method Presenting a tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
result A tight law of the iterated logarithm for empirical KL_inf, applicable to unbounded data.
Optimized AIS scheme reduces bias and MSE for general proposals.
problem Performing Monte Carlo integration with general proposals.
method Global optimization of χ²-divergence using stochastic gradient Langevin dynamics.
result Explicit theoretical guarantees for uniform-in-time MSE reduction.
FIEM accelerates EM for large datasets with nonasymptotic convergence bounds.
problem Efficiently optimizing large datasets using EM framework.
method FIEM recasts EM in Stochastic Approximation framework and provides nonasymptotic convergence bounds.
result Nonasymptotic bounds for convergence in expectation as a function of n and $\kmax$. We study the problem of robustly estimating the posterior distribution for the setting where observed data can be contaminated with potentially adversarial outliers. We propose Rob-ULA, a robust variant of the Unadjusted Langevin Algorithm (ULA), and provide a finite-sample analysis of its sampling distribution. In par…
This paper introduces time-uniform CLT-based confidence intervals for statistical inference.
problem Developing valid statistical inference methods for sequential data.
method Time-uniform central limit theory and strong invariance principles.
result Asymptotic confidence sequences (CSs) that are uniformly valid over time.
We take a Hamiltonian-based perspective to generalize Nesterov's accelerated gradient descent and Polyak's heavy ball method to a broad class of momentum methods in the setting of (possibly) constrained minimization in Euclidean and non-Euclidean normed vector spaces. Our perspective leads to a generic and unifying non…
New method estimates gradients accurately with sharp bounds.
problem Accurate gradient estimation in regression problems.
method Nearest-neighbor based pointwise estimate of gradients.
result Sharp nonasymptotic bounds for gradient estimation.
In this work, we study the problem of reconstructing shapes from simple nonasymptotic densities measured only along shape boundaries. The particular density we study is also known as the integral area invariant and corresponds to the area of a disk centered on the boundary that is also inside the shape. It is easy to s…
We propose a new algorithm---Stochastic Proximal Langevin Algorithm (SPLA)---for sampling from a log concave distribution. Our method is a generalization of the Langevin algorithm to potentials expressed as the sum of one stochastic smooth term and multiple stochastic nonsmooth terms. In each iteration, our splitting t…
The Rasch model is widely used for item response analysis in applications ranging from recommender systems to psychology, education, and finance. While a number of estimators have been proposed for the Rasch model over the last decades, the available analytical performance guarantees are mostly asymptotic. This paper p…
The paper provides bounds for regression schemes using nonstationary training samples.
problem Developing confidence intervals for nonparametric regression with nonstationary data.
method The approach involves Rademacher and Vapnik-Chervonenkis theories to analyze the cost and optimality of regression schemes.
result The paper establishes nonasymptotic bounds for regression schemes and optimality in L2-distance. Deep networks can perfectly classify two low-dimensional manifolds on a sphere with large depth and width.
problem Binary classification of two low-dimensional submanifolds on a sphere.
method Analysis of a deep fully-connected neural network trained to separate two submanifolds of the unit sphere.
result Randomly-initialized gradient descent can perfectly classify the two manifolds with high probability when the network depth is large relative to certain geometric and statistical properties of the data.
In this paper, we are concerned with a non-asymptotic analysis of sampling algorithms used in nonconvex optimization. In particular, we obtain non-asymptotic estimates in Wasserstein-1 and Wasserstein-2 distances for a popular class of algorithms called Stochastic Gradient Langevin Dynamics (SGLD). In addition, the afo…
Despite the empirical success of the actor-critic algorithm, its theoretical understanding lags behind. In a broader context, actor-critic can be viewed as an online alternating update algorithm for bilevel optimization, whose convergence is known to be fragile. To understand the instability of actor-critic, we focus o…
The paper creates nonparametric confidence bands for band-limited functions.
problem Estimating confidence bands for band-limited functions with finite samples and unknown noise.
method Uses Paley-Wiener reproducing kernel Hilbert spaces and gradient-perturbation methods.
result Non-asymptotic guarantees for confidence regions without assuming a parametric model.
Range penalization enhances statistical accuracy and resource efficiency in federated learning.
problem Statistical accuracy and resource efficiency in federated learning.
method Range regularization and polar clustering.
result Enhanced statistical accuracy and reduced iteration complexity.
We give a complete characterization of the sampling complexity of best Markovian arm identification in one-parameter Markovian bandit models. We derive instance specific nonasymptotic and asymptotic lower bounds which generalize those of the IID setting. We analyze the Track-and-Stop strategy, initially proposed for th…
Many modern big data applications feature large scale in both numbers of responses and predictors. Better statistical efficiency and scientific insights can be enabled by understanding the large-scale response-predictor association network structures via layers of sparse latent factors ranked by importance. Yet sparsit…
Sparse principal component analysis (PCA) is an important technique for dimensionality reduction of high-dimensional data. However, most existing sparse PCA algorithms are based on non-convex optimization, which provide little guarantee on the global convergence. Sparse PCA algorithms based on a convex formulation, for…
In this paper, we explore a general Aggregated Gradient Langevin Dynamics framework (AGLD) for the Markov Chain Monte Carlo (MCMC) sampling. We investigate the nonasymptotic convergence of AGLD with a unified analysis for different data accessing (e.g. random access, cyclic access and random reshuffle) and snapshot upd…
Algorithm improves online canonical correlation analysis.
problem Online canonical correlation analysis.
method Stochastic Scaled-Gradient Descent (SSGD) for minimizing expectation over Riemannian manifolds.
result Achieved optimal one-time-scale algorithm with explicit rate of local asymptotic convergence.
Study on signal detection in sparse additive models with nonasymptotic minimax rates.
problem Signal detection in sparse additive models.
method Nonasymptotic minimax analysis of signal detection in sparse additive models.
result Established minimax separation rate for signal detection.
Paper improves confidence intervals and variance estimation for deep learning models.
problem Improving confidence intervals and variance estimation in deep learning models.
method Residual-based framework for conditional variance estimation; robust bootstrap procedure for confidence intervals.
result First non-asymptotic bounds for variance estimation using ReLU networks.
Modern geometric measure theory, developed largely to solve the Plateau problem, has generated a great deal of technical machinery which is unfortunately regarded as inaccessible by outsiders. Some of its tools (e.g., flat norm distance and decomposition in generalized surface space) hold interest from a theoretical pe…
Quantifies polynomial approximation rates for smooth functions under various distributions.
problem Approximating smooth functions with polynomials under different distributional constraints.
method Develops a quantitative analogue of Carleman's theorem using complex analysis.
result Establishes superexponential rates of approximation for certain function classes over general distributions.
Study Q-learning with averaging for reinforcement learning, proving efficient inference and error bounds.
problem Efficient inference and error bounds for Q-learning with averaging.
method Functional central limit theorem and asymptotic linear estimator for optimal Q-value function.
result Standardized partial-sum process converges weakly to a rescaled Brownian motion, matching instance-dependent lower bound for error.
New theory explains how overparametrized neural networks generalize well without bias-variance trade-off.
problem Overparametrized neural networks generalize well despite classical bias-variance trade-off.
method Nonasymptotic generalization theory for two-layer neural networks with ReLU activation, incorporating scaled variation regularization.
result Prediction bounds for all network widths reproduce the double descent phenomenon, and overparametrized models are nearly minimax optimal.
The paper explains how nearest neighbor methods succeed in prediction.
problem Explaining the success of nearest neighbor methods in prediction.
method The paper covers both theoretical and practical aspects of nearest neighbor methods, including statistical guarantees and practical algorithms.
result The paper provides nonasymptotic statistical guarantees and practical algorithms for nearest neighbor methods.
The paper shows how label noise in training can lead to solutions that solve a Lasso program.
problem Understanding the implicit bias of training algorithms in overparametrised models.
method Analyzing the continuous time version of the training dynamics of a quadratically parametrised model.
result The stochastic flow implicitly solves a Lasso program, providing convergence guarantees and support recovery conditions.
The US Census Bureau corrupts data to protect privacy, but we show how to clean and analyze it effectively.
problem Analyzing Census data with intentional corruption to maintain privacy.
method Formulated a semiparametric model, proposed data cleaning, estimation, and inference procedures.
result Demonstrated that data cleaning can maintain precision and provided theoretical and empirical support.
We study sparse principal components analysis in high dimensions, where p (the number of variables) can be much larger than n (the number of observations), and analyze the problem of estimating the subspace spanned by the principal eigenvectors of the population covariance matrix. We introduce two complementary not…
A new method detects changes in data sequences by comparing backward and forward confidence sequences.
problem Detecting changes in data sequences over time.
method Constructing and comparing backward and forward confidence sequences.
result The method successfully detects changes with strong nonasymptotic guarantees.
We investigate the relationship between the structure of a discrete graphical model and the support of the inverse of a generalized covariance matrix. We show that for certain graph structures, the support of the inverse covariance matrix of indicator variables on the vertices of a graph reflects the conditional indepe…
New algorithm improves stability and efficiency of neural network training.
problem Stability and efficiency issues in adaptive optimization for neural networks.
method Polygonal approximations for SDEs with monotone coefficients, providing stability and addressing vanishing gradients.
result TheoPouLa algorithm shows superior performance over popular adaptive optimizers.
New method estimates precision matrices without models, achieving dense, consistent, and model-free properties.
problem Lack of methods that are dense, consistent, and model-free for precision matrix estimation.
method General class of estimators that unify dense, consistent, and model-free properties within a nonasymptotic framework.
result Ridgeless regression exhibits the double descent phenomenon, establishing a precision matrix analogue to linear regression's double descent.
New method tests independence using ROC analysis and bipartite ranking.
problem Testing independence of two random variables with unknown marginals.
method Nonparametric framework based on ROC analysis and bipartite ranking.
result The method detects small departures from independence in high dimensions.
Method curates cost-effective, high-quality datasets using AI models.
problem Costly manual labeling of datasets.
method Probably Approximately Correct Labels (PACL) method.
result Curates high-quality datasets with low overall labeling error.
New methods for estimating complex causal effects in econometrics.
problem Estimating causal parameters in short panel data models using nested nonparametric instrumental variable regression.
method Introducing techniques to limit ill-posedness in nested NPIV, providing explicit mean square rates and efficient inference.
result Explicit mean square rates for nested NPIV and efficient inference for causal parameters.