Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
Abstract
We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with O(δ−1ε−3) stochastic gradient queries or O(dδ−1ε−3) function-value queries, where δ is the Goldstein radius, ε is the stationarity tolerance, and d is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.
Related
- Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
- Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity
BibTeX
@misc{li2026composite,
title = {{Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity}},
author = {Mingyi Li and Taira Tsuchiya and Kenji Yamanishi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12328},
eprint = {2610.12328},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12328},
}
RIS
TY - UNPB
TI - Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
AU - Mingyi Li
AU - Taira Tsuchiya
AU - Kenji Yamanishi
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12328
UR - https://arxiv.org/abs/2610.12328
AB - We consider stochastic nonsmooth nonconvex composite optimization, which includes several important problems such as constrained optimization and the regularized training of neural networks. The objective is the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, and the function is accessed through stochastic gradients or function values. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives. To our knowledge, no oracle complexity bound for this setting is known under first-order access, and existing complexities under zeroth-order access are suboptimal. To handle this issue, we employ the framework of online-to-nonconvex conversion, which chooses update directions by an online learner and is known to achieve optimal rates for noncomposite problems. We extend the framework to our composite scenario by introducing new losses for the learner, which contain the regularizer itself rather than its linearization and for which a variant of online mirror descent achieves low regret. We show that the resulting algorithm finds such a point with O(δ^−1ε^−3) stochastic gradient queries or O(dδ^−1ε^−3) function-value queries, where δ is the Goldstein radius, ε is the stationarity tolerance, and d is the dimension. These rates match the optimal ones for noncomposite nonsmooth nonconvex optimization, demonstrating that the additional convex regularizer does not worsen the oracle complexity. We also give rates for the smooth case and present numerical experiments.
ER -