Smooth Approximations for Non-Smooth Optimization

18 concepts17 papers1 proposal

Standard gradient-based optimization relies on a simple geometric premise: if you can calculate the slope of a landscape, you can step downhill to find the minimum. However, many foundational problems in machine learning and image processing involve objective functions with sharp "kinks" or discontinuous steps where gradients do not exist.

Functions containing $L_1$ norms, Total Variation (TV) penalties, or indicator functions are notoriously difficult to optimize. While subgradient methods can navigate these landscapes, they are painfully slow, converging at a rate of $\mathcal{O}(1/\epsilon^2)$ compared to the much faster $\mathcal{O}(1/\sqrt{\epsilon})$ rate achievable on smooth landscapes.

The core intuition behind smooth approximation is simple: if we can mathematically "shave off" or "round out" the sharp corners of a non-smooth function, we can replace it with a closely matching differentiable surrogate. This allows us to deploy highly efficient, accelerated first-order optimization algorithms while maintaining strict, provable bounds on how far our approximate solution deviates from the true optimum.

The Geometry of Smoothing

To understand why smoothing works, consider the absolute value function $f(x) = |x|$, which has a sharp, non-differentiable corner at $x=0$. A subgradient algorithm reaching $x=0$ encounters an ambiguity of slopes, forcing it to take small, cautious steps.

We can smooth this function by adding a small, strongly convex regularization term to its dual formulation—a paradigm known as Nesterov's smoothing technique. Geometrically, this acts like a local filter that rounds out the sharp corner within a small neighborhood controlled by a smoothness parameter, $\mu$.

As explored by Ji et al. and Nam et al., this transformation yields a continuously differentiable function whose gradient is Lipschitz continuous. An alternative intuition, described by Wilder for submodular optimization, is to average gradients over a local neighborhood. This prevents optimization algorithms from becoming trapped at non-differentiable points where performance transitions are abrupt.

Non-Smooth Objective (Sharp Kink)       Smoothed Surrogate (Rounded Corner)
           \       /                                   \       /
            \     /                                     \     /
             \   /                                       \_ _/  <- Controlled by μ
              \_/                                          

This introduces a fundamental trade-off:

  • Large $\mu$: The surrogate function is highly smooth (low Lipschitz constant), allowing optimization algorithms to take large, aggressive steps and converge rapidly. However, the surrogate deviates significantly from the original function.
  • Small $\mu$: The surrogate tracks the original non-smooth function with high fidelity, but the landscape retains high curvature, forcing the optimizer to take smaller steps.

Handling Structural Non-Smoothness

Smoothing is rarely applied blindly; instead, it exploits the specific mathematical structure of the non-smooth terms in an objective function.

Total Variation and Sparsity

In image processing and network reconstruction, penalties like the $L_1$ norm or Total Variation (TV) are used to enforce sparsity or piecewise constancy. Weiss et al. and Fadili et al. demonstrate that smoothing TV norms allows complex image denoising and deblurring tasks to be solved using fast gradient-based schemes. Similarly, Luo et al. apply Nesterov's smoothing to handle joint TV and elastic net penalties, enabling the robust reconstruction of hidden network structures from highly limited data.

Minimax and Adversarial Learning

In minimax optimization (such as training Generative Adversarial Networks), the objective takes the form $\min_x \max_y f(x,y)$. The inner maximization phase often creates a non-smooth upper envelope. Tran-Dinh et al. and Qiu et al. use smoothing functions to approximate these non-smooth equations. This converts a challenging minimax problem into a tractable, differentiable one, allowing single-loop or trust-region gradient methods to proceed without getting stuck in the inner loop.

Discontinuous Indicators

When dealing with step transitions or indicator functions—such as in change-plane estimation—the objective function is not just non-smooth, but entirely discontinuous. Mukherjee et al. show that substituting these step functions with a smoothed continuous approximation restores the ability to compute gradients, making the estimation process computationally tractable while achieving near-optimal convergence rates.

Algorithmic Integration and Dynamic Tuning

Once a non-smooth problem is converted into a smooth surrogate, it can be integrated into powerful algorithmic frameworks.

Accelerated Dynamics and Splitting

Smoothed functions can be directly optimized using accelerated first-order methods. For instance, Zhao et al. couple smoothing with accelerated primal-dual mirror dynamics for centralized and distributed optimization. In splitting frameworks like the Alternating Direction Method of Multipliers (ADMM), Yuan shows that smoothing non-differentiable components allows gradient-based update rules to be applied to structured fractional minimization. For stochastic settings, Peña et al. demonstrate that a smooth lower approximation can transform computationally intractable projection steps into easily solvable unconstrained quadratic subproblems.

Excessive Gap Smoothing

To circumvent the trade-off of picking a fixed $\mu$, Tran-Dinh et al. utilize an "excessive gap smoothing" technique. Instead of keeping the smoothness parameter constant, the algorithm dynamically adjusts $\mu$ throughout the optimization process.

Early in the optimization, $\mu$ is kept large, smoothing out the landscape so the algorithm can make rapid progress toward the general region of the minimum. As the algorithm converges, $\mu$ is systematically decreased, "sharpening" the function back to its original form to ensure the final solution is highly accurate.

Iteration 1 (Large μ)        Iteration 50 (Medium μ)       Iteration 100 (Small μ)
       \_ _/                         \_/                           \_/
  (Rapid descent)             (Refining region)             (Exact convergence)

Why It Works: Theoretical Guarantees

A critical question remains: does optimizing a modified, smoothed function alter the original problem's solution?

Theoretical analyses confirm that smoothing preserves the essential geometric properties of the underlying function. Doikov establishes lower complexity bounds for regularized functions, proving that local smoothing maintains a quantifiable relationship to the original objective, ensuring that existing fast gradient methods remain optimal.

This mathematical consistency is so robust that it extends beyond standard vector spaces. In the context of stochastic control for complex Lévy processes, Noba et al. demonstrate that one can construct a sequence of smooth cost functions that converge uniformly to a non-smooth running cost. By proving that an optimal control strategy holds for the smooth approximations, they show that this optimality naturally transfers to the original non-smooth problem in the limit.

Key Foundational Work

Efficient Schemes for Total Variation Minimization Under Constraints in Image Processing (2009) — contributed 1 concept elements to this direction.
First-Order Algorithm with O(ln(1/ε)) Convergence for ε-Equilibrium in Two-Person Zero-Sum Games (2008) — contributed 1 concept elements to this direction.
Multi-label Multiple Kernel Learning (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_smooth_approximation_d6b61103,
  title = {smooth approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/smooth-approximation/rdr_d6b6110357694aeabd668814a254dd79},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_smooth_approximation_d6b61103_v1,
  title = {smooth approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/smooth-approximation/rdr_d6b6110357694aeabd668814a254dd79/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake