One implicit gradient step — the atom of every modern convex solver. Moreau's prox is the argmin of a function plus a spring pulling toward a point: proxt·h(v) = argminx [ h(x) + ‖x−v‖²∕2t ]. For h = ‖·‖1 it is soft-thresholding; for the indicator of a convex set it is Euclidean projection. Down the center a point goes in, the argmin is solved, the shrunk point comes out. The blue team proves each closed form; the red team tries to make the formula lie.
source J.-J. Moreau, Proximité et dualité dans un espace hilbertien, Bull. Soc. Math. France 93 (1965) 273–299 — numdam.org/…/BSMF_1965__93__273_0. Rendered, not quoted.
The argmin is never searched; for two important h it has a formula derived from the optimality condition 0 ∈ ∂h(x) + (x−v)∕t:
‖·‖₁ → soft-threshold shrink(v,t)=sign(v)·max(|v|−t,0): pull toward 0 by t, clamp at 0. indicator 𝟙C → projection ΠC(v); for a box that is just clip(v,lo,hi).
Live optimality-condition check for the L1 prox at the current v,t (window 0):
| quantity | value | KKT residual |
|---|
A gradient step is explicit: x⁺ = x − t∇f(x). A prox step is implicit: x⁺ = proxt·h(x − t∇f(x)) — it lands where the non-smooth part is already accounted for. That single move is ISTA (the sparse-autoencoder's L1 solver), ADMM, and projected gradient.
When h = 𝟙C, prox = projection and the implicit step is projected gradient descent — the method this panel runs on a constructed strongly-convex QP. Each sphere is the next one's premise.
The blue team's live check: re-derive shrink from a brute-force 1-D minimization of h(x)+‖x−v‖²∕2t, confirm projection = clip, non-expansiveness, and the QP's known rate. If red tampers, this badge is where it shows.
Feed the operator a point v, a step size t > 0, and a choice of non-smooth part h. Everything else is forced:
| h(x) | proxt·h(v) | what it does |
|---|---|---|
| ‖x‖₁ = |x| | sign(v)·max(|v|−t,0) | shrink toward 0 |
| 𝟙[lo,hi](x) | clip(v,lo,hi) | project into box |
| 0 | v | identity |
Larger t ⇒ more shrink / the spring is looser. A box prox ignores t: the closest feasible point does not depend on it. That is what you feed the panel below.
Curve = proxt·h(v) vs v (green); dashed = identity. The dot is the current v → x⁎.
The result is the argmin, cross-checked against a brute-force grid minimization on the spot — never looked up.
What the machine produces, proven: prox of ‖·‖₁ equals soft-thresholding (matches brute-force argmin to 1e-3, KKT exact); prox of a box indicator equals the clip; prox is non-expansive; a fixed point of proxt·h is a minimizer of h; and projected gradient on the constructed QP converges to x⁎ = (½, ½) at the known rate ρ = ¾.
The blue team's witness (left) re-derives these live; the red team (right) tries to make them wrong.
And the fast outer rate is conditional: plain ISTA is O(1∕k), not linear, unless f is strongly convex; the accelerated O(1∕k²) (FISTA) needs the correct momentum and a step ≤ 1∕L. Pick t > 1∕L and the whole scheme can diverge. The prox is an atom, not a guarantee.
"The prox of |x| just sets small values to zero." Kept, corrected. It also shrinks the survivors by exactly t — soft, not hard, thresholding. Hard-thresholding is the prox of the non-convex ‖·‖₀, a different operator.
"prox is projection." Cut. Projection is the special case h = 𝟙C. For a general h the argmin is not on any set boundary.
"Bigger step size = faster." Cut. Beyond 1∕L the implicit step overshoots and the method can diverge; the step trades progress against stability, it is not free speed.
The red team's move: flip soft-thresholding to grow the value (v + t·sign(v)) instead of shrinking it — so it is no longer the argmin of the Moreau envelope. The blue team's witness (window 7) is watching.
Grow instead of shrink and the formula no longer matches the brute-force minimizer — the witness recomputes, the KKT residual blows up, and it turns red. Nothing is faked; the attack is real and it is caught.