scripts/fill_logbook.py

"""Write all logbook pages (run with the repro venv from the workspace root)."""

import json, os, uuid, datetime

ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
PAGES = os.path.join(ROOT, ".trackio", "logbook", "pages")
NOW = datetime.datetime.now(datetime.timezone.utc).strftime("%Y-%m-%dT%H:%M:%S+00:00")
SPACE = (
    "https://huggingface.co/spaces/SabaPivot/"
    "repro-provably-data-driven-lagrangian-relaxation-for-mixed-integer-linear-programming"
)


def cell(kind, title, body, pinned=False, extra=None):
    meta = {
        "type": kind,
        "id": "cell_" + uuid.uuid4().hex[:12],
        "created_at": NOW,
        "title": title,
    }
    if pinned:
        meta["pinned"] = True
        meta["pinned_at"] = NOW
    if extra:
        meta.update(extra)
    return (
        "\n---\n<!-- trackio-cell\n"
        + json.dumps(meta)
        + "\n-->\n"
        + body.rstrip()
        + "\n"
    )


def write(slug, heading, cells):
    d = os.path.join(PAGES, slug)
    os.makedirs(d, exist_ok=True)
    with open(os.path.join(d, "page.md"), "w") as f:
        f.write("# " + heading + "\n\n" + "".join(cells))
    print("wrote", slug)


# ======================================================================== executive summary
EXEC = """# Executive summary

**All six claims of "Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear
Programming" (arXiv 2605.19052) reproduce, on CPU, in 52 minutes, for $0.** This is a pure-theory
paper with no released code, so every result is re-derived and re-measured from scratch on MILP
families where the Lagrangian dual is computable *exactly*: the dual value and its subgradient come
from exhaustive enumeration of the sub-problem solution sets, cross-checked against
`scipy.optimize.milp` (HiGHS) to 7e-15, and both the population optimum and the ERM optimum are
solved exactly by Kelley cutting planes on HiGHS rather than estimated. For the two lower bounds we
do not race estimators: we compute the **exact Bayes risk of the optimal estimator** under a uniform
prior over the paper's own hard family, which is a rigorous lower bound over *every* learning
algorithm. Two audit findings sharpen rather than contradict the paper: the chi-squared step quoted
inside Lemma 5.8 is `4e^2/(1-e^2) > 4e^2` (the lemma's conclusion still holds), and the assembled
Fano factor `1/2 - 8/s` is exactly zero at `s = 16`, so Theorem 5.6's stated hypothesis `s >= 16`
should read `s >= 17`.

| Claim | Verdict | Key number |
| --- | --- | --- |
| C1 Thm 5.5 — ERM risk `O(s^1.5/sqrt(N))` | **verified** | never violated in 60 `(s,N)` cells; worst measured/bound = 2.1e-4; minimax-regime exponents `N^-0.55`, `s^0.97` |
| C2 Thm 5.6 — minimax `Omega(s/sqrt(N))` | **verified** | exact Bayes lower bound `0.0425 s/sqrt(N)`; fitted `N^-0.5053` (R2 0.99994), `s^1.0000` (R2 1.000) |
| C3 Thm 5.12 — SGA + averaging `O(s/sqrt(N))` | **verified** | constant `2 B pi_max s/sqrt(N)` re-derived to machine zero and never violated; measured `N^-0.54..-0.60`, `s^1.02..1.07` |
| C4 Thm 6.1/6.2 — warm start `Theta(s/N)` | **verified** | upper `N^-1.000`, `s^0.982`; exact lower bound `N^-0.986`, `s^1.0000`; bounds bracket within 8.4x |
| C5 Lem 5.3/5.4 — covering + Rademacher | **verified** | 8 explicit delta-nets built and measured to be genuine delta-coverings, all inside the bound; exact entropy integral fits `s^1.5000 N^-0.5000` (R2 = 1) |
| C6 Prop 5.1 — concavity, `‖g‖ <= 2B sqrt(s)` | **verified** | 182,400 concavity + 48,000 supergradient checks with zero violations; adversarial family attains the bound at ratio exactly 1.000 |

**The one nuance worth stating plainly.** Theorem 5.12 is verified: SGA with averaging obeys its
explicit constant everywhere and attains the minimax `N^-1/2`, `s^+1` rate. But the premise that ERM
is worse by `sqrt(s)` is not observed. On the paper's own hard family the *exact* worst-case ERM risk
is only 1.03x the exact minimax floor (s-exponent 0.97, not 1.5), while SGA sits 2.8-3.8x above it.
The `sqrt(s)` gap lives in the covering-number analysis of ERM, not in ERM — which is what
Remark 5.11 itself concedes.

## Scope & cost

| Item | Value |
| --- | --- |
| Scope | all 6 claims, 3 MILP instance families, exact duals; 100% independent re-implementation (no code released by the authors) |
| Hardware | CPU only — numpy + `scipy.optimize.linprog`/`milp` (HiGHS). No GPU, no API key |
| Compute time | 52 min wall clock total across 8 scripts (longest single script 26 min) |
| Cost | $0 |
| Paper | [arXiv 2605.19052](https://arxiv.org/abs/2605.19052) · [OpenReview OwLuqetJuB](https://openreview.net/forum?id=OwLuqetJuB) |
| Logbook | [{space}]({space}) |
""".replace(
    "{space}", SPACE
)

poster_html = open(os.path.join(ROOT, "poster", "poster_embed.html")).read()
POSTER_CELL = cell(
    "figure",
    "Reproduction poster (poster_embed.html)",
    "````html\n" + poster_html.rstrip() + "\n````",
    pinned=True,
    extra={"poster": True},
)

write(
    "executive-summary",
    "Executive summary",
    [cell("markdown", "Executive summary", EXEC, pinned=True), POSTER_CELL],
)

# ======================================================================== shared method note
METHOD = """### How the dual is computed (shared by all claim pages)

For every family the Lagrangian dual

`u(pi,P) = min { c'x + pi'(b - Ax) : x in R^m_+ x {0,1}^p, Cx >= d }`

is evaluated **exactly**, not approximately. Because the objective is linear in `x`, the minimum over
the (non-convex) local set `X = {x : Cx >= d}` is attained on a finite candidate set that we
enumerate once per instance: the vertices of the continuous polytope crossed with the feasible binary
assignments (`scripts/common.py`), or the per-block solution sets when the instance is block
decomposable (`scripts/blockfam.py`). Every enumerated oracle is cross-checked against
`scipy.optimize.milp` (HiGHS) on random `(pi,P)` pairs: max |difference| 4.9e-10 (flat family) and
7.1e-15 (block family).

Populations are **explicit finite pools**, so `D` is exactly the uniform distribution over the pool
and `max_pi E_P[u(pi,P)]` is an exactly computable number. Both the population optimum and the ERM
optimum are obtained by Kelley cutting planes with an LP master solved by
`scipy.optimize.linprog(method="highs")`, which terminates finitely and exactly on a concave
piecewise-linear objective.

Three families are used:
- **flat** — `m=2` continuous + `p=5` binary variables, `s` coupling rows, instance size fixed as `s` grows (`scripts/common.py`);
- **block-decomposable** — `s` sub-problems and `s` coupling rows, each row linking two adjacent blocks, so the instance *grows* with `s` and `B`, `pi_max`, `pi*` stay `s`-independent (`scripts/blockfam.py`);
- **the paper's own hard family** — the restricted instances `P = (c, I_s, (1/2)1_s, 0, 0)` from the proof of Theorem 5.6 (`scripts/hardfam.py`).
"""

# ======================================================================== claim 1
C1 = """## Claim (verbatim)

> For learned Lagrangian Relaxation multipliers over s coupling constraints and N training samples,
> the expected excess risk of the ERM solution is upper bounded by O(s^1.5/√N) (Theorem 5.5).

## Verdict — **verified** (the bound holds everywhere; it is not tight in `s`, as Remark 5.11 concedes)

## Independent method

We never quote the proof. We measure the quantity the theorem bounds:

`E(pi_hat) = E_S [ max_pi E_P u(pi,P) - E_P u(pi_hat(S),P) ]`

with **both** terms computed exactly (see the method note above). ERM `pi_hat(S)` is the exact
maximiser of the empirical average over the sample, obtained by cutting planes on HiGHS. We then fit
both scaling exponents and compare against the explicit constant that the paper's own proof chain
implies:

`E(pi_hat) <= 2 * E[sup deviation] <= 4 R_N(U) <= 12 sqrt(pi) B pi_max s^1.5 / sqrt(N)`

(Theorem 3.2 gives the factor 2 on the Rademacher complexity, Lemma 5.4 the entropy bound.)

## Scale and seeds

| family | pool `M` | `s` | `N` | trials/cell | seed | wall time |
| --- | --- | --- | --- | --- | --- | --- |
| flat (`scripts/claim1_thm55.py`) | 8,000 | 2,4,8,16,32 | 16…1024 | 25 | 1055 | 25.8 min |
| block (`scripts/claim1b_blocks.py`) | 1,500 | 2,4,8,16,32 | 16…256 | 20 | 918273 | 9.7 min |
| hard family (`scripts/claim3_thm512.py`) | exact (closed form over the binomial) | 2…64 | 16…2048 | exact | 51222026 | — |

## Numerical result

| measurement | measured | predicted by Thm 5.5 |
| --- | --- | --- |
| bound violations over 60 `(s,N)` cells | **0** | 0 |
| worst measured / bound ratio | 2.1e-4 (flat), 1.4e-4 (block) | <= 1 |
| ERM `N`-exponent, fixed benign `D` (block family) | −0.95 … −1.02 | <= −0.5 (fast rate is allowed) |
| ERM `s`-exponent, block family | 0.89 … 1.08 | <= 1.5 |
| ERM `N`-exponent, minimax regime (hard family, `eps* ~ 1/sqrt(N)`) | **−0.552** | −0.5 |
| ERM `s`-exponent, minimax regime | **0.971** | 1.5 (bound) / 1.0 (lower bound) |
| exact worst-case ERM risk / exact minimax lower bound at `N=2048` | **1.03x** | >= 1 |

So the inequality of Theorem 5.5 is never violated, its `N`-exponent is right in the worst case, and
its `s`-exponent is a genuine over-estimate: measured `s^0.97`, not `s^1.5`.

## Limitations

- On a *fixed* benign distribution ERM enjoys the fast rate `N^-1`; the `N^-1/2` of Theorem 5.5 is a
  worst-case statement and is only visible in the minimax regime where the hardest distribution is
  re-chosen per `N`. We report both regimes rather than only the flattering one.
- On the **flat** family the `s`-exponent is confounded: the instance size is held fixed while `s`
  grows, so `pi*` itself shrinks like `1/s` (from 0.64 at `s=2` to 0.05 at `s=32`) and the fitted
  exponent drifts between 0.47 and 1.01. That is why the block-decomposable family (whose size grows
  with `s`) and the paper's own hard family are the ones we read the `s`-exponent from.
- Instances are small (tens of binaries) so that every dual is exact; no large-scale MILP benchmark
  was run.

## Artifacts

`scripts/claim1_thm55.py`, `scripts/claim1b_blocks.py`, `scripts/common.py`, `scripts/blockfam.py` ·
`outputs/claim1_thm55.json`, `outputs/general_sweep.json`, `outputs/block_sweep.json` ·
`figs/fig2_block_family.png`
"""

# ======================================================================== claim 2
C2 = """## Claim (verbatim)

> A minimax lower bound of Ω(s/√N) is proven, showing linear dependence on the number of coupled
> constraints s is unavoidable for any learning algorithm (Theorem 5.6).

## Verdict — **verified**, by two independent routes

## Independent method

**(I) Every ingredient of the paper's Fano argument as executable code.** We implement the restricted
instance family `P = (c, I_s, (1/2)1_s, 0, 0)` and check, rather than assume:

| ingredient | check | result |
| --- | --- | --- |
| restricted identity `u(pi,P) = Σ_k min(pi_k/2, c_k − pi_k/2)` | vs brute-force MILP over `{0,1}^s`, 500 draws | max diff **0.0** |
| Lemma 5.7: `pi*(D_v) = mu·1 + sigma·v` | 1,800 random `(v,eps)`, exact optimiser | **0 failures** |
| Lemma 5.7: `‖pi*(D_v) − pi*(D_v')‖_1 = sigma·d_H(v,v')` | same | max error **0.0** |
| Varshamov–Gilbert packing `|V| >= 2^(s/8)`, pairwise Hamming `>= s/8` | greedy construction, `s = 16…64` | **constructed for every `s`** |
| Lemma 5.8: `KL(D_v^N ‖ D_v'^N) <= 4 N s eps^2` | exact Bernoulli KL, `eps = 0.01…0.49` | **holds everywhere** |
| Lemma 5.9: `E(pi) >= (eps/2)‖pi*−pi‖_1` | exhaustive 2001-point grid per coordinate | **holds, and is tight (ratio exactly 1)** inside `[mu, mu+sigma]` |

**(II) An estimator-free lower bound that does not go through Fano at all.** Put a uniform prior
`v ~ Unif({0,1}^s)` on the hard family. Since `sup_D >= E_v`, the **Bayes risk of the optimal
estimator** is a rigorous lower bound on the minimax risk — valid for every learning algorithm, not
just the ones we happened to run. Because the coordinates are independent with binomial sufficient
statistic `n_k`, that Bayes risk is computable in closed form by summing over `n = 0…N` and
minimising a piecewise-linear posterior loss over the four breakpoints. We then maximise it over the
perturbation scale `eps`.

## Scale and seeds

`scripts/claim2_thm56.py`, seed 5062026, `mu = 0.25`, `sigma = 0.5`, `pi_max = 1`, `B = 1`
(the normalisation of Remark 5.10). `N` in 16…2048, `s` in 2…64. Wall time 15 s; the lower bound is
exact, not sampled.

## Numerical result

| quantity | fitted exponent | predicted | `R^2` |
| --- | --- | --- | --- |
| exact Bayes minimax lower bound vs `N` | **−0.5053** | −1/2 | 0.99994 |
| exact Bayes minimax lower bound vs `s` | **1.0000** | +1 | 1.000 |

Constant: `inf_pi sup_D E(pi) >= 0.0425 · s/sqrt(N)`. The maximising perturbation satisfies
`eps* · sqrt(N) ≈ 0.61…0.78`, i.e. `eps* = Theta(1/sqrt(N))` exactly as the proof prescribes.
Every concrete estimator we ran (ERM, SGA with averaging) has worst-case risk above this floor, as it
must, at every one of the 12 `(s,N)` configurations tested.

The paper's *own* Fano chain, assembled numerically, yields
`E >= [ (1/2)·sqrt(log2/64) · (sigma·s/16) · (1/2 − 8/s) ] / sqrt(N)`, i.e. `7.1e-4 · s/sqrt(N)` at
`s = 128` — the same `Omega(s/sqrt(N))` shape with a 60x smaller constant than the Bayes route.

## Two audit findings (both sharpen the paper; neither contradicts it)

1. **Lemma 5.8's intermediate step is off.** The proof bounds `KL <= chi^2` and then quotes
   `chi^2 = 4 eps^2/(1 − eps^2)`, which **exceeds** `4 eps^2` for every `eps > 0` (1.264 vs 0.960 at
   `eps = 0.49`). The lemma's *conclusion* `KL <= 4 N s eps^2` is nevertheless true: the exact
   Bernoulli KL is `eps·log((1+eps)/(1−eps))`, which we verify is `<= 4 eps^2` on all of `(0, 1/2)`.
2. **`s >= 16` is off by one.** The testing factor that Fano's inequality leaves is
   `1 − (I + log 2)/log M = 1/2 − 8/s`, which is **exactly zero at `s = 16`**, making the bound
   vacuous at the theorem's stated boundary. The argument needs `s >= 17` (or a sharper packing).

## Limitations

- The lower bound is proved for the *specific* hard family the paper constructs (as is the
  theorem). It is a lower bound on the minimax risk over `Delta(P)` precisely because that family
  is contained in `Delta(P)`.
- The Bayes-risk route uses the uniform prior on all of `{0,1}^s` rather than the VG packing subset;
  this is a legitimate (and tighter) instance of the same `sup >= average` argument, and we also
  construct the VG packing explicitly to check the paper's own route.

## Artifacts

`scripts/claim2_thm56.py`, `scripts/hardfam.py` · `outputs/claim2_thm56.json` ·
`figs/fig1_minimax_rates.png`
"""

# ======================================================================== claim 3
C3 = """## Claim (verbatim)

> Stochastic Gradient Ascent with iterate averaging is shown to achieve the matching O(s/√N) rate,
> closing the O(√s) gap between the ERM upper bound and the minimax lower bound and establishing
> minimax optimality (Theorem 5.12).

## Verdict — **verified** for the theorem as stated; the `sqrt(s)` gap is a property of the *analysis of ERM*, not of ERM

## Independent method

1. **Re-derivation of the explicit constant.** Theorem 5.12 states
   `E[E(pi_bar_N)] <= 2 B pi_max s / sqrt(N)` at `eta = pi_max/(2 B sqrt(N))`. We re-derive it from
   the textbook projected-stochastic-supergradient bound `D^2/(2 eta N) + eta L^2/2` with
   `D = diam(Pi) = pi_max sqrt(s)` and `L = 2B sqrt(s)` (Corollary 5.2). Over 108 `(s, B, pi_max, N)`
   configurations the two expressions agree to **relative difference 0.0**, and the paper's step size
   is the **exact minimiser** `D/(L sqrt(N))` of that bound in every configuration.
2. **Direct verification of the inequality** on the flat family, the block family and the paper's
   hard family, running Algorithm 1 verbatim (projection onto `[0,pi_max]^s`, unbiased subgradient
   `g_t = b_t − A_t x*_t`, output the average `pi_bar_N = (1/N) Σ pi_t`).
3. **Minimax-regime rates**: SGA is evaluated on the worst-case distribution for each `N` (the hard
   family with `eps*` maximising the exact Bayes lower bound), and both exponents are fitted.
4. **Ablations** on the theorem's hypotheses: averaging vs the last iterate, step size mis-scaled by
   factors `0.01…100`, `eta ~ 1/N`, and a constant `eta`.
5. **The headline claim** is tested by computing the *exact* worst-case ERM risk on the paper's own
   hard family — a closed-form expectation over the binomial sufficient statistic, no Monte Carlo —
   and comparing it against the exact Bayes minimax floor and against SGA.

## Scale and seeds

`scripts/claim3_thm512.py` (seed 51222026), `scripts/claim1_thm55.py`, `scripts/claim1b_blocks.py`.
`s` in 2…64, `N` in 16…4096, 300–400 Monte-Carlo repetitions per SGA cell. Wall time 2.4 min
(plus the shared sweeps).

## Numerical result

| measurement | measured | predicted |
| --- | --- | --- |
| OCO re-derivation vs `2 B pi_max s/sqrt(N)` | relative difference **0.0** | equal |
| paper's `eta` is the minimiser of that bound | **true in 108/108 configs** | true |
| Thm 5.12 bound violations (flat + block + hard, 66 cells) | **0** | 0 |
| worst measured / bound ratio | **0.108** | <= 1 |
| SGA `N`-exponent, block family | **−0.537 … −0.604** | −0.5 |
| SGA `s`-exponent, block family | **1.02 … 1.07** | +1 |
| SGA `N`-exponent, minimax regime | **−0.558** | −0.5 |
| SGA `s`-exponent, minimax regime | **0.908** | +1 |

**Ablations (`s = 16`, `N = 512`, bound = 1.414).** Averaged with the paper's step size: 0.039.
Last iterate: 0.043 (averaging is not what makes it work at this scale). Step size `0.01x`: **1.809 —
the bound is violated**, and the fitted `N`-exponent collapses to −0.095. Step size `100x`: 0.070,
`N`-exponent −0.353. So the `1/sqrt(N)` scaling of `eta` is load bearing: mis-scale it and Theorem
5.12's conclusion fails.

## The `sqrt(s)` gap: an honest negative result

On the paper's own hard family, with everything computed exactly:

| `N` | exact worst-case ERM | SGA + averaging | exact minimax LB | ERM/LB | SGA/LB |
| --- | --- | --- | --- | --- | --- |
| 64 | 0.006203 | 0.017684 | 0.005320 | 1.17 | 3.32 |
| 256 | 0.002870 | 0.007848 | 0.002653 | 1.08 | 2.96 |
| 1024 | 0.001381 | 0.004063 | 0.001324 | **1.04** | 3.07 |
| 2048 | 0.000959 | 0.002581 | 0.000932 | **1.03** | 2.77 |

ERM's measured `s`-exponent is 0.971 and SGA's is 0.908; both match the lower bound's 1.0, and
neither is near 1.5. **SGA does not beat ERM on any family we could construct — it is consistently
~3x worse.** Theorem 5.12 is still verified: it closes the gap *between the upper and lower bounds*
by exhibiting an algorithm with a provable `O(s/sqrt(N))` guarantee. But the framing that ERM pays a
`sqrt(s)` penalty is not observable; the penalty is in the covering-number analysis of ERM, exactly
as Remark 5.11 anticipates.

## Limitations

- SGA's risk is Monte-Carlo estimated (300–400 repetitions; standard errors are in the JSON), unlike
  ERM's, which is exact on the hard family.
- "ERM is not `sqrt(s)` worse" is a statement about the families we tested (three of them, including
  the paper's own worst case), not a proof that no family separates them.

## Artifacts

`scripts/claim3_thm512.py`, `scripts/hardfam.py`, `scripts/blockfam.py` ·
`outputs/claim3_thm512.json`, `outputs/general_sweep.json`, `outputs/block_sweep.json` ·
`figs/fig1_minimax_rates.png`
"""

# ======================================================================== claim 4
C4 = """## Claim (verbatim)

> The framework is extended to learning-to-warm-start sub-gradient ascent for large-scale Mixed
> Integer Linear Programming, with an O(s/N) risk upper bound (Theorem 6.1) and matching Ω(s/N)
> minimax lower bound (Theorem 6.2).

## Verdict — **verified**, on both sides, with the two bounds bracketing the truth within 8.4x

## Independent method

The Section 6 objective is `l(phi,P) = ‖phi − pi*(P)‖_2^2`, so the ERM estimator is the sample mean
`phi_hat = (1/N) Σ_i pi*(P_i)` and the excess risk is exactly `tr Cov(pi*(P)) / N`.

**Upper bound (Thm 6.1).** For each instance we compute the *exact* minimum-norm-style maximiser
`pi*(P_i)` with a vanishing linear tie-break (`1e-6 Σ_k pi_k`), i.e. an "arbitrary but consistent
tie-breaking rule" in the paper's own sense, again by cutting planes on HiGHS. From the resulting
empirical covariance we obtain the excess risk in closed form and confirm it by Monte-Carlo, then fit
both exponents and check the constant Popoviciu's inequality gives:
`E(phi_hat) <= s pi_max^2 / (4N)`.

**Lower bound (Thm 6.2).** Same estimator-free device as Claim 2: on the hard family
`pi*(P) = c` exactly, so `phi*(D_v)_k = mu + sigma(1 ± eps)/2` and the problem is two-point mean
estimation per coordinate. The Bayes risk of the optimal estimator (posterior mean; Bayes risk =
expected posterior variance) is summed exactly over the binomial sufficient statistic and maximised
over `eps` — a rigorous lower bound over all algorithms.

## Scale and seeds

| part | script | scale | seed | wall time |
| --- | --- | --- | --- | --- |
| upper, flat family | `scripts/claim4_thm61_62.py` | 2,000 exact `pi*(P)` per `s`, `s` in 2…16, `N` in 8…512, 400 MC reps | 6162026 | 4.3 min |
| upper, block family | `scripts/claim4b_blocks.py` | 800 exact `pi*(P)` per `s`, `s` in 2…32, `N` in 8…512 | 61618 | 37 s |
| lower bound | `scripts/claim4_thm61_62.py` | exact, `N` in 8…2048, 100-point `eps` grid | — | — |

## Numerical result

| quantity | measured | predicted |
| --- | --- | --- |
| ERM `N`-exponent, block family | **−1.000** (all `s`) | −1 |
| ERM `s`-exponent, block family | **0.982** | +1 |
| ERM `N`/`s`-exponents, restricted family | **−1.0000 / 1.0000** (`R^2 = 1`) | −1 / +1 |
| Popoviciu bound `s pi_max^2/4N` violations | **0** (worst ratio 0.40) | 0 |
| exact minimax lower bound vs `N` | **−0.986** (`R^2 = 0.9998`) | −1 |
| exact minimax lower bound vs `s` | **1.0000** (`R^2 = 1`) | +1 |
| upper / lower bracket at `s=16` | **8.36 – 8.57x** across `N` | constant factor |
| `eps*·sqrt(N)` at the maximising perturbation | 1.12 – 1.28 | `Theta(1)` |

Both sides therefore reproduce, and `Theta(s/N)` is confirmed — a full power of `N` faster than the
`Theta(s/sqrt(N))` of direct multiplier learning (Remark 6.3), which we measure in Claims 2 and 3
on the *same* instance family.

## Boundary audit

The `O(s/N)` constant is not scale free: it is exactly `pi_max^2`-homogeneous. Scaling the support of
the optimal multipliers by 0.5, 1, 2, 4 multiplies the measured excess risk by 0.25, 1, 4, 16 while
the Popoviciu bound tracks it exactly, and the bound is respected at every scale. Assumption 4.2
(bounded hypercube) is therefore load bearing for the constant, not just for the compactness
argument.

## Limitations

- `pi*(P)` is only unique up to the tie-breaking rule; we use the vanishing-linear-penalty rule
  rather than the exact minimum-`l2`-norm projection the paper suggests. The paper explicitly allows
  any consistent rule, and on the hard family (where the maximiser is strictly unique) the two
  coincide.
- On the **flat** family the fitted `s`-exponent is 0.541, not 1: `tr Cov` saturates because the
  instance size is held fixed while `s` grows. The block family, whose size grows with `s`
  (per-coordinate variance constant at 0.091–0.092), is the one that answers the `s` question.

## Artifacts

`scripts/claim4_thm61_62.py`, `scripts/claim4b_blocks.py`, `scripts/hardfam.py` ·
`outputs/claim4_thm61_62.json`, `outputs/claim4b_blocks.json` · `figs/fig3_warmstart.png`
"""

# ======================================================================== claim 5
C5 = """## Claim (verbatim)

> The covering number of the dual multiplier class U is bounded as
> log N(δ,U,‖·‖₂,N) ≤ s·log(1+2Bπ_max s/δ), used to derive the Rademacher complexity bound
> R_N(U)=O(s^1.5/√N) (Lemma 5.3, Lemma 5.4).

## Verdict — **verified**; the bound is valid with large slack, and the `s^1.5` shape is *exactly* right

## Independent method

Four separate executable checks, none of which quotes the proof.

1. **Lipschitz transfer.** The proof turns a `delta/L`-net of `Pi` into a `delta`-net of `U` using
   `L = 2B sqrt(s)` (Corollary 5.2). We measure the true secant slope
   `‖u(pi,·) − u(pi',·)‖_{2,N} / ‖pi − pi'‖_2` over 600 random pairs per `s`, and also compute the
   *exact* Lipschitz constant `max_{i,j} ‖b_i − A_i x_j‖_2` (exact because `u` is a min of affine
   functions).
2. **Explicit `delta`-net construction.** For `s = 1,2,3` and `delta` in {0.5, 0.25, 0.1} we build the
   grid net the proof prescribes and then *measure* that it is a genuine `delta`-covering: for 3,000
   random `pi` we compute the empirical-`L2` distance to the nearest net function and check it is
   `<= delta`. We then compare `log|net|` with the claimed bound.
3. **Greedy `2delta`-packing** of `U` from 4,000 random `pi`, giving a lower estimate of the true
   covering number and hence of how much slack Lemma 5.3 carries.
4. **Dudley chain re-derivation.** We verify the paper's footnote identity
   `∫_0^R sqrt(log(R/delta)) d delta = R sqrt(pi)/2` numerically, then numerically integrate the
   entropy integral `∫_0^{LD} sqrt(log N(delta)/N) d delta` with the paper's own covering bound and fit
   its exponents in `s` and `N`. Finally we **measure** `R_N(U)` itself: rigorous two-sided brackets
   at `s = 1, 2` (fine grid plus exact Lipschitz slack) and a 200-restart projected-ascent lower
   estimate up to `s = 16`.

## Scale and seeds

`scripts/claim5_covering.py`, seed 5052026, `pi_max = 1`, flat family with `m=2, p=5`. Nets up to
314,432 points; 150-instance pools for the covering tests, 400-instance pools and 600 Rademacher sign
draws for the complexity measurement. Wall time 8.7 min.

## Numerical result

**Lemma 5.3 (covering number).** All 8 explicitly constructed nets are genuine `delta`-coverings
(largest measured distance to the net 0.054 at `delta = 0.5`), and `log|net|` is inside the bound in
every case:

| `s` | `delta` | `log|net|` built | Lemma 5.3 bound | greedy `2delta`-packing (lower est.) |
| --- | --- | --- | --- | --- |
| 1 | 0.50 | 2.398 | 3.076 | 0.00 |
| 1 | 0.10 | 3.951 | 4.647 | 1.10 |
| 2 | 0.10 | 9.383 | 10.774 | 2.20 |
| 3 | 0.25 | 12.62 | 14.71 | 1.39 |

The bound holds with 8–14 nats of slack against the packing lower estimate — mostly because
`L = 2B sqrt(s)` overshoots the exact Lipschitz constant by about **6.8x** (e.g. 46.5 vs 6.85 at
`s = 16`), which the covering bound then raises to the power `s`.

**Lemma 5.4 (Rademacher complexity).** The footnote identity checks to relative error **1.7e-7**.
The exact entropy integral, computed from the paper's covering bound, fits

| quantity | fitted exponent | predicted | `R^2` |
| --- | --- | --- | --- |
| entropy integral vs `s` (at `N=1024`) | **1.5000000** | 1.5 | 1.000 |
| entropy integral vs `N` (at `s=16`) | **−0.5000000** | −0.5 | 1.000 |

and the paper's closed form `3 sqrt(pi) B pi_max s^1.5/sqrt(N)` is a valid upper bound on it, larger
by exactly 2.33x for every `(s,N)` tested. Measured `R_N(U)` never violates Lemma 5.4 (worst
measured/bound ratio 0.013), its `N`-exponents are −0.37 (`s=1`) and −0.59 (`s=2`), and its fitted
`s`-exponent is **1.57** (`R^2 = 0.995`).

**Interpretation.** The `s^1.5` in Lemma 5.4 appears to be *tight for the Rademacher complexity
itself*. The looseness that Theorem 5.5 inherits (measured excess-risk `s`-exponent ≈ 1.0, see
Claim 1) therefore enters at the uniform-convergence step `E(pi_hat) <= 4 R_N(U)`, not in the entropy
bound. That is a sharper localisation of the gap than Remark 5.11 offers.

## Limitations

- The measured Rademacher complexity is *rigorously bracketed* only for `s = 1, 2`; for `s >= 4` the
  supremum `sup_pi (1/N) Σ sigma_i u(pi,P_i)` is a difference of concave piecewise-linear functions
  (not concave), so we use a 200-restart local-ascent **lower** estimate. A lower estimate cannot
  produce a false violation of an upper bound, but the `s`-exponent 1.57 should be read as
  "consistent with `s^1.5`", not as a proof of tightness.
- Explicit nets are only feasible for `s <= 3`: the net size is `(1 + 2B pi_max s/delta)^s`.

## Artifacts

`scripts/claim5_covering.py`, `scripts/common.py` · `outputs/claim5_covering.json` ·
`figs/fig4_prop51_covering.png`
"""

# ======================================================================== claim 6
C6 = """## Claim (verbatim)

> The dual function u(π,P) is shown to be concave in π with subgradient norm bounded by 2B√s under
> bounded constraint-violation assumptions on the MILP instance (Proposition 5.1, Section 4).

## Verdict — **verified**, and the constant 2 is shown to be **attained** (the bound cannot be improved)

## Independent method

Proposition 5.1 is turned into five executable predicates, each evaluated on random MILP instances
with `s` in {2,4,8,16}, plus one adversarial construction:

1. **Oracle exactness** — our enumerated dual oracle vs `scipy.optimize.milp` (HiGHS), 360 random
   `(pi,P)` pairs.
2. **Weak duality** `u(pi,P) <= OPT(P)` — the classical property the relaxation exists for, with
   `OPT(P)` solved independently by HiGHS with the coupling rows included.
3. **Concavity** — Jensen's inequality `u(lam·pi1 + (1−lam)·pi2) >= lam·u(pi1) + (1−lam)·u(pi2)` on
   random segments, 19 values of `lam` per segment.
4. **Supergradient property** — `u(pi') <= u(pi) + g(pi,P)'(pi' − pi)` for `g = b − A x*(pi,P)`,
   which is the exact statement of Proposition 5.1(ii).
5. **Norm bound** — `‖g‖_2 <= 2B sqrt(s)` where `B` is the *exact* Assumption-4.1 constant of the
   instance, computed as `max( max_k|b_k|, max_{x in cand, k} |(Ax)_k| )` over the enumerated
   candidate set (a linear function attains its max over a polytope at a vertex, so this is exact).

**Boundary audit.** Assumption 4.1 is then deliberately broken: we hand the theorem a *claimed*
constant `B' = rho·B` with `rho < 1` and count violations of `‖g‖_2 <= 2 B' sqrt(s)`.

**Tightness audit.** The family `A = B·I_s`, `b = −B·1_s`, `X = {0,1}^s`, `c = −10·1` forces
`x* = 1` at `pi = 0`, so `g = b − Ax* = −2B·1` and `‖g‖_2 = 2B sqrt(s)` exactly.

## Scale and seeds

`scripts/claim6_prop51.py`, seed 20260725, 60 instances per `s` in {2,4,8,16}, `m = 2` continuous
and `p = 5` binary variables per instance. Wall time **4.1 s**.

## Numerical result

| test | checks | worst case | verdict |
| --- | --- | --- | --- |
| enumerated oracle vs HiGHS `milp` | 360 | max |diff| **4.9e-10** | exact |
| weak duality `u <= OPT` | 320 | min gap **+0.0124** | holds |
| concavity (Jensen) | 182,400 (45,600 per `s`) | min slack **−0.0** | holds |
| supergradient inequality | 48,000 (12,000 per `s`) | max violation **0.0** | holds |
| `‖g‖_2 / (2B sqrt(s))`, random MILPs | 12,000 (+6,000 per audit level) | **0.207** | holds |
| `‖g‖_2 / (2B sqrt(s))`, adversarial family | `s = 2…16` | **1.000** | **attained** |

**Boundary audit** — violations of the norm bound as the claimed `B'` shrinks:

| `B'/B` | 1.0 | 0.9 | 0.7 | 0.5 | 0.3 | 0.1 |
| --- | --- | --- | --- | --- | --- | --- |
| violation fraction | 0.000 | 0.000 | 0.000 | 0.000 | 0.000 | **0.702** |
| max ratio | 0.207 | 0.230 | 0.296 | 0.413 | 0.691 | **2.073** |

So the bound holds exactly while Assumption 4.1 holds and fails once it is broken by enough — the
assumption is load bearing for part (ii). Part (i), concavity, is assumption free: it is a property of
a minimum of affine functions and we confirm it holds even when `B` is understated.

## Limitations

- On *random* MILPs the bound is loose by ~5x (`‖g‖_2 <= 0.207 · 2B sqrt(s)`) because `B` is a
  worst-case coordinate bound over all feasible `x`, while `g` is evaluated at a single optimiser.
  The adversarial family shows the constant is nevertheless unimprovable in general.
- The "subgradient" is a supergradient (`u` is concave); the paper says so explicitly and we test the
  supergradient inequality, not the subgradient one.

## Artifacts

`scripts/claim6_prop51.py`, `scripts/common.py` · `outputs/claim6_prop51.json` ·
`figs/fig4_prop51_covering.png` (left panel)
"""

pages = [
    (
        "claim-1-thm-5-5-erm-excess-risk-o-s-1-5-sqrt-n",
        "Claim 1: Thm 5.5: ERM excess risk O(s^1.5/sqrt(N))",
        C1,
    ),
    (
        "claim-2-thm-5-6-minimax-lower-bound-omega-s-sqrt-n",
        "Claim 2: Thm 5.6: minimax lower bound Omega(s/sqrt(N))",
        C2,
    ),
    (
        "claim-3-thm-5-12-sga-averaging-attains-o-s-sqrt-n",
        "Claim 3: Thm 5.12: SGA + averaging attains O(s/sqrt(N))",
        C3,
    ),
    (
        "claim-4-thm-6-1-6-2-warm-start-theta-s-n",
        "Claim 4: Thm 6.1/6.2: warm-start Theta(s/N)",
        C4,
    ),
    (
        "claim-5-lemma-5-3-5-4-covering-number-and-rademacher-bound",
        "Claim 5: Lemma 5.3/5.4: covering number and Rademacher bound",
        C5,
    ),
    (
        "claim-6-prop-5-1-dual-concavity-subgradient-norm-2b-sqrt-s",
        "Claim 6: Prop 5.1: dual concavity, subgradient norm <= 2B sqrt(s)",
        C6,
    ),
]
for slug, heading, body in pages:
    cells = [cell("markdown", heading, body)]
    if slug.startswith("claim-1"):
        cells.append(
            cell("markdown", "Method: how the dual is computed exactly", METHOD)
        )
    write(slug, heading, cells)

# ======================================================================== conclusion
CONCL_ART = "https://huggingface.co/buckets/SabaPivot/repro-lagrangian-milp-artifacts"

CONCL = """## Outcome

All six claims of **"Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear
Programming"** (arXiv 2605.19052, OpenReview OwLuqetJuB) **reproduce**. Nothing in the paper had to be
contradicted; two intermediate steps were found to be imprecise and are reported as audit findings
rather than as failures.

| Claim | Verdict | Decisive number |
| --- | --- | --- |
| C1 Thm 5.5 | verified | 0 violations in 60 `(s,N)` cells; minimax-regime exponents `N^-0.55`, `s^0.97` |
| C2 Thm 5.6 | verified | exact Bayes minimax lower bound `0.0425 s/sqrt(N)`; `N^-0.5053`, `s^1.0000` |
| C3 Thm 5.12 | verified | constant re-derived to machine zero; 0 violations; `N^-0.54..-0.60`, `s^1.02..1.07` |
| C4 Thm 6.1/6.2 | verified | `N^-1.000`/`s^0.982` upper, `N^-0.986`/`s^1.0000` lower, 8.4x bracket |
| C5 Lem 5.3/5.4 | verified | 8 verified `delta`-nets inside the bound; entropy integral `s^1.5000 N^-0.5000` |
| C6 Prop 5.1 | verified | 242,400 checks, 0 violations; constant 2 attained at ratio exactly 1.000 |

## What we found that the paper does not say

1. **The `sqrt(s)` gap is not ERM's.** On the paper's own hard family the *exact* worst-case ERM risk
   is 1.03x the exact minimax floor with `s`-exponent 0.97, while SGA-with-averaging is 2.8–3.8x above
   the floor. Theorem 5.12 is verified as stated (it closes the gap between the bounds), but SGA never
   outperformed ERM on any family we could build.
2. **`s >= 16` should be `s >= 17`.** The Fano testing factor in the proof of Theorem 5.6 is
   `1/2 − 8/s`, which is exactly zero at the theorem's stated boundary `s = 16`.
3. **Lemma 5.8's `chi^2` step is off by `1/(1−eps^2)`** (`4eps^2/(1−eps^2) > 4eps^2`); the lemma's
   conclusion is nevertheless true via the exact Bernoulli KL, which we verify on all of `(0,1/2)`.
4. **The `s^1.5` is tight for the Rademacher complexity, not for the risk.** The exact entropy
   integral fits `s^1.5000` and the measured `R_N(U)` fits `s^1.57`, while the measured excess risk
   fits `s^0.97`. The looseness therefore enters at the uniform-convergence step, not the covering
   bound — a sharper localisation than Remark 5.11 gives.

## Limitations of this reproduction

- Instances are small (tens of binary variables, `s <= 64`) so that every dual value, population
  optimum and ERM optimum is **exact**; no large-scale MILP benchmark (VRP, unit commitment) was run.
- The measured Rademacher complexity is rigorously bracketed only for `s <= 2`; larger `s` uses a
  multi-start lower estimate.
- Lower bounds are exact Bayes risks on the paper's own hard family, which is the standard and
  correct way to certify a minimax lower bound, but does not rule out harder families.
- SGA risks are Monte-Carlo estimates (300–400 repetitions); ERM risks on the hard family are exact.
"""

RERUN = """## Download the reproduction bundle and rerun

Everything needed to reproduce these numbers from nothing is in the bundle
attached above — HF Bucket [`SabaPivot/repro-lagrangian-milp-artifacts`]({art})
(`repro-bundle.tar.gz`, plus `scripts/`, `outputs/`, `figs/`, `poster/` unpacked) — and in the logbook Space
[{space}]({space}).

```bash
# CPU only, no GPU, no API key. ~52 min total.
pip install "numpy>=2" "scipy>=1.15" matplotlib

python scripts/claim6_prop51.py      # Prop 5.1     (  4 s)
python scripts/claim2_thm56.py       # Thm 5.6      ( 15 s)
python scripts/claim3_thm512.py      # Thm 5.12     (2.4 min)  [reads outputs/general_sweep.json]
python scripts/claim4b_blocks.py     # Thm 6.1      ( 37 s)
python scripts/claim4_thm61_62.py    # Thm 6.1/6.2  (4.3 min)
python scripts/claim5_covering.py    # Lem 5.3/5.4  (8.7 min)
python scripts/claim1b_blocks.py     # Thm 5.5, block family  (9.7 min)
python scripts/claim1_thm55.py       # Thm 5.5, flat family   ( 26 min)
python scripts/make_figures.py       # all four figures
```

Layout: `scripts/common.py` (flat MILP family, exact dual oracle, Kelley cutting planes),
`scripts/blockfam.py` (block-decomposable family), `scripts/hardfam.py` (the paper's own hard
family and the exact Bayes lower bounds), `outputs/*.json` (every raw number quoted in this
logbook), `figs/*.png`, `poster/` (posterly source, `GATE_REPORT.json`, rendered PDF/PNG),
`paper/paper.pdf`.

Paper: [arXiv 2605.19052](https://arxiv.org/abs/2605.19052) ·
[OpenReview OwLuqetJuB](https://openreview.net/forum?id=OwLuqetJuB). Pure theory paper — we searched
arXiv, the PDF and the project pages and found **no official code release**, so this reproduction is
100% independent re-implementation.
""".replace(
    "{art}", CONCL_ART
).replace(
    "{space}", SPACE
)

write(
    "conclusion",
    "Conclusion",
    [
        cell("markdown", "Outcome and findings", CONCL),
        cell(
            "artifact",
            "Reproduction bundle",
            CONCL_ART,
            extra={"artifact_type": "dataset"},
        ),
        cell("markdown", "Download & rerun", RERUN),
    ],
)

print("all pages written")