Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity

arXiv:2610.12328 · cs.LG, math.OC, stat.ML · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity".

Tom: The gist The paper presents a novel framework called Composite O2NC that achieves optimal oracle complexity bounds for finding Goldstein-type stationary points in stochastic nonsmooth nonconvex composite optimization.

Jane: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper now called "Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity." It’s about finding these specific stationary points in problems that mix nonsmooth functions and convex regularizers, like those you see in constrained optimization or even training neural networks.

Jane: Exactly. The main thing they tackle is how to find a Goldstein-type stationary point when you have this composite objective function accessed through either stochastic gradients or just function values. It seems they're aiming for the best possible performance bounds that are known for this kind of problem setup.

Lu: What’s interesting about their approach is using what they call the online-to-nonconvex conversion framework, which is already known for getting good rates in noncomposite problems, but they adapt it here.

Meng: So, how do they actually handle the composite part? I'm thinking about those regularization terms that aren't just simple functions.

Tom: That’s where they introduce these new losses for the learner. Instead of just using the linearization of the regularizer, they give it a loss that includes the regularizer itself, specifically t(u) = g t, u + h(x + u) - h(x).

Jane: That part is key because it lets the algorithm account for the regularizer or constraint when it decides which direction to move. It seems like a clever way to integrate that extra structure into the learning process.

Lalam: From an AI perspective, this suggests that we can build learning algorithms that are inherently aware of structural constraints in the objective function, not just its surface locally.

Tom: And the results for first-order access are quite strong. They find a PGSP with O(delta-one epsilon-three) stochastic gradient queries, and they say this matches the optimal complexity for noncomposite nonsmooth nonconvex optimization, meaning the regularizer doesn't make things harder in terms of query count <ref:2610.12328#pg2>.

Jane: That’s good to hear. But they also have bounds for zeroth-order access. They claim you can find that same stationary point using O(d delta-one epsilon-three) function-value queries, where d is the dimension <ref:2610.12328#pg2>.

Lu: Wait, I read their Zeroth-Order bound and it seems to be linear in d. This is a significant improvement compared to some previous work that had a three-halves dependence on d.

Meng: Linear dependence on the dimension makes a huge difference for practical applications, especially when we’re dealing with high-dimensional neural networks where d can be very large.

Tom: Right. And they also have results for smooth settings, specifically when the function is L1-smooth. In that case, they get sharp bounds using optimistic online mirror descent to find an epsilon-stationary point of the objective.

Jane: That smooth setting result is also pretty clean. They show a rate of O(epsilon-two) for stochastic gradient queries in that specific scenario, which is what you'd expect when things are well-behaved locally.

Lu: I also saw that they connect this to Moreau-envelope stationarity, showing every epsilon-stationary point of delta in the Moreau-envelope sense is a (gamma, delta, (one plus gamma L delta) epsilon) -PGSP of the original objective <ref:2610.12328#pg2>.

Title and authors: Tom: That link through Proposition D.one is important because it bridges the gap between stationarity measures for different objectives and gives a concrete query count in the smooth case as O(dL 20L1 epsilon-four).

Jane: So, to summarize, this paper presents the Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity framework. It tackles composite optimization by using losses that include the regularizer directly, leading to optimal query bounds for both stochastic gradient and function-value access.

Lu: The implication for me is that we can design algorithms that are robust to these composite structures without needing complex linear approximations of the regularizer, which is a known weakness in other approaches.

Meng: From an engineering standpoint, the fact that the zeroth-order bound improves on previous work by achieving O(d delta-one epsilon-three) function-value queries is what matters for us when we have black-box models where we can only get evaluations <ref:2610.12328#pg2>.

Tom: It really shows that adding a convex regularizer to a nonsmooth function doesn't inherently destroy the optimal complexity scaling you already know for these types of problems.

Jane: So, before we wrap up, let's look at the specific improvements they highlight. They point out that their method handles composite objectives in constrained optimization, like one-regularized training for neural networks, using these optimal rates without needing to linearize the regularizer <ref:2610.12328#pg2>.

Lu: And they also show this works well for smooth composite optimization, getting O(epsilon-two) stochastic gradient queries when the function is L1-smooth. That’s a very tight bound for that class of problems.

Meng: I just want to make sure we nail the practical impact: they show this method outperforms other zeroth-order methods like Chen et al.'s work, specifically in terms of both the stationarity measure and the objective value when using function-value queries.

Tom: And finally, they give us a clearer picture of how their method relates to Moreau-envelope stationarity, which helps connect the theoretical guarantees to something more intuitive about how stationary points are defined for smoothed objectives.

Jane: So, in conclusion, this paper on Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity provides robust rates for finding Goldstein-type stationary points across different access models and smoothness assumptions. It’s a solid tool for tackling complex composite optimization problems out there.

Lalam: For me, the vision here is that we can start building AI systems that are inherently aware of these structural constraints in their learning process, leading to more efficient and constrained model training cycles overall.

Lu: I think the potential lies in how this framework allows us to apply these optimal rates directly when training very large models where the objective functions are inherently composite.

Meng: As an engineer, I see this as a way to make sure our optimization routines don't get bogged down by unnecessarily high query counts when we are dealing with those regularizers.

Tom: Yeah, that’s what it boils down to. This work on Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity gives us the optimal complexity bounds for finding these points in stochastic nonsmooth nonconvex composite optimization.

The paper's summary: Tom: So, this paper is about finding those specific stationary points in optimization problems that mix nonsmooth functions and those convex regularizer terms we talked about earlier.

Jane: Right, Tom, they’re tackling the problem of finding a Goldstein-type stationary point when you have these composite objectives that can be accessed through either gradients or just function values.

Lu: What they really did was introduce this new framework called Composite O2NC which converts online regret bounds into guarantees for those stationarity conditions.

Meng: I remember they talked about this framework using these new losses for the learner, which incorporate the regularizer itself instead of just linearizing it, and that’s a big deal because it avoids having to approximate the regularizer.

Tom: Exactly, because in other approaches you have to use those linearizations which can get messy when things aren't smooth.

Jane: And they show that this approach works for both first-order access, meaning using stochastic gradients, and zeroth-order access, meaning just using function values.

Lu: They achieved what they called optimal oracle complexity bounds for both scenarios, which is saying the rates are as good as they can possibly be in terms of how many queries you need.

Tom: That’s a huge point because when you add that regularizer on top of something already hard, you don't see a massive penalty in terms of query counts.

Jane: The zeroth-order bound, specifically, is interesting because it’s linear in the dimension d, which is much better than some previous results that had a three-halves dependence on d.

Meng: Linear dependence on the dimension means this method scales well when you are dealing with those huge models we use in AI today.

Tom: And they even have results for smooth settings, like when the function is L1-smooth, giving us sharp bounds for finding an epsilon-stationary point of that objective.

Jane: It’s clear this framework provides a robust way to solve these complex composite problems without relying on those potentially inaccurate linear approximations of the regularizer.

Lu: And they connect it to Moreau-envelope stationarity, which links the stationarity measures for different objectives together in a very specific way.

Tom: So, what does this mean for us practically? It means we can apply these optimal rates directly when training things like neural networks that have those composite structures without worrying about the complexity of linearizing every single term.

Jane: It’s a powerful tool for making sure our optimization routines are efficient even in these complicated composite settings.

Lu: And I think this opens up new ways to design learning algorithms that are inherently aware of these structural constraints in their objective functions, which could lead to more efficient and constrained model training cycles overall.

The paper's improvements: Tom: So, we’ve seen how they get those optimal complexity bounds for finding stationary points in these composite optimization problems, and now they’re pointing out what this work specifically improves on compared to other methods.

Jane: Right, Tom, it shows that their Composite O2NC method is really efficient across different access models like stochastic gradients and function values.

Lu: They highlight a few key improvements in the complexity numbers themselves, especially for zeroth-order access where they manage to get linear dependence on the dimension d instead of that three-halves scaling we saw in some older papers.

Meng: That linear scaling is what makes a huge difference for practical applications involving high-dimensional data, like those massive neural networks we’re training today.

Tom: And they also show that when the function itself is smooth, specifically L1-smooth, they can achieve very tight bounds for finding an epsilon-stationary point of the objective.

Jane: That smooth setting result gives us a rate of O(epsilon squared) for stochastic gradient queries, which is quite sharp and useful when things are behaving nicely.

Lu: They also emphasize that their method handles composite objectives in constrained optimization, like those L1-regularized training scenarios, without needing to linearize the regularizer.

Tom: That’s a big win because it means we can use these optimal rates directly even when dealing with those specific structures in neural network training.

Jane: So the main implication is that you get optimal query counts for composite problems even when you have to deal with nonsmooth parts and convex regularizers.

Meng: For me, this means less computational overhead on the optimization side, which translates to faster training cycles for those complex models we’re building.

Lu: Lalam thinks this opens up new ways for AI to be inherently aware of these structural constraints in their learning process, leading to more efficient and constrained model training cycles overall.

Conclusion: Tom: So, we’ve covered how they use the Composite O2NC framework to get optimal complexity bounds for finding Goldstein-type stationary points in those tricky composite optimization problems.

Jane: That’s right, Tom; it boils down to using new losses for the learner that include the regularizer directly, which works well for both stochastic gradients and function values.

Lu: The big picture is that this method proves you don't have to use complicated linear approximations of those regularizers just to solve these problems efficiently.

Meng: For us engineers, this means we can stick with the structure of our composite models and still get state-of-the-art query counts without adding extra layers of approximation.

Lalam: I see this as a way for AI culture to become more robust; algorithms that are inherently aware of structural constraints will lead to more reliable and less brittle AI systems.

Tom: And they’ve shown that the zeroth-order access bound is linear in dimension d, which is a very solid result for high-dimensional problems.

Jane: It really does change how we think about black-box optimization because we can predict the query count much more reliably than before.

Lu: The connection they made to Moreau-envelope stationarity is important because it ties these different types of stationarity guarantees together in a very clear mathematical way.

Meng: That’s a nice link; it gives us a clearer picture of what we are actually achieving in terms of the optimization goal itself.

Lalam: It suggests that the future of AI systems will involve optimizing for inherent structure rather than just chasing local gradients blindly across the whole landscape.

Tom: So, to wrap up, this paper on Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity gives us robust rates for finding those stationary points across different access models and smoothness assumptions.

Jane: It’s a powerful tool for tackling complex composite problems out there, Tom; it shows that adding a regularizer doesn't inherently destroy the optimal complexity scaling you already know.

Lu: We should keep watching how this framework inspires new ways to design learning algorithms that are inherently aware of these structural constraints in their objective functions.

cs.LG, math.OC, stat.ML

Submitted: 2026-10-08

Updated: 2026-10-08

Comments: 27 pages, 3 figures, 2 tables

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 89/100

The gist: The gist The paper presents a novel framework called Composite O2NC that achieves optimal oracle complexity bounds for finding Goldstein-type stationary points in stochastic nonsmooth nonconvex

Key concepts

Composite Optimization: This involves minimizing a sum of two parts: a possibly nonsmooth nonconvex function (like $f(x)$) and a convex regularizer (like $ ext{h}(x)$). It covers many important problems, including $\ell_1$-regularized optimization and constrained optimization, where the objective is $f(x) + h(x)$.
Goldstein-type Stationarity: This is a specific stationarity condition designed for composite objectives. Instead of just finding a point where the gradient is zero, it ensures that the objective function satisfies certain optimality criteria related to both the main function and its regularizer, guiding the search towards a good solution.
Composite O2NC Framework: This is a novel method that converts online regret bounds into guarantees for Goldstein stationarity. It achieves this by giving an online learner specific losses that include the regularizer itself, allowing the algorithm to effectively account for constraints or regularization terms during its decision-making process.
Oracle Complexity Bounds: These are the theoretical limits on how many queries (stochastic gradients or function evaluations) are needed to find a solution. The paper establishes optimal rates for both first-order and zeroth-order access, showing that the proposed method achieves these best possible theoretical limits.

Terminology

Regret — 16× in this paper · explained in 3 episodes
Query Complexity — 14× in this paper · explained in 2 episodes
Adam — 5× in this paper · explained in 2 episodes
Regularization — 2× in this paper · explained in 3 episodes
Computational overhead — 1× in this paper · explained in 2 episodes
Core — 1× in this paper · explained in 2 episodes
Inverse Problem — 1× in this paper · explained in 2 episodes

Summary

The gist The paper presents a novel framework called Composite O2NC that achieves optimal oracle complexity bounds for finding Goldstein-type stationary points in stochastic nonsmooth nonconvex composite optimization.

Problem Setting and Objective

The study considers stochastic nonsmooth nonconvex composite optimization, defined as minimizing the sum of a possibly nonsmooth nonconvex Lipschitz function and a convex regularizer, accessed through stochastic gradients or function values where x is the variable, f(x) is locally Lipschitz and may be nonconvex and nonsmooth, and h(x) is a proper closed convex function. Composite optimization encompasses important problem classes such as l1-regularized optimization, nuclearnorm-regularized optimization, and constrained optimization. The goal is to find a point that satisfies a Goldstein-type stationarity condition designed for composite objectives where x is the variable, f(x):= Eξ[F(x, ξ)], (1) where ξ is a random vector.

Composite O2NC Framework

The Composite O2NC framework converts online regret bounds into Goldstein stationarity guarantees by introducing new losses for the learner which contain the regularizer itself rather than its linearization. The learner is given the losses lt(u) = ⟨gt, u⟩ + h(x + u) − h(x), where x ∈ dom h is the current point. This loss allows the algorithm to account for the regularizer or constraint when choosing a direction. The algorithm runs K blocks of T rounds, and in each block k ∈ [K] the update is centered at an anchor xk where xk+1 = xk + uk,Ik.

Oracle Complexity Guarantees

The paper establishes optimal rates for both first-order and zeroth-order access to achieve PGSP guarantees.

First-Order Access:

For first-order access, the algorithm finds a PGSP with O(δ−1ε−3) stochastic gradient queries or O(dδ−1ε−3) function-value queries. This rate matches the optimal ones for noncomposite nonsmooth nonconvex optimization demonstrating that the additional convex regularizer does not worsen the oracle complexity.

Zeroth-Order Access:

For zeroth-order access, the resulting method finds such a point with O(dδ−1ε−3) function-value queries, where δ is the Goldstein radius, ε is the stationarity tolerance, and d is the dimension. This zeroth-order bound is linear in d, improving on the d 3/2 dependence of Chen et al. (2025).

Smooth Setting Results

When f is smooth, specifically L1-smooth, the framework yields sharp bounds for finding an ε-stationary point of Φ where x is the variable, f is L1-smooth, that is, ∥∇f(x)−∇f(y)∥ ≤ L1∥x−y∥ for all x, y ∈ R d. The deterministic case achieves O(ε−2) proximal-gradient rate using optimistic online mirror descent.

Experimental Validation

Numerical experiments validate the theoretical results on nonsmooth nonconvex composite problems using absolute loss for ReLU regression and ramp loss with various dimensions d ∈ 16, 256, and 1024. Composite O2NC outperforms other methods in terms of both the stationarity measure and the composite objective value. The results show that Composite O2NC attains smaller values of both the stationarity measure and the objective than the zeroth-order methods of Chen et al. (2025) for the same number of function-value queries.

Relation to Moreau-envelope Stationarity

The analysis shows that every ε-stationary point of Φδ in the Moreau-envelope sense is a (γ, δ,(1+γLδ)ε)-PGSP of the original objective Φ. This relationship is established through Proposition D.1 which links stationarity measures to PGSP guarantees for the smoothed objective. The resulting number of function-value queries is O(dL20L1∆ε−4) in the smooth setting, matching existing bounds.

Conclusion

The Composite O2NC method successfully converts online regret into proximal Goldstein stationarity guarantees for composite objectives, achieving optimal oracle complexity bounds for both stochastic gradient and function-value access. This framework is robust across different access models and objective smoothness assumptions, providing a powerful tool for solving complex composite optimization problems.

--- Page 1 ---

Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity with Optimal Oracle Complexity Mingyi Li∗ Taira Tsuchiya† Kenji Yamanishi‡ October 8, 2026 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 nonconvex 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. 1 Introduction We consider stochastic nonsmooth nonconvex composite optimization, min x∈Rd

How it works

The algorithm runs K blocks of T rounds, and in each block k ∈ [K] the update is centered at an anchor xk where xk+1 = xk + uk,Ik.
The online learner chooses a direction uk,t from UD(xk):= u ∈ R d: ∥u∥ ≤ D, xk + u ∈ dom h in each round t.
The algorithm then draws sk,t ∼ Unif[0, 1], sets yk,t = xk + sk,tuk,t, and queries gk,t = Q(yk,t) (Lines 5 and 6).
The algorithm gives the learner the convex loss in (5): lk,t(u) = ⟨gk,t, u⟩ + h(xk + u) − h(xk).

Complexity Bounds

The paper derives complexity bounds based on the analysis of local composite gaps and gradient estimation errors.

First-Order Access:

Theorem 4.4 shows that Algorithm 1 with the COMID learner of Theorem 4.1 and Q = Qfo outputs yR that is a (γ, δ, ε)-PGSP in expectation for every γ > 0, using O(∆(G+σ)2δe3) stochastic gradient queries. This bound matches the O(δ−1ε−3) complexity of Cutkosky et al. (2023) for h = 0.

Zeroth-Order Access:

Theorem 4.6 shows that Algorithm 1 with the COMID learner of Theorem 4.1 and Q = Qzo outputs yR that is a (γ, δ, ε)-PGSP in expectation for every γ > 0, using O(dL20L1∆δε3) function-value queries. This bound improves on the O(d 3/2 δ−1ε−4) and O(d 3/2 δ−1ε−3) complexities obtained by Chen et al. (2025).

Smooth Setting Results

In the smooth setting, Theorem 5.3 shows that Algorithm 1 with the optimistic COMID learner of Theorem 5.2 and Q = Qfo outputs a point yR that is an εstationary point of Φ for every γ > 0, using O(maxnL1∆ε2σ2ε4) stochastic gradient queries.

Improvements for AI systems

Smooth composite optimization in neural network training: The algorithm can find an ε-stationary point of Φ with a complexity of O(maxn L1∆ε squared, σ 2ε squared, L1∆σ 2ε 4) stochastic gradient queries when the function is L1-smooth.
Zeroth-order optimization for black-box problems: The system can find a (γ, δ, ε)-PGSP using function-value queries with a complexity of O(dL 20(∆ + δL0)δε 3), which improves upon existing bounds like those from Chen et al. (2025).
Handling composite objectives in constrained optimization: The system can solve problems involving both nonsmooth functions and convex regularizers, such as l1-regularized optimization, by achieving the optimal rates for Composite O2NC without relying on linearization of the regularizer.