Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

Mingyi Li; Taira Tsuchiya; Kenji Yamanishi

cs.LGOct 8, 2026

Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

Authors: Mingyi Li, Taira Tsuchiya, Kenji Yamanishi

Organizations: The University of Tokyo · The University of Tokyo, The University of Osaka, and RIKEN

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}\varepsilon^{-3})$ stochastic gradient queries or $O(dδ^{-1}\varepsilon^{-3})$ function-value queries, where $δ$ is the Goldstein radius, $\varepsilon$ 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.

Figures & tables

Reference	Problem class	Oracle	Complexity
Cutkosky et al. (2023)	$h=0$	First-order	$O(\delta^{-1}\varepsilon^{-3})$
Kornowski and Shamir (2024)	$h=0$	Zeroth-order	$O(d\delta^{-1}\varepsilon^{-3})$
Chen et al. (2025, Theorem 2)	Composite	Zeroth-order (minibatch)	$O(d^{3/2}\delta^{-1}\varepsilon^{-4})$
Chen et al. (2025, Theorem 3)	Composite	Zeroth-order (variance reduction)	$O(d^{3/2}\delta^{-1}\varepsilon^{-3})$
Pougkakiotis and Kalogerias (2026)	Composite	Zeroth-order	$O(d^{3/2}\delta^{-1}\varepsilon^{-4})$
This work ( Theorem 4.4 )	Composite	First-order	$O(\delta^{-1}\varepsilon^{-3})$

Table 1: Oracle complexity for finding a

(\gamma,\delta,\varepsilon)

-PGSP (see Definition 3.3 ), which reduces to

(\delta,\varepsilon)

-Goldstein stationarity when

h=0

. The bounds show the dependence on

d

\delta

, and

\varepsilon

for

\delta,\varepsilon\in(0,1]

Figure 1: Query points and iterate updates in Composite O2NC . Each anchor (black dot) is fixed for

T

rounds. The dashed circle denotes

\mathbb{B}(x_{k},D)

Panel of Figure 2 — Figure 2: Stationarity measure $\min_{g\in\partial_{\delta}f(x)}\|G_{\gamma h}(x,g)\|$ (left) and objective values (right) for absolute loss for ReLU regression at $d=16$ (top), $d=256$ (middle), and $d=1024$ (bottom). Curves and shaded bands show means and one standard deviation over ten trials.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Reference	Oracle	Access	Assumption on the oracle	Complexity
Nesterov (2013) ; Ghadimi et al. (2016)	Deterministic	First-order	–	$O(\varepsilon^{-2})$
Ghadimi et al. (2016)	Stochastic	First-order	Bounded variance	$O(\varepsilon^{-4})$
Wang et al. (2019) ; Pham et al. (2020) ; Tran-Dinh et al. (2022)	Stochastic	First-order	Bounded variance, mean-squared smoothness	$O(\varepsilon^{-3})$
Ghadimi et al. (2016)	Stochastic	Zeroth-order	Each $F(\cdot,\xi)$ is smooth	$O(d\varepsilon^{-4})$
This work ( Theorem 5.3 )	Deterministic	First-order	–	$O(\varepsilon^{-2})$
This work ( Theorem 5.3 )	Stochastic	First-order	Bounded variance	$O(\varepsilon^{-4})$

Appendix

Table 2: Oracle complexity for finding an

\varepsilon

-stationary point of

\Phi=f+h

with

L_{1}

-smooth

f

. The bounds show the dependence on

d

and

\varepsilon

Panel of Figure 3 — Figure 3: Stationarity measure $\min_{g\in\partial_{\delta}f(x)}\|G_{\gamma h}(x,g)\|$ (left) and composite objective values (right) for ramp loss at $d=16$ (top), $d=256$ (middle), and $d=1024$ (bottom). Curves and shaded bands show means and one standard deviation over ten trials.

Explore similar work

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization
Sep 21, 2026Dan GarberOracle Complexity Optimization Convergence Analysis
Faculty of Data and Decision Sciences Technion - Israel Institute of Technology
Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles
Jul 20, 2026Haichen Hu, David Simchi-LeviNonconvex Stochastic Optimization Adaptive Gradient Methods
Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT
Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise
May 23, 2026Zhuanghua Liu, Luo LuoStochastic Optimization Gradient Clipping

Sep 21, 2026, math.OCJ/K move · Enter open · S save

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

Dan Garber

Faculty of Data and Decision Sciences Technion - Israel Institute of Technology

Oracle Complexity Optimization Convergence Analysis Nonsmooth Convex Optimization

Open paper AskPDF arXiv

We consider a standard convex composite optimization problem with either smooth or nonsmooth objective function, and under quadratic growth. In recent years, several works gave algorithms based on a \textit{weak proximal oracle} (WPO) that essentially match in oracle complexities proximal (sub)gradient methods relying on exact prox operations. Importantly, such WPOs, which relax the strong optimality condition of the standard prox operator, may admit much more efficient implementation in terms of runtime when optimal solutions have some sparse structure. A question remained if such WPO-based methods can be accelerated (in the sense of Nesterov's accelerated gradient). In this work we provide a negative answer by establishing lower bounds against both deterministic and randomized methods. Thus, while WPOs can substantially reduce the cost of individual oracle calls, this comes with an inherent loss in oracle complexity. We also provide a new upper-bound for WPO-based nonsmooth convex composite optimization, nearly matching the proximal subgradient method.

Abstract

Explore similar work

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

Optimizing the Preconditioner: A Black-box Online-to-Nonconvex Conversion with Static Regret Minimization Oracles

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise