△ Mechanism confirmed, baseline not beaten 2026

Exact Multi-Output Linear-Probe Coreset

Implementation & benchmark of arXiv:2608.30254 — Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression

Usefulness7/10

Difficulty6/10

Novelty5/10

Memory Memory Speedup Sample efficiency Embedding Memory Fine tuning Linear algebra Convex analysis Combinatorics

Source paper: Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression arXiv:2608.30254 ⓘ · analyzed Sep 1, 2026

AI-generated research hypothesis, automatically tested. Not peer-reviewed.

Idea description

Compress a dataset for a frozen neural embedding and multi-output linear head into at most (m+1)r weighted examples while preserving the full-data minimum-Frobenius-norm least-squares solution. This can make repeated linear probing, classifier refitting, or replay-buffer training much smaller without changing the optimum in exact arithmetic.

Formulas

$$n^{\star}(d,m)=\min\{n:F_{\mathrm{weighted}}(d,m,n)=1\}=(m+1)d.$$

$$|S|\le (m+1)r\quad\Longrightarrow\quad \text{some weighted selection recovers a full-data optimum exactly},$$

$$A_w=\sum_{i\in S}w_i x_i x_i^{\top},\qquad B_w=\sum_{i\in S}w_i y_i x_i^{\top},\qquad W_w=B_wA_w^{\dagger}.$$

$$\min_W\sum_i\|Wx_i-y_i\|_2^2\quad\leadsto\quad \min_W\sum_{i\in S}w_i\|Wx_i-y_i\|_2^2.$$

Mathematical statement

The paper defines the exact-recovery threshold by n^{\star}(d,m)=\min\{n:F_{\mathrm{weighted}}(d,m,n)=1\} and proves that n^{\star}(d,m)=(m+1)d in the worst case. More generally, for a dataset whose feature matrix has rank r, some (m+1)r weighted points recover a full-data optimum exactly. For feature vectors x_i\in\mathbb{R}^d, targets y_i\in\mathbb{R}^m, and nonnegative weights w_i, define A_w=\sum_i w_i x_i x_i^{ op} and B_w=\sum_i w_i y_i x_i^{ op}. The minimum-Frobenius-norm weighted least-squares solution is W_w=B_wA_w^{\dagger}, where A_w^{\dagger} is the Moore-Penrose pseudoinverse, provided the weighted normal equations represent the same optimum. The implementation searches for a sparse nonnegative representation preserving the sufficient statistics needed by the quadratic objective.

Implementation notes

Integrate this after a frozen backbone and before a linear classifier or regression head. Given embeddings x_i\in\mathbb{R}^d and targets y_i\in\mathbb{R}^m, compute a numerical rank r using an SVD, retaining singular values above 10^{-6} times the largest singular value. Compute full statistics A=\sum_i x_ix_i^T and B=\sum_i y_ix_i^T. Initialize a support S with r linearly independent examples and positive weights. Form each atom z_i=[\operatorname{vech}(x_ix_i^T);\operatorname{vec}(y_ix_i^T)]. While the support is larger than the target, find a null vector c of the active atom matrix Z_S, choose a sign and step t so that w\leftarrow w-tc remains nonnegative, and delete any zero-weight atom. Because Z_Sc=0, this preserves the aggregate statistics. If generic elimination stops above (m+1)r, use support exchange: sample candidates outside S, solve nonnegative least squares to match [A;B], and accept swaps reducing support while keeping relative residual below 10^{-6}. The theorem supplies the support target; rank thresholds, NNLS tolerances, and exchange heuristics are empirical. Test on CIFAR-10 or a small multi-target regression task with a frozen ResNet-18 or MLP embedding, comparing the compressed head with the full-data head and a random subset of equal size. Measure support size, loss error, probe-refit time, and peak memory. Success means support near (m+1)r, relative loss error below 10^{-5}, and lower refit cost.

Verification

Mechanism confirmed, baseline not beaten

Stage 1 · Toy mechanism gate: Passed ✓

Stage 2 · Mechanism transferred to benchmark: Confirmed ✓

Stage 2 · Practical benchmark result: No measurable effect

Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works

Stage 1 — Mechanism check agent confidence 8/10

Built an exact weighted linear-probe coreset implementation using nonnegative nullspace elimination on residual-feature atoms. Across rank r=1..4 and output m=1,2,4, support met the predicted (m+1)r bound, with maximum normal-equation error 1.34e-15 and maximum relative fitted-parameter error 6.32e-15. At fixed r=3,m=2, support stayed at 9 while compression grew from 4.44x at N=40 to 35.56x at N=320; random equal-size subsets had mean relative parameter error 0.979. The mechanism manifested on synthetic low-rank regression, but this does not establish a win for frozen neural embeddings.

Agent confidence: 8/10

Baseline: Random equal-size subset: mean relative fitted-parameter error 0.979 on the rank/output sweep, with generally nonzero full-data loss degradation.
Idea: Support <= (m+1)r in every sweep; maximum residual-normal-equation relative error 1.34e-15; maximum solution relative error 6.32e-15; maximum full-loss relative error 5.09e-16; for r=3,m=2 support=9 at N=40,80,160,320 with compression 4.44x, 8.89x, 17.78x, 35.56x.

Limitations: Only synthetic exact-rank multi-output regression was tested. No CIFAR or frozen neural backbone benchmark, repeated refit timing benchmark, large-scale memory benchmark, noisy or ill-conditioned rank-threshold sweep, or support-exchange NNLS fallback was tested.

How to run: python3 run_experiment.py

Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.30254) Sep 2, 2026

No significant difference vs. the tuned baseline (+1.2%, p=0.6962, wins 4 / 8 paired seeds).

Benchmark: Tabular regression (Friedman)
Model: mlp_tiny
Paired seeds: 8
Baseline mean: 7.1366
Idea mean: 0
Effect (Δ): 0.0886 (+1.2%; negative = idea better)
Wins: 4 / 8 paired seeds
p-value: 0.6962 (permutation test, 20 000 shuffles)
Smallest detectable effect: n/a
Mechanism: Confirmed ✓
Practical effect: No effect
Baseline tuning: swept over 3 configs

Limitations:

Only the built-in tabular Friedman regression track and mlp_tiny were tested; no vision, sequence, dynamics, larger embeddings, repeated-refit timing, peak-memory measurement, noisy/ill-conditioned rank sweeps, or NNLS support-exchange fallback was tested.

How to run: python3 stage2_bench.py

Verdict computed by deterministic test code from paired-seed statistics — not by the language model.

Stage 2 — Benchmark Sep 2, 2026 latest Failed ✗

Agent confidence: 9/10

Implemented the exact weighted linear-probe coreset on the structurally matched tabular MLP track, using bench.train_model and parity-matched three-point learning-rate sweeps. The trained-embedding mechanism was confirmed: observed mean support 69 matched the estimated (m+1)r bound of 69, with mean relative normal-equation residual 1.36e-11. The idea had worse mean test MSE, delta +0.088573, and permutation p=0.6962, so it did not achieve a significant win.

Baseline: Best lr=0.003, epochs=10; 8-seed test MSE mean 7.136611352879902, std 0.942271126563791.
Idea: Best lr=0.001, epochs=10; 8-seed test MSE mean 7.225184601729713, std 0.8393894535095389; paired delta +0.08857324884981232; 4/8 wins; permutation p=0.6962; verdict no significant win.

Benchmark result