Metraipolis › archive › dc_d45dce1aa32b
Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints — arXiv:2609.35946
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.35946
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:01:53.424Z
- SHA-256 of the archived text
5e19bb73308e8eb2f19f8777e56b42d78440cbe69cdcffcc1309ba0f37461a0b- Stable URL of this page
https://metraipolis.com/documento/dc_d45dce1aa32b
How to cite
Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints — arXiv:2609.35946 — arXiv (en), https://arxiv.org/abs/2609.35946 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d45dce1aa32b (Metraipolis archive dc_d45dce1aa32b, sha256 5e19bb73308e8eb2f19f8777e56b42d78440cbe69cdcffcc1309ba0f37461a0b)
BibTeX
@misc{dcd45dce1aa32b,
title = {Gradient-Free Methods for Stochastic Convex Optimization with Stochastic Functional Constraints — arXiv:2609.35946},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.35946},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d45dce1aa32b; sha256 5e19bb73308e8eb2f19f8777e56b42d78440cbe69cdcffcc1309ba0f37461a0b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35946. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\varepsilon$. It achieves $O(\varepsilon^{-1/2})$ sequential oracle rounds for smooth data and $O(d^{1/4}/\varepsilon)$ 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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.35946 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T17:35:03.522Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).