M1-030M1: Mathematics & Statistics FundamentalsConvex Optimization & KKTHard
⚡Flashcard Drill➔Mastery:

Explain Subgradients and Proximal Operators, and How Proximal Gradient Descent Optimizes Non-Smooth L1 Penalties

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M1-031 →
📐 Mathematical Definition
proxλ∥⋅∥1(v)i=sign(vi)max⁡(∣vi∣−λ,0)\mathrm{prox}_{\lambda\|\cdot\|_1}(v)_i=\mathrm{sign}(v_i)\max(|v_i|-\lambda,0)
⚡ One-Sentence Core Answer
A subgradient generalizes derivatives for non-smooth convex functions via supporting hyperplanes, while proximal operators solve composite optimization via exact closed-form soft-thresholding.

📌 Key Takeaways

  • •
    Subgradient: Vector gg satisfying f(y)≥f(x)+gT(y−x)f(y) \ge f(x) + g^T(y - x) for all yy; for ∣x∣|x| at 0, subdifferential is [−1,1][-1, 1].
  • •
    Proximal operator: proxγg(x)=arg⁡min⁡z(g(z)+12γ∥z−x∥22)\text{prox}_{\gamma g}(x) = \arg\min_z \left(g(z) + \frac{1}{2\gamma}\|z - x\|_2^2\right).
  • •
    Proximal Gradient Method (ISTA): Splits f(x)+g(x)f(x) + g(x) into smooth gradient step on ff followed by exact prox step on non-smooth gg.

📐 Mathematical Derivations

For composite objective min⁡F(x)=f(x)+g(x)\min F(x) = f(x) + g(x) where ff is smooth and g(x)=λ∥x∥1g(x) = \lambda \|x\|_1 is non-smooth: Standard subgradient descent converges slowly at rate O(1/k)O(1/\sqrt{k}) because subgradients do not decrease near the minimum. Proximal Gradient Descent applies the update: xk+1=proxηλ∥⋅∥1(xk−η∇f(xk))x_{k+1} = \text{prox}_{\eta \lambda \|\cdot\|_1}\left(x_k - \eta \nabla f(x_k)\right). The proximal operator for L1 norm decomposes elementwise: arg⁡min⁡z(λ∣z∣+12η(z−v)2)\arg\min_z \left(\lambda |z| + \frac{1}{2\eta}(z - v)^2\right). Setting subgradient to zero yields the soft-thresholding operator: Sηλ(v)=sign(v)max⁡(∣v∣−ηλ,0)S_{\eta\lambda}(v) = \text{sign}(v)\max(|v| - \eta\lambda, 0). This achieves the fast O(1/k)O(1/k) convergence rate of smooth gradient descent while enforcing exact sparsity.

🏭 Production Trade-offs

Proximal algorithms (ISTA and accelerated FISTA with Nesterov momentum achieving O(1/k2)O(1/k^2)) are the industrial gold standard for sparse linear models, compressed sensing, and low-rank matrix recovery. In modern deep learning frameworks, PyTorch native optimizers handle non-smooth penalties via Proximal steps or subgradient sign heuristics (e.g. In AdamW, weight decay is separated from gradient updates).
⚠️ Common Interview Pitfalls
  • ✕
    Confusing soft-thresholding (L1 prox) with hard-thresholding (L0 prox, which discards small values without shifting large ones).
  • ✕
    Applying naive SGD with momentum to L1 loss, which destroys weight sparsity due to momentum accumulation.
🎯 Interviewer Follow-up Inquiries
  • ?
    How does FISTA achieve optimal O(1/k2)O(1/k^2) convergence rate for composite convex optimization?
  • ?
    How does the Alternating Direction Method of Multipliers (ADMM) generalize proximal operators to split constraints?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM1-029: Explain Geometrically and Algebraically Why L1 Regularization Promotes Sparsity While L2 Does Not📋 Back to BankNext →M1-031: Explain Why Softmax Must Subtract the Maximum Value and How It Prevents Numerical Overflow