Stochastic Zeroth-order Optimization in High Dimensions
This work addresses optimization challenges in high-dimensional settings for fields like machine learning and data science, though it appears incremental as it builds on existing zeroth-order methods with sparsity assumptions.
The paper tackles the problem of optimizing high-dimensional convex functions using stochastic zeroth-order queries, showing that under sparsity assumptions, two algorithms achieve convergence rates that depend only logarithmically on the ambient dimension, with empirical results confirming they outperform classical methods.
We consider the problem of optimizing a high-dimensional convex function using stochastic zeroth-order queries. Under sparsity assumptions on the gradients or function values, we present two algorithms: a successive component/feature selection algorithm and a noisy mirror descent algorithm using Lasso gradient estimates, and show that both algorithms have convergence rates that de- pend only logarithmically on the ambient dimension of the problem. Empirical results confirm our theoretical findings and show that the algorithms we design outperform classical zeroth-order optimization methods in the high-dimensional setting.