Saddle-Point Min-Max duality · Rafael Braga-Kribitz

Contents

01Deep Breakdown
02Flowchart
03Real-world use
04The formula, piece by piece
05The formula in words
06Critical Concepts
07Step-by-step calculation (tiny example)
08Code examples

\min_{Ax=y} f(y) + g(x) = \max_u \min_{x,y} f(y) + g(x) + (Ax-y)^T u

(1)

Deep Breakdown

What it tells me (Situation Awareness): This is a saddle-point reformulation of a constrained composite minimization problem. The primal problem $\min_{Ax=y} f(y) + g(x)$ — minimize $f(y) + g(x)$ subject to the linear constraint $Ax = y$ — is converted via Lagrangian duality to $\max_u \min_{x,y} [f(y) + g(x) + (Ax-y)^T u]$ , where $u$ is the dual variable (multiplier) for the constraint $Ax - y = 0$ . The $(Ax-y)^T u$ term penalizes constraint violation. This is the foundation of ADMM (Alternating Direction Method of Multipliers), primal-dual algorithms, and operator splitting methods — all widely used in distributed optimization and sparse signal recovery. In DA/DS: ADMM is used for distributed Lasso, Elastic Net on large datasets, graph-regularized learning, and consensus optimization across compute nodes.

Flowchart

Real-world use

Where it is used

Distributed Lasso: split data across machines, use ADMM to coordinate updates; basis pursuit (sparse signal recovery); total variation denoising; graph-regularized learning; SVM training for large-scale datasets; consensus optimization in federated learning.

Problem it solves

Many convex problems have the form $\min f(y) + g(x)$ subject to $Ax = y$ , where $f$ and $g$ are each easy to minimize separately but hard to minimize jointly. For example: Lasso splits as $f(y) = \|y - b\|^2$ (least squares on $y = Xw$ ) and $g(x) = \lambda\|x\|_1$ (L1 penalty on $x = w$ ) with $Ax = y$ enforcing $x = w$ . ADMM exploits this by solving the $x$ -update and $y$ -update separately, then updating the dual variable $u$ .

How it solves the problem

The saddle-point equality $\min_{Ax=y} f(y)+g(x) = \max_u \min_{x,y} [f(y)+g(x)+(Ax-y)^Tu]$ holds under convexity and Slater's condition. ADMM solves the saddle point by augmenting the Lagrangian with a proximal term $\frac{\rho}{2}\|Ax-y\|^2$ (penalty), then alternately minimizing over $x$ , minimizing over $y$ , and dually ascending over $u$ . Each sub-problem is often easily solvable (proximal operator of $g$ for $x$ -update; proximal of $f$ for $y$ -update).

Example in a business

A DS runs Lasso regression on a distributed dataset split across 4 machines. Each machine holds data $X_k$ and labels $y_k$ . Using ADMM with the saddle-point structure: (1) each machine solves a local Lasso problem, (2) a central server averages the solutions and updates a shared multiplier $u$ , (3) repeat until consensus. This avoids sending all data to one machine while achieving the same solution as centralized Lasso.

The formula, piece by piece

$\min_{Ax=y}$ : constrained minimization subject to linear equality $Ax = y$
$f(y)$ : the "data fit" term in the $y$ -variable (e.g., least squares $\|y - b\|^2$ )
$g(x)$ : the "regularization" or "penalty" term in the $x$ -variable (e.g., $\lambda\|x\|_1$ )
$Ax = y$ : linear coupling constraint linking $x$ and $y$ variables (often just $x = y$ for consensus)
$u$ : the dual variable (Lagrange multiplier) for the constraint $Ax - y = 0$ ; vector of same dimension as $y$
$(Ax - y)^T u$ : constraint residual $(Ax-y)$ dotted with dual variable; zero at feasibility
$\max_u \min_{x,y}$ : minimax saddle-point structure; maximizing over dual $u$ while minimizing over primal $(x,y)$
ADMM augmentation: add $\frac{\rho}{2}\|Ax-y\|^2$ to improve conditioning (augmented Lagrangian)

The formula in words

"Constrained minimization over linked variables $x$ and $y$ equals a minimax game: the primal player minimizes over $(x,y)$ , and the dual player maximizes over the multiplier $u$ . At the saddle point, both players are satisfied and the constraint $Ax = y$ is exactly enforced." Tiny example: $\min_{x=y} x^2 + |y|$ (i.e., $\min_x x^2 + |x|$ , which has solution $x^*=0$ ). Saddle form: $\max_u \min_{x,y} [x^2 + |y| + (x-y)u]$ . $y$ -update: $\min_y |y| - yu = \text{soft-threshold}(u, 1) = \max(|u|-1, 0) \cdot \text{sign}(u)$ . $x$ -update: $\min_x x^2 + xu = (x^* = -u/2)$ . Dual: $d(u) = (-u/2)^2 + |u| - (-u/2)u = -u^2/4 + |u| + u^2/2 = u^2/4 + |u|$ . At $u=0$ : $d(0) = 0 = f(x^*)$ . $\checkmark$

Critical Concepts

ADMM algorithm (Alternating Direction Method of Multipliers): Given augmented Lagrangian $\mathcal{L}_\rho = f(y) + g(x) + u^T(Ax-y) + \frac{\rho}{2}\|Ax-y\|^2$ :

$x$ -update: $x^{k+1} = \arg\min_x [g(x) + \frac{\rho}{2}\|Ax - y^k + u^k/\rho\|^2]$ 2. $y$ -update: $y^{k+1} = \arg\min_y [f(y) + \frac{\rho}{2}\|Ax^{k+1} - y + u^k/\rho\|^2]$ 3. Dual update: $u^{k+1} = u^k + \rho(Ax^{k+1} - y^{k+1})$

Proximal operators: $\text{prox}_{\gamma f}(v) = \arg\min_x [f(x) + \frac{1}{2\gamma}\|x-v\|^2]$ . ADMM $y$ -update is $\text{prox}_{f/\rho}(Ax + u/\rho)$ . For $f = \lambda\|\cdot\|_1$ : proximal = soft-thresholding. For $f = \|\cdot\|^2$ : proximal = ridge shrinkage.
Convergence: ADMM converges for convex $f, g$ (under mild conditions) at rate $O(1/k)$ in the primal and dual residuals. Convergence does not require choosing $\rho$ optimally, but good $\rho$ speeds up practical convergence.
Distributed consensus ADMM: special case where $A = I$ and each node has its own $x_i$ and $y$ is the consensus variable (average of all $x_i$ ).

Used in federated learning and parallel optimization.

Step-by-step calculation (tiny example)

Solve Lasso $\min_{w \in \mathbb{R}^2} \frac{1}{2}\|y - Xw\|^2 + \lambda\|w\|_1$ via ADMM with $x=w$ , $z=w$ (consensus variable). $f(z) = \lambda\|z\|_1$ , $g(w) = \frac{1}{2}\|y-Xw\|^2$ , constraint $w = z$ . Augmented Lagrangian: $\mathcal{L}_\rho = \frac{1}{2}\|y-Xw\|^2 + \lambda\|z\|_1 + u^T(w-z) + \frac{\rho}{2}\|w-z\|^2$ . $w$ -update (ridge with offset): $(X^TX + \rho I)w = X^Ty + \rho z - u$ . $z$ -update (soft-threshold): $z = S_{\lambda/\rho}(w + u/\rho)$ where $S_\tau(v) = \text{sign}(v)\max(|v|-\tau, 0)$ . Dual update: $u \leftarrow u + \rho(w - z)$ .

Code examples

Beginner example (Python)

python

import numpy as np

def soft_threshold(v: np.ndarray, threshold: float) -> np.ndarray:
    """Proximal operator of L1 norm: soft-thresholding."""
    return np.sign(v) * np.maximum(np.abs(v) - threshold, 0)


def admm_lasso(
    X: np.ndarray,
    y: np.ndarray,
    lam: float = 0.1,
    rho: float = 1.0,
    n_iter: int = 100,
    tol: float = 1e-6,
) -> np.ndarray:
    """ADMM for Lasso: min 0.5*||y-Xw||^2 + lam*||w||_1.

    Saddle-point form: min_{w=z} 0.5*||y-Xw||^2 + lam*||z||_1.
    """
    n, d = X.shape

    # Precompute for w-update: (X^T X + rho I)^{-1}
    XtX = X.T @ X
    XtX_rho = XtX + rho * np.eye(d)
    Xty = X.T @ y
    L = np.linalg.cholesky(XtX_rho)  # for fast solves

    w = np.zeros(d)
    z = np.zeros(d)
    u = np.zeros(d)
    for iteration in range(n_iter):
        # w-update: min_w 0.5*||y-Xw||^2 + rho/2*||w - z + u/rho||^2
        rhs = Xty + rho * (z - u / rho)
        w = np.linalg.solve(L.T, np.linalg.solve(L, rhs))
        z_prev = z.copy()

        # z-update: soft-threshold (proximal of L1)
        z = soft_threshold(w + u / rho, lam / rho)

        # Dual update
        u += rho * (w - z)

        # Check convergence
        primal_res = np.linalg.norm(w - z)
        dual_res = np.linalg.norm(rho * (z - z_prev))
        if primal_res < tol and dual_res < tol:
            print(f" ADMM converged at iteration {iteration}")
            break
    return w


np.random.seed(42)
n, d = 100, 20
X_data = np.random.randn(n, d)
true_w = np.zeros(d)
true_w[:5] = [2.0, -1.5, 1.0, -0.5, 0.3]
y_data = X_data @ true_w + 0.5 * np.random.randn(n)
w_lasso = admm_lasso(X_data, y_data, lam=0.5, rho=1.0, n_iter=200)
print(f"\nTrue non-zero: {np.where(true_w != 0)[0].tolist()}")
print(f"ADMM Lasso active (|w|>0.05): {np.where(np.abs(w_lasso) > 0.05)[0].tolist()}")
print(f"Top-5 estimated coefficients: {w_lasso[:5].round(3)}")
print(f"True coefficients (first 5): {true_w[:5]}")

Beginner example (R)

# ADMM for Lasso: saddle-point structure
soft_threshold <- function(v, threshold) sign(v) * pmax(abs(v) - threshold, 0)
admm_lasso_r <- function(X, y, lam = 0.1, rho = 1.0, n_iter = 100, tol = 1e-6) {
  n <- nrow(X); d <- ncol(X)
  XtX_rho <- t(X) %*% X + rho * diag(d)
  Xty <- t(X) %*% y
  w <- numeric(d); z <- numeric(d); u <- numeric(d)
  for (i in seq_len(n_iter)) {
    # w-update
    rhs <- Xty + rho * (z - u / rho)
    w <- solve(XtX_rho, rhs)
    z_prev <- z
    # z-update: soft-threshold
    z <- soft_threshold(w + u/rho, lam/rho)
    # dual update
    u <- u + rho * (w - z)
    if (sqrt(sum((w-z)^2)) < tol && sqrt(sum((rho*(z-z_prev))^2)) < tol) {
      cat(sprintf("Converged at iteration %d\n", i))
      break
    }
  }
  w
}
set.seed(42)
n <- 100; d <- 20
X_data <- matrix(rnorm(n*d), n, d)
true_w <- c(2, -1.5, 1, -0.5, 0.3, rep(0, 15))
y_data <- X_data %*% true_w + 0.5 * rnorm(n)
w_est <- admm_lasso_r(X_data, y_data, lam = 0.5, rho = 1.0)
cat("True w[1:5]:", round(true_w[1:5], 3), "\n")
cat("ADMM w[1:5]:", round(w_est[1:5], 3), "\n")

Professional example (Python)

python

import numpy as np
from sklearn.linear_model import Lasso
from sklearn.preprocessing import StandardScaler
np.random.seed(42)

# -- Distributed consensus ADMM for Lasso (2 compute nodes) -------------------
# Split data across 2 nodes; each solves local subproblem; consensus via ADMM
N_TOTAL = 300
D = 15
n_nodes = 2
X_raw = np.random.randn(N_TOTAL, D)
scaler = StandardScaler()
X = scaler.fit_transform(X_raw)
true_w = np.array([1.5, -1.0, 0.8, -0.6, 0.4] + [0] * (D - 5))
y = X @ true_w + 0.3 * np.random.randn(N_TOTAL)
LAM = 0.3
RHO = 2.0
N_ITER = 200
TOL = 1e-6

def soft_threshold(v: np.ndarray, tau: float) -> np.ndarray:
    return np.sign(v) * np.maximum(np.abs(v) - tau, 0)


# Split data across nodes
indices = [np.arange(i * N_TOTAL // n_nodes, (i + 1) * N_TOTAL // n_nodes) for i in range(n_nodes)]
X_nodes = [X[idx] for idx in indices]
y_nodes = [y[idx] for idx in indices]

# Pre-compute per-node matrices
node_XtX_rho = [X_k.T @ X_k + RHO * np.eye(D) for X_k in X_nodes]
node_Xty = [X_k.T @ y_k for X_k, y_k in zip(X_nodes, y_nodes)]

# Consensus ADMM state
w_local = [np.zeros(D) for _ in range(n_nodes)]  # per-node estimates
z_global = np.zeros(D)  # consensus variable
u_dual = [np.zeros(D) for _ in range(n_nodes)]  # per-node dual vars

for iteration in range(N_ITER):
    # Step 1: each node updates its local w (ridge sub-problem)
    for k in range(n_nodes):
        rhs = node_Xty[k] + RHO * (z_global - u_dual[k])
        w_local[k] = np.linalg.solve(node_XtX_rho[k], rhs)
    z_prev = z_global.copy()

    # Step 2: consensus update (average + soft-threshold)
    w_avg = np.mean(w_local, axis=0)
    u_avg = np.mean(u_dual, axis=0)
    z_global = soft_threshold(w_avg + u_avg, LAM / (RHO * n_nodes))

    # Step 3: per-node dual update
    for k in range(n_nodes):
        u_dual[k] += w_local[k] - z_global

    # Convergence check
    primal_res = max(np.linalg.norm(w_local[k] - z_global) for k in range(n_nodes))
    dual_res = RHO * np.linalg.norm(z_global - z_prev)
    if primal_res < TOL and dual_res < TOL:
        print(f"Distributed ADMM converged at iteration {iteration}")
        break

# Compare to centralized Lasso
centralized = Lasso(alpha=LAM / N_TOTAL, fit_intercept=False, max_iter=10000)
centralized.fit(X, y)
print(f"\nDistributed vs Centralized Lasso")
print(f"{'Coef':<8} {'True':>8} {'Distributed':>14} {'Centralized':>14}")
for j in range(D):
    print(f" w[{j}] {true_w[j]:>8.3f} {z_global[j]:>14.4f} {centralized.coef_[j]:>14.4f}")
print(f"\n||w_dist - w_central||: {np.linalg.norm(z_global - centralized.coef_):.4e}")

Source: MML1 p. 200

#calculus #continuous-optimisation #constrained-optimisation-and-lagrange-multipliers