Optimization

Proximal Gradient Methods

Split a smooth loss from a nonsmooth regularizer: gradient-step the smooth part, then apply the proximal operator of the rest.

Composite objectives

Many problems minimize f(x) + g(x) where f is smooth (a data-fitting loss) and g is convex but nonsmooth (a regularizer such as the L1 norm). Proximal gradient methods take a gradient step on f, then apply the proximal operator of g, handling the nonsmooth part exactly rather than through subgradients.

The proximal operator

Kronos motion — loss cone

prox_{a*g}(v) = argmin_x [ g(x) + (1/(2a)) ||x - v||^2 ]. It balances staying near v against reducing g. The update is x_{k+1} = prox_{a*g}(x_k - a * grad f(x_k)). For many important g the prox has a closed form, making the method as cheap as gradient descent.

Key examples

g = L1 norm: prox is soft-thresholding, giving ISTA for sparse regression (lasso).
g = indicator of a set: prox is projection, giving projected gradient descent.
g = L2 norm: prox is a shrinkage toward zero.
g = nuclear norm: prox is singular-value thresholding for low-rank recovery.

Acceleration: FISTA

Adding Nesterov momentum yields the fast iterative shrinkage-thresholding algorithm (FISTA), which improves the convergence rate from O(1/k) to O(1/k^2) for convex composite problems. FISTA is a standard solver for lasso and total-variation image reconstruction.

Why split

Handling the nonsmooth term through its proximal operator avoids the slow convergence and lack of exact sparsity of subgradient methods. The smooth part uses fast gradient steps while the prox enforces structure (sparsity, low rank, feasibility) exactly, combining the strengths of both.

python

def soft_threshold(v, t):
    return np.sign(v)*np.maximum(np.abs(v)-t, 0)
for _ in range(iters):
    x = soft_threshold(x - lr*grad_f(x), lr*lam)  # ISTA for lasso

Proximal methods deliver the sparse and low-rank solutions favored in signal reconstruction and regularized model fitting.