Unverified 2026

Exact Multi-Output Linear-Probe Coreset

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

This idea has not been verified yet.

Verification happens in two stages: Stage 1 — a mechanism check on a toy system confirms the claimed mathematical phenomenon reproduces; Stage 2 — a benchmark implements the idea on a real (small) neural network task and compares it against a tuned baseline over 8 paired seeds with a permutation test.

Artifacts

Artifacts unavailable.