Are proximal algorithms only for nonsmooth functions?

No. They can also be useful for smooth or poorly conditioned problems.

Is projected gradient a proximal algorithm?

Yes, through the indicator-function representation of a constraint set.

Does a proximal operator always have a closed formula?

No. Some require numerical solution, which affects the algorithm's cost.

AI Glossary / Mathematics and optimization / Advanced

Proximal algorithm

Definition

A proximal algorithm is an optimization method built around proximal operators, which balance reducing a function against staying near a supplied point. These methods can handle useful nonsmooth terms and constraints without pretending that every part of the objective has an ordinary derivative. Proximal point and proximal gradient methods are important examples within this broader family.

What it means

Many learning objectives combine a smooth data-fitting term with a penalty or constraint that is easier to handle through its own specialized operation. A proximal algorithm takes advantage of that structure rather than forcing the entire problem into one undifferentiated update.

The word “proximal” refers to the quadratic preference for proximity inside the operator's subproblem. It does not mean nearest-neighbor learning. Nor does it identify one universal update rule: different proximal algorithms use different splittings, auxiliary variables, and convergence conditions.

How it works

For a function g and a positive scale η, its proximal operator at v minimizes g(u) + ||u − v||²/(2η). Under the usual closed, proper, convex assumptions, this minimizer is unique.

Proximal gradient addresses an objective f + g where f is smooth. It first takes a gradient step on f, producing v = w − η∇f(w), and then applies the proximal operator of ηg to v. The nonsmooth part is handled by a minimization operation rather than an ordinary gradient at a corner.

Proximal point instead applies the proximal operator of the full objective repeatedly. Other splitting methods organize several such operations. Convergence statements depend on the chosen method, existence of a solution, step sizes, and accuracy of subproblem solutions. An easy-to-write proximal subproblem is not necessarily inexpensive to solve.

Three practical examples

1. Sparse regression: combine a smooth squared-error loss with an L1 penalty handled by soft thresholding.

2. Constrained learning: encode a closed convex constraint set through its indicator function so that the proximal step becomes projection.

3. Signal restoration: separate a data-fidelity term from a structured regularizer, using an appropriate proximal or splitting method for the resulting objective.

Think of it this way

Think of revising a draft by balancing a requested improvement with a preference to keep the revision close to the current version. Different kinds of improvement may need different editing operations. The analogy is limited: a proximal step solves a precisely defined mathematical subproblem, and “close” normally means a specified squared Euclidean distance rather than an informal similarity judgment.

Worked example

Consider minimizing F(a, b) = ((a − 3)² + (b + 0.5)²)/2 + |a| + |b|. Split it into a smooth squared-error term f and an L1 penalty g. Start at (0, 0) with step size η = 0.5.

The first gradient of f is (−3, 0.5), so the proposed point is (1.5, −0.25). The proximal operation for ηg soft-thresholds each coordinate at 0.5: reduce its magnitude by 0.5, stopping at zero. The first iterate is therefore (1, 0).

The next gradient proposal is (2, −0.25), giving the second iterate (1.5, 0). A third iteration gives (1.75, 0). The first coordinate approaches 2, while the second remains exactly zero.

The objective begins at 4.625. At (1, 0) it is 3.125; at (1.5, 0), 2.75; and at the optimum (2, 0), 2.625. For the positive first coordinate, the stationary equation is (a − 3) + 1 = 0, giving a = 2. At b = 0, the smooth derivative 0.5 is balanced by a valid subgradient −0.5 of |b|.

The threshold uses η times the penalty coefficient. Using threshold 1 with the same half-step would implement a different tradeoff. This is a hand-checked trace for the stated algorithm, not an assertion that every proximal method follows these iterates or that every objective decreases at every accelerated step.

Illustrative case study

Fictional case: Acorn Signals fits a sparse linear representation. Its first implementation treats the absolute-value penalty as differentiable at zero and replaces its undefined derivative with an arbitrary number. The resulting coefficients oscillate around zero.

The team implements the intended proximal-gradient splitting, verifies its threshold on simple inputs, and checks a small problem with a known solution. It records both data loss and regularization cost, then evaluates representation quality independently. The corrected update implements the selected objective; it does not automatically prove better performance on future signals. No measured production result is claimed.

Common misconceptions and mistakes

One proximal step is not usually the full solution to the original optimization problem. It solves a nearby regularized subproblem. Repeated steps or a suitable splitting scheme are what make it an algorithm for the larger objective.

The proximal operator of a sum is not generally obtained by applying each term's proximal operator once in sequence. Splitting algorithms include additional structure precisely because this shortcut is not valid in general.

Do not confuse the iteration's proximity term with a permanent statistical regularizer centered at a fixed point. In proximal point iteration the center moves, and the objective being targeted remains the original function under the algorithm's assumptions.

Business use

Choose a proximal approach when the objective has components whose individual operations are tractable and meaningful. Compare complete iteration costs, including linear solves or inner optimization required by the proximal step.

Document the splitting, step-size convention, stopping residuals, and inner-solve accuracy. A convergence theorem for exact convex subproblems cannot simply be transferred to an arbitrary approximate or nonconvex implementation without further justification.

Check your understanding

In proximal gradient, why does doubling the step size change the soft-threshold level when the penalty coefficient stays fixed?

Answer: The proximal step acts on the step-size-scaled penalty, so its threshold is the product of those quantities.

Related terms

Proximal operator
proximal gradient
proximal point
soft thresholding
nonsmooth optimization
operator splitting
projection

Learn next

derive soft thresholding from its scalar minimization problem, then compare proximal gradient with proximal point on the same convex objective.

Sources

Primary source: Parikh and Boyd, Proximal Algorithms, Sections 4.1, 4.2, and 6.5.2: https://web.stanford.edu/~boyd/papers/pdf/prox_algs.pdf . The relevant update and thresholding passages were read. The two-coordinate trace, implementation scenario, and calculations are original.

Previous: Provisioning Next: Proximal gradient methods for learning