Masalah komposit dan oracle stokastik

Pertimbangkan masalah komposit \[\begin{equation} \label{orig01:eq:composite-problem} \min_{x\in\mathbb{R}^d} F(x), \qquad F(x)=f(x)+g(x), \end{equation}\] dengan \(f:\mathbb{R}^d\to\mathbb{R}\) konveks, terdiferensialkan, dan mempunyai gradien \(L\)-Lipschitz, sedangkan \(g:\mathbb{R}^d\to(-\infty,+\infty]\) proper, konveks, dan semikontinu bawah. Andaikan himpunan peminim \(X^*=\arg\min F\) tidak kosong.

Oracle pada \(x_k\) mengembalikan \(G_k\) dan memenuhi, hampir pasti, \[\begin{equation} \label{orig01:eq:oracle} \mathbb{E}[G_k\mid\mathcal F_k]=\nabla f(x_k), \qquad \mathbb{E}\!\left[\left\lVert G_k-\nabla f(x_k)\right\rVert^2\mid\mathcal F_k\right] \leq \nu_k^2. \end{equation}\] Besaran \(\nu_k^2\) boleh berubah sepanjang iterasi. Notasi ini sengaja memisahkan varians oracle dari konstanta kemulusan \(L\) dan dari fungsi kerugian \(\ell\) pada model statistik.

Gradien proksimal stokastik

Dengan ukuran langkah \(\tau_k>0\), pembaruan gradien proksimal stokastik ialah \[\begin{equation} \label{orig01:eq:spg-update} x_{k+1} =\operatorname{prox}_{\tau_k g}\bigl(x_k-\tau_kG_k\bigr). \end{equation}\] Jika \(g=\delta_C\) adalah fungsi indikator himpunan konveks tertutup \(C\), pembaruan ini menjadi proyeksi stokastik. Jika \(g(x)=\lambda\left\lVert x\right\rVert_1\), pembaruan ini menjadi ambang lunak setelah langkah gradien stokastik.

Algoritma 1: gradien proksimal stokastik. Pilih \(x_0\in\operatorname{dom}g\). Untuk \(k=0,1,\dots\), panggil oracle pada \(x_k\) untuk memperoleh \(G_k\), pilih \(\tau_k\), lalu hitung (3). Untuk pelaporan ergodik, simpan rerata iterat yang disebutkan dalam teorema berikut.

Jika \(R=\left\lVert x_0-x^*\right\rVert>0\), \(\sigma>0\), dan batas kemulusan tidak aktif, pilihan yang menyeimbangkan kedua suku pada (6) ialah \[\begin{equation} \tau=R\sqrt{\frac{b}{2\sigma^2K}}, \qquad \mathbb{E}[F(\bar x_K)-F(x^*)] \leq\frac{\sqrt2R\sigma}{\sqrt{bK}}. \end{equation}\] Dalam praktik, \(R\) dan \(\sigma\) biasanya tidak diketahui. Rumus ini adalah penjelas skala, bukan resep penalaan tanpa diagnosis.

Minibatch: identitas varians dan biaya oracle

Ambil \(b\) sampel bersyarat iid \(G_{k,1},\dots,G_{k,b}\) dengan rerata \(\nabla f(x_k)\) dan varians kuadrat paling besar \(\sigma^2\). Penaksir minibatch dengan penggantian adalah \[\begin{equation} \label{orig01:eq:minibatch} \widehat G_k^{(b)}=\frac1b\sum_{j=1}^{b}G_{k,j}. \end{equation}\]

Untuk jumlah hingga \(f=N^{-1}\sum_{i=1}^{N}f_i\), pengambilan sampel tanpa penggantian mempunyai koreksi populasi hingga yang tidak boleh disamakan dengan rumus iid.

Minibatch menurunkan varians per iterasi, tetapi memakai \(b\) evaluasi gradien komponen. Jika biaya serial yang tersedia adalah \(T=bK\), batas tertala ideal \(\sqrt2R\sigma/\sqrt{bK}\) menjadi \(\sqrt2R\sigma/\sqrt T\): tidak ada percepatan kompleksitas oracle hanya dari pengelompokan. Keuntungan nyata dapat datang dari paralelisme, arsitektur perangkat, pengurangan komunikasi, atau batas langkah yang lebih baik. Pernyataan ini juga menjelaskan mengapa perbandingan hanya berdasarkan banyak iterasi dapat menyesatkan.

Penurunan cermin stokastik

Proyeksi Euklides memperlakukan semua arah dengan geometri yang sama. Pada simpleks, matriks semidefinit positif, atau ruang dengan struktur sparsitas, pilihan geometri lain dapat lebih alami.

Misalkan \(X\subset\mathbb{R}^d\) tak kosong, tertutup, dan konveks. Ambil fungsi pembangkit \(h:X\to\mathbb{R}\) yang bernilai hingga dan kontinu pada \(X\), terdiferensialkan di setiap iterat, dan \(\alpha\)-konveks kuat terhadap \(\left\lVert \cdot\right\rVert\). Untuk setiap \(x\in X\) dan setiap titik keterdiferensialan \(y\), \[\begin{equation} h(x)\geq h(y)+\left\langle \nabla h(y),x-y\right\rangle +\frac\alpha2\left\lVert x-y\right\rVert^2. \end{equation}\] Divergensi Bregman yang dibangkitkan oleh \(h\) ialah \[\begin{equation} \label{orig01:eq:bregman} D_h(x,y)=h(x)-h(y)-\left\langle \nabla h(y),x-y\right\rangle. \end{equation}\] Divergensi ini tidak harus simetris dan bukan metrik, tetapi \(D_h(x,y)\geq(\alpha/2)\left\lVert x-y\right\rVert^2\).

Untuk fungsi konveks \(\Phi:X\to\mathbb{R}\), andaikan oracle menghasilkan \(G_k\) dengan \[\begin{equation} \label{orig01:eq:mirror-oracle} \bar G_k\coloneqq\mathbb{E}[G_k\mid\mathcal F_k]\in\partial\Phi(x_k), \qquad \mathbb{E}[\left\lVert G_k\right\rVert_*^2\mid\mathcal F_k]\leq M^2. \end{equation}\] Ambil \(\tau_k>0\) dan andaikan masalah berikut hampir pasti mencapai peminim unik \(x_{k+1}\) pada titik keterdiferensialan \(h\): \[\begin{equation} \label{orig01:eq:mirror-update} x_{k+1}=\arg\min_{x\in X} \left\{\tau_k\left\langle G_k,x\right\rangle+D_h(x,x_k)\right\}. \end{equation}\] Untuk pembanding optimum \(x^*\) yang dipakai di bawah, andaikan pula \(D_h(x^*,x_0)<\infty\). Asumsi eksplisit ini dapat diganti dengan syarat Legendre/interior standar yang menjamin sifat-sifat yang sama.

Algoritma 2: penurunan cermin stokastik. Pilih \(x_0\) dalam daerah terdiferensialkan \(h\). Pada iterasi \(k\), ambil subgradien stokastik \(G_k\), selesaikan masalah Bregman (11), dan perbarui rerata berbobot \(\sum_j\tau_jx_j/\sum_j\tau_j\).

Untuk \(M>0\) dan \(D_h(x^*,x_0)>0\), gunakan \(\tau=\sqrt{2\alpha D_h(x^*,x_0)/(M^2K)}\). Ruas kanan kemudian menjadi \[\begin{equation} M\sqrt{\frac{2D_h(x^*,x_0)}{\alpha K}}. \end{equation}\] Pada geometri Euklides, \(h(x)=\left\lVert x\right\rVert_2^2/2\) dan pembaruan cermin menjadi subgradien stokastik terproyeksi. Jadi metode cermin memperluas, bukan menduplikasi, teorema stokastik Habring.

Dari SAGA ke pembaruan proksimal

Untuk masalah jumlah hingga \(f=N^{-1}\sum_i f_i\), modul Becker 3 mendefinisikan penaksir SAGA \[\begin{equation} v_k=\nabla f_{J_k}(x_k)-g_{J_k}^k+\bar g_k \end{equation}\] dan membuktikan \(\mathbb{E}[v_k\mid\mathcal F_k]=\nabla f(x_k)\). Untuk masalah komposit, perubahan algoritmik yang benar bukan mengurangkan subgradien \(g\), melainkan memakai langkah proksimal \[\begin{equation} \label{orig01:eq:prox-saga} x_{k+1}=\operatorname{prox}_{\tau g}(x_k-\tau v_k). \end{equation}\]

Korolari ini menjelaskan hubungan yang hilang, tetapi sengaja tidak mengklaim bahwa varians SAGA selalu turun geometrik. Pembuktian klaim semacam itu memerlukan fungsi Lyapunov gabungan untuk galat iterat dan galat tabel. Teorema laju linear bersyarat pada modul Becker 3 menyediakan hasil khusus untuk kasus mulus dan konveks kuat; korolari di sini menunjukkan bagaimana penaksir yang sama masuk ke masalah komposit.

Laboratorium 1: regresi renggang dengan biaya oracle tetap

Laboratorium terbuka pada labs/original-01/stochastic-composite-lab.py membangun masalah regresi kuadrat dengan regularisasi \(\ell_1\), \[\begin{equation} \label{orig01:eq:lab-objective} F(x)=\frac{1}{2N}\left\lVert Ax-y\right\rVert_2^2+\lambda\left\lVert x\right\rVert_1. \end{equation}\] Skrip membandingkan gradien proksimal stokastik, minibatch dengan penggantian, dan Prox-SAGA pada anggaran evaluasi gradien komponen yang sama. Referensi numerik dihitung oleh FISTA deterministik sampai norma pemetaan gradien proksimal memenuhi toleransi yang dilaporkan.

Tugas laboratorium:

1. jalankan skrip tanpa mengubah benih acak dan verifikasikan konfigurasi beku yang dicatat pada berkas hasil;

2. bandingkan kesenjangan objektif terhadap evaluasi gradien komponen, bukan hanya terhadap iterasi;

3. periksa apakah minibatch menurunkan varians arah pada checkpoint yang sama;

4. ubah ukuran minibatch tetapi pertahankan anggaran oracle, lalu jelaskan perbedaan antara keuntungan statistik dan keuntungan paralel;

5. ganti \(\lambda\) dan ukur perubahan sparsitas serta norma pemetaan gradien proksimal;

6. laporkan setiap hasil yang bertentangan dengan batas teori beserta asumsi yang mungkin tidak terpenuhi.

CSV dan JSON yang dihasilkan adalah permukaan aksesibel utama. Grafik SVG hanya merupakan bantuan visual dan tidak menjadi satu-satunya pembawa informasi.

Dengan konfigurasi beku (\(N=320\), \(d=40\), \(\lambda=0{,}03\), 12 epoch, dan 3.840 evaluasi gradien komponen per metode), nilai referensi FISTA adalah \(0{,}31517396778742246\) dengan norma pemetaan gradien proksimal \(1{,}49\times10^{-15}\). Hasil terminal deterministik adalah:

Angka tersebut adalah satu eksperimen terkontrol, bukan urutan kinerja universal. Berkas hasil JSON, CSV, dan SVG mempunyai SHA-256 berikut:

Identitas lengkap dicatat dalam receipt QA.

Latihan, petunjuk, dan solusi lengkap

Peta asumsi dan batas klaim

Bab ini tidak membahas ketaksamaan variasional atau operator monoton maksimal; materi tersebut adalah tranche asli berikutnya. Bab ini juga tidak mengulang LP/MIP, simpleks sebagai algoritma pemrograman linear, dualitas LP, sensitivitas LP, jaringan, atau optimisasi diskret yang merupakan cakupan O018. Kata simpleks di sini hanya menunjuk himpunan probabilitas \(\Delta_d\).

Grafik kesenjangan objektif

Tabel data lengkap

Tabel berikut memuat semua baris hasil eksperimen dengan tajuk kolom yang dapat ditelusuri oleh teknologi bantu.

Berkas laboratorium byte-identik

• stochastic-composite-lab.py — 13655 byte; SHA-256 21a0df89524b34916d1f659636bf8f92a5730efb7e263e0fbd7393e6f2c936fd
• results.json — 2432 byte; SHA-256 86ff701a51d091ee74c110917cb1888c6e7448489207e6ee1372753bd1e4c447
• results.csv — 4189 byte; SHA-256 61a6591ad7d1b41230a086482314448871f3697954d4c84133a7a5f4f775d37c
• objective-gap.svg — 86616 byte; SHA-256 87c772d901ee734356981ee35f19fc3c3ae47fea6f11528edbee6d015a3f2830

Daftar berikut diikat oleh ukuran byte dan SHA-256. Pada HTML tautannya mengunduh berkas byte-identik; pada EPUB tautannya menuju representasi lengkap di dalam pembaca, sementara salinan byte-identik tetap termanifestasi.

Kode program Python lengkap

#!/usr/bin/env python3
"""Deterministic open-computation lab for O015 original tranche 1.

The experiment compares proximal SGD, proximal minibatch SGD, and Prox-SAGA
on an L1-regularized least-squares problem under a common component-gradient
evaluation budget. It writes accessible CSV/JSON results and a redundant SVG
plot. No network access or proprietary solver is required.

Original lab code and documentation: CC BY-SA 4.0
https://creativecommons.org/licenses/by-sa/4.0/
Produced by OpenAI Codex gpt-5.6-sol, Ultra, on the repository user's
instructions. Python, NumPy, and Matplotlib are unbundled runtime dependencies;
their own licenses remain unchanged. Cited researchers did not author this code.
"""

from __future__ import annotations

import csv
import hashlib
import json
import math
from pathlib import Path

import matplotlib

matplotlib.use("Agg")
matplotlib.rcParams["svg.hashsalt"] = "o015-original-01-20260825"
import matplotlib.pyplot as plt
import numpy as np


HERE = Path(__file__).resolve().parent
RESULT_JSON = HERE / "results.json"
RESULT_CSV = HERE / "results.csv"
RESULT_SVG = HERE / "objective-gap.svg"

SEED = 20260825
N = 320
D = 40
TRUE_NONZERO = 8
NOISE_STD = 0.08
LAMBDA = 0.03
EPOCHS = 12
BATCH_SIZE = 16
REFERENCE_MAX_ITER = 50000
REFERENCE_TOL = 1e-11


def sha256(path: Path) -> str:
    return hashlib.sha256(path.read_bytes()).hexdigest()


def soft_threshold(z: np.ndarray, threshold: float) -> np.ndarray:
    return np.sign(z) * np.maximum(np.abs(z) - threshold, 0.0)


def objective(a: np.ndarray, y: np.ndarray, x: np.ndarray) -> float:
    residual = a @ x - y
    return float(0.5 * residual @ residual / len(y) + LAMBDA * np.abs(x).sum())


def full_gradient(a: np.ndarray, y: np.ndarray, x: np.ndarray) -> np.ndarray:
    return a.T @ (a @ x - y) / len(y)


def component_gradient(
    a: np.ndarray, y: np.ndarray, x: np.ndarray, index: int
) -> np.ndarray:
    return a[index] * (a[index] @ x - y[index])


def prox_gradient_mapping_norm(
    a: np.ndarray, y: np.ndarray, x: np.ndarray, step: float
) -> float:
    mapped = soft_threshold(x - step * full_gradient(a, y, x), step * LAMBDA)
    return float(np.linalg.norm((x - mapped) / step))


def reference_fista(
    a: np.ndarray, y: np.ndarray, smooth_lipschitz: float
) -> tuple[np.ndarray, dict[str, float | int]]:
    step = 1.0 / smooth_lipschitz
    x = np.zeros(D)
    z = x.copy()
    t = 1.0
    mapping = math.inf
    iteration = 0
    for iteration in range(1, REFERENCE_MAX_ITER + 1):
        x_next = soft_threshold(
            z - step * full_gradient(a, y, z), step * LAMBDA
        )
        t_next = 0.5 * (1.0 + math.sqrt(1.0 + 4.0 * t * t))
        z = x_next + ((t - 1.0) / t_next) * (x_next - x)
        x = x_next
        t = t_next
        if iteration % 25 == 0:
            mapping = prox_gradient_mapping_norm(a, y, x, step)
            if mapping <= REFERENCE_TOL:
                break
    return x, {
        "iterations": iteration,
        "step": step,
        "mapping_norm": mapping,
        "objective": objective(a, y, x),
    }


def checkpoint(
    rows: list[dict[str, float | int | str]],
    method: str,
    evaluations: int,
    epoch: float,
    a: np.ndarray,
    y: np.ndarray,
    x: np.ndarray,
    optimum: float,
    mapping_step: float,
    direction_variance: float,
) -> None:
    value = objective(a, y, x)
    rows.append(
        {
            "method": method,
            "component_gradient_evaluations": evaluations,
            "epochs": epoch,
            "objective": value,
            "objective_gap": max(value - optimum, 0.0),
            "prox_gradient_mapping_norm": prox_gradient_mapping_norm(
                a, y, x, mapping_step
            ),
            "nonzero_coordinates": int(np.count_nonzero(np.abs(x) > 1e-8)),
            "direction_variance_trace": direction_variance,
        }
    )


def empirical_direction_variance(
    a: np.ndarray, y: np.ndarray, x: np.ndarray
) -> float:
    gradients = a * (a @ x - y)[:, None]
    centered = gradients - gradients.mean(axis=0)
    return float(np.mean(np.sum(centered * centered, axis=1)))


def run_prox_sgd(
    a: np.ndarray,
    y: np.ndarray,
    optimum: float,
    component_lipschitz: float,
    mapping_step: float,
) -> list[dict[str, float | int | str]]:
    rng = np.random.default_rng(SEED + 1)
    x = np.zeros(D)
    step = 0.75 / component_lipschitz
    rows: list[dict[str, float | int | str]] = []
    budget = EPOCHS * N
    checkpoint(
        rows,
        "prox_sgd_b1",
        0,
        0.0,
        a,
        y,
        x,
        optimum,
        mapping_step,
        empirical_direction_variance(a, y, x),
    )
    for evaluation in range(1, budget + 1):
        i = int(rng.integers(N))
        gradient = component_gradient(a, y, x, i)
        x = soft_threshold(x - step * gradient, step * LAMBDA)
        if evaluation % N == 0:
            checkpoint(
                rows,
                "prox_sgd_b1",
                evaluation,
                evaluation / N,
                a,
                y,
                x,
                optimum,
                mapping_step,
                empirical_direction_variance(a, y, x),
            )
    return rows


def run_prox_minibatch(
    a: np.ndarray,
    y: np.ndarray,
    optimum: float,
    component_lipschitz: float,
    mapping_step: float,
) -> list[dict[str, float | int | str]]:
    rng = np.random.default_rng(SEED + 2)
    x = np.zeros(D)
    step = 0.75 / component_lipschitz
    rows: list[dict[str, float | int | str]] = []
    budget = EPOCHS * N
    checkpoint(
        rows,
        f"prox_minibatch_b{BATCH_SIZE}",
        0,
        0.0,
        a,
        y,
        x,
        optimum,
        mapping_step,
        empirical_direction_variance(a, y, x) / BATCH_SIZE,
    )
    evaluations = 0
    while evaluations + BATCH_SIZE <= budget:
        indices = rng.integers(N, size=BATCH_SIZE)
        residual = a[indices] @ x - y[indices]
        gradient = a[indices].T @ residual / BATCH_SIZE
        x = soft_threshold(x - step * gradient, step * LAMBDA)
        evaluations += BATCH_SIZE
        if evaluations % N == 0:
            checkpoint(
                rows,
                f"prox_minibatch_b{BATCH_SIZE}",
                evaluations,
                evaluations / N,
                a,
                y,
                x,
                optimum,
                mapping_step,
                empirical_direction_variance(a, y, x) / BATCH_SIZE,
            )
    return rows


def run_prox_saga(
    a: np.ndarray,
    y: np.ndarray,
    optimum: float,
    component_lipschitz: float,
    mapping_step: float,
) -> list[dict[str, float | int | str]]:
    rng = np.random.default_rng(SEED + 3)
    x = np.zeros(D)
    table = a * (a @ x - y)[:, None]
    table_mean = table.mean(axis=0)
    step = 1.0 / (3.0 * component_lipschitz)
    rows: list[dict[str, float | int | str]] = []
    budget = EPOCHS * N
    evaluations = N
    checkpoint(
        rows,
        "prox_saga",
        evaluations,
        evaluations / N,
        a,
        y,
        x,
        optimum,
        mapping_step,
        0.0,
    )
    while evaluations < budget:
        i = int(rng.integers(N))
        fresh = component_gradient(a, y, x, i)
        estimate = fresh - table[i] + table_mean
        old = table[i].copy()
        x = soft_threshold(x - step * estimate, step * LAMBDA)
        table[i] = fresh
        table_mean += (fresh - old) / N
        evaluations += 1
        if evaluations % N == 0:
            current_components = a * (a @ x - y)[:, None]
            differences = current_components - table
            centered = differences - differences.mean(axis=0)
            saga_variance = float(np.mean(np.sum(centered * centered, axis=1)))
            checkpoint(
                rows,
                "prox_saga",
                evaluations,
                evaluations / N,
                a,
                y,
                x,
                optimum,
                mapping_step,
                saga_variance,
            )
    return rows


def write_svg(rows: list[dict[str, float | int | str]]) -> None:
    fig, ax = plt.subplots(figsize=(7.2, 4.5), constrained_layout=True)
    methods = sorted({str(row["method"]) for row in rows})
    for method in methods:
        subset = [row for row in rows if row["method"] == method]
        x = [int(row["component_gradient_evaluations"]) for row in subset]
        y = [max(float(row["objective_gap"]), 1e-16) for row in subset]
        ax.semilogy(x, y, marker="o", linewidth=1.5, markersize=3.5, label=method)
    ax.set_xlabel("Evaluasi gradien komponen")
    ax.set_ylabel("Kesenjangan objektif (skala log)")
    ax.set_title("Regresi renggang: biaya oracle yang sama")
    ax.grid(True, which="both", alpha=0.28)
    ax.legend()
    fig.savefig(
        RESULT_SVG,
        format="svg",
        metadata={
            "Title": "Kesenjangan objektif terhadap evaluasi gradien komponen",
            "Date": "2026-08-25T00:00:00Z",
            "Description": (
                "Grafik redundan; seluruh nilai tersedia dalam results.csv dan "
                "results.json."
            ),
        },
    )
    plt.close(fig)


def main() -> None:
    rng = np.random.default_rng(SEED)
    a = rng.normal(size=(N, D)) / math.sqrt(D)
    true_x = np.zeros(D)
    support = rng.choice(D, size=TRUE_NONZERO, replace=False)
    true_x[support] = rng.normal(loc=0.0, scale=2.0, size=TRUE_NONZERO)
    y = a @ true_x + NOISE_STD * rng.normal(size=N)

    smooth_lipschitz = float(np.linalg.norm(a, ord=2) ** 2 / N)
    component_lipschitz = float(np.max(np.sum(a * a, axis=1)))
    reference_x, reference = reference_fista(a, y, smooth_lipschitz)
    optimum = float(reference["objective"])
    mapping_step = 1.0 / smooth_lipschitz

    rows = []
    rows.extend(
        run_prox_sgd(a, y, optimum, component_lipschitz, mapping_step)
    )
    rows.extend(
        run_prox_minibatch(a, y, optimum, component_lipschitz, mapping_step)
    )
    rows.extend(
        run_prox_saga(a, y, optimum, component_lipschitz, mapping_step)
    )

    fieldnames = [
        "method",
        "component_gradient_evaluations",
        "epochs",
        "objective",
        "objective_gap",
        "prox_gradient_mapping_norm",
        "nonzero_coordinates",
        "direction_variance_trace",
    ]
    with RESULT_CSV.open("w", encoding="utf-8", newline="") as stream:
        writer = csv.DictWriter(stream, fieldnames=fieldnames, lineterminator="\n")
        writer.writeheader()
        writer.writerows(rows)

    final_rows = {
        method: max(
            (row for row in rows if row["method"] == method),
            key=lambda row: int(row["component_gradient_evaluations"]),
        )
        for method in sorted({str(row["method"]) for row in rows})
    }
    payload = {
        "schema": "o015-original-01-stochastic-composite-lab-v1",
        "result": "pass",
        "configuration": {
            "seed": SEED,
            "samples": N,
            "dimension": D,
            "true_nonzero_coordinates": TRUE_NONZERO,
            "noise_standard_deviation": NOISE_STD,
            "l1_regularization": LAMBDA,
            "epochs": EPOCHS,
            "component_gradient_budget": EPOCHS * N,
            "minibatch_size": BATCH_SIZE,
            "sampling": "with replacement for SGD/minibatch/SAGA index draws",
        },
        "problem": {
            "objective": "0.5/N * ||A x - y||_2^2 + lambda * ||x||_1",
            "smooth_lipschitz": smooth_lipschitz,
            "max_component_lipschitz": component_lipschitz,
            "reference": reference,
            "reference_nonzero_coordinates": int(
                np.count_nonzero(np.abs(reference_x) > 1e-8)
            ),
        },
        "final_rows": final_rows,
        "row_count": len(rows),
        "csv": {"path": RESULT_CSV.name},
        "svg": {
            "path": RESULT_SVG.name,
            "redundant_with_accessible_tables": True,
        },
        "dependencies": {
            "python": __import__("sys").version.split()[0],
            "numpy": np.__version__,
            "matplotlib": matplotlib.__version__,
        },
        "network_access": False,
        "upstream_contact": False,
    }
    RESULT_JSON.write_text(
        json.dumps(payload, ensure_ascii=False, indent=2, sort_keys=True) + "\n",
        encoding="utf-8",
        newline="\n",
    )
    write_svg(rows)

    # Bind generated outputs after every file exists. The JSON deliberately
    # omits its own hash to avoid a self-reference cycle.
    payload["csv"].update(
        {"bytes": RESULT_CSV.stat().st_size, "sha256": sha256(RESULT_CSV)}
    )
    payload["svg"].update(
        {"bytes": RESULT_SVG.stat().st_size, "sha256": sha256(RESULT_SVG)}
    )
    RESULT_JSON.write_text(
        json.dumps(payload, ensure_ascii=False, indent=2, sort_keys=True) + "\n",
        encoding="utf-8",
        newline="\n",
    )
    print(
        json.dumps(
            {
                "result": "pass",
                "rows": len(rows),
                "reference_mapping_norm": reference["mapping_norm"],
                "json_bytes": RESULT_JSON.stat().st_size,
                "json_sha256": sha256(RESULT_JSON),
                "csv_bytes": RESULT_CSV.stat().st_size,
                "csv_sha256": sha256(RESULT_CSV),
                "svg_bytes": RESULT_SVG.stat().st_size,
                "svg_sha256": sha256(RESULT_SVG),
            },
            indent=2,
            sort_keys=True,
        )
    )


if __name__ == "__main__":
    main()

Hasil JSON lengkap

{
  "configuration": {
    "component_gradient_budget": 3840,
    "dimension": 40,
    "epochs": 12,
    "l1_regularization": 0.03,
    "minibatch_size": 16,
    "noise_standard_deviation": 0.08,
    "samples": 320,
    "sampling": "with replacement for SGD/minibatch/SAGA index draws",
    "seed": 20260825,
    "true_nonzero_coordinates": 8
  },
  "csv": {
    "bytes": 4189,
    "path": "results.csv",
    "sha256": "61a6591ad7d1b41230a086482314448871f3697954d4c84133a7a5f4f775d37c"
  },
  "dependencies": {
    "matplotlib": "3.10.9",
    "numpy": "2.4.4",
    "python": "3.13.9"
  },
  "final_rows": {
    "prox_minibatch_b16": {
      "component_gradient_evaluations": 3840,
      "direction_variance_trace": 0.01638661162760481,
      "epochs": 12.0,
      "method": "prox_minibatch_b16",
      "nonzero_coordinates": 10,
      "objective": 0.3177447126633351,
      "objective_gap": 0.002570744875912634,
      "prox_gradient_mapping_norm": 0.009863014116815592
    },
    "prox_saga": {
      "component_gradient_evaluations": 3840,
      "direction_variance_trace": 4.5430827278459796e-07,
      "epochs": 12.0,
      "method": "prox_saga",
      "nonzero_coordinates": 5,
      "objective": 0.3151739698318594,
      "objective_gap": 2.0444369530636664e-09,
      "prox_gradient_mapping_norm": 9.866567454031472e-06
    },
    "prox_sgd_b1": {
      "component_gradient_evaluations": 3840,
      "direction_variance_trace": 0.26136164865160183,
      "epochs": 12.0,
      "method": "prox_sgd_b1",
      "nonzero_coordinates": 33,
      "objective": 0.3643430437640875,
      "objective_gap": 0.04916907597666503,
      "prox_gradient_mapping_norm": 0.021155328208993934
    }
  },
  "network_access": false,
  "problem": {
    "max_component_lipschitz": 1.7390392069736775,
    "objective": "0.5/N * ||A x - y||_2^2 + lambda * ||x||_1",
    "reference": {
      "iterations": 75,
      "mapping_norm": 1.4911593730067174e-15,
      "objective": 0.31517396778742246,
      "step": 22.65203499676275
    },
    "reference_nonzero_coordinates": 5,
    "smooth_lipschitz": 0.044146144050320954
  },
  "result": "pass",
  "row_count": 38,
  "schema": "o015-original-01-stochastic-composite-lab-v1",
  "svg": {
    "bytes": 86616,
    "path": "objective-gap.svg",
    "redundant_with_accessible_tables": true,
    "sha256": "87c772d901ee734356981ee35f19fc3c3ae47fea6f11528edbee6d015a3f2830"
  },
  "upstream_contact": false
}

Hasil CSV lengkap

method,component_gradient_evaluations,epochs,objective,objective_gap,prox_gradient_mapping_norm,nonzero_coordinates,direction_variance_trace
prox_sgd_b1,0,0.0,0.5513362316807581,0.2361622638933356,0.10832855794967476,0,1.1468193719792907
prox_sgd_b1,320,1.0,0.3702175482052296,0.05504358041780716,0.021444123030821837,35,0.20287630148456232
prox_sgd_b1,640,2.0,0.3456910435897478,0.030517075802325322,0.018590943751343902,26,0.2049691821609164
prox_sgd_b1,960,3.0,0.35261241671387245,0.037438448926449985,0.01936197482100853,34,0.2519231892272348
prox_sgd_b1,1280,4.0,0.36811937169959086,0.0529454039121684,0.029796229670094147,34,0.13168723150568945
prox_sgd_b1,1600,5.0,0.3440604597431073,0.028886491955684823,0.01772940293189908,32,0.17837355463918506
prox_sgd_b1,1920,6.0,0.36730400424645354,0.05213003645903108,0.022939657645467362,36,0.1855969433395085
prox_sgd_b1,2240,7.0,0.33967464511660245,0.024500677329179987,0.012560809370328175,28,0.20583985615470013
prox_sgd_b1,2560,8.0,0.33277169799112805,0.017597730203705586,0.013759461627893042,22,0.21181935832129542
prox_sgd_b1,2880,9.0,0.34224173083603737,0.027067763048614912,0.015798406128366645,28,0.27433629954292693
prox_sgd_b1,3200,10.0,0.3539651427066747,0.038791174919252214,0.020535508430316735,35,0.16457694344643045
prox_sgd_b1,3520,11.0,0.34488872564568707,0.029714757858264607,0.016623659246199234,33,0.2108599340100843
prox_sgd_b1,3840,12.0,0.3643430437640875,0.04916907597666503,0.021155328208993934,33,0.26136164865160183
prox_minibatch_b16,0,0.0,0.5513362316807581,0.2361622638933356,0.10832855794967476,0,0.07167621074870567
prox_minibatch_b16,320,1.0,0.47802984093064677,0.1628558731432243,0.08798911404534003,19,0.05572471404755659
prox_minibatch_b16,640,2.0,0.42575094873287517,0.11057698094545271,0.07263472377858442,19,0.04530167691546953
prox_minibatch_b16,960,3.0,0.39309556908426724,0.07792160129684478,0.05967953266400586,27,0.03731134660361215
prox_minibatch_b16,1280,4.0,0.3652506832322026,0.05007671544478015,0.04678905972517255,26,0.029991266926131112
prox_minibatch_b16,1600,5.0,0.34732809753256816,0.0321541297451457,0.038856894448275725,17,0.02655369940668307
prox_minibatch_b16,1920,6.0,0.33857422339713694,0.023400255609714482,0.03232876621638514,15,0.02411665732740852
prox_minibatch_b16,2240,7.0,0.33313130497336096,0.017957337185938504,0.026317750019252795,18,0.021550879809775537
prox_minibatch_b16,2560,8.0,0.3253996490028912,0.01022568121546874,0.021504470211626138,11,0.01951610028110142
prox_minibatch_b16,2880,9.0,0.32155612458903304,0.006382156801610583,0.01623058440910809,12,0.017903354865238353
prox_minibatch_b16,3200,10.0,0.31863928091487426,0.0034653131274517968,0.012937145055556078,7,0.017365712120880016
prox_minibatch_b16,3520,11.0,0.3187931787112053,0.0036192109237828674,0.010395977334385874,17,0.01643895223004758
prox_minibatch_b16,3840,12.0,0.3177447126633351,0.002570744875912634,0.009863014116815592,10,0.01638661162760481
prox_saga,320,1.0,0.5513362316807581,0.2361622638933356,0.10832855794967476,0,0.0
prox_saga,640,2.0,0.3364671079185516,0.02129314013112915,0.030882283903767606,13,0.09782001800634663
prox_saga,960,3.0,0.32103318206917736,0.005859214281754899,0.012180776828082843,18,0.06029196457916808
prox_saga,1280,4.0,0.31574500657605503,0.0005710387886325718,0.005155181368145557,6,0.03248213576359973
prox_saga,1600,5.0,0.3153073845642892,0.00013341677686673492,0.002337202852006731,6,0.012430610167196843
prox_saga,1920,6.0,0.3151831621856891,9.194398266632042e-06,0.0006657881583918369,5,0.003997002859597115
prox_saga,2240,7.0,0.315190635623481,1.6667836058525953e-05,0.0009069062956898701,5,0.001237648754466667
prox_saga,2560,8.0,0.3151752443195945,1.2765321720231704e-06,0.0002559732064124996,5,8.69567909247325e-05
prox_saga,2880,9.0,0.31517410977002475,1.4198260228637238e-07,8.335204162947475e-05,5,2.0228054402838927e-05
prox_saga,3200,10.0,0.3151740826328425,1.1484542006279241e-07,7.642797522666668e-05,5,1.029106808858402e-05
prox_saga,3520,11.0,0.31517398783419104,2.0046768578474428e-08,3.045036972269875e-05,5,2.2866507233178645e-06
prox_saga,3840,12.0,0.3151739698318594,2.0444369530636664e-09,9.866567454031472e-06,5,4.5430827278459796e-07