aiqbench analysis
This research introduces a novel Bregman linearized augmented Lagrangian method for nonconvex constrained stochastic zeroth-order optimization, specifically addressing scenarios where only noisy function values are accessible. By integrating variance reduction techniques with Rademacher smoothing, the approach achieves improved oracle complexity in high-dimensional settings without relying on additional assumptions. The method demonstrates practical efficacy through numerical experiments on constrained Lasso problems and black-box adversarial attacks, offering a more efficient path to finding KKT points compared to existing literature.
Bregman Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Zeroth-order Optimization
arXiv:2504.09409v2 Announce Type: replace-cross Abstract: In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems, for which we have access to exact information of constraints and noisy function values of the objective. We propose a Bregman linearized augmented Lagrangian method that utilizes stochastic zeroth-order gradient estimators combined with a variance reduction technique. We analyze its oracle complexity, in terms of the total number of stochastic function value evaluations required to achieve an \(\epsilon\)-KKT point in \(\ell_p\)-norm metrics with \(p \ge 2\), where \(p\) is a parameter associated with the selected Bregman distance. In particular, starting from a near-feasible initial point and using Rademacher smoothing, the oracle complexity is in order \(O(p d^{2/p} \epsilon^{-3})\) for \(p \in [2, 2 \ln d]\), and \(O(\ln d \cdot \epsilon^{-3})\) for \(p > 2 \ln d\), where \(d\) denotes the problem dimension. Those results show that the complexity of the proposed method can achieve a dimensional dependency lower than \(O(d)\) without requiring additional assumptions, provided that a Bregman distance is chosen properly. This offers a significant improvement in the high-dimensional setting over existing work, and matches the lowest complexity order with respect to the tolerance \(\epsilon\) reported in the literature. Numerical experiments on constrained Lasso and black-box adversarial attack problems highlight the promising performances of the proposed method.
Abstract:In this paper, we study nonconvex constrained stochastic zeroth-order optimization problems, for which we have access to exact information of constraints and noisy function values of the objective. We propose a Bregman linearized augmented Lagrangian method that utilizes stochastic zeroth-order gradient estimators combined with a variance reduction technique. We analyze its oracle complexity, in terms of the total number of stochastic function value evaluations required to achieve an \(\epsilon\)-KKT point in \(\ell_p\)-norm metrics with \(p \ge 2\), where \(p\) is a parameter associated with the selected Bregman distance. In particular, starting from a near-feasible initial point and using Rademacher smoothing, the oracle complexity is in order \(O(p d^{2/p} \epsilon^{-3})\) for \(p \in [2, 2 \ln d]\), and \(O(\ln d \cdot \epsilon^{-3})\) for \(p > 2 \ln d\), where \(d\) denotes the problem dimension. Those results show that the complexity of the proposed method can achieve a dimensional dependency lower than \(O(d)\) without requiring additional assumptions, provided that a Bregman distance is chosen properly. This offers a significant improvement in the high-dimensional setting over existing work, and matches the lowest complexity order with respect to the tolerance \(\epsilon\) reported in the literature. Numerical experiments on constrained Lasso and black-box adversarial attack problems highlight the promising performances of the proposed method.
Optimization and Control (math.OC); Machine Learning (cs.LG)
arXiv:2504.09409 [math.OC]
(or arXiv:2504.09409v2 [math.OC] for this version)
https://doi.org/10.48550/arXiv.2504.09409 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 305 words
Related coverage
Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
arXiv · Oct 16, 2026
Topology-Guided Modular Actor-Critic Learning for Continuous Systems under Temporal Objectives
arXiv · Aug 26, 2026
Constrained Flow Policy Updates: A Generalized Schr\"odinger Bridge View
arXiv · Sep 30, 2026
Residual-Controlled Multiplier Learning for Stochastic Constrained Decision-Making
arXiv · Jun 10, 2026