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

Sep 21, 2026math.OC

Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization

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.

Dan Garber

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

Oracle Complexity Optimization Convergence Analysis Nonsmooth Convex Optimization

Ask PDF

Jul 20, 2026cs.LG

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

Stochastic nonconvex optimization is central to training deep networks and LLMs in modern machine learning. We give a black-box reduction from stochastic nonconvex optimization to ordinary static regret minimization in online convex optimization (OCO), thereby resolving the open problem posed by Chen and Hazan (2024). Our reduction maintains a predictable gradient tracker, while a black-box online learner

\mathcal{A}

selects a preconditioner that transforms this tracker into the update direction. Given a

β

-smooth function with a range bounded by

M

and an unbiased gradient oracle with variance bounded by

σ^2

, we bound the expected average squared gradient norm by

O(σ\sqrt{Mβ/T}+\sqrt{Mβ}\mathrm{Reg}_T(\mathcal{A})/T+\frac{Mβ}{T})

, where

\mathrm{Reg}_T(\mathcal{A})

is the static regret of

\mathcal{A}

. Thus, any OCO oracle with

O(\sqrt{T})

regret recovers the classical

O(T^{-1/2})

convergence rate. We further extend the framework to nonsmooth nonconvex objectives, still relying only on ordinary static regret, and attain the optimal convergence rate for Goldstein-type stationarity. Finally, we conduct numerical experiments on nonconvex objectives to illustrate how the reduction exploits online-selected preconditioners while using the same stochastic-oracle budget as stochastic gradient descent.

Haichen Hu, David Simchi-Levi

Center for Computational Science and Engineering, MIT · Department of Civil and Environmental Engineering, MIT · Institute for Data, Systems, and Society, MIT

Nonconvex Stochastic Optimization Adaptive Gradient Methods

Ask PDF

May 23, 2026cs.LG

Zeroth-Order Nonconvex Nonsmooth Optimization with Heavy-Tailed Noise

This paper considers the nonconvex nonsmooth problem in which the objective function is Lipschitz continuous. We focus on the stochastic setting where the algorithm can access stochastic function value evaluations with heavy-tailed noise, which is prevalent in many popular machine learning applications. We propose a stochastic zeroth-order algorithm that refines the framework of online-to-nonconvex conversion by clipping the two-point gradient estimator. The theoretical analysis shows that our algorithm can find a

(δ, ε)

-Goldstein stationary point with zeroth-order oracle complexity of

{\mathcal O}(d^{\frac{p}{2(p-1)}}δ^{-1}ε^{-\frac{2p-1}{p-1}})

, where

d

is the problem dimension and

p\in(1,2]

is the order of bounded moments. Note that our dependence on dimension

d

matches the best-known results of stochastic zeroth-order optimization for finding the sub-optimal solution of a stochastic convex nonsmooth problem. In addition, our dependence on accuracy parameters

δ

and

ε

is consistent with that of the best-known stochastic first-order algorithms for stochastic nonconvex nonsmooth problems. Finally, we conduct numerical experiments to demonstrate the effectiveness of the proposed method.

Zhuanghua Liu, Luo Luo

Stochastic Optimization Gradient Clipping Zeroth-Order Optimization Heavy-Tailed Noise Nonconvex Optimization Nonsmooth Convex Optimization+1

Ask PDF