cs.LGMar 31, 2026

Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

Authors: Kaustubh Kartikey, Shalabh Bhatnagar

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We present a finite-time analysis of two smoothed functional stochastic approximation algorithms for simulation-based optimization. The first is a two time-scale gradient-based method, while the second is a three time-scale Newton-based algorithm that estimates both the gradient and the Hessian of the objective function JJ. Both algorithms involve zeroth order estimates for the gradient/Hessian. Although the asymptotic convergence of these algorithms has been established in prior work, finite-time guarantees of two-timescale stochastic optimization algorithms in zeroth order settings have not been provided previously. For our Newton algorithm, we derive mean-squared error bounds for the Hessian estimator and establish a finite-time bound on min⁡0≤m≤TE∥∇J(θ(m))∥2\min\limits_{0 \le m \le T} \mathbb{E}\| \nabla J(θ(m)) \|^2, showing convergence to first-order stationary points. The analysis explicitly characterizes the interaction between multiple time-scales and the propagation of estimation errors. We further identify step-size choices that balance dominant error terms and achieve near-optimal convergence rates. We also provide corresponding finite-time guarantees for the gradient algorithm under the same framework. The theoretical results are further validated through experiments on the Continuous Mountain Car environment.

Figures & tables

 Hi,i(t+1)\displaystyle H_{i,i}(t+1)=Hi,i(t)+b(t)(ηi2(t)−1β2h(X(t))−\displaystyle=H_{i,i}(t)+b(t)\Big(\frac{\eta_{i}^{2}(t)-1}{\beta^{2}}h(X(t))- 
 Hi,i(t))\displaystyle H_{i,i}(t)\Big) 
Algorithm 1 Newton Smoothed Functional (NSF1) Algorithm
Figure 1: Convergence of algorithms for Mountain Car environment
HyperparameterGSF1Diagonal NSF1
β\beta0.050.05
LL400400
a(0)a(0)0.10.1
b(0)b(0)10.5
c(0)c(0)—0.05
σ\sigma0.60.6
Table 1: Hyperparameters used for GSF1 and diagonal NSF1 experiments
More in this topic

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 209 papers

Explore similar work

CardsList
Feb 23, 2026

Generalized Random Direction Newton Algorithms for Stochastic Optimization

We present a family of generalized Hessian estimators of the objective using random direction stochastic approximation (RDSA) by utilizing only noisy function measurements. The form of each estimator and the order of the bias depend on the number of function measurements. In particular, we demonstrate that estimators with more function measurements exhibit lower-order estimation bias. We show the asymptotic unbiasedness of the estimators. We also perform asymptotic and non-asymptotic convergence analyses for stochastic Newton methods that incorporate our generalized Hessian estimators. Finally, we perform numerical experiments to validate our theoretical findings.

Soumen Pachal, Prashanth L. A., Shalabh Bhatnagar +1

Indian Institute of Technology Madras · Indian Institute of Science, Bangalore · TCS Research, Chennai, India

Stochastic OptimizationStochastic Optimization ConvergenceZeroth-Order OptimizationStochastic Approximation
AskPDF
May 23, 2026

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a (δ,ε)(δ, ε)-Goldstein stationary point with zeroth-order oracle complexity of O(dp2(p−1)δ−1ε−2p−1p−1){\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}}), where dd is the problem dimension and p∈(1,2]p\in(1,2] is the order of bounded moments. Note that our dependence on dimension dd matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters δδ and εε is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.

Zhuanghua Liu, Luo Luo

Stochastic OptimizationGradient ClippingZeroth-Order OptimizationHeavy-Tailed NoiseNonconvex OptimizationNonsmooth Convex Optimization+1
AskPDF
Apr 14, 2025

Towards Weaker Variance Assumptions for Stochastic Optimization

We revisit a classical assumption for analyzing stochastic gradient algorithms where the squared norm of the stochastic subgradient (or the variance for smooth problems) is allowed to grow as fast as the squared norm of the optimization variable. We contextualize this assumption in view of its inception in the 1960s, its seemingly independent appearance in the recent literature, its relationship to weakest-known variance assumptions for analyzing stochastic gradient algorithms, and its relevance in deterministic problems for non-Lipschitz nonsmooth convex optimization. We build on and extend a connection recently made between this assumption and the Halpern iteration. For convex nonsmooth, and potentially stochastic, optimization, we analyze horizon-free, anytime algorithms with last-iterate rates. For problems beyond simple constrained optimization, such as convex problems with functional constraints or regularized convex-concave min-max problems, we obtain rates for optimality measures that do not require boundedness of the feasible set.

Ahmet Alacaoglu, Yura Malitsky, Stephen J. Wright

Department of Mathematics, University of British Columbia · Faculty of Mathematics, University of Vienna · Department of Computer Sciences, University of Wisconsin–Madison

Stochastic OptimizationLast-Iterate ConvergenceStochastic ApproximationConvergence AnalysisNonsmooth Convex Optimization
AskPDF