Optimization over Non-Smooth and Non-Convex Landscapes

948 concepts795 papers6 proposals

Imagine navigating a mountain range where the terrain alternates between perfectly smooth slopes, vertical cliffs, and jagged, unpredictable ridges. Standard gradient descent is like a hiker who only looks at the tilt of the ground directly beneath their boots. If the slope is smooth, they can easily find the valley. But if they step onto a sharp ridge or a flat plateau, their compass spins out of control: the gradient either becomes undefined, jumps discontinuously, or drops to zero, leaving them stranded far from the true minimum.

In classical optimization, we often assume that functions are both smooth (differentiable with Lipschitz continuous gradients) and convex. However, real-world applications routinely break these assumptions. Non-smoothness and non-convexity arise naturally across machine learning, economics, and engineering, necessitating a shift from standard calculus to robust, generalized optimization frameworks.

Why Smoothness Breaks Down

Non-smoothness typically occurs when an objective function incorporates discrete choices, hard constraints, or robustness criteria.

Consider three distinct scenarios where smoothness vanishes:

  1. Bilevel Optimization: In hierarchical problems where an upper-level objective depends on the optimal solution of a lower-level task, the presence of inequality or equality constraints in the lower level creates sharp corners in the upper-level objective. As shown by Siyuan Xu et al. in Efficient Gradient Approximation Method for Constrained Bilevel Optimization, standard gradient methods oscillate or stall at these points because the gradient is undefined.
  2. Economic Auctions: In second-price auctions, revenue functions are inherently discontinuous, characterized by flat regions (where small price changes do not affect the outcome) and sudden, vertical cliffs (where a bidder drops out). Lorenzo Croissant et al. demonstrate in Real-Time Optimisation for Online Learning in Auctions that these features prevent traditional solvers from computing reliable descent directions.
  3. Risk Management: Optimizing for worst-case scenarios or risk-averse metrics like Conditional Value-at-Risk (CVaR) introduces non-differentiable kinks where the objective switches focus from one bad outcome to another. As Bryan Wilder notes in Risk-Sensitive Submodular Optimization, these mathematical discontinuities leave standard optimization algorithms vulnerable to sub-optimal or highly unstable solutions.

To overcome these challenges, researchers have developed three core strategies: smoothing the landscape, redefining the derivative, or bypassing gradients entirely.

Strategy 1: Smoothing the Landscape

If a landscape is too jagged to navigate, the most intuitive solution is to blur the sharp edges, creating a differentiable surrogate function that can be optimized using standard first-order methods.

  Jagged Objective              Smoothed Surrogate
       /\    /\                     _..---.._
      /  \  /  \                 .-'         '-.
_____/    \/    \_____     _____/               \_____

One powerful approach is convolutional smoothing, which averages out discontinuities by convolving the objective function with a smoothing kernel. In Real-Time Optimisation for Online Learning in Auctions, the authors apply this technique to transform step-like revenue functions into smooth, differentiable curves, enabling real-time, constant-time gradient updates.

Alternatively, researchers use proximal operators like the Moreau envelope to approximate non-smooth functions. In Variable Smoothing for Weakly Convex Composite Functions, Axel Böhm introduces an algorithm that gradually refines this smooth approximation over time. By dynamically adjusting the smoothing parameter, the method balances the rapid convergence rates of smooth optimization with the structural accuracy required to find true feasible points.

Similarly, in large-scale engineering problems like power grid management, Shenyinying Tu leverages interior-point barrier formulations in A Two-Stage Decomposition Approach for AC Optimal Power Flow to smooth out the non-differentiable cost responses that occur when different physical constraints become active.

Strategy 2: Embracing the Kinks via Generalized Derivatives

When smoothing is computationally expensive or alters the problem structure undesirable ways, we must instead redefine what a "gradient" means at a non-differentiable point. Instead of a single derivative, we look at the set of all possible bounding slopes, known as the subdifferential.

             Subgradient Selection
                 \   |   /
                  \  |  /
                   \ | /
                    v v
                    /\
                   /  \
                  /    \

For non-convex, non-smooth functions, the standard convex subdifferential does not apply. Instead, algorithms rely on the Clarke subdifferential. In Efficient Gradient Approximation Method for Constrained Bilevel Optimization, the authors construct a Gradient Approximation Method (GAM) that samples a small set of representative gradients around a non-smooth point. By computing a convex combination of these gradients, the algorithm identifies a guaranteed descent direction even when the exact gradient is undefined.

For higher-order optimization, classical Newton methods fail without a well-defined Hessian matrix. To resolve this, Pham Duy Khanh et al. introduce generalized Newton methods in Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization. They utilize coderivatives of subgradient mappings—advanced tools from variational analysis that act as generalized Hessians—to achieve robust global convergence without requiring the objective function to be twice differentiable.

Furthermore, when optimizing across distributed networks, Hideaki Iiduka demonstrates in Parallel computing subgradient method for nonsmooth convex optimization over the intersection of fixed point sets of nonexpansive mappings how parallelized subgradient updates can successfully guide a system through non-differentiable constraint intersections.

Strategy 3: Bypassing Gradients Entirely

When calculating any form of derivative is impossible, too noisy, or computationally prohibitive, optimization must rely strictly on function evaluations, turning to zeroth-order oracles or global stochastic search.

In signSGD via Zeroth-Order Oracle, Sijia Liu et al. combine the gradient-free flexibility of zeroth-order optimization with sign-based stochastic gradient descent (ZO-signSGD). By estimating descent directions purely through localized function sampling, the algorithm bypasses the need for explicit gradients while maintaining the robustness required for non-smooth or constrained landscapes.

When the objective function is "approximately convex"—meaning it possesses a global convex structure but is corrupted by high-frequency noise, small local dips, or discontinuities—local search methods easily get trapped. Alexandre Belloni et al. solve this in Escaping the Local Minima via Simulated Annealing: Optimization of Approximately Convex Functions by pairing a Hit-and-Run sampling algorithm with Simulated Annealing. The random walks allow the solver to "jump over" small non-smooth bumps, proving that a global minimum can be found in polynomial time using only function evaluations.

          Simulated Annealing over Noise
               _.._       _.._
   Hops over  /    \     /    \   Global Descent
  ==>  o     /      \ o /      \     ===>
______/_\___/________/_\________\___________

Where classical calculus breaks down entirely, evolutionary heuristics offer a theoretically sound alternative. Chao Qian et al. show in Towards Theoretically Grounded Evolutionary Learning that evolutionary algorithms, when properly grounded in asymptotic analysis, provide provable approximation ratios for messy, non-differentiable machine learning objectives.

Finally, one can bypass optimization altogether by reframing the problem as a simulation. In An MCMC approach to classical estimation, Han Hong introduces Laplace Type Estimators (LTE), which transform an irregular, non-smooth frequentist criterion function into a "quasi-posterior" distribution. By using Markov Chain Monte Carlo (MCMC) sampling rather than numerical optimization, the framework completely avoids the local optima traps and gradient failures that plague traditional estimators.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_differentiable_objective_functions_n_2fa129ca,
  title = {non-differentiable objective functions (non-smooth objective optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-differentiable-objective-functions-non-smooth-objective-optimization/rdr_2fa129cab43a4333b53f99476c43c380},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_differentiable_objective_functions_n_2fa129ca_v1,
  title = {non-differentiable objective functions (non-smooth objective optimization)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-differentiable-objective-functions-non-smooth-objective-optimization/rdr_2fa129cab43a4333b53f99476c43c380/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake