mlsanityData to 14 Oct 2026

Adaptive Stochastic Optimisation of Nonconvex Composite Objectives

arXiv 2211.11710 ↗First posted 21 Nov 2022math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose and analyse a family of generalised stochastic composite mirror descent algorithms. With adaptive step sizes, the proposed algorithms converge without requiring prior knowledge of the problem. Combined with an entropy-like update-generating function, these algorithms perform gradient descent in the space equipped with the maximum norm, which allows us to exploit the low-dimensional structure of the decision sets for high-dimensional problems. Together with a sampling method based on the Rademacher distribution and variance reduction techniques, the proposed algorithms guarantee a logarithmic complexity dependence on dimensionality for zeroth-order optimisation problems.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 33 of its 51 references that are in the map. First posted on arXiv 21 Nov 2022.

Builds on

33 of 51 references.

References · 33

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 724
  3. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  4. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 287
  5. 2018Explanations based on the Missing: Towards Contrastive Explanations with Pertinent Negativescited by 262
  6. 2019Simple Black-box Adversarial Attackscited by 251
  7. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 220
  8. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 198
  9. 2018AdaGrad stepsizes: Sharp convergence over nonconvex landscapescited by 182
  10. 2020A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learningcited by 162
  11. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  12. 2017EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examplescited by 155
21 more
  1. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 145
  2. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 143
  3. 2015An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedbackcited by 111
  4. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
  5. 2013Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programmingcited by 75
  6. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 63
  7. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  8. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  9. 2016A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Ordercited by 44
  10. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 40
  11. 2015Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectivescited by 38
  12. 2019ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimizationcited by 37
  13. 2017Online Learning Without Prior Informationcited by 36
  14. 2018A Frank-Wolfe Framework for Efficient and Effective Adversarial Attackscited by 29
  15. 2020Model Agnostic Multilevel Explanationscited by 24
  16. 2017Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applicationscited by 22
  17. 2013A Generalized Online Mirror Descent with Applications to Classification and Regressioncited by 19
  18. 2020Accelerated Stochastic Gradient-free and Projection-free Methodscited by 12
  19. 2020Sparse Perturbations for Improved Convergence in Stochastic Zeroth-Order Optimizationcited by 8
  20. 2022Optimistic Optimisation of Composite Objective with Exponentiated Updatecited by 3
  21. 2015Accelerated Stochastic Gradient Descent for Minimizing Finite Sumscited by 2

Built on by

Not cited yet.