Adaptive two-points zero-order accelerated methods for stochastic convex optimization problems
Abstract
We study stochastic convex optimization, where each sampled function can be evaluated at two arbitrary points. Our accelerated method chooses step sizes, batch sizes and smoothing radii from function values. A forward difference between smoothing scales controls the radius; we account for changes in the smoothed objective. Under the stated regularity and second-moment assumptions, exact function evaluations give 𝔼[f(xN)−f(x⋆)] ≤ Õbiggl( (√d M2 D)/√T +minbiggl( (L D2)/N2, (d1/4 M D)/N+(√d M D2)/(γmax N2) biggr)biggr). Here N,T,d,D denote the numbers of optimization steps and paired evaluations, the dimension and a feasible-set diameter bound, respectively. Evaluations are available within Euclidean distance γmax of the feasible set. For the population objective f(x)=𝔼ξ F(x,ξ), M satisfies |f(x)−f(y)|≤ M|x−y|2, and M2 satisfies 𝔼ξ|∇ F(x,ξ)|22≤ M22 for sample weak gradients in the interior of the evaluation domain. The method requires no L,M,M2, where L is a Lipschitz constant of ∇ f; set L=+∞ without smoothness. The method uses exactly 2T values in 3N sequential sampling rounds with predetermined batches, or 5N with batches chosen from observations. An extension selects a search radius without a supplied distance bound. Fixed radius parameters can leave nonvanishing error; suitable choices depending on the budgets yield convergence.
Related
- Accelerated Stochastic Zeroth-Order Quasar-Convex Optimization
- Accelerated Prox-Level Methods for Unknown Piecewise-Smooth Optimization II: Function-constrained Optimization
- A Safeguarded Accelerated Proximal ADMM Algorithm for Solving Structured Cardinality Penalized Optimization Problems
- ABrA-GD: Adaptive Bregman Accelerated Gradient Descent for Relatively Smooth and (Strongly-)Convex Optimization
- Accelerated Push-Pull with Local Updates for Decentralized Stochastic Optimization
BibTeX
@misc{dorn2026adaptive,
title = {{Adaptive two-points zero-order accelerated methods for stochastic convex optimization problems}},
author = {Yuriy Dorn and Osman Osmanov and Timofei Loginov and Nazarii Tupitsa and Darina Dvinskikh and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15202},
eprint = {2610.15202},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15202},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Adaptive two-points zero-order accelerated methods for stochastic convex optimization problems
AU - Yuriy Dorn
AU - Osman Osmanov
AU - Timofei Loginov
AU - Nazarii Tupitsa
AU - Darina Dvinskikh
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.15202
UR - https://arxiv.org/abs/2610.15202
AB - We study stochastic convex optimization, where each sampled function can be evaluated at two arbitrary points. Our accelerated method chooses step sizes, batch sizes and smoothing radii from function values. A forward difference between smoothing scales controls the radius; we account for changes in the smoothed objective. Under the stated regularity and second-moment assumptions, exact function evaluations give 𝔼[f(x_N)−f(x^⋆)] ≤ Õbiggl( (√d M_2 D)/√T +minbiggl( (L D^2)/N^2, (d^1/4 M D)/N+(√d M D^2)/(γ_max N^2) biggr)biggr). Here N,T,d,D denote the numbers of optimization steps and paired evaluations, the dimension and a feasible-set diameter bound, respectively. Evaluations are available within Euclidean distance γ_max of the feasible set. For the population objective f(x)=𝔼_ξ F(x,ξ), M satisfies |f(x)−f(y)|≤ M|x−y|_2, and M_2 satisfies 𝔼_ξ|∇ F(x,ξ)|_2^2≤ M_2^2 for sample weak gradients in the interior of the evaluation domain. The method requires no L,M,M_2, where L is a Lipschitz constant of ∇ f; set L=+∞ without smoothness. The method uses exactly 2T values in 3N sequential sampling rounds with predetermined batches, or 5N with batches chosen from observations. An extension selects a search radius without a supplied distance bound. Fixed radius parameters can leave nonvanishing error; suitable choices depending on the budgets yield convergence.
ER -