Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints
Abstract
We develop accelerated gradient-free methods for stochastic convex optimization with constraints defined by expectations. Our batched primal-dual sliding method uses two-point evaluations sharing a random sample and guarantees expected objective error and expected maximum constraint violation at most ε. It achieves O(ε−1/2) sequential oracle rounds for smooth data and O(d1/4/ε) for nonsmooth data in dimension d, recovering the accuracy and dimension dependence of the corresponding unconstrained accelerated methods. The smooth rate is optimal in accuracy. Each round collects all samples needed for its inner primal-dual updates. Total evaluations retain quadratic dependence on inverse accuracy, with only polylogarithmic dependence on the number of constraints under vector feedback. Complementary lower bounds distinguish the dimension cost of gradient estimation from the unavoidable logarithmic cost of estimating noisy constraint levels. For smooth strongly convex objectives, restarts give logarithmic round complexity and objective evaluation cost linear in inverse accuracy, while constraint-level estimation necessarily remains quadratic. Known affine constraints require no constraint-oracle calls.
Related
- Recursive Gradient Retraction Methods for Stochastic Nonconvex Optimization on Stiefel Manifolds
- Stochastic Gradient Methods with Online Scaling
- Restart and Adaptive Acceleration in Stochastic Gradient Methods
- Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
- Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise
BibTeX
@misc{abronin2026gradientfree,
title = {{Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints}},
author = {Vadim Abronin and Alexander Gasnikov and Darina Dvinskikh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.35946},
eprint = {2609.35946},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35946},
}
RIS
TY - UNPB
TI - Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints
AU - Vadim Abronin
AU - Alexander Gasnikov
AU - Darina Dvinskikh
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2609.35946
UR - https://arxiv.org/abs/2609.35946
AB - We develop accelerated gradient-free methods for stochastic convex optimization with constraints defined by expectations. Our batched primal-dual sliding method uses two-point evaluations sharing a random sample and guarantees expected objective error and expected maximum constraint violation at most ε. It achieves O(ε^−1/2) sequential oracle rounds for smooth data and O(d^1/4/ε) for nonsmooth data in dimension d, recovering the accuracy and dimension dependence of the corresponding unconstrained accelerated methods. The smooth rate is optimal in accuracy. Each round collects all samples needed for its inner primal-dual updates. Total evaluations retain quadratic dependence on inverse accuracy, with only polylogarithmic dependence on the number of constraints under vector feedback. Complementary lower bounds distinguish the dimension cost of gradient estimation from the unavoidable logarithmic cost of estimating noisy constraint levels. For smooth strongly convex objectives, restarts give logarithmic round complexity and objective evaluation cost linear in inverse accuracy, while constraint-level estimation necessarily remains quadratic. Known affine constraints require no constraint-oracle calls.
ER -