Source-linked AI summary
Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
Mingyi Li, Taira Tsuchiya, Kenji Yamanishi
TL;DR
Stochastic nonsmooth nonconvex composite optimization lacks a known first-order PGSP complexity bound, and existing zeroth-order bounds are suboptimal. The paper extends online-to-nonconvex conversion with learner losses that retain the regularizer. Its method achieves oracle complexities matching the noncomposite rates.
Problem
For stochastic nonsmooth nonconvex composite optimization, no first-order PGSP complexity bound is known and existing zeroth-order bounds are suboptimal.
Source: §1 · p. 2Method
The paper extends online-to-nonconvex conversion using learner losses that include the convex regularizer rather than its linearization.
Source: §1.1 · pp. 2–3Results
O(δ^-1ε^-3) stochastic gradient queries and O(dδ^-1ε^-3) function-value queries match the optimal noncomposite rates in the stated senses.
Source: §1.1 · p. 2Takeaways & Limitations
The convex regularizer does not worsen the oracle complexity relative to the noncomposite rates.
Source: §1.1 · p. 2The analysis assumes a finite initial objective gap and the stated objective and first-order-oracle assumptions.
Source: §3.1 · p. 5
Abstract
from arXiv · showhide
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(\delta^{-1}\varepsilon^{-3})$ stochastic gradient queries or $O(d\delta^{-1}\varepsilon^{-3})$ function-value queries, where $\delta$ 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.
1 Introduction
The paper studies stochastic nonsmooth nonconvex composite optimization, where prior composite analyses largely assume smoothness and no stochastic first-order PGSP complexity bound is known. It extends online-to-nonconvex conversion to composite objectives and obtains oracle rates matching those for noncomposite nonsmooth nonconvex optimization.
1 Introduction
- The paper addresses a gap: most existing composite convergence analyses assume smooth f, while no stochastic first-order complexity bound for PGSPs is known for general Lipschitz nonconvex f and proper closed convex h.Prior zeroth-order composite methods have d^3/2 dependence, even with variance reduction.Source: §1 · pp. 1–2
1.1 Contributions of this paper
- The method finds a proximal Goldstein stationary point with O(δ^-1ε^-3) stochastic gradient queries or O(dδ^-1ε^-3) function-value queries.The zeroth-order rate improves the dimension dependence of the prior composite bound from d^3/2 to d and is optimal in d, δ, and ε individually; the first-order rate matches the joint lower bound in δ and ε when h = 0.Source: §1.1 · p. 2
- Composite O2NC replaces O2NC's linear learner losses with losses that retain the convex regularizer, enabling a regret-to-PGSP conversion.For the resulting losses, composite objective mirror descent attains the same regret bound as for linear losses.Source: §1.1 · p. 3
- The PGSP guarantee holds for every proximal parameter γ > 0, and neither the algorithm nor its oracle complexity depends on γ.The returned point is formed by minimizing the averaged online loss over feasible directions at the selected anchor.Source: §1.1 · p. 3
- For smooth f, the paper reports O(ε^-4) stochastic gradient or O(dε^-4) function-value query bounds, and experiments report lower stationarity measures and objective values than Chen et al. (2025) at equal query counts.With deterministic gradients, the result recovers the O(ε^-2) proximal-gradient rate.Source: §1.1 · p. 3
2 Related work
Prior composite optimization work emphasizes proximal-gradient methods and often assumes smoothness or weak convexity. Related work also develops nonsmooth zeroth-order methods and online-to-nonconvex conversion, while this paper extends the latter to composite objectives.
Composite optimization
- For smooth nonconvex f, minibatch proximal-gradient methods attain O(ε^-4) stochastic gradient query complexity; other analyses use the Kurdyka–Łojasiewicz property.The literature also includes FISTA and nonconvex extensions, including Ghadimi and Lan (2016).Source: §2 · p. 3
- Weakly convex nonsmooth problems have stochastic first-order and zeroth-order Moreau-envelope guarantees, while deterministic Goldstein-type results without weak convexity overlap with convex constraints.The latter setting differs by using deterministic first-order oracles rather than the more general stochastic oracles considered here.Source: §2 · pp. 3–4
- Prior composite zeroth-order methods for proximal Goldstein stationarity use O(d^3/2δ^-1ε^-4) or O(d^3/2δ^-1ε^-3) queries, while this paper gives O(dδ^-1ε^-3) without variance reduction.The cited earlier bounds include minibatch and variance-reduced methods; related inexact-query work has an O(d^3/2δ^-1ε^-4) converted bound.Source: §2 · p. 4
Online-to-nonconvex conversion
- O2NC converts online regret bounds into Goldstein stationarity guarantees, and randomized smoothing gives a dimension-linear zeroth-order bound; this paper extends the framework to composite objectives.The composite conversion uses losses retaining h and composite objective mirror descent, including when h can equal +∞.Source: §2 · p. 4
3 Preliminaries
The preliminaries specify the composite objective, stochastic oracle assumptions, and Goldstein-type stationarity measure used in the analysis. They also explain how guarantees for a smoothed objective transfer to the original nonsmooth objective.
3.1 Problem setting
- The first-order oracle returns unbiased stochastic gradients with bounded variance and second moment; the setup also specifies a function-value oracle and a finite initial objective gap.For zeroth-order access, the same sample may be used at two points.Source: §3.1 · p. 5
- Smoothing f with radius ρ makes it differentiable, and a PGSP guarantee for fρ + h transfers to f + h with the Goldstein radius increased by ρ.The transfer lemma states that a (γ, ν, ε)-PGSP for fρ + h is a (γ, ρ + ν, ε)-PGSP for f + h.Source: §3.1 · p. 5, §3.2 · p. 6
3.2 Goldstein-type stationarity
- A PGSP extends Goldstein stationarity to the composite objective; when h = 0, the composite mapping reduces to the gradient.In smooth settings, the text relates the proximal-gradient mapping to standard stationarity and also gives a connection to the Moreau envelope of a smoothed objective.Source: §3.2 · p. 6
- For random outputs, the stationarity guarantee bounds the expected residual.Source: §3.2 · p. 6
4 Composite O2NC
Composite O2NC uses an online learner with convex losses that retain the regularizer, then returns a locally shifted anchor. The framework gives first- and zeroth-order PGSP guarantees, with oracle complexities matching the stated noncomposite rates.
4.1 Proposed conversion framework
- The learner receives convex losses combining a gradient estimate with h(xk + u) − h(xk), while queries are made along segments from each fixed anchor.The first- and zeroth-order versions differ only in their query oracle.Source: §4.1 · pp. 6–7
- After each block, the algorithm updates from a randomly selected direction and returns a selected anchor shifted by the minimizer of its local composite model.Source: §4.1 · pp. 7–8
- The returned point satisfies the PGSP guarantee for every γ > 0, and the algorithm's complexity does not depend on γ.Here γ is used only to state the stationarity condition.Source: §4.1 · pp. 8–9
4.2 First-order complexity
- The first-order method uses O(δ^-1 ε^-3) stochastic gradient queries, matching the noncomposite rate and its joint lower bound in δ and ε.The theorem's output is a (γ, δ, ε)-PGSP in expectation for every γ > 0.Source: §4.2 · pp. 9–10
4.3 Zeroth-order complexity
- The zeroth-order function-value complexity matches O(dδ^-1 ε^-3), improving on prior d^3/2 bounds with minibatch estimation and variance reduction.The stated rate is optimal individually in d, δ, and ε.Source: §4.3 · pp. 10–11
5 Smooth setting
For L1-smooth objectives, the section relates Goldstein-type stationarity to proximal-gradient stationarity and gives first- and zeroth-order guarantees. It also describes optimistic COMID, which uses a previous stochastic gradient as a hint.
5 Smooth setting
- For L1-smooth f, the proximal-gradient mapping is bounded by the Goldstein-type measure plus L1δ, linking the two stationarity notions.Combining this lemma with Theorem 4.4 at δ = ε/(2L1) gives O(ε⁻⁴) stochastic gradient query complexity.Source: §5 · p. 11
- Optimistic COMID uses the previous stochastic gradient as a hint, and its analysis does not require the oracle's second-moment bound.An independent stochastic gradient at the block's anchor initializes the hint; smoothness and the variance bound control the hint error.Source: §5 · p. 11
- Theorem 5.3 returns a point that is ε-stationary for every γ > 0, under the stated smoothness and oracle assumptions.The stationarity guarantee is expressed through the expected norm of the proximal-gradient mapping.Source: §5 · p. 11
- In the deterministic case, Theorem 5.3 uses O(L1∆/ε²) gradient queries; its σ²ε⁻⁴ dependence matches an unbiased bounded-variance oracle lower bound.The comparison to the lower bound applies even when h = 0.Source: §5 · p. 11
- Theorem 5.4 gives a zeroth-order query bound with dε⁻⁴ dependence for finding an ε-stationary point.The section states that this has the same dε⁻⁴ dependence as the smooth-composite bound of Ghadimi et al. (2016, Corollary 8).Source: §5 · pp. 11–12
6 Numerical experiments
The experiments compare Composite O2NC with two methods of Chen et al. on nonsmooth composite ReLU regression problems. Across three dimensions, Composite O2NC performs better on both stationarity and objective value for the same function-query count.
6 Numerical experiments
- Across d = 16, 256, and 1024, Composite O2NC outperforms both comparison methods in stationarity measure and composite objective value.The experiments use absolute loss for ReLU regression, with ℓ1 and ℓ2 regularization and box constraints; stationarity is evaluated using a numerical upper bound with δ = 0.01 and γ = 1.Source: §6 · pp. 12–13
- Figure 2 plots the stationarity measure, evaluated using a numerical upper bound with δ = 0.01 and γ = 1, and composite objective value against function-value queries; across all three dimensions, Composite O2NC outperforms other methods on both.Source: §6 · p. 13
AI use statement
The authors report using AI tools to assist with proof development and checking, literature searches, and editing, and state that they reviewed the AI-assisted work and take responsibility for the paper.
AI use statement
- The authors used GPT-5.5, GPT-5.6-Sol, GPT-6.1-Sol, and Claude Opus 5.5 for proof development and checking, literature searches, and editing.They state that they reviewed all AI-assisted work and take responsibility for the paper.Source: AI use statement · p. 13
A Deferred proofs of the regret bounds for COMID
The appendix section derives regret bounds for COMID and optimistic COMID, the learners used to generate update directions. Its proof setup applies COMID to linear losses with a regularizer over feasible directions and uses an independent gradient hint for optimistic COMID.
A Deferred proofs of the regret bounds for COMID
- The appendix derives regret bounds for COMID and optimistic COMID as mechanisms for generating update directions.The COMID proof instantiates online mirror descent over feasible directions with linear losses and a regularizer based on h.Source: A Deferred proofs of the regret bounds… · p. 18
- The optimistic COMID proof initializes its hint with an independent stochastic gradient at the block anchor and uses previous gradients as later hints.The proof bounds the difference using smoothness and the oracle's variance condition.Source: A Deferred proofs of the regret bounds… · pp. 18, 20
B Deferred proofs for Section 4
The deferred proofs establish bounds for composite gradient mappings and transfer a smoothed zeroth-order guarantee to the original objective. The comparison notes clarify how the smooth-case bounds relate to existing methods.
B Deferred proofs for Section 4
- The composite gradient mapping satisfies ∥Gγh(x, g)∥ ≤ ∥g + s∥ for every s ∈ ∂h(x).The proof uses the proximal operator's optimality condition.Source: B Deferred proofs for Section 4 · pp. 20–21
- A minimizer of the regularized linear model over the radius-D neighborhood yields a point whose composite gradient mapping is bounded by C_D(x, g).The proof uses a Lagrange multiplier for the neighborhood constraint.Source: B Deferred proofs for Section 4 · p. 21
- The zeroth-order proof approximates f by fρ, transfers the guarantee using the smoothing bound, and uses ρ + 2D = δ to obtain PGSP stationarity.The proof relies on |fρ(x) − f(x)| ≤ ρL0 and inclusion of the smoothed subdifferential in the original one.Source: B Deferred proofs for Section 4 · p. 22
C.1 Comparison with existing bounds
- Existing comparison bounds use their methods' specified step sizes, whereas the paper's bounds hold for every γ > 0.Mean-squared smoothness in the comparison is stronger than smoothness of f.Source: §C.1 · p. 22, Table 2 · p. 23
C.2 Deferred proofs
The deferred proofs establish the first-order oracle guarantee and the function-value guarantee by adapting the main theorem's proof to smoothed objectives. The latter proof accounts for gradient bias and charges two function evaluations per block step.
C.2 Deferred proofs
- The first-order proof combines the earlier lemmas and parameter choices to obtain E[∥Gγh(yR, ∇f(yR))∥] ≤ ε.Its parameter conditions include 6L1D = ε/2 and ∆/(DK) ≤ ε/4.Source: §C.2 · p. 23
- The function-value proof uses gradients of a smoothed objective, whose expectation equals the gradient of fρ, and bounds the smoothing error using L1-smoothness.Each block uses 2(T + 1) function-value queries.Source: §C.2 · pp. 23–24
- The zeroth-order argument applies the main theorem's proof with a two-point gradient estimate and the parameter choices specified for Theorem 5.4.It uses the gradient-bias bound to establish the target stationarity guarantee.Source: §C.2 · p. 24
D Relation between Moreau-envelope stationarity and PGSP
The section relates stationarity of a smoothed composite objective to proximal Goldstein stationarity for the original objective. It then uses this relation to transfer a Moreau-envelope guarantee to the PGSP criterion.
D Relation between Moreau-envelope stationarity and PGSP
- For the smoothed objective, the envelope stationarity measure is defined by ∥∇eγΦδ(x)∥ ≤ ε when 0 < γ < 1/Lδ.Here Φδ = fδ + h.Source: D Relation between Moreau-envelope… · p. 24
- Every ε-stationary point of Φδ in the Moreau-envelope sense is a (γ, δ, (1 + γLδ)ε)-PGSP of Φ = f + h.The argument uses the Lδ-weak convexity of Φδ and the optimality condition for the envelope minimizer.Source: D Relation between Moreau-envelope… · pp. 24–25
- The zeroth-order guarantee yields a (γ, δ, 3ε/2)-PGSP using the same number of function-value queries.The proof transfers the guarantee from the smoothed objective to the original objective.Source: D Relation between Moreau-envelope… · p. 25
E Experimental details
The experiments compare Composite O2NC with Chen et al.'s methods on ReLU regression and ramp loss, measuring stationarity and composite objective values. For ramp loss, Composite O2NC has lower mean objective values at all tested dimensions as optimization proceeds.
E Experimental details
- The ramp-loss experiments use n = 512 and dimensions d ∈ {16, 256, 1024}, with absolute loss for ReLU regression as the other test problem.Both sample losses are 1-Lipschitz, and the experiments use a common regularizer.Source: E Experimental details · pp. 25–26
- For ramp loss, labels are generated from sign(⟨ai, w̄⟩) and independently flipped with probability 0.1; each dataset remains fixed during optimization.Evaluation uses a numerical upper bound on the stationarity measure with γ = 1 and the composite objective value.Source: E Experimental details · p. 26
- For ramp loss, Composite O2NC has lower mean composite objective values than both Chen methods over optimization at d = 16, 256, and 1024.Its mean stationarity measure also becomes lower than both methods' as optimization proceeds.Source: Figure 3 · p. 26, E Experimental details · p. 27
- The online learner solves convex subproblems at each round, adding computational overhead compared with minibatch methods.The paper leaves reducing costs and tuning learning rates for practical use to future work.Source: E Experimental details · p. 27