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 N N . 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.
New algorithm achieves instance-optimality in decision making.
problem Develop adaptive algorithms for interactive decision making.
method Introduce Allocation-Estimation Coefficient (AEC) and develop A E 2 \mathsf{AE}^2 AE 2 algorithm. result First non-asymptotic instance-optimal performance guarantees.
Study non-asymptotic BPI guarantees for online RL.
problem Identify optimal policy in MDP with high confidence.
method Non-asymptotic sample complexity guarantees for NaS algorithm.
result Sample complexity depends on MDP connectivity and curvature.
Paper provides exponential convergence guarantees for Iterative Markovian Fitting.
problem Addressing the Schrödinger Bridge problem in computational optimal transport and generative modeling.
method Develops non-asymptotic exponential convergence guarantees for Iterative Markovian Fitting.
result First non-asymptotic exponential convergence guarantees for IMF under mild structural assumptions.
New IRL algorithm identifies optimal reward and policy from expert demonstrations.
problem Understanding reward functions from expert demonstrations with neural networks.
method Two-timescale single-loop IRL algorithm for neural network parameterized rewards.
result First IRL algorithm with non-asymptotic convergence guarantee and global optimality in neural network settings.
Paper derives convergence rates and confidence intervals for LSA with Markovian noise.
problem Analyzing convergence rates and constructing confidence intervals for LSA with Markovian noise.
method Derives non-asymptotic Berry-Esseen bounds and multiplier block bootstrap procedure.
result Provides O ( n − 1 / 4 ) \mathcal{O}(n^{-1/4}) O ( n − 1/4 ) convergence rates and guarantees consistent inference. New algorithm reduces sample complexity for Top Two method.
problem Fixed-confidence best arm identification for Top Two methods.
method UCB-based Top Two algorithm for non-asymptotic analysis.
result First non-asymptotic upper bound on expected sample complexity.
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.
Novel framework for uncertainty quantification in metric spaces.
problem Uncertainty quantification in regression models with metric responses.
method Developed algorithms for large datasets, agnostic to predictive models, with asymptotic and non-asymptotic guarantees.
result Asymptotic and non-asymptotic guarantees for special cases, demonstrated in clinical applications.
kTULA improves sampling from distributions with super-linear log-gradients.
problem Sampling from distributions with super-linearly growing log-gradients in deep learning.
method kTULA: tamed Langevin dynamics algorithm with KL divergence guarantee.
result Improved KL divergence convergence rate of 2- ε ‾ \overlineε ε . New quasi-Newton method guarantees global superlinear convergence.
problem Global convergence and superlinear convergence of quasi-Newton methods.
method Hybrid proximal extragradient method with online learning for Hessian approximation.
result First globally convergent quasi-Newton method with explicit superlinear convergence rate.
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.
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.
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 ( d 1 / 4 ε − 1 / 2 ) \mathcal{O}(d^{1/4}ε^{-1/2}) O ( d 1/4 ε − 1/2 ) steps in Wasserstein-2 distance. 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.
The paper develops a method to create non-asymptotic confidence ellipsoids for linear regression without strong noise distribution assumptions.
problem Constructing reliable confidence regions for linear regression with finite sample sizes and general noise distributions.
method The paper introduces the SPS EOA algorithm to create non-asymptotically guaranteed confidence ellipsoids for linear regression problems.
result The sizes of SPS outer ellipsoids are shown to decrease at the optimal rate for linear regression problems.
New method for semiparametric bandits reduces regret to optimal levels.
problem Complex reward structures in semiparametric bandits.
method Experimental-design approach with sharp regret bound and PAC bound.
result Minimax regret of i l d e O ( d T ) ilde{O}(\sqrt{dT}) i l d e O ( d T ) and logarithmic regret under positive suboptimality gap. DALMC provides non-asymptotic error bounds for generative models.
problem Efficiently generating samples from complex data distributions.
method Analysis of diffusion paths and Langevin Monte Carlo.
result Theoretical guarantees for a class of generative models.
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.
Study optimal and instance-dependent guarantees for solving linear equations with Markovian data.
problem Approximately solving linear fixed point equations with Markovian data.
method Non-asymptotic bounds and instance-dependent characterizations for stochastic approximation.
result Instance-optimality of the averaged SA estimator and matching upper and lower bounds.
New algorithm achieves near optimal sample complexity for 1-identification problem.
problem Determining if an arm's mean reward is at least a known threshold with high probability.
method Design of Sequential-Exploration-Exploitation (SEE) algorithm with non-asymptotic analysis.
result Achieves near optimality in sample complexity, matching upper and lower bounds up to a polynomial logarithmic factor.
The paper provides a non-asymptotic error bound for linear system identification under nonlinear policies.
problem System identification for linear systems with nonlinear and/or time-varying policies under i.i.d. random excitation noises.
method Least square estimation with non-asymptotic error bound for bounded state and action trajectories.
result The error bound is consistent with linear policies and generalizes existing guarantees.
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 \mathsf{f} f -divergences. New DRO algorithm finds robust models without strong assumptions.
problem Learning robust models against distribution shift.
method Non-convex, non-smooth, non-asymptotic convergence guarantees for DRO.
result Algorithm finds first-order stationary points efficiently.
We study the constrained linear quadratic regulator with unknown dynamics, addressing the tension between safety and exploration in data-driven control techniques. We present a framework which allows for system identification through persistent excitation, while maintaining safety by guaranteeing the satisfaction of st…
Gaussian DP improves reporting of ML algorithms' differential privacy guarantees.
problem Incomplete and misleading DP guarantees for ML algorithms.
method Using non-asymptotic Gaussian Differential Privacy (GDP) to provide accurate bounds on privacy profiles of ML algorithms.
result GDP captures the entire privacy profile of DP-SGD and related algorithms with virtually no error.
New bounds on efficiency for conformalized regression methods.
problem Efficiency of conformal prediction in regression models.
method Non-asymptotic bounds on prediction set length for conformalized quantile and median regression.
result Identifies phase transitions in convergence rates across different regimes of miscoverage level.
Paper proposes a debiased estimator for adaptive linear regression.
problem Non-normal asymptotic behavior of OLS estimator in adaptive linear regression.
method Adaptive linear estimating equations to construct debiased estimator.
result Established asymptotic normality of the debiased estimator.
New schemes improve error estimates for sampling from non-log-concave distributions.
problem Improving sampling from non-log-concave distributions with super-linear drift growth.
method Developed tamed Euler and randomized Euler schemes with error estimates.
result Near-optimal error bounds for sampling and optimization problems.
New algorithm for computing Wasserstein barycenters with guarantees.
problem Computing Wasserstein barycenters with varying regularization strengths.
method Damped Sinkhorn iterations followed by exact maximization/minimization steps.
result First non-asymptotic convergence guarantees for approximating Wasserstein barycenters.
Maximum likelihood estimator performance in logistic regression analyzed.
problem Performance of maximum likelihood estimator in logistic regression.
method Sharp non-asymptotic guarantees for existence and excess logistic risk.
result Sharp guarantees for the existence and excess risk of MLE in logistic regression.
New algorithm samples superlinearly growing log-gradient distributions.
problem Sampling from distributions with superlinearly growing log-gradient.
method Proposes a novel taming Langevin-based scheme called sTULA.
result Derives non-asymptotic convergence bounds in KL, TV, and W2 distances.
Value aggregation is a general framework for solving imitation learning problems. Based on the idea of data aggregation, it generates a policy sequence by iteratively interleaving policy optimization and evaluation in an online learning setting. While the existence of a good policy in the policy sequence can be guarant…
Smooth DNNs mitigate the curse of dimensionality in uniform convergence for various regression tasks.
problem The curse of dimensionality in uniform convergence of ReLU networks.
method Analysis of smoothly activated deep neural networks (smooth DNNs), establishing pseudo-dimension bounds and non-asymptotic approximation guarantees.
result Smooth DNNs achieve non-asymptotic uniform convergence rates across multiple statistical contexts, mitigating the curse of dimensionality.
Sharp bounds derived for test error of finite-rank kernel ridge regression.
problem Loose bounds on test error for finite-rank kernels in machine learning.
method Sharp non-asymptotic upper and lower bounds for KRR test error.
result Tighter bounds on finite-rank KRR test error, valid for any regularization parameters.
SyncRank recovers global ranking from noisy comparisons with theoretical guarantees.
problem Recovering a global ranking from noisy pairwise comparisons.
method Complex-valued data model and SDP relaxation for exact ranking recovery.
result SyncRank achieves exact ranking recovery with high probability above a critical noise threshold of O(sqrt(n / log n)).
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.
This paper presents a class of new algorithms for distributed statistical estimation that exploit divide-and-conquer approach. We show that one of the key benefits of the divide-and-conquer strategy is robustness, an important characteristic for large distributed systems. We establish connections between performance of…
Study on estimating unstable open-loop matrices from state trajectories.
problem System identification for stochastic continuous-time dynamics.
method Employing randomized control inputs to estimate unstable open-loop matrix.
result Estimation error decays with trajectory length, signal-to-noise ratio, and excitability.
Improved VB algorithm for high-dimensional logistic regression with theoretical guarantees.
problem Sparse high-dimensional logistic regression model selection.
method Spike and slab variational Bayes approximation.
result Optimal convergence rates in ℓ 2 \ell_2 ℓ 2 and prediction loss for sparse truths. Study provides convergence guarantees for discrete diffusion models on finite and infinite state spaces.
problem Challenges in understanding discrete diffusion models on combinatorial state spaces.
method Established convergence bounds for three discrete diffusion models using Euler approximations.
result Optimal non-asymptotic convergence guarantees for discrete diffusion models without boundedness assumptions.
In this paper, we study a fast approximation method for {\it large-scale high-dimensional} sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional vectors into a low-dimensional space. In particular, we propose to apply the JL transforms to …
The paper provides convergence guarantees for VAEs using SGD and Adam.
problem Understanding theoretical convergence guarantees for VAEs.
method Derives non-asymptotic convergence rates for VAEs trained with SGD and Adam.
result Convergence rate of \(\mathcal{O}(\log n / \sqrt{n})\) with explicit hyperparameter dependencies.
The paper develops robust tests for detecting independence in synchronous stochastic systems with finite sample guarantees.
problem Detecting independence in synchronous stochastic systems with finite sample guarantees.
method Combines confidence region estimates with permutation tests and dependence measures to detect nonlinear dependence.
result Consistent hypothesis tests for detecting independence under mild assumptions.
New convergence guarantees for learning with unknown nuisance parameters.
problem Learning problems with unknown nuisance parameters.
method Stochastic gradient optimization with Neyman orthogonality and approximately orthogonalized updates.
result Stochastic gradient algorithms can converge under conditions of nuisance parameters.
This paper establishes non-asymptotic learning bounds for the DR covariate shift adaptation.
problem Distribution shift between training and test domains in machine learning.
method Doubly-robust (DR) estimator combining density ratio estimation and pilot regression model.
result First non-asymptotic learning bounds for DR covariate shift adaptation.
Paper tackles unbounded density ratio estimation for covariate shift adaptation.
problem Understudied challenge in statistical learning: unbounded density ratios.
method Three-step estimation method: relative density ratio, truncation, and transformation.
result Established rigorous convergence guarantees for density ratio and regression estimators.