CS Paper Radar

Exact Recovery Thresholds for Weighted Data Selection in Vector-Valued Linear Regression

Guangjian Zhang

cs.LG math.ST ·submitted 2026-08-31 05:04 UTC · v2
theory

Abstract

We resolve the threshold part of Question 4 of the COLT 2025 open problem "Data Selection for Regression Tasks" of Hanneke, Moran, Shlimovich and Yehudayoff. We study vector-valued linear regression with square loss $\ell_{(x,y)}(W)=\lVert Wx-y\rVert_2^2$, where $x\in\mathbb{R}^d$ and $y\in\mathbb{R}^m$. The learner returns the minimum-Frobenius-norm empirical risk minimizer. We prove that the minimal budget of weighted examples for recovering the full-data loss on every finite dataset is exactly $n^{\star}(d,m)=(m+1)d$. We determine the weighted selection profile $F_{\mathrm{weighted}}(d,m,n)$ at the near-threshold budget: $F_{\mathrm{weighted}}(d,m,(m+1)d-1)=1+1/(dm^2)$. We recover the known spanning-budget value $F_{\mathrm{weighted}}(d,m,d)=d+1$ for every $m$, and $F_{\mathrm{weighted}}(d,m,n)=\infty$ for $n<d$. For the smallest open intermediate cell $(d,m)=(2,2)$ we prove $F_{\mathrm{weighted}}(2,2,3)\in[13/8,15/8]$ and $F_{\mathrm{weighted}}(2,2,4)\in[5/4,3/2]$. We reduce the conjectured exact values $13/8$ and $5/4$ to a finite moment problem on the circle with at most seven atoms and assemble structural evidence for it. The upper bounds use a fixed-basis conic compression lemma, a determinant--facet rigidity theorem for maximal certificates, and sharp sparsification lemmas for zero-mean weighted point systems. These tools may be of independent interest. We also exhibit an explicit six-point integer dataset with $d=m=2$ on which no weighted selection of $2d$ points recovers the optimal loss. Thus the scalar sufficient budget $2d$ does not extend to vector-valued outputs. Our new regression-profile results for $m\ge2$ extend the scalar theory for $m=1$.

Comment
36 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Risk Ratios for Weighted Data Selection in Linear Regression

cs.LG math.ST ·2026-08-28 ·Guangjian Zhang
theory similarity 0.71
Abstract · 48 pages

How much data must a fixed learner retain? Hanneke, Moran, Shlimovich and Yehudayoff (COLT 2025) posed this question for linear regression with the minimum-norm empirical risk minimizer. A selector sees a finite dataset $D\subseteq R^d\times R$, keeps at most $n$ examples with nonnegative weights, and $F_w(d,n)$ is the worst-case ratio between the full-data loss of the trained predictor and the optimal loss. The value is $\infty$ for $n<d$, $d+1$ at $n=d$ and $1$ for $n\ge2d$, and the regime $d<n<2d$ was left open. We settle several cases. For every $d$ we prove $F_w(d,2d-1)=1+1/d$, which confirms a claim stated without proof in the original note. We also prove $F_w(3,4)=5/3$, $F_w(4,5)=2$ and $F_w(4,6)=3/2$, the three smallest cells not covered by that formula. For every intermediate budget $n=d+k$ we prove the lower bound $F_w(d,d+k)\ge1+Γ_{d,k}$, where $Γ_{d,k}$ is an explicit harmonic quantity over balanced partitions of $d$. This bound is the exact minimax value on the class of datasets whose whitened systems split into orthogonal circuit blocks. All proved values equal $1+Γ_{d,k}$, and we conjecture that this holds throughout the open regime. Our upper bounds combine a rigidity theorem for positive spanning configurations of loss gradients with normal forms of the small positive bases in $R^3$ and $R^4$. These forms are special cases of the classification of Cornaz, Kerleau and Royer; we also control all gradients outside the basis. A dimension-free extremal-basis argument converts sign-cone geometry into selections of $d+1$ points. Explicit counterexamples rule out several shorter routes. Every upper bound is constructive, with selection procedures polynomial in the number of points for fixed dimension. Every numerical claim about a specific instance is an exact rational or algebraic identity, recomputed in exact arithmetic in the supplementary material.

0.53

A Strict Upper Bound for Three-Point Weighted Selection in Planar Vector-Valued Regression

cs.AI math.STcs.LG ·2026-11-09 ·Sergey Volkov
theory similarity 0.65
Abstract

We prove $F_{\mathrm{weighted}}(2,2,3)<11/6$ for minimum-Frobenius-norm least-squares regression with two input and two output coordinates, improving the upper bound $15/8$. More precisely, a universal $\varepsilon_0>0$ satisfies $\mathcal T_3\le(5/6-\varepsilon_0)E$ for every finite residual frame. The proof combines an exact scalar certificate, rigidity of equality in planar selection, and a compactness argument that controls disappearing weights. Together with the known lower bound, this gives $13/8\le F_{\mathrm{weighted}}(2,2,3)<11/6$. No numerical value of $\varepsilon_0$ is claimed.

0.20

Regret-Optimal Wasserstein-Robust Linear Regression

cs.LG stat.MLmath.OC ·2026-10-30 ·Sloan Nietert, Daniel Kuhn
top venuetheory similarity 0.61
Abstract · Accepted at NeurIPS 2026

Distributionally robust optimization (DRO) minimizes worst-case risk under distributional uncertainty, but its decisions can be suboptimal in terms of their excess risk, or regret. We study this gap for multivariate least-squares regression, assuming that the observed source law and unknown target law differ by an adversarial 2-Wasserstein perturbation of size $\varepsilon$. We first identify the asymptotic complexity of robust decision-making in the $\varepsilon \to 0$ limit, characterized by a problem-specific condition number $κ$. Here, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of $O(κ\varepsilon^2)$. For fixed $\varepsilon > 0$, we prove that DRO still achieves the minimax rate if the problem has bounded residual effective rank. On the other hand, we identify significant failure modes where DRO is provably suboptimal by dimension-dependent factors. Fortunately, we prove that two alternative procedures, minimax regret optimization (MRO) and spectral-norm regularization (SNR), attain the minimax rate. We derive an exact convex reformulation of MRO and an accelerated proximal algorithm for SNR, along with high-probability finite-sample guarantees. We support these theoretical results with numerical experiments separating the performance of MRO and SNR from DRO.

0.23

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

cs.LG ·2026-10-08 ·Xiaofeng Cao, Junfan Li, Langzhang Liang, Mingwei Xu, Xiao Zhang
publishedtheoryhot direction similarity 0.60
Abstract · This work was accepted by IJTCS-FAW 2026

We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only $b$ out of $d$ attributes per instance for prediction and $b_0\geq 0$ additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.

0.38

Reweighting for Transfer Classification: Exact Risk Conversion and Minimax Adaptation

cs.LG math.STstat.ML ·2026-11-06 ·Aoran Chen, Yang Feng
similarity 0.59
Abstract · 87 pages, 5 figures. Main text (32 pages) followed by the Supplementary Material

A source can make a training mixture easier to learn while making its accuracy less valuable for the target. We study how the training problem a source creates and the finite-sample error of learning it jointly determine target-risk guarantees under reweighting. For binary classification, for each pair of laws and each positive target weight, we derive the sharpest target excess hinge-risk bound implied by mixture excess alone, uniformly over clipped predictors. This exact conversion curve is determined by density-weighted local votes. A two-sample oracle inequality for weighted support vector machines supplies the mixture excess, and the composition becomes explicit for Gaussian kernels. On a tilted-boundary class, we establish the all-procedure minimax classification rate $[n+s_+^2/(m^{-1}+τ^2)]^{-1}$ in the transferable strength $s_+$ and the tilt $τ$, separating source sampling uncertainty ($m^{-1}$) from relation uncertainty ($τ^2$). A target-checked Gaussian-SVM selector adapts to unknown $s_+$ and $τ$ up to a logarithmic factor for fixed dimension, and retains the target-only rate up to the same factor against arbitrary independent sources under the stated target model. On a separate smooth opposition class, the minimax risk within the family of exact Gaussian SVMs fitted to the original labels with nonnegative weights is exponentially larger than the unrestricted minimax risk whenever the target sample is at most half the source sample, despite arbitrary data-dependent weighting and tuning. The value of a source thus depends on the training problem it creates, on what accuracy there means for the target, and on whether the permitted use of the source can implement the needed correction.

0.27

Weighted Data Selection: Sharp Upper-Half and Five-Dimensional Laws

cs.LG stat.ML ·2026-09-08 ·Zhongxuan Liu, Hongzhi Wang
theory similarity 0.59
Abstract · 35 pages, 2 figures; supplementary verification code included

How much risk does a small reweighted training support retain? For finite weighted least squares with the minimum-norm learner, we prove the exact law $Γ_d(n)=3-n/d$ throughout $\lceil3d/2\rceil\leq n\leq2d-1$. The guarantee covers every observed feature rank and uses selections that preserve the full feature span. Balanced simplex anchors reduce dimension; positive-weight lifting and independent-line compression close the risk bound. Shifted coordinate pairs attain the matching lower bound. The complete dataset-level upper bound and sharpness construction are verified in Lean 4. At the smaller budget $(d,n)=(5,6)$, we also prove $Γ_5(6)=11/5$, matching the simplex-block prediction from $5=3+2$ over arbitrary interacting configurations. Circuit covers, comparison second moments, and circuit-plane probabilities give the sharp excess $6/5$, while polar-face geometry resolves shared rank-three circuits. The general simplex-block frontier connects these laws within the intermediate-budget selection problem.

0.37

Improving the Optimization Landscape of Matrix Completion with $ε$-close Surrogates

cs.LG math.OC ·2026-10-30 ·Ziye Ma
top venue similarity 0.58
Abstract · 30 pages, accepted at NeurIPS'26

Non-convex optimization is central to machine learning and AI, yet unlike its convex counterpart, it still lacks a general and principled framework. In this work, we try to highlight the importance of combining noisy perturbations with over-parametrization mathematically under the classic setting of matrix completion (MC). Matrix completion is an important non-convex recovery problem in which only a subset of a matrix's entries is observed, and the remaining entries must be recovered using low-rank constraints. This problem is notoriously difficult because observations are limited. However, we show that by injecting $ε$-level perturbations into the nullspace of the observation mask, we can construct noisy matrix sensing surrogates whose solutions remain $\mathcal{O}(ε)$-close to the ground truth with valid restricted isometry property (RIP) constants. The existence of RIP further enables powerful tensor frameworks to be applied with theoretical guarantees. This approach reflects a broader empirical trend in which stochasticity or noise improves the curvature of the optimization landscape, allowing over-parameterized (a.k.a large) models to better separate signal from noise. Assuming each matrix entry is observed independently, we establish quantitative recovery guarantees without explicit requirements on sampling rate or incoherence, and discuss how such assumptions can further strengthen our results.

0.36

Minimax Quantile Bounds via Information Measures

cs.IT math.ST ·2026-08-21 ·Amedeo Roberto Esposito
similarity 0.58
Abstract

We develop a unified information-theoretic framework for lower bounding minimax quantiles. The starting point is a loss-adapted Neyman--Pearson metaconverse that bounds the minimax success probability at every loss threshold and confidence level. The bound separates the small-ball behaviour of the prior under the loss from the statistical distinguishability of the observation model, and is optimised over an auxiliary output distribution. Different relaxations of this Neyman--Pearson bound yield converses based on \(f\)-informativity, Sibson mutual information \(I_α\), Maximal Leakage, and Amemiya norms. Classical Fano and Le Cam lower bounds are recovered as special cases. The framework also clarifies why different information measures are suited to different recovery criteria. Maximal Leakage is exact for a class of symmetric exact-recovery problems. We use this identity to derive finite-sample bounds on the full minimax exact-recovery risk in the balanced Gaussian weighted stochastic block model, as well as two-sided finite-sample minimax-quantile bounds for low-rank matrix estimation under isotropic bounded-energy noise. For approximate Hamming recovery, we exhibit a heterogeneous binary model in which an optimised finite Sibson order yields a strong converse while the Maximal Leakage specialisation is trivial. Finally, for one-coordinate Poisson localisation, a Bennett-type Young function used through its Amemiya norm recovers the exact success-probability scale, whereas classical Fano and fixed-power relaxations are strictly weaker. These results show that sharp converses for minimax quantiles require adapting the information measure to the recovery resolution, whether exact or approximate, and to the tail behaviour of the likelihood ratio.

0.45