VR-SZD, a variance-reduced zeroth-order method using orthogonal structured directions, achieves O(d n^{2/3} ε^{-1}) function evaluations for non-convex composite finite-sum problems and linear convergence under the Polyak-Łojasiewicz condition, matching state-of-the-art rates at lower…
Randomized Derivative-Free Optimization of Noisy Convex Functions
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We propose STARS, a randomized derivative-free algorithm for unconstrained optimization when the function evaluations are contaminated with random noise. STARS takes dynamic, noise-adjusted smoothing step-sizes that minimize the least-squares error between the true directional derivative of a noisy function and its finite difference approximation. We provide a convergence rate analysis of STARS for solving convex problems with additive or multiplicative noise. Experimental results show that (1) STARS exhibits noise-invariant behavior with respect to different levels of stochastic noise; (2) the practical performance of STARS in terms of solution accuracy and convergence rate is significantly better than that indicated by the theoretical result; and (3) STARS outperforms a selection of randomized zero-order methods on both additive and multiplicative-noisy functions.
fields
math.OC 1years
2025 1verdicts
ACCEPT 1representative citing papers
citing papers explorer
-
A Structured Proximal Stochastic Variance Reduced Zeroth-order Algorithm
VR-SZD, a variance-reduced zeroth-order method using orthogonal structured directions, achieves O(d n^{2/3} ε^{-1}) function evaluations for non-convex composite finite-sum problems and linear convergence under the Polyak-Łojasiewicz condition, matching state-of-the-art rates at lower…