# Stochastic Zeroth-order Functional Constrained Optimization: Oracle Complexity and Applications

arXiv: https://arxiv.org/abs/2210.04273 · HTML: https://mlsanity.com/paper/2210.04273/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2022.

## Built on by (most cited first, 5 of 5)

- [Diffusion Models as Constrained Samplers for Optimization with Unknown Constraints](https://mlsanity.com/paper/2402.18012/) (2024)
- [Multi-channel Autobidding with Budget and ROI Constraints](https://mlsanity.com/paper/2302.01523/) (2023)
- [Communication-Efficient Zeroth-Order Distributed Online Optimization: Algorithm, Theory, and Applications](https://mlsanity.com/paper/2306.05655/) (2023)
- [Mirror Descent Linearized Augmented Lagrangian Methods for Nonconvex Constrained Stochastic Zeroth-Order Optimization](https://mlsanity.com/paper/2504.09409/) (2025)
- [Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds](https://mlsanity.com/paper/2601.08039/) (2026)

## Abstract (arXiv)

Functionally constrained stochastic optimization problems, where neither the objective function nor the constraint functions are analytically available, arise frequently in machine learning applications. In this work, assuming we only have access to the noisy evaluations of the objective and constraint functions, we propose and analyze stochastic zeroth-order algorithms for solving the above class of stochastic optimization problem. When the domain of the functions is ℝn, assuming there are m constraint functions, we establish oracle complexities of order O((m+1)n/ε2) and O((m+1)n/ε3) respectively in the convex and nonconvex setting, where ε represents the accuracy of the solutions required in appropriately defined metrics. The established oracle complexities are, to our knowledge, the first such results in the literature for functionally constrained stochastic zeroth-order optimization problems. We demonstrate the applicability of our algorithms by illustrating its superior performance on the problem of hyperparameter tuning for sampling algorithms and neural network training.