A tutorial on non-asymptotic system identification methods.
problem Identifying system parameters in linear models.
method Covering technique, Hanson-Wright Inequality, method of self-normalized martingales.
result Streamlined proofs of least-squares based estimator performance.
This paper provides performance guarantees for neural estimation of statistical distances.
problem Developing performance guarantees for neural estimation of statistical distances.
method Non-asymptotic error bounds using function approximation theorems and empirical process theory.
result Established a fundamental tradeoff between approximation and estimation errors in neural estimation of statistical distances.
The paper develops AMP theory for sparse and robust regression with polynomial iterations.
problem Challenges in high-dimensional statistical estimation due to asymptotic theory breakdown.
method Non-asymptotic distributional theory of AMP for sparse and robust regression.
result First finite-sample non-asymptotic distributional theory of AMP for polynomial iterations.
New algorithm achieves instance-optimality in decision making.
problem Develop adaptive algorithms for interactive decision making.
method Introduce Allocation-Estimation Coefficient (AEC) and develop AE2 algorithm. result First non-asymptotic instance-optimal performance guarantees.
New theory improves diffusion models' convergence rates.
problem Understanding and optimizing diffusion models for faster data generation.
method Developed non-asymptotic theory for diffusion models with minimal assumptions.
result Established convergence rates for two diffusion models.
Proof of Gaussian ML estimator consistency in linear auto-regressive models.
problem Consistency of Gaussian maximum likelihood estimator in linear auto-regressive models.
method Information-theoretic proof without stability assumptions.
result Nearly optimal non-asymptotic rates for parameter recovery.
The paper analyzes methods for estimating linear functionals from observational data, proving upper bounds and showing optimal procedures.
problem Estimating linear functionals from observational data in causal inference and bandit literature.
method Two-stage procedures that first estimate treatment effect function, then use it to estimate the linear functional.
result Proves non-asymptotic upper bounds on mean-squared error for two-stage procedures and shows instance-dependent optimality.
The paper analyzes Karcher means on restricted PSD matrices with statistical guarantees.
problem Statistical analysis of non-linear manifolds in machine learning.
method Intrinsic mean model on restricted PSD matrices, Karcher mean analysis, extrinsic signal-plus-noise model.
result Non-asymptotic statistical analysis of Karcher means with deterministic error bounds.
Study non-asymptotic Langevin Monte Carlo for Gibbs distributions.
problem Sampling from Gibbs distributions with dissipative potentials.
method Langevin-type algorithms based on Liptser--Shiryaev theory and Poincaré inequalities.
result Upper bound on 2-Wasserstein distance for accurate approximation.
New methods improve temporal difference learning for policy evaluation in Markov decision processes.
problem Improving temporal difference learning for policy evaluation in Markov decision processes.
method Introduced variance-reduced forms of stochastic approximation to achieve non-asymptotic, instance-dependent optimality.
result Temporal difference learning is strictly suboptimal, but variance-reduced forms achieve optimality up to logarithmic factors.
Analyzes learning and applying preconditioners in MCMC for efficiency.
problem Improving efficiency of MCMC algorithms.
method Non-asymptotic analysis of schemes that learn preconditioners.
result Established non-asymptotic guarantees for preconditioned ULA.
We analyze training dynamics in Gaussian mixture models using a comparison theorem.
problem Analyzing training algorithms with Gaussian mixture data.
method Applying a Gaussian comparison theorem to a specific family of training algorithms.
result Validated dynamic mean-field expressions and provided iterative refinement schemes.
Particle-optimization-based sampling (POS) is a recently developed effective sampling technique that interactively updates a set of particles. A representative algorithm is the Stein variational gradient descent (SVGD). We prove, under certain conditions, SVGD experiences a theoretical pitfall, {\it i.e.}, particles te…
New theory improves diffusion model convergence for generating data.
problem Improving convergence of diffusion models for data generation.
method Developed a non-asymptotic convergence theory for probability flow ODEs.
result Proves d/ε iterations suffice for approximating target distributions. The paper gives bounds for how long it takes for gossip protocols to spread information in networks.
problem Understanding the diffusion time in asynchronous gossip protocols.
method Provides non-asymptotic bounds for the number of messages needed for consensus in asynchronous gossip protocols.
result Explicit formula and approximation for the number of messages needed for consensus in different types of graphs.
New analysis for learning and applying preconditioners in MCMC improves efficiency.
problem Improving efficiency of MCMC algorithms by modifying them with preconditioners.
method Analyzes and compares computational costs of MCMC schemes with and without preconditioners.
result Establishes non-asymptotic guarantees for MCMC algorithms that learn and use preconditioners.
Study variance-reduced method for estimating fixed points in Banach spaces.
problem Estimating fixed points of contractive operators in Banach spaces with noisy evaluations.
method Variance-reduced stochastic approximation scheme in Banach spaces.
result Establish non-asymptotic bounds for operator defect and estimation error.
Stochastic particle-optimization sampling (SPOS) is a recently-developed scalable Bayesian sampling framework that unifies stochastic gradient MCMC (SG-MCMC) and Stein variational gradient descent (SVGD) algorithms based on Wasserstein gradient flows. With a rigorous non-asymptotic convergence theory developed recently…
Study efficient iterative method for distribution matching using sliced optimal transport.
problem Efficiently match distributions using sliced optimal transport.
method Slice-matching scheme based on sliced optimal transport, with quantitative non-asymptotic rates derived.
result Derive quantitative non-asymptotic rates for convergence to target distribution.
Estimates treatment effects in rare extreme events using EVT.
problem Estimating treatment effects in rare, impactful events like extreme climate events.
method Introduces a novel framework using EVT and multivariate regular variation for consistent treatment effect estimation.
result Developed a consistent estimator for extreme treatment effects with rigorous non-asymptotic analysis.
Study shows robust method for estimating density ratios even with heavy contamination.
problem Estimating density ratios in the presence of heavy contamination.
method Weighted density ratio estimation (DRE) with doubly strong robustness.
result Weighted DRE achieves sparse consistency under heavy contamination.
The paper proves a non-asymptotic test error approximation for KRR.
problem Understanding the test error of Kernel Ridge Regression.
method Established a non-asymptotic deterministic approximation for test error of KRR.
result The test error of KRR can be approximated by a closed-form estimate derived from the spectrum of the kernel operator.
Prove non-asymptotic bounds for minimal risk in statistical learning
problem Estimating minimal risk in statistical learning
method Using concentration inequalities
result Non-asymptotic bounds for minimal risk
Constructs non-asymptotic confidence regions for unknown functions in RKHS.
problem Global probabilistic confidence regions for unknown functions in RKHS.
method Reduces confidence region construction to estimating RKHS norm.
result Valid confidence regions can be constructed non-asymptotically.
We provide non-asymptotic convergence rates of the Polyak-Ruppert averaged stochastic gradient descent (SGD) to a normal random vector for a class of twice-differentiable test functions. A crucial intermediate step is proving a non-asymptotic martingale central limit theorem (CLT), i.e., establishing the rates of conve…
Lecture notes on advanced linear regression methods.
problem Understanding the properties of linear regression estimators in high dimensions.
method Proposition-proof exploration of least squares, ridgeless, ridge, and lasso estimators.
result Detailed analysis of the existence, uniqueness, relations, computation, and non-asymptotic properties of these estimators.
New SGD method uses adaptive sampling to converge faster in non-convex problems.
problem Non-convex optimization problems with noisy gradients.
method Adaptive coordinate sampling in stochastic gradient descent (SGD).
result Almost sure convergence and non-asymptotic bounds established.
The paper studies reward concentration in MDPs, covering asymptotic and non-asymptotic settings.
problem Reward concentration in Markov Decision Processes (MDPs).
method Unified approach to reward concentration in MDPs, including asymptotic and non-asymptotic bounds.
result Rate-equivalent definitions of regret for learning policies.
We prove a new generalization bound that shows for any class of linear predictors in Gaussian space, the Rademacher complexity of the class and the training error under any continuous loss ℓ can control the test error under all Moreau envelopes of the loss ℓ. We use our finite-sample bound to directly recover…
In this paper, we analyze the finite sample complexity of stochastic system identification using modern tools from machine learning and statistics. An unknown discrete-time linear system evolves over time under Gaussian noise without external inputs. The objective is to recover the system parameters as well as the Kalm…
Neural networks estimate statistical divergences with performance guarantees.
problem Estimating statistical divergences with theoretical performance guarantees.
method Parametrizing empirical variational form by a neural network and optimizing over parameter space.
result Established non-asymptotic absolute error bounds for neural estimators of four f-divergences. New framework predicts AMP behavior in spiked models for finite iterations.
problem Understanding AMP dynamics in high-dimensional spiked models.
method Developed a non-asymptotic framework for AMP in spiked matrix estimation.
result Predicted AMP behavior for up to O(polylognn) iterations in Z2 synchronization. Paper analyzes ensemble Kalman updates for effective dimension and localization.
problem Why small ensemble sizes work well in inverse problems and data assimilation.
method Non-asymptotic analysis of ensemble Kalman updates, focusing on effective dimension and localization.
result Rigorously explains why a small ensemble size is sufficient when prior covariance has moderate effective dimension.
New bounds for generative models under weaker assumptions.
problem Establishing convergence guarantees for generative models under weak assumptions.
method Non-asymptotic 2-Wasserstein distance bounds for probability flow ODEs under weak log-concavity and Lipschitz continuity.
result Concrete convergence rates for generative models, including non-log-concave distributions.
We prove non-asymptotic lower bounds on the expectation of the maximum of d independent Gaussian variables and the expectation of the maximum of d independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (…
This study analyzes AdaGrad's stability and convergence in non-convex optimization.
problem Lack of theoretical analysis for AdaGrad in non-convex optimization.
method Novel stopping time-based techniques from probability theory.
result Established stability and derived convergence rates for AdaGrad.
Paper characterizes gradient descent in high-dimensional learning problems.
problem Understanding gradient descent dynamics in high-dimensional statistical learning.
method Non-asymptotic joint distributional characterization of gradient descent iterates and debiased statistics.
result Gradient descent iterates approximate normality after debiasing correction.
Paper improves Bayesian inference in federated learning with new algorithm VR-FALD*.
problem Bayesian inference in federated learning with communication bottlenecks and statistical heterogeneity.
method Federated Averaging Langevin Dynamics (FALD) and VR-FALD*.
result VR-FALD* corrects client drift due to statistical heterogeneity, improving convergence.
Constructing an efficient parameterization of a large, noisy data set of points lying close to a smooth manifold in high dimension remains a fundamental problem. One approach consists in recovering a local parameterization using the local tangent plane. Principal component analysis (PCA) is often the tool of choice, as…
Corrects local error estimates for UBU integrator in SDEs, improving complexity guarantees.
problem Improper local error estimates in UBU integrator for SDEs.
method Reconciles theory with practice by correcting local error estimates.
result Stronger assumptions needed for O(d1/4ε−1/2) steps in Wasserstein-2 distance. VRPG algorithm optimizes convex constraints with non-asymptotic guarantees.
problem Stochastic convex optimization under convex constraints.
method Natural variance reduced proximal gradient (VRPG) algorithm.
result VRPG achieves local minimax lower bound up to constants and log factor of N. Optimizes prediction error method for time-varying models.
problem Achieving optimal prediction error rates for time-varying models.
method Nonlinear least squares method for time-varying parametric models.
result First rate-optimal non-asymptotic analysis for time-varying models.
Study optimal stopping for diffusion processes using data-driven methods.
problem Optimal stopping for diffusion processes under unknown conditions.
method Data-driven approach, deriving upper and lower bounds on simple and cumulative regret.
result Verified minimax optimality and improved convergence rates.
The paper improves methods for estimating set size using samples.
problem Estimating the size of a set from a uniform sample.
method Refines estimators using the birthday problem and maximum of sample.
result Develops a general theory for non-asymptotic error bounds.
Motivated by the pursuit of a systematic computational and algorithmic understanding of Generative Adversarial Networks (GANs), we present a simple yet unified non-asymptotic local convergence theory for smooth two-player games, which subsumes several discrete-time gradient-based saddle point dynamics. The analysis rev…
New method improves training of PINNs for PDEs by adding noisy supervision terms.
problem Slow or failed convergence of PINNs on challenging PDEs.
method Operator preconditioning using Feynman-Kac supervision and non-asymptotic error bounds.
result Non-asymptotic error bounds for FK-PINNs, showing improved performance over standard PINNs.
This work analyzes DP-SGD for online LDP problems with practical convergence rates.
problem Analyzing DP-SGD for online LDP problems with practical convergence rates.
method Developed a general framework for online LDP model in stochastic optimization problems, conducted non-asymptotic convergence analysis.
result Comprehensive non-asymptotic convergence analysis of the proposed estimators in finite-sample situations.
Paper approximates risk measures using SGD with Langevin dynamics.
problem Approximating arbitrary law invariant risk measures.
method Stochastic Gradient Langevin Dynamics (SGD-Langevin) for general risk measures.
result Non-asymptotic convergence rates of the approximation algorithm.