2.11f — Comparaison bloc A / bloc B : le tableau croisé de l’optimisation convexe

Série 02-ML-Cours (Data Science With Agents) — Bloc B.8 de l’issue #16061 (Optimisation convexe avancée from scratch), et notebook de clôture de la chaîne optimisation convexe.

Pourquoi une accrétion 2.11f (et pas un nouveau numéro) : ce notebook ne crée aucun solveur nouveau. Il re-mesure, dans un même processus, les six solveurs Lasso écrits par la chaîne 2.11b (ISTA/FISTA, bloc A.3) → 2.11c (coordinate descent + sklearn, bloc B.6) → 2.11d (ADMM, bloc A.2) → 2.11e (cvxpy, bloc B.7), et les deux solveurs SVM de 2.7b (SMO de Platt, bloc A.1) → 2.7c (LIBSVM, bloc B.5). Une synthèse n’existe que par la chaîne qu’elle synthétise : elle s’attache donc au numéro de son parent, et f marque le dernier grain de cette chaîne.

Ce que ce notebook livre — le tableau récapitulatif demandé par le body de l’issue (§ Bloc B, point 8) :

pour chaque famille (SVM : classification binaire ; Lasso : régression sparse), un tableau mesuré ici, dans ce processus : objectif final, temps d’entraînement, nombre d’itérations, lignes de code, capacité à scaler ;
la discipline de comparaison honnête : même dataset, même graine, même normalisation, même convention d’objectif — jamais deux formulations différentes comparées comme si elles étaient identiques ;
deux sondes d’échelle mesurées (SVM : n croissant ; Lasso : p croissant) ;
la réponse au « pourquoi du from scratch » (compréhension : dualité KKT, opérateurs proximaux, convergence) et au « quand du SOTA » (production : vitesse, robustesse, échelle).

Chaîne pédagogique : 2.11-Regularisation-Sparse-LASSO (la règle) → 2.11b-Proximal-Operators-From-Scratch (bloc A.3) → 2.11c-Lasso-SOTA-Comparison (bloc B.6) → 2.11d-Optimisation-ADMM-From-Scratch (bloc A.2) → 2.11e-CVXPY-Optimisation (bloc B.7) → 2.11f-Comparaison-Optimisation-Convexe (ce notebook, bloc B.8 — clôture de la chaîne) ; chaîne SVM parallèle : 2.7-Modeles-Non-Parametriques → 2.7b-SMO-From-Scratch (bloc A.1) → 2.7c-SVM-SOTA-Comparison (bloc B.5) → 2.11f (ce notebook).

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez :

énoncer le contrat de comparaison qui rend deux solveurs comparables (même problème, même normalisation, même convention d’objectif, budget de tolérance nommé) ;
lire un tableau croisé bloc A / bloc B et identifier ce que chaque colonne mesure — et pourquoi les unités d’itérations diffèrent d’une ligne à l’autre ;
mesurer la capacité à scaler d’un solveur (coût par itération, croissance en n ou p) et la relier à la structure de l’algorithme (boucle Python, algèbre pré-factorisée, code C) ;
décider quand écrire le solveur, quand appeler la bibliothèque — et ce que chaque geste achète que l’autre n’achète pas.

Prérequis

Avoir parcouru 2.7b/2.7c (dual SVM, SMO, KKT) et la chaîne 2.11 → 2.11e (Lasso, proximal, ADMM, cvxpy). Les sections qui suivent re-définissent tout ce qui est exécuté (notebook autonome, CPU seul), mais la théorie vit dans les notebooks parents.
Python 3.10+ ; numpy, scipy, scikit-learn, cvxpy.

Duree estimee : ~30 minutes

1. Le contrat de comparaison

Comparer des solveurs est l’endroit où l’approximation fabrique les pires erreurs de lecture : un « plus rapide » mesuré sur un autre problème, une accuracy comparée à un objectif de régression, un α de sklearn confondu avec un λ de papier. Ce notebook pose donc son contrat avant toute mesure — chaque règle est appliquée dans toutes les sections qui suivent.

#	Règle	Application concrète ici
1	Même terrain	SVM : `make_moons(200, noise=0.25, seed=42)`, split 30 % stratifié (seed 42) — reprise exacte de 2.7b/2.7c. Lasso : problème P1 `(n=200, p=500, k=30, seed 42)` — reprise exacte de 2.11b/2.11c/2.11e.
2	Même normalisation	SVM : features brutes (aucune standardisation — protocole des parents). Lasso : `A` divisée par `√n` à la génération (`A ~ N(0,1)/√n`), pas de centrage/réduction supplémentaire, `fit_intercept=False`.
3	Même convention d’objectif	SVM : dual \(W(\alpha)=\sum_i \alpha_i - \tfrac{1}{2}\sum_{ij} \alpha_i \alpha_j y_i y_j K_{ij}\) et gap primal−dual. Lasso : \(\tfrac{1}{2}\\|Ax-b\\|^2 + \lambda\\|x\\|_1\) — et pour `sklearn` la conversion explicite `alpha = λ/n` (sa convention interne divise le terme d’attache par `2n`).
4	Budget de tolérance nommé	Chaque ligne du tableau porte son critère d’arrêt (tol KKT, ε_abs/ε_rel, tol sur objectif, budget d’itérations fixe) — comparer un solveur arrêté à 10⁻⁴ à un solveur arrêté à 10⁻⁸ sans le dire est une faute de lecture.
5	Un seul processus	Tous les timings de ce notebook sont mesurés dans le même interpréteur, même BLAS, même machine — les nombres des notebooks parents sont cités uniquement comme attestation de reproductibilité, jamais comparés en valeur absolue de temps.
6	Deux familles, jamais mélangées	L’objectif dual d’un SVM et l’objectif d’un Lasso ne sont pas dans la même unité : les tableaux sont par famille, et aucune ligne SVM n’est comparée numériquement à une ligne Lasso.

LOC (lignes de code) : deux portées distinctes, étiquetées comme telles et non comparables entre elles. Lignes from scratch : le corps du solveur tel que défini dans ce notebook — lignes non vides, hors docstring, hors commentaire plein, sous-fonctions et briques appelées incluses (rbf_kernel pour SMO, prox_l1 pour ISTA/FISTA/ADMM). Lignes bibliothèque : la surface d’appel publique (quelques lignes seulement, sklearn comme cvxpy — le compte exact est mesuré et imprimé par les tableaux), jamais l’implémentation interne. La colonne compare ce qu’il faut écrire pour obtenir la solution — pas l’empreinte d’implémentation totale : le compte bibliothèque n’est pas un compte d’implémentation, le compte maison n’inclut pas numpy/scipy.

Commençons par vérifier que l’environnement porte tout ce que les deux familles exigent.

import sys
import numpy as np
import scipy
import sklearn
import cvxpy as cp

print(f"python  : {sys.version.split()[0]}")
print(f"numpy   : {np.__version__}")
print(f"scipy   : {scipy.__version__}")
print(f"sklearn : {sklearn.__version__}")
print(f"cvxpy   : {cp.__version__}")
print("Environnement OK - les deux familles (SVM + Lasso) sont executables sur CPU.")

python  : 3.13.14
numpy   : 2.4.4
scipy   : 1.17.1
sklearn : 1.8.0
cvxpy   : 1.9.2
Environnement OK - les deux familles (SVM + Lasso) sont executables sur CPU.

2. Famille SVM : deux solveurs, un même dual

Le terrain est celui de 2.7b (bloc A.1) et 2.7c (bloc B.5), repris à l’identique :

Élément	Valeur	Commentaire
Dataset	`make_moons(n_samples=200, noise=0.25, random_state=42)`	2 demi-lunes, 2D — problème binaire non linéairement séparable
Split	30 % test, `stratify=y`, `random_state=42`	140 train / 60 test, reproductible
Labels	`y ∈ {-1, +1}`	convention du dual
Hyperparamètres	`C = 1.0`, `γ = 2.0`, `tol = 1e-3`	identiques pour les deux solveurs
Feature scaling	aucun — features brutes	protocole de 2.7b/2.7c : les deux coordonnées des demi-lunes vivent à la même échelle ; toute standardisation changerait le problème (donc le dual, donc la comparaison)

Les deux solveurs attaquent le même problème dual :

\[\max_\alpha \; W(\alpha) = \sum_i \alpha_i - \tfrac{1}{2} \sum_{i,j} \alpha_i \alpha_j y_i y_j K(x_i, x_j) \quad \text{s.c.} \quad 0 \le \alpha_i \le C, \; \sum_i \alpha_i y_i = 0\]

avec le noyau RBF \(K(x, z) = \exp(-\gamma\|x - z\|^2)\). Le certificat croisé est le gap de dualité \(P - D\) : primal soft-margin évalué sur la solution duale, contre objectif dual — les deux solveurs doivent le rendre petit, chacun selon sa tolérance.

2.1 Le solveur du bloc A : SMO de Platt, reprise compacte

La boucle SMO ci-dessous est la reprise compacte de 2.7b (cellules 8-9) — même algorithme, mêmes heuristiques : test KKT par exemple, choix du second index par |E_i − E_j| maximal sur les non-bornés puis balayage complet, sous-problème 2D analytique (dont la branche dégénérée η ≤ 0, résolue aux bornes selon Platt 1998 App. A), cache d’erreurs incrémental. Elle est re-définie ici pour que le notebook soit autonome, et pour que sa mesure de LOC porte sur la source réellement exécutée.

import inspect
import textwrap
import ast


def rbf_kernel(X, Z, gamma):
    """Matrice de Gram RBF K[i, j] = exp(-gamma ||x_i - z_j||^2) - reprise de 2.7b (cellule 4)."""
    dist2 = (X ** 2).sum(axis=1)[:, None] + (Z ** 2).sum(axis=1)[None, :] - 2.0 * X @ Z.T
    np.maximum(dist2, 0.0, out=dist2)
    return np.exp(-gamma * dist2)


def smo_fit(X, y, C=1.0, gamma=1.0, tol=1e-3, max_passes=20, eps=1e-3):
    """SMO de Platt pour SVM soft-margin (noyau RBF) - reprise compacte de 2.7b (cellules 8-9).

    Retourne dict : alpha, b, support_mask, n_iter (appels a examine_example),
    n_steps (sous-problemes 2D reussis - l'unite comparable aux iterations LIBSVM).
    """
    n = X.shape[0]
    alpha = np.zeros(n)
    b = 0.0
    K = rbf_kernel(X, X, gamma)
    E_cache = -y.copy()          # E_k = sum_j alpha_j y_j K_jk + b - y_k, a alpha = 0

    def take_step(i, j, E):
        """Sous-probleme 2D analytique (Platt, eq. 12.7-12.11), branche eta <= 0 aux bornes."""
        nonlocal b
        if i == j:
            return 0
        ai_old, aj_old = alpha[i], alpha[j]
        yi, yj = y[i], y[j]
        if yi != yj:
            L, H = max(0.0, aj_old - ai_old), min(C, C + aj_old - ai_old)
        else:
            L, H = max(0.0, ai_old + aj_old - C), min(C, ai_old + aj_old)
        if L >= H:
            return 0
        Kii, Kjj, Kij = K[i, i], K[j, j], K[i, j]
        eta = Kii + Kjj - 2.0 * Kij          # ||phi(x_i) - phi(x_j)||^2
        if eta > 0:
            aj_new = min(H, max(L, aj_old + yj * (E[i] - E[j]) / eta))
        else:
            c = ai_old * yi + aj_old * yj
            vi = E[i] + yi - b - ai_old * yi * Kii - aj_old * yj * Kij
            vj = E[j] + yj - b - aj_old * yj * Kjj - ai_old * yi * Kij

            def W2d(aj):
                s = yi * yj
                ai = yi * (c - aj * yj)
                return (ai + aj - 0.5 * (Kii * ai * ai + Kjj * aj * aj
                        + 2.0 * s * Kij * ai * aj) - ai * yi * vi - aj * yj * vj)

            WL, WH = W2d(L), W2d(H)
            aj_new = L if WL > WH else (H if WL < WH else aj_old)
        if abs(aj_new - aj_old) < eps * (aj_old + eps):
            return 0
        s = yi * yj
        ai_new = ai_old + s * (aj_old - aj_new)
        alpha[i], alpha[j] = ai_new, aj_new
        b1 = b - E[i] - yi * (ai_new - ai_old) * Kii - yj * (aj_new - aj_old) * Kij
        b2 = b - E[j] - yi * (ai_new - ai_old) * Kij - yj * (aj_new - aj_old) * Kjj
        b_new = b1 if 0 < ai_new < C else (b2 if 0 < aj_new < C else 0.5 * (b1 + b2))
        E += yi * (ai_new - ai_old) * K[:, i] + yj * (aj_new - aj_old) * K[:, j]
        E += (b_new - b)
        b = b_new
        return 1

    def examine_example(i):
        """Test KKT puis cascade de Platt (non-bornees, puis balayage complet)."""
        ri = y[i] * E_cache[i]
        if not ((ri < -tol and alpha[i] < C) or (ri > tol and alpha[i] > 0)):
            return 0
        non_bound = np.where((alpha > 0) & (alpha < C))[0]
        non_bound = non_bound[non_bound != i]
        if len(non_bound) > 0:
            j = non_bound[np.argmax(np.abs(E_cache[non_bound] - E_cache[i]))]
            if take_step(i, j, E_cache):
                return 1
        for j in range(n):
            if j != i and take_step(i, j, E_cache):
                return 1
        return 0

    passes, n_iter, n_steps = 0, 0, 0
    while passes < max_passes:
        num_changed = 0
        for i in range(n):
            n_iter += 1
            ok = examine_example(i)
            num_changed += ok
            n_steps += ok
        passes = passes + 1 if num_changed == 0 else 0
    return {'alpha': alpha, 'b': float(b), 'support_mask': alpha > 1e-6,
            'n_iter': n_iter, 'n_steps': n_steps}


def count_loc(func):
    """LOC d'une fonction : lignes non vides, hors docstrings, hors commentaires pleins.

    Mesure par introspection (ast + inspect) sur la source reellement definie ici.
    Les sous-fonctions imbriquees sont comptees : c'est ce qu'il faut ecrire.
    """
    src = textwrap.dedent(inspect.getsource(func))
    tree = ast.parse(src)
    lines = src.splitlines()
    drop = set()
    for node in ast.walk(tree):
        if isinstance(node, (ast.FunctionDef, ast.AsyncFunctionDef, ast.ClassDef, ast.Module)):
            first = node.body[0] if node.body else None
            if (isinstance(first, ast.Expr) and isinstance(first.value, ast.Constant)
                    and isinstance(first.value.value, str)):
                for ln in range(first.lineno, first.end_lineno + 1):
                    drop.add(ln)
    count = 0
    for idx, line in enumerate(lines, start=1):
        if idx in drop:
            continue
        s = line.strip()
        if not s or s.startswith('#'):
            continue
        count += 1
    return count


print(f"SMO compact defini (reprise 2.7b) : {count_loc(smo_fit)} LOC pour smo_fit "
      f"(sous-fonctions incluses), {count_loc(rbf_kernel)} LOC pour rbf_kernel.")

SMO compact defini (reprise 2.7b) : 70 LOC pour smo_fit (sous-fonctions incluses), 4 LOC pour rbf_kernel.

2.2 La mesure : SMO maison contre LIBSVM, sur le même terrain

Protocole : SMO maison en un run à froid (protocole de 2.7b) ; LIBSVM via sklearn.svm.SVC mesuré en moyenne de 50 fits à froid (protocole de 2.7c — un fit unique de quelques fractions de milliseconde serait dominé par le bruit d’horloge). Le dual de LIBSVM est reconstruit depuis dual_coef_ (geste de 2.7c, cellule 11) : SVC ne rend pas son α, on le reconstitue pour évaluer \(D(\alpha)\) et le gap sur la même grandeur que SMO.

import time
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score
from sklearn.metrics.pairwise import rbf_kernel as sk_rbf_kernel

# --- terrain : reprise exacte de 2.7b (cellule 11) / 2.7c (cellule 5) ---
X, y_pm = make_moons(n_samples=200, noise=0.25, random_state=42)
y = np.where(y_pm == 0, -1.0, 1.0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.30, random_state=42, stratify=y)
C, GAMMA, TOL = 1.0, 2.0, 1e-3
print(f"terrain : {len(y_tr)} train / {len(y_te)} test, features brutes (aucune standardisation)")

# --- bloc A.1 : SMO maison, run unique a froid ---
t0 = time.perf_counter()
m = smo_fit(X_tr, y_tr, C=C, gamma=GAMMA, tol=TOL, max_passes=20)
t_smo = time.perf_counter() - t0

alpha_smo = m['alpha']
K_tr = rbf_kernel(X_tr, X_tr, GAMMA)
ay = alpha_smo * y_tr
D_smo = float(alpha_smo.sum() - 0.5 * ay @ K_tr @ ay)
P_smo = float(0.5 * ay @ K_tr @ ay + C * np.maximum(0.0, 1.0 - y_tr * (K_tr @ ay + m['b'])).sum())
gap_smo = P_smo - D_smo

sv_mask = m['support_mask']
sup_X, sup_y, sup_a = X_tr[sv_mask], y_tr[sv_mask], alpha_smo[sv_mask]
acc_smo = accuracy_score(y_te, np.sign(rbf_kernel(X_te, sup_X, GAMMA) @ (sup_a * sup_y) + m['b']))
nSV_smo = int(sv_mask.sum())

# --- bloc B.5 : LIBSVM via sklearn.svm.SVC ---
clf = SVC(C=C, kernel='rbf', gamma=GAMMA, tol=TOL, max_iter=20000).fit(X_tr, y_tr)
acc_skl = accuracy_score(y_te, clf.predict(X_te))
nSV_skl = int(clf.n_support_.sum())
it_skl = int(np.sum(clf.n_iter_))       # selections de working set LIBSVM (exposees par sklearn)
N_REPETS = 50
t0 = time.perf_counter()
for _ in range(N_REPETS):
    SVC(C=C, kernel='rbf', gamma=GAMMA, tol=TOL, max_iter=20000).fit(X_tr, y_tr)
t_skl = (time.perf_counter() - t0) / N_REPETS

# --- reconstruction du dual LIBSVM (protocole 2.7c, cellule 11) ---
alpha_skl = np.zeros(len(y_tr))
alpha_skl[clf.support_] = np.abs(clf.dual_coef_[0])
ay_skl = clf.dual_coef_[0]
K_ss = sk_rbf_kernel(clf.support_vectors_, clf.support_vectors_, gamma=GAMMA)
w2 = float(ay_skl @ K_ss @ ay_skl)
D_skl = float(alpha_skl.sum() - 0.5 * w2)
P_skl = float(0.5 * w2 + C * np.maximum(0.0, 1.0 - y_tr * clf.decision_function(X_tr)).sum())
gap_skl = P_skl - D_skl

print(f"SMO maison (A.1) : D = {D_smo:.4f}, gap P-D = {gap_smo:.1e}, accuracy = {acc_smo:.3f}, "
      f"|SV| = {nSV_smo}, n_iter = {m['n_iter']}, pas 2D = {m['n_steps']}, temps = {t_smo:.2f} s (run unique a froid)")
print(f"LIBSVM (B.5)     : D = {D_skl:.4f}, gap P-D = {gap_skl:.1e}, accuracy = {acc_skl:.3f}, "
      f"|SV| = {nSV_skl}, n_iter_ = {it_skl} (working set), temps = {t_skl * 1e3:.2f} ms (moyenne de {N_REPETS} fits a froid)")
print(f"certificat croise : |D_smo - D_libsvm| = {abs(D_smo - D_skl):.2e}, "
      f"meme |SV| : {nSV_smo == nSV_skl}, ecart accuracy : {abs(acc_smo - acc_skl):.3f}")

# --- reproductibilite : egalite CALCULEE contre la baseline commitee de 2.7b (meme graine) ---
BASELINE_27B = {'D': 30.3960, 'nsv': 48, 'n_iter': 21560}
ok_27b = (abs(D_smo - BASELINE_27B['D']) < 5e-4 and nSV_smo == BASELINE_27B['nsv']
          and m['n_iter'] == BASELINE_27B['n_iter'])
print(f"reproductibilite vs baseline 2.7b (commitee) : D {D_smo:.4f} vs {BASELINE_27B['D']:.4f}, "
      f"|SV| {nSV_smo} vs {BASELINE_27B['nsv']}, n_iter {m['n_iter']} vs {BASELINE_27B['n_iter']} "
      f"-> identiques : {ok_27b}")

terrain : 140 train / 60 test, features brutes (aucune standardisation)
SMO maison (A.1) : D = 30.3960, gap P-D = 3.3e-03, accuracy = 0.967, |SV| = 48, n_iter = 21560, pas 2D = 1678, temps = 0.23 s (run unique a froid)
LIBSVM (B.5)     : D = 30.3961, gap P-D = 2.0e-03, accuracy = 0.967, |SV| = 48, n_iter_ = 102 (working set), temps = 0.62 ms (moyenne de 50 fits a froid)
certificat croise : |D_smo - D_libsvm| = 4.02e-05, meme |SV| : True, ecart accuracy : 0.000
reproductibilite vs baseline 2.7b (commitee) : D 30.3960 vs 30.3960, |SV| 48 vs 48, n_iter 21560 vs 21560 -> identiques : True

2.3 Le tableau famille SVM

Le tableau est imprimé depuis les variables mesurées à l’instant — aucune valeur recopiée à la main.

# LOC - deux portees ETIQUETEES, non comparables entre elles (cf. contrat S1) :
# SMO   : corps du solveur defini au S2.1 = smo_fit (sous-fonctions incluses) + rbf_kernel
# LIBSVM: surface d'appel publique sklearn (instanciation + fit)
LOC_SMO = count_loc(smo_fit) + count_loc(rbf_kernel)
LOC_SVC = 2

svm_rows = [
    ('SMO Platt maison', 'A.1', D_smo, gap_smo, acc_smo, nSV_smo, t_smo,
     f"{m['n_iter']} ex. / {m['n_steps']} pas", LOC_SMO),
    ('LIBSVM via SVC', 'B.5', D_skl, gap_skl, acc_skl, nSV_skl, t_skl,
     f"{it_skl} (working set)", LOC_SVC),
]

W = 108
print("=" * W)
print("FAMILLE SVM - make_moons(200, noise=0.25, seed=42), C=1.0, gamma=2.0, tol=1e-3, features brutes")
print("=" * W)
print(f"{'solveur':<22}{'bloc':>5}{'D(alpha)':>10}{'gap P-D':>9}{'accuracy':>10}"
      f"{'|SV|':>6}{'temps':>12}{'iterations':>26}{'LOC':>6}")
print("-" * W)
for nom, bloc, D, gap, acc, nsv, t, it, loc in svm_rows:
    t_str = f"{t:.2f} s" if t > 0.1 else f"{t * 1e3:.2f} ms"
    print(f"{nom:<22}{bloc:>5}{D:>10.4f}{gap:>9.1e}{acc:>10.3f}{nsv:>6}{t_str:>12}{it:>26}{loc:>6}")
print("-" * W)
print("notes : unites d'iterations NON homogenes - SMO : 'ex.' = appels a examine_example,")
print("        'pas' = sous-problemes 2D reussis ; LIBSVM : n_iter_ (expose par sklearn) =")
print("        selections de working set. Les compteurs ne se s additionnent pas entre lignes.")
print("        LOC : portees distinctes - SMO = corps defini au S2.1 (smo_fit + rbf_kernel),")
print("        LIBSVM = surface d'appel publique (cf. colonne LOC). Pas un meme compte d'implementation.")
print("        protocole temps : SMO run unique a froid ; LIBSVM moyenne de 50 fits a froid.")
print("        feature scaling : aucun - features brutes, protocole 2.7b/2.7c.")

============================================================================================================
FAMILLE SVM - make_moons(200, noise=0.25, seed=42), C=1.0, gamma=2.0, tol=1e-3, features brutes
============================================================================================================
solveur                bloc  D(alpha)  gap P-D  accuracy  |SV|       temps                iterations   LOC
------------------------------------------------------------------------------------------------------------
SMO Platt maison        A.1   30.3960  3.3e-03     0.967    48      0.23 s      21560 ex. / 1678 pas    74
LIBSVM via SVC          B.5   30.3961  2.0e-03     0.967    48     0.62 ms         102 (working set)     2
------------------------------------------------------------------------------------------------------------
notes : unites d'iterations NON homogenes - SMO : 'ex.' = appels a examine_example,
        'pas' = sous-problemes 2D reussis ; LIBSVM : n_iter_ (expose par sklearn) =
        selections de working set. Les compteurs ne se s additionnent pas entre lignes.
        LOC : portees distinctes - SMO = corps defini au S2.1 (smo_fit + rbf_kernel),
        LIBSVM = surface d'appel publique (cf. colonne LOC). Pas un meme compte d'implementation.
        protocole temps : SMO run unique a froid ; LIBSVM moyenne de 50 fits a froid.
        feature scaling : aucun - features brutes, protocole 2.7b/2.7c.

Lecture : le SOTA n’achète pas la solution, il achète le temps

Sortie obtenue : deux solveurs, un même dual — l’objectif dual \(D(\alpha)\) des deux lignes coïncide (l’écart chiffré est imprimé par la cellule — de l’ordre de 10⁻⁵), les deux gaps de dualité restent dans le même ordre de grandeur que la tolérance commune tol = 1e-3, et les deux solveurs rendent le même nombre de vecteurs supports. C’est l’attestation croisée : deux heuristiques de working set différentes (cascade de Platt contre working set au second ordre de Fan-Chen-Lin) convergent vers le même optimum dual.

Aspect	From scratch (A.1)	SOTA (B.5)
Ce qu’il livre	le dual lisible : α, b, cache d’erreurs, n_iter mesuré	le classifieur industriel : même optimum, en code C
Ce qu’il enseigne	KKT, complémentarité, pourquoi η ≤ 0 doit se résoudre aux bornes	ce que cache une API minimale (shrinking, cache de noyau, WSS 2nd ordre)
Prix	la colonne temps : un rapport qui se compte en centaines sur cette machine (et jusqu’à ~3·10³ sur la machine de 2.7c)	la colonne LOC inverse : une surface d’appel minimale contre le corps de solveur défini au §2.1 (portées distinctes, cf. notes du tableau)

Points clés :

La colonne itérations compare des compteurs d’unités différentes, nommées dans le tableau : notre SMO compte ses appels à examine_example et ses sous-problèmes 2D réussis, quand LIBSVM compte ses sélections de working set (n_iter_, exposé par sklearn) — chaque itération LIBSVM choisit la meilleure paire par le critère du second ordre (Fan-Chen-Lin), là où la cascade de Platt essaie des candidats jusqu’à en trouver un qui progresse. D’où le contraste apparent des compteurs : ce ne sont pas les mêmes unités.
Le rapport de temps dépend de la machine (le tableau ci-dessus le mesure, la prose ne l’épingle pas) ; ce qui est invariant, c’est sa cause : une boucle Python contre une implémentation C avec cache de noyau et shrinking.
Reproductibilité : la cellule de mesure vérifie par une égalité calculée que les valeurs déterministes de la ligne SMO (D, |SV|, n_iter) coïncident avec la baseline committée de 2.7b sur la même graine — la reprise compacte est fidèle.

3. Famille Lasso : six solveurs, un seul optimum

Le terrain P1 est celui de 2.11b (bloc A.3), 2.11c (B.6) et 2.11e (B.7), repris à l’identique :

Élément	Valeur	Commentaire
Problème	\(\min_x \tfrac{1}{2}\\|Ax - b\\|^2 + \lambda\\|x\\|_1\)	sparse recovery / compressed sensing
Dimensions	`n = 200` mesures, `p = 500` inconnues, `k = 30` non-nuls	ratio n/p = 0.4 — le Lasso est nécessaire
Génération	`A ~ N(0,1)/√n`, support aléatoire (seed 42), bruit gaussien 0.01	reprise exacte de 2.11b (cellule 10)
λ	`5 ×` seuil de Donoho-Johnstone \(\sigma\sqrt{2\log p}/\sqrt{n}\)	compromis biais/variance de 2.11b (cellule 12)
Feature scaling	`A` normalisée par √n à la génération (`A ~ N(0,1)/√n`) ; ni centrage ni réduction supplémentaires ; `fit_intercept=False`	protocole de toute la chaîne 2.11b–e — changer la normalisation changerait le λ équivalent
Convention `sklearn`	`Lasso` minimise \(\tfrac{1}{2n}\\|Ax-b\\|^2 + \alpha\\|x\\|_1\) → `alpha = λ/n`	la conversion est écrite dans chaque appel, jamais implicite

Une précision d’honnêteté sur ADMM : 2.11d (bloc A.2) racontait ADMM sur un autre terrain (design corrélé AR(1), p = 50 — son propos était le conditionnement et le balayage de ρ). Ici, ADMM est rejoué sur P1 pour que sa ligne soit comparable aux cinq autres ; son critère d’arrêt (ε_abs = ε_rel = 10⁻⁴ sur les résidus primal/dual) est inchangé. Comparer des nombres mesurés sur des instances différentes serait exactement la faute que le §1 interdit.

# --- P1 : generation identique a 2.11b (cellule 10) / 2.11c (cellule 2) / 2.11e (cellule 2) ---
n, p, k = 200, 500, 30
noise_level = 0.01
rng = np.random.default_rng(42)
A = rng.standard_normal((n, p)) / np.sqrt(n)
support = rng.choice(p, size=k, replace=False)
x_true = np.zeros(p)
x_true[support] = rng.standard_normal(k)
b = A @ x_true + noise_level * rng.standard_normal(n)

lam_theory = noise_level * np.sqrt(2.0 * np.log(p)) / np.sqrt(n)
lam = 5.0 * lam_theory


def objectif(x):
    """Convention du notebook : 0.5||Ax-b||^2 + lam||x||_1 (identique 2.11b/c/e)."""
    return 0.5 * np.linalg.norm(A @ x - b) ** 2 + lam * np.linalg.norm(x, 1)


print(f"carte d'identite P1 : n={n}, p={p}, k={k} (densite {k/p:.1%}), bruit {noise_level}, seed 42")
print(f"lambda theorique (Donoho-Johnstone) = {lam_theory:.5f} | lambda retenu (5x) = {lam:.5f}")
print(f"||b||_2 = {np.linalg.norm(b):.4f} | normalisation : A/√n a la generation, rien d'autre")

carte d'identite P1 : n=200, p=500, k=30 (densite 6.0%), bruit 0.01, seed 42
lambda theorique (Donoho-Johnstone) = 0.00249 | lambda retenu (5x) = 0.01246
||b||_2 = 7.0591 | normalisation : A/√n a la generation, rien d'autre

3.1 Les six solveurs, repris et comptés

Quatre implémentations sont des reprises compactes des notebooks parents (ISTA/FISTA : 2.11b ; ADMM : 2.11d ; coordinate descent : 2.11c/2.11e) ; les deux lignes SOTA (sklearn.Lasso, cvxpy+CLARABEL) sont des appels. Deux adaptations d’ingénierie, documentées :

ADMM : la version de 2.11d appelait numpy.linalg.solve sur la factorisation — un solveur dense O(p³) par appel, indolore à p = 50, prohibitif à p = 500. Ici la pré-factorisation Cholesky est consommée par scipy.linalg.cho_solve (substitutions triangulaires O(p²)) — c’est le geste « pré-factorisation » de 2.11d, pris au sérieux à l’échelle de P1.
ISTA : la version compacte de 2.11c tourne à budget d’itérations fixe (pas de critère d’arrêt) — la colonne itérations du tableau le dira (« budget fixe »), c’est une limite de la reprise, pas une propriété d’ISTA.

def prox_l1(x, t):
    """Operateur proximal de la norme L1 : soft-thresholding (reprise 2.11b, cellule 3)."""
    return np.sign(x) * np.maximum(np.abs(x) - t, 0.0)


def ista_compact(A, b, lam, n_iter=2000):
    """ISTA : pas de gradient + prox - reprise de 2.11c (cellule 9), budget fixe."""
    L = np.linalg.norm(A, 2) ** 2
    x = np.zeros(A.shape[1])
    for _ in range(n_iter):
        x = prox_l1(x - A.T @ (A @ x - b) / L, lam / L)
    return x


def fista_compact(A, b, lam, n_iter=2000, tol=1e-8):
    """FISTA (Beck & Teboulle 2009, Algo 2.2) - reprise de 2.11b (cellule 8)."""
    L = np.linalg.norm(A, 2) ** 2
    x = np.zeros(A.shape[1])
    y = x.copy()
    t = 1.0
    for it in range(1, n_iter + 1):
        x_new = prox_l1(y - A.T @ (A @ y - b) / L, lam / L)
        t_new = 0.5 * (1.0 + np.sqrt(1.0 + 4.0 * t ** 2))
        y = x_new + ((t - 1.0) / t_new) * (x_new - x)
        if np.max(np.abs(x_new - x)) < tol * (1.0 + np.max(np.abs(x))):
            x = x_new
            break
        x = x_new
        t = t_new
    return x, it


def admm_compact(X, y, lam_, rho, max_iter=500, eps_abs=1e-4, eps_rel=1e-4):
    """ADMM pour min 0.5||Xb - y||^2 + lam||z||_1 s.c. b = z - reprise de 2.11d (cellule 9).

    Adaptation P1 : cho_solve sur la Cholesky pre-factorisee (O(p^2) par iteration),
    au lieu du solveur dense de 2.11d (O(p^3) par appel, indolore a p=50 seulement).
    """
    from scipy.linalg import cho_factor, cho_solve
    p_ = X.shape[1]
    Xty = X.T @ y
    cf = cho_factor(X.T @ X + rho * np.eye(p_), lower=True)
    beta = np.zeros(p_)
    z = np.zeros(p_)
    u = np.zeros(p_)
    eps_p, eps_d = np.sqrt(p_) * eps_abs, np.sqrt(p_) * eps_abs
    z_prev = z.copy()
    for it in range(1, max_iter + 1):
        beta = cho_solve(cf, Xty + rho * (z - u))
        z = prox_l1(beta + u, lam_ / rho)
        u = u + beta - z
        r_p = np.linalg.norm(beta - z)
        r_d = rho * np.linalg.norm(z - z_prev)
        tol_p = eps_p + eps_rel * max(np.linalg.norm(beta), np.linalg.norm(z))
        tol_d = eps_d + eps_rel * rho * np.linalg.norm(u)
        if r_p < tol_p and r_d < tol_d:
            break
        z_prev = z.copy()
    return beta, z, it


def lasso_cd(A, b, lam, max_iter=2000, tol=1e-6):
    """Coordinate descent pour min 0.5||Ax-b||^2 + lam||x||_1 - reprise de 2.11c (cellule 4)."""
    p_ = A.shape[1]
    x = np.zeros(p_)
    r = b - A @ x
    Asq = np.einsum('ij,ij->j', A, A)
    obj_local = lambda xx: 0.5 * np.linalg.norm(A @ xx - b) ** 2 + lam * np.abs(xx).sum()
    histo = []
    for it in range(1, max_iter + 1):
        for j in range(p_):
            r += A[:, j] * x[j]
            z = A[:, j] @ r
            x[j] = np.sign(z) * max(abs(z) - lam, 0.0) / max(Asq[j], 1e-12)
            r -= A[:, j] * x[j]
        histo.append(obj_local(x))
        if len(histo) > 1 and abs(histo[-1] - histo[-2]) <= tol * (1 + abs(histo[-1])):
            break
    return x, it


# auto-controle leger : le prox sur un vecteur connu (reponse attendue : [-1, 0, 2])
print(f"auto-controle prox_l1([-2, -0.5, 3], 1) = {prox_l1(np.array([-2.0, -0.5, 3.0]), 1.0).tolist()}")
print(f"brique partagee prox_l1 : {count_loc(prox_l1)} LOC (comptee dans chaque solveur qui l'appelle)")
for f in (ista_compact, fista_compact, admm_compact, lasso_cd):
    briques = count_loc(prox_l1) if f is not lasso_cd else 0
    print(f"{f.__name__:15s} : {count_loc(f):3d} LOC (+{briques} brique{'s' if briques else ''}) "
          f"= {count_loc(f) + briques} au total (introspection)")

auto-controle prox_l1([-2, -0.5, 3], 1) = [-1.0, -0.0, 2.0]
brique partagee prox_l1 : 2 LOC (comptee dans chaque solveur qui l'appelle)
ista_compact    :   6 LOC (+2 briques) = 8 au total (introspection)
fista_compact   :  15 LOC (+2 briques) = 17 au total (introspection)
admm_compact    :  22 LOC (+2 briques) = 24 au total (introspection)
lasso_cd        :  17 LOC (+0 brique) = 17 au total (introspection)

3.2 La mesure : six runs dans le même processus

Protocole : chaque solveur est exécuté 3 fois, on rapporte la médiane (les runtimes vont de quelques millisecondes à quelques centaines de millisecondes — la médiane amortit les à-coups de l’OS sans masquer les ordres de grandeur). Les itérations sont relevées telles que chaque algorithme les compte : passes FISTA, itérations ADMM (résidus), epochs CD (balayages complets des p coordonnées), itérations internes sklearn et CLARABEL.

from sklearn.linear_model import Lasso


def med_time(fn, reps=3):
    ts, out = [], None
    for _ in range(reps):
        t0 = time.perf_counter()
        out = fn()
        ts.append(time.perf_counter() - t0)
    return float(np.median(ts)), out


def solve_cvx():
    xv = cp.Variable(p)
    pr = cp.Problem(cp.Minimize(0.5 * cp.sum_squares(A @ xv - b) + lam * cp.norm1(xv)))
    pr.solve(solver=cp.CLARABEL)
    return np.asarray(xv.value).flatten(), pr.solver_stats.num_iters


t_ista, x_ista = med_time(lambda: ista_compact(A, b, lam))
t_fista, (x_fista, it_fista) = med_time(lambda: fista_compact(A, b, lam))
t_admm, (beta_a, z_a, it_admm) = med_time(lambda: admm_compact(A, b, lam, rho=1.0))
t_cd, (x_cd, it_cd) = med_time(lambda: lasso_cd(A, b, lam))
t_skl, skl = med_time(lambda: Lasso(alpha=lam / n, fit_intercept=False,
                                    max_iter=2000, tol=1e-8).fit(A, b))
x_skl = skl.coef_.copy()
t_cvx, (x_cvx, it_cvx) = med_time(solve_cvx)
x_admm = z_a                      # la parcimonie vit dans z (cf. docstring 2.11d)
f_star = objectif(x_cvx)

for nom, x, t, it in [
        ('ISTA maison (A.3)', x_ista, t_ista, '2000 (budget fixe)'),
        ('FISTA maison (A.3)', x_fista, t_fista, f'{it_fista} (tol 1e-8)'),
        ('ADMM maison (A.2)', x_admm, t_admm, f'{it_admm} (eps 1e-4)'),
        ('CD maison (B.6)', x_cd, t_cd, f'{it_cd} epochs (tol 1e-6)'),
        ('sklearn Lasso (B.6)', x_skl, t_skl, f'{skl.n_iter_} (tol 1e-8)'),
        ('cvxpy CLARABEL (B.7)', x_cvx, t_cvx, f'{it_cvx} (point interieur)')]:
    print(f"{nom:22s} : objectif = {objectif(x):.6f}, ecart f* = {objectif(x) - f_star:+.2e}, "
          f"||x - x_cvx|| = {np.linalg.norm(x - x_cvx):.2e}, "
          f"|x|_0 = {int(np.sum(np.abs(x) > 1e-6)):3d}, temps = {t:.4f} s, iter = {it}")
print(f"\nf* (cvxpy CLARABEL, reference numerique - pas un optimum certifie) = {f_star:.6f}")

ISTA maison (A.3)      : objectif = 0.360645, ecart f* = -2.79e-09, ||x - x_cvx|| = 4.63e-05, |x|_0 =  91, temps = 0.0793 s, iter = 2000 (budget fixe)
FISTA maison (A.3)     : objectif = 0.360645, ecart f* = -2.79e-09, ||x - x_cvx|| = 4.66e-05, |x|_0 =  91, temps = 0.0410 s, iter = 714 (tol 1e-8)
ADMM maison (A.2)      : objectif = 0.360650, ecart f* = +4.72e-06, ||x - x_cvx|| = 7.25e-03, |x|_0 =  91, temps = 0.0532 s, iter = 109 (eps 1e-4)
CD maison (B.6)        : objectif = 0.360646, ecart f* = +1.17e-06, ||x - x_cvx|| = 3.89e-03, |x|_0 =  92, temps = 0.2215 s, iter = 82 epochs (tol 1e-6)
sklearn Lasso (B.6)    : objectif = 0.360645, ecart f* = -2.79e-09, ||x - x_cvx|| = 4.63e-05, |x|_0 =  91, temps = 0.0060 s, iter = 116 (tol 1e-8)
cvxpy CLARABEL (B.7)   : objectif = 0.360645, ecart f* = +0.00e+00, ||x - x_cvx|| = 0.00e+00, |x|_0 =  93, temps = 0.4100 s, iter = 12 (point interieur)

f* (cvxpy CLARABEL, reference numerique - pas un optimum certifie) = 0.360645

3.3 Le tableau famille Lasso

# LOC maison : corps du solveur + briques appelees (prox_l1 pour ISTA/FISTA/ADMM)
LOC_PROX = count_loc(prox_l1)
lasso_rows = [
    ('ISTA maison', 'A.3', objectif(x_ista), int(np.sum(np.abs(x_ista) > 1e-6)),
     float(np.linalg.norm(x_ista - x_cvx)), t_ista, '2000 (budget fixe)',
     count_loc(ista_compact) + LOC_PROX),
    ('FISTA maison', 'A.3', objectif(x_fista), int(np.sum(np.abs(x_fista) > 1e-6)),
     float(np.linalg.norm(x_fista - x_cvx)), t_fista, f'{it_fista} (tol 1e-8)',
     count_loc(fista_compact) + LOC_PROX),
    ('ADMM maison', 'A.2', objectif(x_admm), int(np.sum(np.abs(x_admm) > 1e-6)),
     float(np.linalg.norm(x_admm - x_cvx)), t_admm, f'{it_admm} (eps 1e-4)',
     count_loc(admm_compact) + LOC_PROX),
    ('CD maison', 'B.6', objectif(x_cd), int(np.sum(np.abs(x_cd) > 1e-6)),
     float(np.linalg.norm(x_cd - x_cvx)), t_cd, f'{it_cd} epochs (tol 1e-6)',
     count_loc(lasso_cd)),
    ('sklearn Lasso', 'B.6', objectif(x_skl), int(np.sum(np.abs(x_skl) > 1e-6)),
     float(np.linalg.norm(x_skl - x_cvx)), t_skl, f'{skl.n_iter_} (tol 1e-8)', 2),
    ('cvxpy CLARABEL', 'B.7', objectif(x_cvx), int(np.sum(np.abs(x_cvx) > 1e-6)),
     0.0, t_cvx, f'{it_cvx} (point int.)', 3),
]

W = 116
print("=" * W)
print("FAMILLE LASSO - P1 (n=200, p=500, k=30, seed 42), lam = 5x Donoho-Johnstone, A ~ N(0,1)/sqrt(n)")
print("=" * W)
print(f"{'solveur':<20}{'bloc':>5}{'objectif final':>15}{'ecart a f*':>12}{'||x-x_cvx||':>13}{'|x|_0':>7}"
      f"{'temps':>11}{'iterations':>24}{'LOC':>6}")
print("-" * W)
for nom, bloc, obj, nz, dist, t, it, loc in lasso_rows:
    t_str = f"{t:.4f} s"
    print(f"{nom:<20}{bloc:>5}{obj:>15.6f}{obj - f_star:>+12.2e}{dist:>13.2e}{nz:>7}"
          f"{t_str:>11}{it:>24}{loc:>6}")
print("-" * W)

# certificat KKT de la coordinate descent (geste de 2.11c, cellule 4)
r_cd = b - A @ x_cd
corr = np.abs(A.T @ r_cd)
kkt_max = corr[np.abs(x_cd) < 1e-8].max()
print(f"certificat KKT (CD) : max |A_j^T r| hors support = {kkt_max:.2e} <= lam = {lam:.2e} : {kkt_max <= lam}")
print("notes : f* = reference NUMERIQUE (CLARABEL, a sa tolerance de point interieur),")
print("        pas un optimum certifie - l'ecart negatif des iteratives le montre.")
print("        LOC : portees distinctes - maison = corps + briques (prox_l1 comptee dans")
print("        ISTA/FISTA/ADMM) ; bibliotheque = surface d'appel (sklearn 2, cvxpy 3).")
print("        ADMM rejoue sur P1 (son terrain natif, 2.11d, etait un design corrélé p=50).")
print("        protocole temps : mediane de 3 runs, meme processus.")

====================================================================================================================
FAMILLE LASSO - P1 (n=200, p=500, k=30, seed 42), lam = 5x Donoho-Johnstone, A ~ N(0,1)/sqrt(n)
====================================================================================================================
solveur              bloc objectif final  ecart a f*  ||x-x_cvx||  |x|_0      temps              iterations   LOC
--------------------------------------------------------------------------------------------------------------------
ISTA maison           A.3       0.360645   -2.79e-09     4.63e-05     91   0.0793 s      2000 (budget fixe)     8
FISTA maison          A.3       0.360645   -2.79e-09     4.66e-05     91   0.0410 s          714 (tol 1e-8)    17
ADMM maison           A.2       0.360650   +4.72e-06     7.25e-03     91   0.0532 s          109 (eps 1e-4)    24
CD maison             B.6       0.360646   +1.17e-06     3.89e-03     92   0.2215 s    82 epochs (tol 1e-6)    17
sklearn Lasso         B.6       0.360645   -2.79e-09     4.63e-05     91   0.0060 s          116 (tol 1e-8)     2
cvxpy CLARABEL        B.7       0.360645   +0.00e+00     0.00e+00     93   0.4100 s         12 (point int.)     3
--------------------------------------------------------------------------------------------------------------------
certificat KKT (CD) : max |A_j^T r| hors support = 1.23e-02 <= lam = 1.25e-02 : True
notes : f* = reference NUMERIQUE (CLARABEL, a sa tolerance de point interieur),
        pas un optimum certifie - l'ecart negatif des iteratives le montre.
        LOC : portees distinctes - maison = corps + briques (prox_l1 comptee dans
        ISTA/FISTA/ADMM) ; bibliotheque = surface d'appel (sklearn 2, cvxpy 3).
        ADMM rejoue sur P1 (son terrain natif, 2.11d, etait un design corrélé p=50).
        protocole temps : mediane de 3 runs, meme processus.

Lecture : un optimum, six certificats

Sortie obtenue : les six objectifs se resserrent autour d’un f* unique — ISTA, FISTA et sklearn au milliardième près, avec un écart négatif qui montre que la référence numérique cvxpy n’est pas l’optimum exact (CLARABEL s’arrête à sa propre tolérance de point intérieur) ; CD et ADMM au millionième. La propriété fondatrice de la convexité est là : tous les chemins mènent au même optimum, seule la tarification diffère.

Observation	Valeur mesurée (déterministe, seedée)	Lecture
Accord des objectifs	écarts à f* ~10⁻⁹ pour ISTA, FISTA, sklearn (négatifs) ; ~10⁻⁶ pour CD et ADMM	les itératives descendent ~10⁻⁹ sous la référence : `f` est une référence numérique, pas un optimum certifié ; CD s’arrête sur la variation* d’objectif (tol 10⁻⁶), ADMM sur ses résidus (ε = 10⁻⁴) — des contrats moins stricts, assumés et nommés
Distance en solution	‖x − x_cvx‖ ~10⁻⁵ pour ISTA, FISTA, sklearn ; ~10⁻³ pour ADMM et CD	l’objectif du Lasso est plat près de l’optimum : un écart de solution de 10⁻³ ne coûte que 10⁻⁶ d’objectif — comparer des solveurs sur la seule distance en solution surestimerait leur désaccord
Itérations	FISTA ~700 contre ISTA 2000 (budget) ; ADMM ~100 ; CD ~80 epochs ; CLARABEL ~10	l’inertie de Nesterov paie (FISTA atteint la tolérance avant le budget) ; un point intérieur converge en très peu d’itérations mais chacune est plus chère
Parcimonie	91 non-nuls pour ISTA, FISTA, ADMM et sklearn ; 92 pour CD ; 93 pour CLARABEL	artefacts de seuil : CLARABEL laisse des coordonnées ~10⁻⁷ que les proximaux rament exactement à zéro — même solution, coupure différente
Temps	sklearn le plus rapide des six ; cvxpy paie la reformulation canonique (2.11e §3 : 500 inconnues → 1200 variables coniques)	chaque ligne du tableau porte la structure de coût de son algorithme

Points clés :

La colonne écart à f* compare à une référence numérique, pas à un optimum certifié : cvxpy résout le problème déclarativement à SA tolérance de point intérieur près — l’écart négatif mesuré des itératives (−2.8·10⁻⁹) en est la preuve visible. Sans référence commune, comparer des solveurs reviendrait à comparer des vitesses vers des destinations inconnues.
La colonne distance en solution raconte une histoire plus fine que l’objectif : l’optimum plat du Lasso amortit les écarts de solution — c’est pourquoi ADMM (ε = 10⁻⁴) rend une solution à ~10⁻³ de la référence avec un objectif au millionième.
La colonne itérations compare des choux et des carottes si on ne nomme pas l’unité : un epoch CD balaie p = 500 coordonnées, une itération ADMM résout un système linéaire, une itération CLARABEL factorise — le tableau nomme l’unité de chaque ligne, et c’est pour ça qu’elles ne s’additionnent pas.
Le certificat KKT de la coordinate descent (corrélations résiduelles sous λ hors support) est le langage commun des six solveurs : c’est la condition d’optimalité du problème, indépendante de l’algorithme qui l’atteint.

4. La capacité à scaler, mesurée

La colonne « capacité à scaler » du récapitulatif B.8 ne se déclare pas : elle se mesure. Deux sondes, une par famille — chacune garde le contrat du §1 (même générateur, mêmes conventions) et ne fait croître qu’une dimension à la fois.

4.1 SVM : `n` croissant

n_total ∈ {200, 400, 800} (split 30 % inchangé). Ce qui doit croître : le coût du noyau (O(n²) en mémoire), le nombre d’exemples à balayer par passe, et le nombre d’itérations de SMO.

# --- sonde SVM : n croissant, meme generateur, memes hyperparametres ---
svm_scale = []
for n_tot in [200, 400, 800]:
    X_s, y_pm_s = make_moons(n_samples=n_tot, noise=0.25, random_state=42)
    y_s = np.where(y_pm_s == 0, -1.0, 1.0)
    Xtr_s, Xte_s, ytr_s, yte_s = train_test_split(X_s, y_s, test_size=0.30,
                                                  random_state=42, stratify=y_s)
    t0 = time.perf_counter()
    m_s = smo_fit(Xtr_s, ytr_s, C=C, gamma=GAMMA, tol=TOL, max_passes=20)
    t_smo_s = time.perf_counter() - t0

    t0 = time.perf_counter()
    clf_s = SVC(C=C, kernel='rbf', gamma=GAMMA, tol=TOL, max_iter=20000).fit(Xtr_s, ytr_s)
    t_skl_s = time.perf_counter() - t0
    itl_s = int(np.sum(clf_s.n_iter_))

    svm_scale.append((n_tot, m_s['n_iter'], m_s['n_steps'], int(m_s['support_mask'].sum()),
                      int(clf_s.n_support_.sum()), itl_s, t_smo_s, t_skl_s))
    print(f"n_total={n_tot:4d} (train {len(ytr_s):3d}) : SMO {t_smo_s:6.2f} s, "
          f"n_iter = {m_s['n_iter']:6d}, pas 2D = {m_s['n_steps']:6d}, "
          f"|SV| = {m_s['support_mask'].sum():3d}  |  "
          f"SVC {t_skl_s * 1e3:6.2f} ms, n_iter_ = {itl_s:5d}, |SV| = {clf_s.n_support_.sum():3d}, "
          f"meme |SV| : {int(m_s['support_mask'].sum()) == int(clf_s.n_support_.sum())}")
print("\nlecture preparee : les compteurs SMO croissent avec n ; les temps mesures fluctuent")
print("a petite taille mais leur ordre de grandeur augmente. LIBSVM reste de l'ordre de la")
print("milliseconde (unites d'iterations distinctes, cf. notes du tableau S2.3).")

n_total= 200 (train 140) : SMO   0.18 s, n_iter =  21560, pas 2D =   1678, |SV| =  48  |  SVC   0.90 ms, n_iter_ =   102, |SV| =  48, meme |SV| : True
n_total= 400 (train 280) : SMO   0.15 s, n_iter =  32480, pas 2D =   1452, |SV| =  75  |  SVC   1.28 ms, n_iter_ =   100, |SV| =  75, meme |SV| : True
n_total= 800 (train 560) : SMO   0.86 s, n_iter = 173040, pas 2D =   3318, |SV| = 114  |  SVC   2.53 ms, n_iter_ =   133, |SV| = 114, meme |SV| : True

lecture preparee : les compteurs SMO croissent avec n ; les temps mesures fluctuent
a petite taille mais leur ordre de grandeur augmente. LIBSVM reste de l'ordre de la
milliseconde (unites d'iterations distinctes, cf. notes du tableau S2.3).

4.2 Lasso : `p` croissant, budgets d’itérations fixés

p ∈ {500, 2000, 4000} à n = 200 fixé, budgets d’itérations fixés (ISTA 300 itérations, CD 50 epochs, sklearn max 2000/tol 10⁻⁶) — protocole de 2.11c §5. Attention à la lecture : à budget fixé, les solveurs n’atteignent pas tous l’optimum, la sonde mesure le coût par unité de travail, pas la convergence.

# --- sonde Lasso : p croissant, protocole iso-budgets de 2.11c (section 5) ---
import sys
rng_probe = np.random.default_rng(0)
lasso_scale = []
for p_ in [500, 2000, 4000]:
    A_ = rng_probe.standard_normal((n, p_)) / np.sqrt(n)
    supp_ = rng_probe.choice(p_, size=k, replace=False)
    xt_ = np.zeros(p_)
    xt_[supp_] = rng_probe.standard_normal(k)
    b_ = A_ @ xt_ + noise_level * rng_probe.standard_normal(n)
    lam_ = 5.0 * noise_level * np.sqrt(2.0 * np.log(p_)) / np.sqrt(n)

    t0 = time.perf_counter()
    L_ = np.linalg.norm(A_, 2) ** 2
    x_i = np.zeros(p_)
    for _ in range(300):
        x_i = prox_l1(x_i - A_.T @ (A_ @ x_i - b_) / L_, lam_ / L_)
    t_ista_ = time.perf_counter() - t0

    t0 = time.perf_counter()
    xcd_ = np.zeros(p_)
    r_ = b_ - A_ @ xcd_
    Asq_ = np.einsum('ij,ij->j', A_, A_)
    for _ in range(50):
        for j in range(p_):
            r_ += A_[:, j] * xcd_[j]
            z_ = A_[:, j] @ r_
            xcd_[j] = np.sign(z_) * max(abs(z_) - lam_, 0.0) / max(Asq_[j], 1e-12)
            r_ -= A_[:, j] * xcd_[j]
    t_cd_ = time.perf_counter() - t0

    t0 = time.perf_counter()
    s_ = Lasso(alpha=lam_ / n, fit_intercept=False, max_iter=2000, tol=1e-6).fit(A_, b_)
    t_skl_ = time.perf_counter() - t0

    lasso_scale.append((p_, t_ista_, t_cd_, t_skl_, int(s_.n_iter_)))
    print(f"p={p_:5d} : ISTA {t_ista_:6.3f} s (300 iter) | CD maison {t_cd_:6.3f} s (50 epochs) | "
          f"sklearn {t_skl_:6.3f} s (n_iter_ = {s_.n_iter_})")
    sys.stdout.flush()
print("\nlecture preparee : budgets FIXES (pas l'optimum atteint) - la sonde mesure le cout")
print("par unite de travail : ISTA paie un produit matrice-vecteur par iteration, CD paie la")
print("boucle Python par coordonnee, sklearn paie ses iterations adaptatives (n_iter_ croit avec p).")

p=  500 : ISTA  0.020 s (300 iter) | CD maison  0.127 s (50 epochs) | sklearn  0.002 s (n_iter_ = 71)
p= 2000 : ISTA  0.106 s (300 iter) | CD maison  0.638 s (50 epochs) | sklearn  0.032 s (n_iter_ = 205)
p= 4000 : ISTA  0.506 s (300 iter) | CD maison  1.097 s (50 epochs) | sklearn  0.367 s (n_iter_ = 1250)

lecture preparee : budgets FIXES (pas l'optimum atteint) - la sonde mesure le cout
par unite de travail : ISTA paie un produit matrice-vecteur par iteration, CD paie la
boucle Python par coordonnee, sklearn paie ses iterations adaptatives (n_iter_ croit avec p).

Lecture des sondes : chaque structure de coût se voit

SVM, n croissant — la sortie ci-dessus montre le piège classique du from scratch : doubler n ne double pas le coût, il le multiplie — le n_iter de SMO explose (de ~2·10⁴ à ~1,7·10⁵ mesuré entre n = 200 et n = 800, déterministe) parce que chaque passe balaye plus d’exemples et qu’il faut plus de pas ; chaque pas coûte O(n) sur le cache d’erreurs ; et le noyau O(n²) grossit en mémoire. LIBSVM reste de l’ordre de la milliseconde (temps mesurés ci-dessus) : code C, working set au second ordre qui choisit les deux meilleures variables au lieu d’en essayer, shrinking qui gèle les α stabilisés — ses itérations (n_iter_, imprimées par la sonde) suivent n sans exploser (elles restent dans la même centaine quand la cascade passe de ~2·10⁴ à ~1,7·10⁵ d’essais), chaque unité étant un pas 2D choisi, pas un essai. Les |SV| des deux solveurs restent identiques à chaque taille — le certificat croisé tient à toutes les échelles sondées.

Lasso, p croissant — trois structures de coût distinctes, lisibles en ordre de grandeur (la sonde est courte : ses temps varient d’une exécution à l’autre — effets cache/BLAS sur des matrices qui sortent du cache L2 — seuls les compteurs déterministes sont stables d’un run à l’autre). ISTA (vectorisé) paie ~un produit matrice-vecteur 2np par itération : à budget d’itérations fixe, son coût théorique est ∝ p, et la mesure le suit en ordre de grandeur — mais pas au mot près (super-linéaire sur un run, quasi plat entre deux tailles sur un autre : la sonde identifie des échelles, pas des exposants). La coordinate descent maison paie le facteur constant Python (une boucle interprétée par coordonnée) : croissance régulière avec p, cohérente avec un coût ∝ p par epoch, à pente bien plus raide qu’ISTA — tel qu’attendu. sklearn part très en dessous des deux à petit p, mais son n_iter_ déterministe grimpe fortement avec p (71 → 205 → 1250 mesuré aux trois tailles) : l’arrêt adaptatif travaille plus quand p croît, et aux grandes tailles son avance sur les boucles maison se referme — c’est le seul des trois dont le budget s’adapte au problème.

Ce que les sondes ne mesurent pas : cvxpy (2.11e §9 l’a fait : la reformulation conique paie sa généralité à l’échelle) et ADMM à p croissant — c’est l’objet de l’exercice 3.

5. Le tableau récapitulatif — bloc A contre bloc B (le livrable B.8)

Le tableau demandé par le body de l’issue (§ Bloc B, point 8) est assemblé depuis les mesures des §2–§4 : chaque valeur affichée provient d’une variable mesurée dans ce notebook, aucune n’est recopiée. Les deux familles restent dans deux panneaux séparés — rappel du §1 : leurs objectifs ne sont pas dans la même unité.

W = 112
sep = "=" * W
print(sep)
print("RECAPITULATIF B.8 - bloc A (from scratch) vs bloc B (SOTA) - mesure unique, meme processus")
print(sep)
print()
print("PANEL 1 - FAMILLE SVM : make_moons(200, seed 42), C=1.0, gamma=2.0, tol=1e-3, features brutes")
print("-" * W)
print(f"{'solveur':<22}{'bloc':>5}{'objectif D(a)':>15}{'gap P-D':>10}{'temps':>12}{'iterations':>26}{'LOC':>6}")
for nom, bloc, D, gap, acc, nsv, t, it, loc in svm_rows:
    t_str = f"{t:.2f} s" if t > 0.1 else f"{t * 1e3:.2f} ms"
    print(f"{nom:<22}{bloc:>5}{D:>15.4f}{gap:>10.1e}{t_str:>12}{it:>26}{loc:>6}")
print()
print("PANEL 2 - FAMILLE LASSO : P1 (n=200, p=500, k=30, seed 42), lam=5xDJ, A ~ N(0,1)/sqrt(n)")
print("-" * W)
print(f"{'solveur':<22}{'bloc':>5}{'objectif':>13}{'ecart f*':>11}{'temps':>12}{'iterations':>26}{'LOC':>6}")
for nom, bloc, obj, nz, dist, t, it, loc in lasso_rows:
    t_str = f"{t:.4f} s"
    print(f"{nom:<22}{bloc:>5}{obj:>13.6f}{obj - f_star:>+11.2e}{t_str:>12}{it:>26}{loc:>6}")
print()
print("CAPACITE A SCALER (sondes mesurees au S4, memes generateurs/conventions)")
print("-" * W)
for (n_tot, it_s, st_s, nsv_s, nsv_l, itl_s, t_s, t_l) in svm_scale:
    print(f"SVM n={n_tot:4d} : SMO n_iter {it_s:6d}, {st_s:6d} pas ({t_s:6.2f} s) | "
          f"LIBSVM n_iter_ {itl_s:5d} ({t_l * 1e3:5.2f} ms) | meme |SV| ({nsv_l}) : {nsv_s == nsv_l}")
for (p_, t_i_, t_c_, t_s_, ni_) in lasso_scale:
    print(f"Lasso p={p_:4d} : ISTA {t_i_:6.3f} s (300) | CD maison {t_c_:6.3f} s (50 ep) | "
          f"sklearn {t_s_:6.3f} s (n_iter_ {ni_})")
print()
print("legendes : unites d'iterations NON homogenes - SMO : appels a examine_example / pas 2D ;")
print("LIBSVM : n_iter_ (selections de working set) ; ISTA : budget fixe (reprise sans critere")
print("d'arret) ; ADMM : residus primal/dual ; CD : epochs (p coordonnees par epoch) ;")
print("LOC : portees distinctes - maison = corps defini ici + briques appelees ; bibliotheque =")
print("surface d'appel (sklearn, cvxpy - cf. colonne LOC), jamais")
print("l'implementation interne.")

================================================================================================================
RECAPITULATIF B.8 - bloc A (from scratch) vs bloc B (SOTA) - mesure unique, meme processus
================================================================================================================

PANEL 1 - FAMILLE SVM : make_moons(200, seed 42), C=1.0, gamma=2.0, tol=1e-3, features brutes
----------------------------------------------------------------------------------------------------------------
solveur                bloc  objectif D(a)   gap P-D       temps                iterations   LOC
SMO Platt maison        A.1        30.3960   3.3e-03      0.23 s      21560 ex. / 1678 pas    74
LIBSVM via SVC          B.5        30.3961   2.0e-03     0.62 ms         102 (working set)     2

PANEL 2 - FAMILLE LASSO : P1 (n=200, p=500, k=30, seed 42), lam=5xDJ, A ~ N(0,1)/sqrt(n)
----------------------------------------------------------------------------------------------------------------
solveur                bloc     objectif   ecart f*       temps                iterations   LOC
ISTA maison             A.3     0.360645  -2.79e-09    0.0793 s        2000 (budget fixe)     8
FISTA maison            A.3     0.360645  -2.79e-09    0.0410 s            714 (tol 1e-8)    17
ADMM maison             A.2     0.360650  +4.72e-06    0.0532 s            109 (eps 1e-4)    24
CD maison               B.6     0.360646  +1.17e-06    0.2215 s      82 epochs (tol 1e-6)    17
sklearn Lasso           B.6     0.360645  -2.79e-09    0.0060 s            116 (tol 1e-8)     2
cvxpy CLARABEL          B.7     0.360645  +0.00e+00    0.4100 s           12 (point int.)     3

CAPACITE A SCALER (sondes mesurees au S4, memes generateurs/conventions)
----------------------------------------------------------------------------------------------------------------
SVM n= 200 : SMO n_iter  21560,   1678 pas (  0.18 s) | LIBSVM n_iter_   102 ( 0.90 ms) | meme |SV| (48) : True
SVM n= 400 : SMO n_iter  32480,   1452 pas (  0.15 s) | LIBSVM n_iter_   100 ( 1.28 ms) | meme |SV| (75) : True
SVM n= 800 : SMO n_iter 173040,   3318 pas (  0.86 s) | LIBSVM n_iter_   133 ( 2.53 ms) | meme |SV| (114) : True
Lasso p= 500 : ISTA  0.020 s (300) | CD maison  0.127 s (50 ep) | sklearn  0.002 s (n_iter_ 71)
Lasso p=2000 : ISTA  0.106 s (300) | CD maison  0.638 s (50 ep) | sklearn  0.032 s (n_iter_ 205)
Lasso p=4000 : ISTA  0.506 s (300) | CD maison  1.097 s (50 ep) | sklearn  0.367 s (n_iter_ 1250)

legendes : unites d'iterations NON homogenes - SMO : appels a examine_example / pas 2D ;
LIBSVM : n_iter_ (selections de working set) ; ISTA : budget fixe (reprise sans critere
d'arret) ; ADMM : residus primal/dual ; CD : epochs (p coordonnees par epoch) ;
LOC : portees distinctes - maison = corps defini ici + briques appelees ; bibliotheque =
surface d'appel (sklearn, cvxpy - cf. colonne LOC), jamais
l'implementation interne.

Lecture du récapitulatif : pourquoi le from scratch, quand le SOTA

Le fait central des deux panneaux : dans chaque famille, les lignes bloc A et bloc B atteignent le même optimum (D(α) identiques à 10⁻⁵ près côté SVM, écart chiffré au §2 ; objectifs identiques au millionième près côté Lasso, à tolérances nommées près). Le SOTA n’achète donc pas une meilleure solution — sur un problème convexe, l’optimum est l’optimum. La lecture du tableau devient alors honnête :

la colonne temps mesure ce que le SOTA achète : des ordres de grandeur de vitesse (code C, algèbre optimisée, structures de cache) ;
la colonne LOC mesure ce que le SOTA épargne : les dizaines de lignes mesurées au §2/§3 (corps de solveur défini au notebook, briques incluses) contre une surface d’appel minimale — deux portées étiquetées, non comparables en empreinte d’implémentation, comparables seulement comme « ce qu’il faut écrire » — mais la colonne dit aussi ce que le from scratch rend visible : α, le cache d’erreurs, les résidus primal/dual, et la granularité fine des compteurs (essais contre pas réussis) là où l’API n’en rend qu’un seul, déjà interprété ;
la colonne itérations enseigne les structures algorithmiques : un point intérieur converge en ~10 itérations coûteuses, FISTA divise le budget d’ISTA par inertie, ADMM échange précision (sa ε) contre découplage — c’est le cours d’optimisation, lu sur des compteurs ;
les sondes du §4 donnent la règle de décision : quand n ou p croît, la boucle Python paie un facteur qui empire (n_iter explosif côté SMO, pente raide côté CD) — le SOTA est le geste de production, le from scratch est le geste de compréhension.

6. Pourquoi le from scratch, quand le SOTA — la division du travail

	Bloc A — from scratch	Bloc B — SOTA
Ce qu’il achète	la compréhension : dualité et KKT mesurables (gap, violations), opérateur proximal comme brique, trajectoires de convergence observables, compteur d’itérations ouvert	la production : vitesse (code C, BLAS), robustesse (working set 2nd ordre, shrinking, warm start), échelle, maintenance communautaire
Ce qu’il ne peut pas	rivaliser en vitesse ; passer à l’échelle sans réécriture ; garantir les dizaines d’heures de durcissement d’une bibliothèque	ouvrir la granularité interne (essais contre pas 2D réussis, cache d’erreurs) ; enseigner pourquoi η ≤ 0 se résoud aux bornes ; s’adapter à une formulation non standard sans attendre la lib
Quand l’écrire	recherche, enseignement, diagnostic (« pourquoi mon Lasso ne sélectionne-t-il pas ? »), formulation exotique (contraintes customs, group lasso maison)	tout le reste — et en particulier les gros problèmes, où son écart de vitesse devient la différence entre faisable et pas faisable

Le couplage des deux blocs est la vraie leçon : chaque notebook SOTA de la chaîne (2.7c, 2.11c, 2.11e) a certifié son from scratch (même optimum, même support, gap mesuré sur la solution de la bibliothèque), et chaque from scratch a ouvert son SOTA (dual reconstruit, moteur de sklearn réécrit, récit d’itérations du solveur conique). Le tableau B.8 est la forme finale de ce couplage : deux blocs qui se certifient mutuellement n’ont pas à se battre pour la même place.

7. Exercices

Trois exercices, tous sur le terrain P1 et les conventions du §1 — chaque stub s’exécute sans erreur (renvoie None) tant qu’il n’est pas complété.

Exercice 1 — α = λ/n : le prix d’une normalisation oubliée

La conversion alpha = lam/n est le genre de détail qui ruine une comparaison : sklearn minimise \(\tfrac{1}{2n}\|Ax-b\|^2 + \alpha\|x\|_1\), donc passer alpha=lam résout un autre problème (régularisation n fois plus forte dans notre convention).

Objectif : mesurer l’écart entre la faute (alpha=lam) et la version correcte (alpha=lam/n) — objectif final dans la convention du notebook, |x|_0, écart à f* — et constater que le solveur « fautif » n’a pas échoué : il a convergé, ailleurs.

Étape 1 : entraîner les deux Lasso (mêmes max_iter et tol qu’au §3.2).

Étape 2 : évaluer chaque solution avec objectif() dans la convention du notebook.

Indice : comparer les |x|_0 montre la régularisation excessive ; lire l’écart d’objectif contre f_star. Le solveur fautif résout un problème différent : son objectif peut même être supérieur à celui du solveur correct dans notre convention.

def exercice_1_normalisation_sklearn(A, b, lam, n, f_star=None):
    """Exercice 1 - mesurer le prix d'une normalisation oubliee (alpha = lam/n).

    Retour attendu : dict {'alpha_faute': {...}, 'alpha_ok': {...}} avec pour chaque
    solution : objectif (convention du notebook), |x|_0, ecart a f_star. None tant
    que l'exercice n'est pas complete.
    """
    result = None  # TODO etudiant : remplacer par la mesure decrite dans l'enonce
    return result


print("Exercice a completer : exercice_1_normalisation_sklearn(A, b, lam, n, f_star=f_star)")

Exercice a completer : exercice_1_normalisation_sklearn(A, b, lam, n, f_star=f_star)

Exercice 2 — le budget de tolérance : ce que chaque décimale coûte

Le §3 a figé tol = 1e-8 pour sklearn. Chaque décimale de tolérance s’achète en itérations — et donc en temps. C’est le miroir Lasso du balayage de tol de 2.7c (section 5), côté SVM.

Objectif : balayer tol ∈ {1e-4, 1e-6, 1e-8} pour Lasso(alpha=lam/n), mesurer à chaque tolérance le temps, n_iter_, l’objectif et l’écart à f*, et repérer le point où une décimale supplémentaire n’achète plus rien.

Étape 1 : ajuster un Lasso pour chaque tolérance ; med_time du §3.2 est réutilisable.

Étape 2 : imprimer un mini-tableau : temps, n_iter_ et écart à f*.

Indice : à tolérance grossière, l’arrêt arrive avant l’optimum ; l’écart à f_star le mesure, contrairement au statut de convergence retourné par sklearn.

def exercice_2_sweep_tolerances(A, b, lam, n, tols=(1e-4, 1e-6, 1e-8), f_star=None):
    """Exercice 2 - le compromis tolerance / temps / precision, mesure.

    Retour attendu : liste de dict (un par tol) avec tol, temps, n_iter_, objectif,
    ecart a f_star. None tant que l'exercice n'est pas complete.
    """
    result = None  # TODO etudiant : remplacer par le balayage mesure
    return result


print("Exercice a completer : exercice_2_sweep_tolerances(A, b, lam, n, f_star=f_star)")

Exercice a completer : exercice_2_sweep_tolerances(A, b, lam, n, f_star=f_star)

Exercice 3 — étendre la sonde d’échelle à FISTA et ADMM

Le §4 a sondé ISTA, CD et sklearn à p croissant. Il manque FISTA (même coût par itération qu’ISTA, mais combien d’itérations pour converger ?) et ADMM (une Cholesky O(p³) une fois, puis O(p²) par itération — à quel p la Cholesky commence-t-elle à se voir ?).

Objectif : reproduire la génération de la sonde du §4 pour p ∈ {500, 2000}, y mesurer FISTA (tol 1e-8, budget 2000) et ADMM (ρ = 1, ε = 1e-4) — temps et itérations — puis confronter à la structure de coût attendue.

Étape 1 : régénérer A_, b_ et lam_ comme au §4, avec un générateur dédié, seed=0 et les mêmes dimensions.

Étape 2 : mesurer fista_compact et admm_compact, déjà définis au §3.1, pour chaque p.

Indice : compter les itérations ADMM : si elles augmentent avec p, le coût total ne croît pas seulement par itération. Comparer aussi le temps ADMM au §3.2 pour p=500 afin de vérifier que la sonde porte sur le même terrain.

def exercice_3_sonde_fista_admm(p_list=(500, 2000), n=200, k=30, noise_level=0.01, seed=0):
    """Exercice 3 - FISTA et ADMM a p croissant : temps ET iterations.

    Retour attendu : liste de dict (un par p) avec p, temps_fista, iter_fista,
    temps_admm, iter_admm. None tant que l'exercice n'est pas complete.
    """
    result = None  # TODO etudiant : remplacer par la sonde mesuree
    return result


print("Exercice a completer : exercice_3_sonde_fista_admm(p_list=(500, 2000))")

Exercice a completer : exercice_3_sonde_fista_admm(p_list=(500, 2000))

8. Conclusion

Ce que ce notebook a mesuré — le tableau récapitulatif B.8, assemblé sans aucune valeur recopiée :

Un optimum partagé : dans chaque famille, from scratch et SOTA atteignent le même optimum à tolérance près — le certificat croisé (gap de dualité côté SVM, écart à la référence numérique f* côté Lasso, avec ses limites) est la seule grandeur qui autorise la comparaison.
Des prix différents pour des biens différents : la colonne temps mesure la vitesse du SOTA (code C, algèbre pré-factorisée), la colonne LOC mesure ce que le from scratch écrit — et ce qu’il rend lisible en écrivant (α, résidus, compteurs à la granularité choisie : essais contre pas 2D réussis).
La tolérance fait partie du contrat : ADMM à ε = 10⁻⁴ rend une solution à ~10⁻³ de f* ; comparer son temps au temps d’un solveur à 10⁻⁸ sans nommer les tolérances serait comparer des contrats différents.
La normalisation fait partie du contrat : features brutes côté SVM (toute standardisation changerait le dual), A/√n et α = λ/n côté Lasso — l’exercice 1 mesure ce qu’une normalisation oubliée coûte.
L’échelle tranche : les sondes du §4 montrent les structures de coût (n_iter SMO explosif en n, pente Python de la CD en p, budget adaptatif de sklearn) — la règle pratique : from scratch pour comprendre et diagnostiquer, SOTA pour produire, et les deux se certifient mutuellement.

Pour aller plus loin : les notebooks parents (2.7b/2.7c pour le dual SVM et LIBSVM, 2.11b–2.11e pour proximal, coordinate descent, ADMM et cvxpy) développent la théorie que ce tableau ne fait que chiffrer.

9. Références

Platt, J. (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research TR-98-14. — la boucle SMO reprise au §2.1 (sous-problème 2D, branche η ≤ 0 App. A).
Fan, R.-E., Chen, P.-H., Lin, C.-J. (2005). Working Set Selection Using Second Order Information for Training Support Vector Machines. JMLR 6. — le working set que LIBSVM utilise et que notre cascade de Platt n’a pas.
Chang, C.-C., Lin, C.-J. (2011). LIBSVM: A Library for Support Vector Machines. ACM TIST 2(27). — le solveur derrière sklearn.svm.SVC.
Beck, A., Teboulle, M. (2009). A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems. SIAM J. Imaging Sciences 2(1). — ISTA/FISTA (§3.1).
Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J. (2011). Distributed Optimization and Statistical Learning via the ADMM. Foundations and Trends in ML 3(1). — §6.4 (Lasso ADMM), critères d’arrêt ε_abs/ε_rel du §3.
Friedman, J., Hastie, T., Tibshirani, R. (2010). Regularization Paths for Generalized Linear Models via Coordinate Descent. JSS 33(1). — la coordinate descent de sklearn.Lasso.
Tibshirani, R. (1996). Regression Shrinkage and Selection via the Lasso. JRSS-B 58(1). — le problème P1.
Donoho, D., Johnstone, I. (1994). Ideal Spatial Adaptation by Wavelet Shrinkage. Biometrika 81. — le seuil λ théorique de P1.
Diamond, S., Boyd, S. (2016). CVXPY: A Python-Embedded Modeling Language for Convex Optimization. JMLR 17(83). — la référence numérique déclarative du §3.
Pedregosa, F. et al. (2011). Scikit-learn: Machine Learning in Python. JMLR 12. — la convention alpha = λ/n du Lasso, mesurée à l’exercice 1.
Issue #16061 (dépôt CoursIA) — le body de l’EPIC optimisation convexe, § Bloc B, point 8 : ce tableau récapitulatif.
Notebooks frères : 2.7b-SMO-From-Scratch (A.1) · 2.7c-SVM-SOTA-Comparison (B.5) · 2.11b-Proximal-Operators-From-Scratch (A.3) · 2.11c-Lasso-SOTA-Comparison (B.6) · 2.11d-Optimisation-ADMM-From-Scratch (A.2) · 2.11e-CVXPY-Optimisation (B.7) — terrains et conventions repris à l’identique (seeds 42 / 20260914 selon le parent).

Retour au sommet