# Exact Multi-Output Linear-Probe Coreset

- ID: 2878
- Canonical URL: https://synthcore.org/idea/2878/exact-multi-output-linear-probe-coreset
- API JSON: https://synthcore.org/api/idea/2878.json
- API Markdown: https://synthcore.org/api/idea/2878.md
- Verification status: queued_mechanism
- Source: [arXiv:2608.30254](https://arxiv.org/abs/2608.30254)
- Category: memory
- Solves: memory, speedup, sample-efficiency
- ML areas: embedding, memory, fine-tuning
- Math tags: linear-algebra, convex-analysis, combinatorics
- Ratings: usefulness 7/10; difficulty 6/10; novelty 5/10

## 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.

## 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.

## Key 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.$$

## 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

- Status: queued_mechanism
- Mechanism evidence: no
- Mechanism confirmed: no

## Disclaimer

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