In machine learning and continuous optimization, we often rely on a simple physical intuition: optimizing a function is like rolling a ball down a smooth bowl. If the bowl is smooth, the gradient tells us exactly which way is down, and its continuous variation allows us to build momentum, take large steps, and accelerate our descent.
However, many of the most important objectives in modern machine learning are not smooth. They contain sharp "kinks" or non-differentiable points. These arise naturally from $L_1$ regularization for sparsity, hinge losses in Max-Margin Markov Networks, or continuous relaxations of discrete problems via the Lovász extension (Stobbe et al.; Zhang et al. (2010)). At these kinks, a unique gradient does not exist. Instead, optimization algorithms must rely on subgradients—vectors that provide a global lower bound on the function but lack local directional continuity.
This lack of continuity introduces a severe computational bottleneck. Because subgradients do not vary continuously, they do not provide a reliable local descent direction. An algorithm taking a large step based on a subgradient can easily overshoot a kink, oscillating wildly. To guarantee convergence, traditional subgradient methods are forced to use diminishing step sizes, limiting them to slow, sublinear convergence rates (such as $O(1/\epsilon^2)$ or $O(1/\sqrt{k})$). Reaching high-precision solutions under these constraints becomes an expensive computational bottleneck.
Why Subgradients Fail to Scale
In smooth optimization, a standard recipe for scaling up to massive datasets is parallelization and mini-batching. If our gradient estimates are noisy, averaging them over a mini-batch reduces variance, allowing us to take larger steps and accelerate convergence.
Crucially, this recipe fails for nonsmooth problems. Duchi et al. demonstrated that traditional stochastic subgradient methods do not experience accelerated convergence from mini-batching or variance reduction. Because subgradients only provide a bounding hyperplane rather than a true descent direction, the convergence rate remains strictly bounded by the objective's Lipschitz constant and the total number of iterations. Mini-batching reduces the variance of the subgradient estimate, but it cannot fix the underlying discontinuity of the vector field.
This limitation creates a hard ceiling across many domains. Whether optimizing non-differentiable dual functions for real-time resource allocation in wireless networks (Fan et al.), solving multi-task feature learning problems (Liu et al.), or running distributed learning across multi-agent networks (Ying), standard subgradient schemes stall. Even in graph-based learning, Ameranis notes that nonsmooth hypergraph potentials restrict diffusion algorithms to sublinear rates, preventing them from achieving the rapid, logarithmic convergence seen in linear graph systems.
Mechanism 1: Smoothing and the Homotopy Strategy
If the primary bottleneck is the presence of sharp kinks, the most direct remedy is to smooth them out. By approximating a nonsmooth function with a mathematically smooth surrogate (for example, using Nesterov’s smoothing or Moreau envelopes), we can restore the continuity of the gradient field.
Gould et al. demonstrated the power of this approach by applying Nesterov's smoothing to dual decomposition for MAP inference. By transforming the nonsmooth dual objective into a smooth approximation, they accelerated the convergence rate quadratically from $O(1/\epsilon^2)$ to $O(1/\epsilon)$.
Nonsmooth Objective (with Kinks)
\ /
\/ <-- Subgradients oscillate here
Smoothed Surrogate (with Homotopy)
\ /
\_/ <-- Gradients vary continuously; parameter ε shrinks over time
However, static smoothing introduces a fundamental trade-off:
- If you smooth the function too aggressively, the surrogate is easy to optimize, but its minimum will deviate significantly from the true nonsmooth optimum.
- If you smooth too conservatively, the surrogate preserves the true optimum, but its gradients vary so rapidly near the kinks that the optimization landscape becomes highly ill-conditioned.
To bypass this trade-off, researchers use a homotopy strategy. Instead of picking a single smoothing parameter, the algorithm dynamically adjusts it. It begins with a highly smoothed objective to make rapid initial progress across the landscape. As the iterates approach the optimum, the algorithm gradually drives the smoothing parameter to zero, sharpening the function and tracking the moving optimum.
Yurtsever et al. leveraged this homotopy framework to achieve an optimal $O(1/\sqrt{k})$ rate for composite convex minimization while completely avoiding expensive projection steps. Similarly, Alacaoglu et al. integrated homotopy smoothing into coordinate descent (SMART-CD), preventing the quadratic complexity explosion that typically occurs when smoothing multi-variable systems. By managing the smoothing parameter across sequential, "warm-started" stages, the Homotopy Smoothing (HOPS) framework developed by Xu et al. (2016) breaks the traditional $O(1/\epsilon)$ barrier entirely, achieving a faster complexity of $\tilde{O}(1/\epsilon^{1-\theta})$ by exploiting the local geometry of the objective.
Mechanism 2: Exploiting Local Sharpness and Growth
The reason homotopy strategies and accelerated subgradient methods can break traditional complexity bounds is that practical nonsmooth functions are rarely uniformly flat. While they may lack global smoothness, they often possess favorable local geometry near their minimizers, characterized by "sharpness" or a "local growth condition."
Intuitively, if a function grows rapidly and steeply as you move away from the optimal solution, it behaves like a sharp V-shaped valley rather than a flat, wide basin. In a flat basin, a noisy or unaligned subgradient step leaves the algorithm wandering aimlessly. In a sharp valley, any step that moves away from the optimum experiences a massive increase in the objective value, providing a strong, corrective feedback signal.
Flat Local Geometry Sharp Local Geometry (Fast Growth)
\ / \ /
\___________/ \ /
(Slow convergence; \ / <-- Strong feedback pushes
subgradients stall) \_/ iterates back to optimum
Xu et al. (2017) proved that in stochastic convex optimization, global assumptions like strong convexity or smoothness are unnecessary for fast convergence. If the objective function satisfies a local growth condition around the optimal solution, accelerated stochastic subgradient methods can automatically exploit this geometry to achieve near-linear convergence rates.
This local geometry can also be used to dynamically tune the optimization algorithm itself. The Alternating Direction Method of Multipliers (ADMM) is highly effective for split optimization but is notoriously sensitive to its penalty parameter. Xu et al. (2017) introduced an adaptive penalization scheme that automatically adjusts this parameter based on the objective's local sharpness, allowing ADMM to converge significantly faster without requiring global smoothness.
When a problem naturally lacks this sharp local geometry, it can sometimes be explicitly engineered. For example, standard linear programming relaxations for MAP inference yield flat, nonsmooth dual objectives that suffer from sublinear convergence. Meshi et al. showed that by adding a quadratic $L_2$ regularization term directly to the objective, one can artificially inject strong convexity. This regularized landscape transforms the difficult nonsmooth dual into a smooth, well-conditioned problem that exhibits true linear convergence.
Mechanism 3: Primal-Dual Reformulations and Proximal Splitting
When direct smoothing or local geometry exploitation is unfeasible, a third powerful approach is to change the mathematical perspective entirely. Many nonsmooth objectives can be reframed as smooth saddle-point (min-max) problems via duality, or decoupled using proximal operators.
Consider a nonsmooth, low-rank matrix optimization problem. Directly optimizing this objective with subgradients is slow and requires expensive, full-rank singular value decompositions (SVDs) at every step. However, Kaplan et al. showed that by reformulating the problem as a smooth saddle-point problem and applying the extragradient method, one can achieve a fast $O(1/t)$ convergence rate. Crucially, this dual perspective allows the algorithm to operate using only cheap, low-rank SVDs, bypassing both the nonsmoothness and the computational overhead simultaneously.
For large-scale finite-sum problems, Song et al. introduced VRPDA$^2$, an algorithm that blends variance reduction with a primal-dual dual averaging framework. By tracking both primal and dual variables simultaneously, the algorithm cancels out the variance of the stochastic updates, making the optimization cost independent of the dataset size $n$ once a target accuracy is reached.
To handle complex structural constraints alongside nonsmoothness, researchers rely on proximal splitting. Instead of treating constraints and nonsmooth terms as barriers to be avoided via subgradients, proximal methods isolate them into localized, exact subproblems. Iiduka introduced incremental proximal point algorithms that stabilize iterations when optimizing nonsmooth functions under complex fixed-point constraints. Even in the highly challenging regime of nonconvex, nonsmooth optimization—where algorithms typically stall due to local minima and discontinuities—specialized proximal frameworks can restore optimal scaling. Yang et al. demonstrated that Projective Proximal Gradient Descent (PPGD) can optimize nonconvex, nonsmooth problems with the same $O(1/k^2)$ efficiency as smooth convex optimization, completely bypassing the need for restrictive assumptions like the Kurdyka-Łojasiewicz (KL) property.
Key Foundational Work
Multi-Task Feature Learning Via Efficient l2, 1-Norm Minimization (2009) — contributed 1 concept elements to this direction.
Accelerated dual decomposition for MAP inference (2010) — contributed 1 concept elements to this direction.
Complex Wavelet Regularization for Solving Inverse Problems in Remote Sensing (2009) — contributed 1 concept elements to this direction.