A Dimension-Insensitive Algorithm for Stochastic Zeroth-Order Optimization
This addresses the challenge of scaling optimization algorithms to high-dimensional problems without requiring gradient sparsity or compressibility, which is incremental as it builds on prior dimension-insensitive methods but relaxes stringent conditions.
The paper tackles the problem of stochastic zeroth-order optimization where gradient access is unavailable, proposing a sparsity-inducing stochastic gradient-free algorithm that achieves dimension-free query complexity up to a logarithmic term in convex and strongly convex cases, with numerical results confirming theoretical predictions.
This paper concerns a convex, stochastic zeroth-order optimization (S-ZOO) problem. The objective is to minimize the expectation of a cost function whose gradient is not directly accessible. For this problem, traditional optimization algorithms mostly yield query complexities that grow polynomially with dimensionality (the number of decision variables). Consequently, these methods may not perform well in solving massive-dimensional problems arising in many modern applications. Although more recent methods can be provably dimension-insensitive, almost all of them require arguably more stringent conditions such as everywhere sparse or compressible gradient. In this paper, we propose a sparsity-inducing stochastic gradient-free (SI-SGF) algorithm, which provably yields a dimension-free (up to a logarithmic term) query complexity in both convex and strongly convex cases. Such insensitivity to the dimensionality growth is proven, for the first time, to be achievable when neither gradient sparsity nor gradient compressibility is satisfied. Our numerical results demonstrate a consistency between our theoretical prediction and the empirical performance.