mlsanityData to 7 Oct 2026

Gradient-Free Method for Heavily Constrained Nonconvex Optimization

arXiv 2409.00459 ↗First posted 31 Aug 2024math.OC cs.DS cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

Zeroth-order (ZO) method has been shown to be a powerful method for solving the optimization problem where explicit expression of the gradients is difficult or infeasible to obtain. Recently, due to the practical value of the constrained problems, a lot of ZO Frank-Wolfe or projected ZO methods have been proposed. However, in many applications, we may have a very large number of nonconvex white/black-box constraints, which makes the existing zeroth-order methods extremely inefficient (or even not working) since they need to inquire function value of all the constraints and project the solution to the complicated feasible set. In this paper, to solve the nonconvex problem with a large number of white/black-box constraints, we proposed a doubly stochastic zeroth-order gradient method (DSZOG) with momentum method and adaptive step size. Theoretically, we prove DSZOG can converge to the ε-stationary point of the constrained problem. Experimental results in two applications demonstrate the superiority of our method in terms of training time and accuracy compared with other ZO methods for the constrained problem.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 33 of its 54 references that are in the map. First posted on arXiv 31 Aug 2024.

Builds on

33 of 54 references.

References · 33

  1. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  2. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 656
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  4. 2016Fairness Beyond Disparate Treatment & Disparate Impact: Learning Classification without Disparate Mistreatmentcited by 368
  5. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  6. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  7. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  8. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  9. 2013Optimal rates for zero-order convex optimization: the power of two function evaluationscited by 190
  10. 2013Mini-batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimizationcited by 142
  11. 2020Momentum Improves Normalized SGDcited by 136
  12. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 134
21 more
  1. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 109
  2. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
  3. 2018Stochastic Nested Variance Reduction for Nonconvex Optimizationcited by 63
  4. 2017Stochastic Zeroth-order Optimization in High Dimensionscited by 62
  5. 2017Non-convex Finite-Sum Optimization Via SCSG Methodscited by 61
  6. 2018Structured Evolution with Compact Architectures for Scalable Policy Optimizationcited by 48
  7. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  8. 2021SUPER-ADAM: Faster and Universal Framework of Adaptive Gradientscited by 40
  9. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 39
  10. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 36
  11. 2021BiAdam: Fast Adaptive Bilevel Optimization Methodscited by 33
  12. 2018A Frank-Wolfe Framework for Efficient and Effective Adversarial Attackscited by 29
  13. 2019A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimizationcited by 27
  14. 2017Zeroth-Order Online Alternating Direction Method of Multipliers: Convergence Analysis and Applicationscited by 22
  15. 2020Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexitiescited by 21
  16. 2020Adam^+: A Stochastic Method with Adaptive Variance Reductioncited by 17
  17. 2021Optimizing Large-Scale Hyperparameters via Automated Learning Algorithmcited by 13
  18. 2020Accelerated Stochastic Gradient-free and Projection-free Methodscited by 12
  19. 2015A Light Touch for Heavily Constrained SGDcited by 2
  20. 2016Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reductioncited by 1
  21. 2021An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm for First-order and Zeroth-order Optimizationcited by 1

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimizationcited by 0