Stochastic finite-difference schemes for nondifferentiable quasiconvex optimization: convergence rate

Abstract

This paper investigates stochastic approximation methods based on finite differences for the minimization of quasiconvex functions. Traditional approaches to convex optimization problems primarily rely on exact or stochastic subgradients. However, in many practical situations, only noisy information about function values is available. In such cases, stochastic quasi-gradient schemes constructed using randomized finite-difference estimators are considered. In particular, we study batch two-point schemes that provide unbiased approximations of the gradient of a smoothed objective function. Variance bounds are established for these estimators, which enable a rigorous convergence analysis of projected stochastic descent methods. The paper considers the minimization problem of functions of the form $f(x) = \max_{i \in I} f_i(x),$ where each function $f_i(x),$ $i \in I,$ is quasiconvex and has a Lipschitz-continuous gradient on a convex compact set. The main result of the paper is the derivation of convergence rate estimates for stochastic finite-difference methods in the quasiconvex setting. It is shown that the expected suboptimality decreases at the rate $O\!\left(1/\sqrt{k}\right).$ The obtained results significantly broaden the applicability of stochastic finite-difference methods to nonsmooth quasiconvex optimization problems and provide a rigorous theoretical justification of the algorithm in black-box settings where only noisy function evaluations are available.