Online-to-Nonconvex Conversion Framework Cracks the Optimal Complexity Challenge in Composite Optimization

Stochastic nonsmooth nonconvex composite optimization is a broad class of problems in machine learning—constrained training, regularized neural networks, sparse learning, and more all fall under this framework. Its objective function consists of two parts: a potentially nonsmooth nonconvex Lipschitz function and a convex regularizer. The former is typically accessible only through stochastic gradients or function values, while the latter possesses favorable convex structure.

For a long time, there has been a gap in oracle complexity analysis for such composite problems. According to the paper, under first-order access (stochastic gradients), no known complexity upper bound existed previously; and under zeroth-order access (function values), existing complexity results were not optimal. This means that when we train neural networks or solve constrained optimization using regularization methods, we theoretically do not know how many queries are needed to guarantee finding a stable point that satisfies the required conditions.

Why Composite Optimization Is Harder to Analyze

Nonsmooth nonconvex optimization is itself a tough nut to crack. Classical nonconvex optimization typically seeks points where the gradient is zero, but when the function is nondifferentiable, the concept of gradient must be replaced by more generalized stationarity conditions. For composite objective functions, one must additionally consider how the structure of the regularizer interacts with the stationarity condition.

A natural approach is to decompose the composite problem: compute gradients for the nonconvex part, and use subgradients or proximal operators for the convex regularizer. However, this decomposition introduces additional error terms in complexity analysis, leading to final complexity worse than the non-composite case. Previous zeroth-order results suffered precisely from this issue, with complexity exhibiting less favorable dependence on dimensionality and accuracy.

Goldstein Stationarity Condition: For differentiable nonconvex functions, the commonly used stationarity condition is that the gradient norm is less than ε; but for nonsmooth or composite functions, the gradient may not exist or may not be available, requiring a more relaxed stationarity condition. The Goldstein stationarity condition (also known as the Goldstein condition) requires that within a neighborhood of some radius δ, the lower bound of gradient norms at all points and the function value decrease satisfy a certain inequality; intuitively, it guarantees that near the current point, there is no direction that can make the function value decrease continuously and significantly. When δ ranges over all possible radii, if a point satisfies this condition, it must be a local minimum. In first-order stochastic optimization, since gradients cannot be computed exactly, one typically adopts stochastic Goldstein stationarity as the convergence target, and the introduction of δ is precisely to handle gradient estimation noise.

Proximal Operator and Subgradient: For composite objectives f(x)+h(x) (f nonsmooth nonconvex, h convex), when h is nondifferentiable (e.g., L1 regularization), gradient descent cannot be directly applied. The proximal operator is defined as prox_{ηh}(v) = argmin_x { h(x) + (1/(2η))||x-v||^2 }, which amounts to performing one step of implicit gradient descent on h at point v, without requiring h to be differentiable. The subgradient is a generalization of the gradient for convex functions at nondifferentiable points, satisfying f(y) ≥ f(x) + g^T(y-x). For nonconvex f, the subgradient may not exist or may not be unique, so analysis often uses smoothing or stochastic gradients for f, and proximal operators or subgradients for convex h. Although this hybrid approach is intuitive, it introduces additional bias terms in complexity analysis, leading to worse final rates.

A Unified Algorithmic Framework from the Online Learning Perspective

The core tool adopted in the paper is the online-to-nonconvex conversion framework. This framework was originally designed for non-composite problems, with the idea of viewing the optimization process as an online learning problem: at each step, an online learner selects an update direction, and a theoretical connection exists between the learner's cumulative regret and the quality of the final stable point.

The key to extending this framework to composite settings lies in designing a new loss function for the learner. The authors' approach is quite ingenious: the new loss function directly incorporates the regularizer itself, rather than its linearized approximation. The advantage is that it preserves the complete convex structure information of the regularizer, enabling a variant of online mirror descent to achieve low regret.

This modification transforms the convexity of the regularizer from "an object requiring extra handling" into "a resource that helps control regret," thereby avoiding complexity degradation.

Online Mirror Descent and Regret: Online mirror descent (OMD) is an online learning algorithm that uses Bregman divergence as a distance measure, minimizing instantaneous loss at each step while staying close to the current decision. For a convex, Lipschitz-continuous online loss sequence, OMD can guarantee a cumulative regret upper bound of O(√T) or O(log T), depending on the properties of the loss function and step size selection. In the online-to-nonconvex conversion framework, regret directly corresponds to the quality of the final stable point: if the online learner can guarantee low regret, then through appropriate conversion, one can obtain convergence rates for stationarity conditions in nonconvex optimization. Therefore, designing a low-regret online learner becomes key, and placing the regularizer h(x) directly into the loss function rather than linearizing it is precisely exploiting the convexity of h to construct tighter regret bounds.

Optimal Oracle Complexity and Experimental Validation

The paper provides two types of complexity results. Under first-order access (stochastic gradient queries), the number of queries required for the algorithm to find a point satisfying the Goldstein-type stationarity condition is O(δ⁻¹ε⁻³), where δ is the Goldstein radius and ε is the stationarity tolerance. Under zeroth-order access (function value queries), the complexity is O(dδ⁻¹ε⁻³), where d is the problem dimension.

These two results are completely consistent with the optimal complexity for non-composite nonsmooth nonconvex optimization problems, demonstrating that the additional convex regularizer does not worsen the oracle complexity. The paper also provides corresponding rates for the smooth case and validates the theoretical results through numerical experiments.

First-order and Zeroth-order Oracle Complexity: Oracle complexity measures the number of queries an algorithm needs to achieve a certain accuracy. A first-order oracle allows querying the stochastic gradient of the function at any point, while a zeroth-order oracle only allows querying function values (typically estimating gradients through finite differences). In nonconvex optimization, the goal is usually to find an ε-stationary point, i.e., a point where the gradient norm or stationarity condition is at most ε. For nonsmooth nonconvex problems, the known optimal first-order complexity is O(ε^{-3}), and zeroth-order complexity is O(d ε^{-3}). In the composite setting of this paper, the additionally introduced Goldstein radius δ appears in the complexity as O(δ^{-1} ε^{-3}), because stochastic gradient noise requires a smaller δ to guarantee stationarity quality. When δ is fixed, this complexity exactly matches the non-composite case, indicating that the convex regularizer incurs no additional burden.

Theoretical Significance and Practical Implications

This work fills a theoretical gap in oracle complexity for composite nonconvex optimization. From a practical perspective, it sends a positive signal: commonly used regularization strategies—whether L1, L2, or more general convex penalties—are "free" at the complexity level, and will not make the optimization problem fundamentally harder to solve. For scenarios relying on regularized training of large-scale models, this provides a more solid theoretical foundation for algorithm design.

Of course, the paper's results are in the sense of asymptotic complexity, and constant factors and actual convergence rates still need further evaluation through experiments. There remains room worth exploring between theory and engineering implementation.

One-line Summary

The paper provides the first optimal oracle complexity for composite nonsmooth nonconvex optimization under both first-order and zeroth-order access, proving that convex regularizers do not worsen complexity.

Paragraph Summary

This paper studies stochastic nonsmooth nonconvex composite optimization, where the objective consists of a nonconvex Lipschitz function and a convex regularizer. Previously, no complexity upper bound was known under first-order access, and zeroth-order results were not optimal. The authors adopt the online-to-nonconvex conversion framework, designing a new loss function that incorporates the regularizer itself, and leveraging an online mirror descent variant to achieve low regret, thereby avoiding complexity degradation. The resulting first-order complexity O(δ⁻¹ε⁻³) and zeroth-order complexity O(dδ⁻¹ε⁻³) match the optimal rates for non-composite problems. Numerical experiments validate the theoretical results. This work fills a theoretical gap and shows that commonly used regularization strategies are "free" at the complexity level.