# Nonsmooth Optimization

Optimising objectives with kinks or discontinuous gradients, where classical descent assumptions fail and subgradients or specialised operators are needed.

**Rests on:** Convex Optimization, Gradient Descent

**Leads to:** Proximal Gradient Methods

*Mathematical Foundations · Optimization*


## Why learn this

You have likely encountered situations where you need to find the best solution among many possibilities, but the rules for judging 'best' involve sharp corners or sudden changes in behavior. Standard methods fail here because they assume the path to the best answer is a smooth slide. Without this knowledge, you cannot solve problems where you want to force certain answers to be exactly zero (like filtering out irrelevant noise) or when the cost function has abrupt shifts. Mastering this lets you handle those sharp corners directly, ensuring your solutions are robust and accurate even when the underlying data or rules are not smooth.


## The intuition

Imagine you are trying to find the lowest point in a mountain range, but you can only walk by feeling the ground under your feet. If the ground is smooth, you can always tell which direction goes downhill. But what if you hit a ridge or a sharp crease in the rock? At that exact line, the ground is not smooth—it changes direction abruptly. You cannot say 'the slope here is exactly this' because the slope is different on each side. You can still make progress: you know that any direction that goes downhill is fine, even if there is no single 'steepest' direction. This is the core of nonsmooth optimisation: when the objective has sharp corners (kinks) or jumps, you cannot rely on the usual concept of a slope (the derivative), because it simply does not exist at those points. Instead, you use a generalised notion—the subgradient—which is any direction that falls no slower than the function itself. You then step in a direction that, while not uniquely 'steepest', is guaranteed to reduce the objective. This is what allows optimisation to continue even at the kinks. In machine learning, these kinks appear all the time: adding a penalty for the size of your variables (using absolute values) creates a sharp corner at zero, and measuring error in certain ways creates corners where the prediction just meets or misses a target. Ignoring these kinks means your algorithm gets stuck or misbehaves exactly at the points that matter most.


## An analogy

Think of a delivery driver navigating a city grid with a long rectangular block of buildings in the centre. The driver's goal is to find the fastest route (minimise travel time). On the smooth streets, the driver can tell exactly which turn is 'downhill' in terms of time. But the central block has a sharp corner—the intersection of two one-way streets. At that corner, the 'slope' of time is not defined: coming from one direction, the best way is to turn left; coming from another, it is to turn right. The driver does not stop and panic; instead, they pick any direction that is not worse. In optimisation terms, the driver uses a 'subgradient'—any direction that does not increase the objective (or at least, does so at a rate no worse than linear). The driver also uses a trick: they can 'clip' or 'round' the corner to make it smooth enough to navigate with normal methods, accepting a small trade-off in precision. But this analogy breaks down when the kinks are not physical corners but mathematical discontinuities—like when the objective jumps from one value to another with a gap. No driver can handle a jump, and neither can a plain gradient method; you need specialised operators that look at the function from both sides.


## Definition

Nonsmooth optimisation is the process of minimising an objective function that has points where the derivative does not exist (kinks or discontinuities), requiring generalised notions like subgradients or smoothing techniques to make progress.


## How it connects

You have studied Gradient Descent, where the algorithm relies on the smooth slope (derivative) to step downhill. That works beautifully when the loss is smooth, like a quadratic. But your library notes on Convex Optimization and Proximal Gradient Methods hint at the fact that many real-world objectives are not smooth. This concept fills that gap: it tells you what to do when the derivative does not exist. It also connects to your notes on Least Squares Regression: the plain least-squares loss is smooth, but when you add an L1 penalty (as in LASSO), the objective becomes nonsmooth at the point where any coefficient is exactly zero, which is exactly where sparsity happens. So this is the mathematical foundation for why L1 regularisation creates zeros in a way that L2 (smooth) does not.


## The mathematics

You are used to finding the bottom of a smooth valley by looking at the slope. If the ground slopes down to the left, you step left. If it slopes down to the right, you step right. This works because the slope is a single, clear number at every point.

But some functions have sharp corners, or "kinks," where the slope suddenly changes. A simple example is the absolute value function, written as f(x) = |x|. Imagine a V-shape sitting on a graph. The bottom of the V is at x = 0. 

If you are standing anywhere to the right of zero (for example, at x = 2), the ground slopes down to the left with a steady steepness of -1. You can calculate this slope easily. If you are standing anywhere to the left of zero (for example, at x = -2), the ground slopes up to the right with a steepness of +1. 

The problem is exactly at the bottom, at x = 0. There is no single slope here. Coming from the right, the slope was -1. Coming from the left, the slope was +1. The standard rule for calculus says the slope "does not exist" at this point. This breaks the usual optimization method because it tells you to look at the slope to decide which way to step, but there is no single number to look at.

Nonsmooth optimization solves this by widening the definition of "slope." Instead of asking for one specific tangent line, we ask: "What are all the possible slopes of lines that pass through this point and stay below or on the function?"

For a convex function (a function shaped like a bowl or a V), these valid slopes form a range. At the kink of |x| at x=0, any slope between -1 and +1 is valid. Why? Because if you draw a line through the bottom point with any steepness between -1 and +1, that line will never go above the V-shape of the function. This entire range of numbers is called the "subdifferential" at that point. Any single number chosen from this range is called a "subgradient."

The optimization algorithm works just like before, but with a small change in step selection:
1. You are at a current position x_k.
2. You look for the subdifferential (the range of valid slopes) at that point.
3. If there is only one slope (you are on a smooth part), you use it. 
4. If there is a range of slopes (you are at a kink), you can pick any number from that range. A common and safe choice is 0, because it means "I am at the bottom, do not move."
5. You take a step in the opposite direction of your chosen subgradient.

This method guarantees that you will not climb uphill. If you pick a subgradient that points downhill, you move down. If you pick a subgradient of 0 at the bottom, you stay put. This allows us to handle sharp corners without the algorithm breaking.


## A worked example

Let us walk through minimizing the function f(x) = |x| using this method. We start at x = 2. We will use a step size (how far we move each time) of 1.

Step 1: Start at x_0 = 2.
At x = 2, we are on the right side of the V-shape. The function is just f(x) = x. The slope here is clearly +1. Because there is only one valid slope, the subgradient g_0 is 1.

Step 2: Calculate the next position.
The rule is: new position = old position - (step size * subgradient).
So, x_1 = 2 - (1 * 1) = 1.
We have moved from 2 to 1. The function value dropped from 2 to 1.

Step 3: Move to x_1 = 1.
At x = 1, we are still on the right side of the V-shape. The slope is still +1. The subgradient g_1 is 1.
Calculate the next position:
x_2 = 1 - (1 * 1) = 0.
We have moved from 1 to 0. The function value dropped from 1 to 0.

Step 4: Arrive at x_2 = 0.
At x = 0, we are at the kink. As explained above, any slope between -1 and +1 is valid. We need to pick one subgradient g_2 from this range [-1, 1]. 
A standard choice at the minimum of a convex function is 0, because it indicates that no further descent is possible. So we choose g_2 = 0.
Calculate the next position:
x_3 = 0 - (1 * 0) = 0.
We stay at 0.

Step 5: Check for convergence.
Since our new position is the same as our old position, the algorithm has stopped. We have found the minimum at x = 0 with a function value of 0.

Note: If we had chosen a different subgradient at step 4, say g_2 = 0.5, we would have moved to x_3 = -0.5. At x = -0.5, the slope is -1. We would then step back to x_4 = 0.5. The algorithm might oscillate around the kink if we do not reduce the step size over time, but it will stay close to the minimum. Using a subgradient of 0 stops this oscillation immediately.


## From scratch, in Python

```python
# Plain Python: subgradient descent on |x|, starting at x=5

def subgradient(x):
    # The subgradient of |x|: +1 if x > 0, -1 if x < 0, any between -1 and 1 at x=0
    if x > 0:
        return 1.0
    elif x < 0:
        return -1.0
    else:
        return 0.0  # a valid choice for the subgradient at the kink

# Parameters
x = 5.0  # starting point
alpha = 0.5  # step size
num_steps = 10

# Loop over iterations
for i in range(num_steps):
    g = subgradient(x)
    x = x - alpha * g  # step opposite to the subgradient
    print(f"Step {i+1}: x = {x:.4f}, subgradient = {g:.2f}")

print(f"Final x after {num_steps} steps: {x:.4f}")
```


## The same thing, with a framework

```python
In NumPy, you rarely need to implement subgradients by hand for simple cases—optimisers like scipy.optimize.minimize handle them. Here is a snippet using scipy.optimize with a nonsmooth objective:

import numpy as np
from scipy.optimize import minimize

# Define the nonsmooth objective: L1-norm of a vector x
def objective(x):
    return np.sum(np.abs(x))

# Starting point
x0 = np.array([1.5, -2.5, 0.5])

# Use a method that can handle nonsmoothness (e.g., 'Powell' or 'Nelder-Mead')
result = minimize(objective, x0, method='Nelder-Mead')

print('Optimal x:', result.x)
print('Minimum value:', result.fun)

Under the hood, methods like Nelder-Mead do not use gradients at all; they sample the function at multiple points. For subgradient-based methods, you would need a custom implementation like the one above, or use libraries like cvxpy that recognise sparse/nonsmooth penalties and apply appropriate algorithms. In deep learning, PyTorch's optimisers (e.g., SGD, Adam) are designed for smooth objectives; for nonsmooth ones, you can clip gradients or use proximal methods, but that is beyond this page.
```


## What the code does

First, we define a function subgradient(x) that returns a valid subgradient for |x|. For positive x, the slope is 1; for negative x, it's -1; at zero, we choose 0 (any value between -1 and 1 works). Then we set the starting point x=5 and a step size alpha=0.5. The loop runs 10 times: each iteration calls subgradient(x) to get the direction, then updates x by subtracting alpha times that direction, which moves downhill. The print statement shows the progress. You will see that after a few steps, x converges to 0, even though at the last step the subgradient is 0, so no more movement happens. This is the essence of subgradient descent: it works at kinks by picking a valid direction, and it can converge to the minimum even when the derivative does not exist.


## Common misconceptions

**Subgradient is the same as a derivative** — I thought a subgradient is just a derivative that might not exist, so I just use the derivative when it exists and ignore the rest.

A derivative is a unique slope; a subgradient is a whole set of slopes that satisfy a certain property. At a kink, there are infinitely many subgradients, and a derivative does not exist. Using a one-sided derivative would only be one possible choice, and it could mislead the optimisation. In fact: A subgradient is a generalisation: if the function is smooth, the subgradient set contains only the derivative. At a kink, the set is an interval, and any element works for descent, but not all are equally safe.

**Nonsmooth means the objective is not continuous** — I thought nonsmooth and discontinuous are the same, so a step function would be optimised the same way as an L1 penalty.

A function can be continuous but have a sharp corner (like |x|). That is nonsmooth but continuous. A step function has a jump, which is a discontinuity. The mathematical tools are different: subgradients work for continuous nonsmooth functions; discontinuous functions require more exotic approaches like proximal operators or mixed-integer methods. In fact: Nonsmoothness is about lack of differentiability, not lack of continuity. The absolute value function is continuous everywhere but non-differentiable at zero; that is the classic nonsmooth case.

**Gradient descent works fine if I just ignore the kink** — I can just use gradient descent and hope it passes through the kink; the derivative error is small.

At the kink, the gradient is undefined, and the algorithm may oscillate or get stuck. For example, in subgradient descent on |x|, if you use +1 every time near zero, you will bounce around zero and never exactly land on it, depending on the step size. Ignoring the kink means you are not using the right search direction. In fact: You need to either use a subgradient (any valid one) or smooth the kink (e.g., Huber) to get stable convergence. Proximal methods are the standard fix for L1 penalties.

**L1 regularisation is hard because it's discontinuous** — I thought L1 regularisation makes the loss discontinuous, so it's impossible to optimise.

The L1 norm is continuous—it's the sum of absolute values, which are continuous (just not differentiable at zero). So the loss is continuous, but non-differentiable at points where any coefficient is zero. It is optimisable with subgradient or proximal methods. In fact: L1 is continuous but nonsmooth. The kinks are exactly what drive coefficients to zero, which is the desired sparsity. Algorithms like ADMM or proximal gradient handle this well.

**The subgradient is always unique at a non-smooth point** — At a kink, I thought there is exactly one best 'slope' to use, so I just pick the average of the left and right slopes.

The subgradient set is often an interval: any slope between the left and right derivatives is valid. The average is one valid choice, but not necessarily the best for descent; the choice can affect the trajectory. In fact: You have freedom to pick any subgradient in the set. In practice, you might pick the one with the smallest norm (which gives the steepest descent among valid directions), or a specific one like the left derivative, depending on the algorithm.


## In short

Nonsmooth optimisation deals with objectives that have kinks or discontinuities, where the derivative does not exist. The central tool is the subgradient, a set of slopes that generalises the derivative. Subgradient descent steps opposite to any valid subgradient and converges, albeit often slower than gradient descent on smooth problems. In machine learning, L1 penalties and hinge losses are the common nonsmooth cases; they are handled with proximal operators or smoothing (like the Huber function). This is the foundation for sparse models and robust losses.


## Where this is used

In large language models, training objectives are typically smooth, but techniques like weight decay and L1 regularisation (when used) introduce nonsmoothness. For example, L1 regularisation on weights is used to encourage sparsity in certain components, which can help with pruning and efficiency. The kink at zero is where weights become exactly zero, and without proper handling, gradient descent would oscillate around that point. In practice, frameworks like PyTorch implement a proximal step for L1 that effectively 'clips' the weights, which is a nonsmooth optimisation technique. In small models running on devices (TinyML), L1 regularisation is common to compress models; the same proximal step is used. In retrieval-augmented generation, the embedding vectors are often L2-normalised (smooth), but the similarity search may use L1 distances (Manhattan distance), which is nonsmooth. The search algorithm itself is not optimised via gradients—it is a nearest-neighbour problem—but understanding nonsmoothness helps when tuning the loss functions that train the embeddings, some of which use triplet losses with margin (which can have kinks). In agentic systems, planning often involves discrete decisions (which tool to call), which are inherently nonsmooth: the objective (task success) is a step function. Optimising such objectives requires gradient-free or subgradient-like methods, or smoothing the objective through techniques like soft-argmax. In everyday applied machine learning, the hinge loss (used in SVMs) is the classic nonsmooth loss. The derivative is zero when the margin is satisfied and a constant otherwise; the kink is at the margin boundary. This requires special handling in training: either subgradient descent or a smoothed version (like the squared hinge or the Huber loss). The Huber loss is a smoothed version of the absolute error, which has a kink at zero; it is used in robust regression to reduce the influence of outliers while remaining differentiable. In forecasting, the pinball loss for quantile regression is also nonsmooth; it has a kink at zero, and training requires subgradient methods. In fraud detection, many models use L1 regularisation to select important features, relying on proximal gradient methods to handle the nonsmoothness. A developer working with these models writes code like: model = LogisticRegression(penalty='l1', solver='saga') in scikit-learn, where the solver 'saga' is a stochastic average gradient algorithm that handles L1 nonsmoothness via proximal steps. If they were to use a plain gradient descent with an L1 penalty, they would see the weights never settle exactly at zero, and the loss would oscillate. The proximal operator is the key: it applies a soft-thresholding step, setting small weights to zero, which is the nonsmooth analogue of a gradient step.


---

Read this on the web: https://basavapurushottam.com/learn-ai/nonsmooth-optimization
