Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives
Not on the map. Why?
Abstract (arXiv)
In this paper, we propose and analyze algorithms for zeroth-order optimization of non-convex composite objectives, focusing on reducing the complexity dependence on dimensionality. This is achieved by exploiting the low dimensional structure of the decision set using the stochastic mirror descent method with an entropy alike function, which performs gradient descent in the space equipped with the maximum norm. To improve the gradient estimation, we replace the classic Gaussian smoothing method with a sampling method based on the Rademacher distribution and show that the mini-batch method copes with the non-Euclidean geometry. To avoid tuning hyperparameters, we analyze the adaptive stepsizes for the general stochastic mirror descent and show that the adaptive version of the proposed algorithm converges without requiring prior knowledge about the problem.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 23 of its 40 references that are in the map. First posted on arXiv 9 Aug 2022.
Builds on
23 of 40 references.
References · 23
- 2015Deep Residual Learning for Image Recognitioncited by 51,809
- 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
- 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
- 2018Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negativescited by 261
- 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
- 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 160
- 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 155
- 2017EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examplescited by 154
- 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
- 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 109
- 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 105
- 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 74
11 more
- 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
- 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
- 2016A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Ordercited by 43
- 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
- 2017Online Learning Without Prior Informationcited by 36
- 2018A Frank-Wolfe Framework for Efficient and Effective Adversarial Attackscited by 29
- 2020Model Agnostic Multilevel Explanationscited by 24
- 2017Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applicationscited by 22
- 2013A Generalized Online Mirror Descent with Applications to Classification and Regressioncited by 18
- 2020Accelerated Stochastic Gradient-free and Projection-free Methodscited by 12
- 2020Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimizationcited by 8
Built on by
Citing papers per year: 2023: 1.
1 paper.