This paper analyzes momentum Q-learning with finite-sample guarantees.
problem Improving Q-learning performance with momentum schemes.
method Proposes MomentumQ algorithm integrating Nesterov and Polyak's momentum schemes, analyzes convergence for function approximations.
result Establishes finite-sample convergence rates for MomentumQ, demonstrating better performance than vanilla Q-learning.
The paper analyzes GTD algorithms with finite-sample bounds.
problem Convergence rate analysis of GTD family of algorithms.
method Formulated as stochastic gradient algorithms and analyzed using saddle-point error.
result Obtained finite-sample bounds on GTD performance.
Paper provides convergence guarantees for off-policy NAC with finite sample complexity.
problem Convergence analysis of off-policy natural actor-critic algorithm.
method Finite-sample analysis with Importance Sampling and Q-trace algorithm.
result Converges to global optimal policy with sample complexity O ( ε − 3 log 2 ( 1 / ε ) ) \mathcal{O}(ε^{-3}\log^2(1/ε)) O ( ε − 3 log 2 ( 1/ ε )) . Unified framework for finite-sample RL algorithms using Lyapunov theory.
problem Finite-sample convergence guarantees of asynchronous RL algorithms.
method Reformulate RL algorithms as Markovian SA, develop Lyapunov analysis.
result Mean-square error bounds and convergence for various RL algorithms.
The paper investigates the convergence of Vendi scores under finite samples and introduces a truncated version for better performance.
problem The Vendi score's convergence is hindered by computational limitations when using large sample sizes.
method The authors introduce the t-truncated Vendi score to address this issue by truncating the eigenspectrum of the kernel matrix.
result The t-truncated Vendi score converges to its asymptotic limit with a smaller number of samples, improving upon the standard Vendi score.
Proofs high-dimensional spectrum convergence of weighted sample covariance.
problem High-dimensional spectrum convergence of weighted sample covariance.
method Proposes a new, concise proof with stronger assumptions.
result Spectrum convergence proven for different weight distributions.
Improved mean estimation for symmetric distributions with finite-sample guarantees.
problem Estimating the mean of a symmetric distribution from samples.
method Using Fisher information rate for finite-sample guarantees.
result Finite-sample convergence close to subgaussian with variance 1/(n * I_r), where I_r is r-smoothed Fisher information.
New learning rule for quantum measurement classes overcomes uniform convergence issues.
problem Characterizing learnability of POVM hypothesis classes in quantum settings.
method Introduced a new learning rule called denoised ERM to address uniform convergence issues.
result Characterized learnability conditions and sample complexity bounds for POVM classes.
Paper analyzes Greedy-GQ for reinforcement learning with Markovian noise.
problem Analyzing Greedy-GQ for reinforcement learning with Markovian noise.
method Develops finite-sample analysis for Greedy-GQ with linear function approximation under Markovian noise.
result Provides theoretical justification for choosing stepsizes for faster convergence.
MF-TRPO optimizes MFGs with finite sample guarantees.
problem Computing approximate Nash equilibria in MFGs.
method Extends TRPO to MFGs, providing convergence guarantees.
result Theoretical guarantees on MF-TRPO's convergence.
Paper analyzes convergence rates of two time-scale AC and NAC algorithms.
problem Finite-sample convergence rate analysis of two time-scale AC and NAC algorithms.
method Developed novel techniques for bias error and convergence rate analysis.
result Established non-asymptotic convergence rates for two time-scale AC and NAC.
Study convergence and approximations of entropic regularized Wasserstein distances for Gaussian and RKHS measures.
problem Convergence and approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings.
method Analysis of convergence and finite sample approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings.
result Strictly weaker convergence in 2-Sinkhorn divergence for Gaussian measures compared to exact 2-Wasserstein distance.
Develops robust MDPs for unknown disturbances with performance guarantees.
problem Unknown disturbance distribution in MDPs.
method Empirical distribution, sublevel set of distance function, weak convergence, concentration inequality.
result Robust optimal value function converges to true optimal value function with increasing sample sizes.
New algorithms improve spectral clustering for finite mixture models.
problem Issues with EM algorithm in spectral clustering.
method Spectral decomposition and non-parametric bootstrap sampling.
result Improved convergence and avoidance of poor solutions.
We consider the problem of sequential sampling from a finite number of independent statistical populations to maximize the expected infinite horizon average outcome per period, under a constraint that the expected average sampling cost does not exceed an upper bound. The outcome distributions are not known. We construc…
This work analyzes actor-critic methods for faster convergence.
problem Finite-time analysis and sample complexity of two-time-scale actor-critic methods.
method Non-asymptotic analysis under non-i.i.d. setting, proving convergence to first-order stationary point.
result Actor-critic method finds a first-order stationary point with i l d e O ( ε − 2.5 ) \mathcal{ ilde{O}}(ε^{-2.5}) i l d e O ( ε − 2.5 ) sample complexity. Sampling without replacement speeds up optimization in minimax problems.
problem Optimizing minimax problems with faster convergence rates.
method Analysis of gradient descent ascent and proximal point method with two sampling strategies.
result Sampling without replacement leads to faster convergence rates in minimax optimization.
Paper analyzes online tensorial ICA convergence with stochastic approximation.
problem Online tensorial ICA convergence analysis.
method Stochastic approximation for nonconvex optimization.
result Sharp finite-sample error bound of O ~ ( d / T ) \tilde{O}(\sqrt{d/T}) O ~ ( d / T ) . New analysis shows actor-critic method converges efficiently in practical settings.
problem Understanding finite-time convergence of single-timescale actor-critic methods.
method Investigated online single-timescale actor-critic algorithm with linear function approximation and Markovian sampling.
result Proved convergence to ε-approximate stationary point with sample complexity of O(ε^(-2)).
In Bayesian inference, the posterior distributions are difficult to obtain analytically for complex models such as neural networks. Variational inference usually uses a parametric distribution for approximation, from which we can easily draw samples. Recently discrete approximation by particles has attracted attention …
A new sampler speeds up Bayesian mixture models.
problem Sampling from Bayesian finite mixture models is slow and hard.
method Introduces a non-reversible sampling scheme for Bayesian finite mixture models.
result The new sampler outperforms classical samplers in many scenarios, especially during convergence.
New framework improves EM algorithm convergence under log-Sobolev inequality.
problem Improving convergence of the EM algorithm.
method Extending gradient flow techniques to EM algorithm, using free energy representation.
result Exponential convergence of EM algorithm under log-Sobolev inequality.
We provide finite-sample analysis of a general framework for using k-nearest neighbor statistics to estimate functionals of a nonparametric continuous probability density, including entropies and divergences. Rather than plugging a consistent density estimate (which requires k → ∞ k \to \infty k → ∞ as the sample size $n \to \in…
DDPMs are robust to noisy score estimates and achieve optimal convergence rates in Wasserstein-2 distance.
problem Evaluating the quality of DDPMs in Wasserstein distance with noisy score estimates.
method Established finite-sample guarantees in Wasserstein-2 distance for DDPMs, considering noisy score estimates.
result Optimal convergence rates in Wasserstein-2 distance for DDPMs, matching Gaussian case.
Let F be a family of Borel measurable functions on a complete separable metric space. The gap (or fat-shattering) dimension of F is a combinatorial quantity that measures the extent to which functions f in F can separate finite sets of points at a predefined resolution gamma > 0. We establish a connection between the g…
In reinforcement learning (RL) , one of the key components is policy evaluation, which aims to estimate the value function (i.e., expected long-term accumulated reward) of a policy. With a good policy evaluation method, the RL algorithms will estimate the value function more accurately and find a better policy. When th…
Unified view on learning unnormalized distributions using NCE.
problem Learning unnormalized distributions across different communities.
method Noise-Contrastive Estimation (NCE) for a unified perspective.
result Established finite-sample convergence rates for exponential families.
CNFs learn distributions from samples with error bounds.
problem Learning probability distributions from finite samples.
method Continuous normalizing flows with linear interpolation and flow matching objective function.
result Non-asymptotic error bounds for distribution estimator in Wasserstein-2 distance.
The paper analyzes convergence of neural SDEs as sample size increases.
problem Understanding the limiting behavior of neural SDEs as sample size grows.
method Analyzes Hamilton-Jacobi-Bellman equation and uses stochastic maximum principle.
result Convergence of minima and optimal parameters of neural SDEs as sample size increases.
This work analyzes Q Q Q -learning with adaptive stepsizes for finite-time convergence.
problem Finite-time convergence analysis for average-reward Q Q Q -learning with adaptive stepsizes. method Adaptive stepsizes as local clocks, time-inhomogeneous Markovian reformulation, almost-sure time-varying bounds, conditioning arguments, and Markov chain concentration inequalities.
result Convergence rates of i l d e O ( 1 / k ) ilde{\mathcal{O}}(1/k) i l d e O ( 1/ k ) for mean-square and pointwise mean-square convergence. Optimizes data collection for ranking and selection problems.
problem Identifying the best system from multiple solutions with limited data.
method Sequential sampling algorithm with MPB estimator and kernel ridge regression.
result OSAR achieves optimal sampling ratios almost surely in the limit.
This work analyzes nonexpansive stochastic approximations with Markovian noise, proving convergence in reinforcement learning.
problem Applying stochastic approximation to reinforcement learning settings with nonexpansive operators.
method Investigates nonexpansive stochastic approximations with Markovian noise, providing asymptotic and finite sample analysis.
result First-time proof of convergence for classical tabular average reward temporal difference learning.
Paper analyzes convergence of dynamic policy gradient for MDPs, improving performance in finite-time problems.
problem Optimal policies in finite-time MDPs are not stationary and require epoch-specific training.
method Introduces dynamic policy gradient combining dynamic programming and policy gradient, analyzes convergence for softmax parametrisation.
result Dynamic policy gradient training exploits finite-time structure, leading to better convergence bounds.
New methods optimize functions faster with less gradient accuracy needed.
problem Optimizing complex functions with limited gradient accuracy.
method Hessian averaging and adaptive gradient sampling methods.
result Improved convergence rates for various function types.
This study approximates distances between Gaussian processes and covariance operators using RKHS.
problem Approximating distances between Gaussian processes and covariance operators from finite samples.
method Using reproducing kernel Hilbert space (RKHS) covariance and cross-covariance operators, the study shows how to consistently and efficiently estimate Sinkhorn divergence from finite samples.
result Convergence rates are dimension-independent and of the same order as Hilbert-Schmidt distance.
Enhanced DFO using adaptive batch-based FD estimates.
problem Derivative-free optimization with imprecise gradient estimates.
method Adaptive batch-based finite difference estimation and dynamic sampling strategy.
result Algorithm achieves convergence rate similar to KW and SPSA methods.
We obtain an improved finite-sample guarantee on the linear convergence of stochastic gradient descent for smooth and strongly convex objectives, improving from a quadratic dependence on the conditioning ( L / μ ) 2 (L/μ)^2 ( L / μ ) 2 (where L L L is a bound on the smoothness and μ μ μ on the strong convexity) to a linear dependence on L / μ L/μ L / μ . …
We prove exact BNN posterior convergence to GP limit and provide sampling methods.
problem Theoretical and empirical challenges in obtaining exact posterior distributions of wide BNNs.
method Theoretical proof and rejection sampling for generating exact samples.
result Exact BNN posterior converges to GP limit as width increases.
New method reduces sample complexity for robust reinforcement learning.
problem Finite sample analysis in robust reinforcement learning.
method Stochastic approximation framework with controlled bias, using MLMC techniques and geometric truncation.
result Order-optimal sample complexity of i l d e O ( ε − 2 ) ilde{\mathcal{O}}(ε^{-2}) i l d e O ( ε − 2 ) for robust policy evaluation. The paper analyzes reinforcement learning methods for estimating weights and quality functions with fast convergence rates.
problem Estimating weights and quality functions in reinforcement learning with function approximation.
method The paper uses minimax methods for estimating marginal importance weights and q-functions.
result The minimax approach enables fast rates of convergence for weights and quality functions, achieving first-order efficiency.
Paper introduces a new reinforcement learning method with improved performance.
problem Designing and analyzing efficient reinforcement learning algorithms.
method Proximal gradient temporal difference learning (GTD) with accelerated algorithm GTD2-MP.
result GTD algorithms have linear complexity and improved convergence rate.
Study on Nesterov's method in stochastic settings, revealing divergence under certain conditions.
problem Understanding Nesterov's method in stochastic settings, especially finite-sum.
method Analysis of Nesterov's accelerated gradient method in stochastic and finite-sum settings.
result Nesterov's method may diverge in finite-sum settings without additional conditions.
The paper improves Monte Carlo methods for optimization problems.
problem Efficiently solving optimization problems with biased Monte Carlo estimators.
method Introduces Multilevel Monte Carlo (MLMC) within Sample Average Approximation (SAA).
result Establishes uniform convergence and sample complexity for MLMC in SAA.
We consider a situation in which we see samples in R d \mathbb{R}^d R d drawn i.i.d. from some distribution with mean zero and unknown covariance A. We wish to compute the top eigenvector of A in an incremental fashion - with an algorithm that maintains an estimate of the top eigenvector in O(d) space, and incrementally adju…
As a popular meta-learning approach, the model-agnostic meta-learning (MAML) algorithm has been widely used due to its simplicity and effectiveness. However, the convergence of the general multi-step MAML still remains unexplored. In this paper, we develop a new theoretical framework to provide such convergence guarant…
A theorem for debiasing machine learning with finite sample guarantees.
problem Calculating confidence intervals for machine learning functionals.
method Debiased machine learning based on bias correction and sample splitting.
result Nonasymptotic debiased machine learning theorem with finite sample guarantees.
AMP method reconstructs rank-one matrices from noisy data efficiently.
problem Reconstructing rank-one matrices with prior structural information from noisy observations.
method Approximate Message Passing (AMP) with random initialization.
result AMP from random initialization converges rapidly and globally.
SARSA is an on-policy algorithm to learn a Markov decision process policy in reinforcement learning. We investigate the SARSA algorithm with linear function approximation under the non-i.i.d.\ data, where a single sample trajectory is available. With a Lipschitz continuous policy improvement operator that is smooth eno…