Near-Optimal Label Complexity
for Active Huber Regression

Abstract

We resolve, up to logarithmic factors, the Huber dimension-dependence question posed by Musco, Musco, Woodruff, and Yasuda [14], reducing the rank exponent from $4-2\sqrt{2}$ to one. We study fixed-design active regression in the exact-real label-query model: the feature matrix $A\in\mathbb{R}^{n\times d}$ is known, while an arbitrary response vector is accessible only through coordinate queries. For $r=\operatorname{rank}(A)$ , our randomized nonadaptive algorithm queries $\min\{n,\widetilde{O}(r/\varepsilon^{2})\}$ labels and, with probability at least $0.99$ , returns a $(1+\varepsilon)$ -approximation to the square root of the empirical Huber loss. All query locations are fixed before any label is read. For every admissible pool size and rank, and $0<\varepsilon\leq 1/800$ , we construct a fixed rank- $r$ design on which every adaptive randomized algorithm with the same worst-case guarantee needs $\Omega(\min\{n,r/\varepsilon^{2}\})$ labels in worst-case expectation. Thus label complexity is jointly optimal in pool size, rank, and accuracy up to logarithmic factors in this range. The guarantee requires no distributional or noise assumptions and includes zero-optimum instances. The key ingredient is a centered affine transfer lemma: design-only multiscale scores preserve the objective increments needed to locate the minimizer after an independent constant-factor pilot. This overcomes the hidden-label dependence of standard affine sparsification and turns near-linear design sparsification into a near-optimal active algorithm.

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction

The Huber loss is quadratic for small residuals and linear for large ones, combining the local efficiency of least squares with bounded influence in the tails [9]. It is consequently a standard robust surrogate in statistics and machine learning. In large pools of unlabeled examples, however, observing a response may itself be the dominant cost: a label can require a human annotation, a physical experiment, or an expensive simulation. This motivates active regression: the feature matrix is available in full, but the algorithm should fit the responses after inspecting as few of them as possible.

We study the strongest transductive version of this question. The design $A\in\mathbb{R}^{n\times d}$ is arbitrary and known, the response $b\in\mathbb{R}^{n}$ is arbitrary and hidden, and one query reveals one coordinate of $b$ . There is no distributional model, no stochastic-noise assumption, and no promise that the optimum is bounded away from zero. The target is a relative approximation to the empirical Huber objective on the entire fixed pool. This worst-case formulation sharply separates label complexity from the statistical literature on Huber regression, where samples are drawn from a population and robustness is measured through estimation or prediction risk [18].

For squared loss, geometric sampling gives label complexity linear in the effective dimension for constant accuracy [4]. Lewis-weight methods likewise give nearly tight guarantees for least absolute deviations [2, 15]. Huber regression is harder because it is not homogeneous: the same direction can behave quadratically at one radius and linearly at another. Musco, Musco, Woodruff, and Yasuda developed a general active-regression framework. After the standard reduction to the column space, their Huber specialization uses $\widetilde{O}(r^{4-2\sqrt{2}}\operatorname{poly}(1/\varepsilon))$ queries, where $r=\operatorname{rank}(A)$ [14]. Their dimension-reduction discussion motivates asking whether the exponent of this effective dimension can be reduced to one.

At first sight, the near-linear unshifted Huber sparsifier of Jambulapati et al. [12] appears to settle the question. It does not. A standard affine reduction replaces each row by $(a_{i},-b_{i})$ , so the importance scores of the resulting sparsifier inspect precisely the labels that an active algorithm is trying not to query. Nor can one hope for a label-independent strong affine coreset for every response vector: an unqueried coordinate can hide an arbitrarily large constant term. The algorithm must preserve less than the whole objective, but enough to locate its minimizer.

Our results.

We give a nonadaptive, label-oblivious algorithm with query complexity

\min\{n,\widetilde{O}(r/\varepsilon^{2})\},\qquad r=\operatorname{rank}(A),

(1.1)

and constant success probability. After the same column-space reduction, the advance is the linear, rather than $r^{4-2\sqrt{2}}$ , rank dependence together with the joint dependence on $n$ and $\varepsilon$ . The sampling locations are fixed before any response is read. Our lower bound holds for the same approximation criterion even against adaptive randomized algorithms: for every admissible triple $(n,d,r)$ and $0<\varepsilon\leq 1/800$ , some fixed rank- $r$ design requires

\Omega\!\left(\min\left\{n,\frac{r}{\varepsilon^{2}}\right\}\right)

(1.2)

queries in worst-case expectation. Hence, in this small-error range, (1.1) is optimal simultaneously in sample size, rank, and accuracy up to logarithmic factors. In particular, the full-query cap is not merely an artifact of the algorithm: when the pool is too small to support $r/\varepsilon^{2}$ informative responses, a fixed positive fraction of the entire pool can be necessary.

The technical contribution behind the upper bound is a centered affine transfer principle. From $A$ alone we construct one multiscale score vector of total mass $O(r\log n)$ . For any fixed residual $z$ , sampling by these scores uniformly preserves the increments of the translated objective $F_{z}(h):=\sum_{i}H(z_{i}+a_{i}^{\mathsf{T}}h)$ over the relevant unshifted Huber ball. The baseline $F_{z}(0)$ , which may contain unseen and arbitrarily large labels, cancels. An independent pilot supplies a constant-factor center, and the centered estimate then localizes its own unconstrained minimizer. The complete query set is chosen before any label is read.

The pilot, residualization, and localization steps originate in Musco et al. [14]; the multiscale unshifted sparsifier comes from Jambulapati et al. [12]; and the common-basepoint chaining principle is already present in Jambulapati et al. [11]. Our use of these ingredients is specific: the design-only multiscale scores control centered affine increments after an independent pilot, avoiding label-dependent augmented rows. We do not claim that centering, localization, or Huber sparsification is new in isolation.

The lower bound has two regimes. When $n/r$ is large, independent biased-Bernoulli blocks of size $N$ and bias $\beta=\max\{200\varepsilon,\sqrt{10/N}\}$ encode $r$ hidden signs. A relative Huber solution decodes almost all signs, while each adaptively selected response carries only $O(\beta^{2})=O(\varepsilon^{2}+1/N)$ information. When $n/r$ is small, a realizable instance has zero optimum, so a multiplicative guarantee forces exact recovery of $r=\Omega(n)$ independent labels. This second regime is what turns the earlier fixed-row-count construction into the all- $n$ minimax statement.

Organization.

Section 2 formalizes the model and the minimax result. Section 3 develops the design-only scores, centered transfer, and two-batch upper bound. Section 4 proves the adaptive lower bound. Section 5 places the result in the active-regression and sparsification literatures and records its scope. Technical constructions and auxiliary calculations appear after the references.

2 Problem, model, and main results

This section fixes the loss, query model, and approximation convention before stating the two minimax bounds. It also records the width scaling used to reduce the analysis to the width-one loss.

For the width-one Huber loss, write

H(t):=\begin{cases}t^{2}/2,&\left\lvert t\right\rvert\leq 1,\\ \left\lvert t\right\rvert-1/2,&\left\lvert t\right\rvert>1,\end{cases}\qquad F_{b}(x):=\sum_{i=1}^{n}H(a_{i}^{\mathsf{T}}x-b_{i}),

(2.1)

where $a_{i}^{\mathsf{T}}$ is row $i$ of $A$ . Following the active regression literature, we call $F_{b}(x)^{1/2}$ the Huber norm objective, although this terminology is only shorthand for the square root of the loss. The algorithm knows $A$ in advance and learns $b_{i}$ only by querying coordinate $i$ . It may perform unrestricted computation on $A$ and on queried labels; in particular, the results below concern label complexity, not total running time, and permit exact minimization of finite convex Huber objectives.

A query count always means the number of distinct response coordinates inspected: repeated requests are answered from a cache, and a run that never returns has query count $Q=\infty$ . Absolute constants below are universal unless a dependence is displayed, and $[k]:=\{1,\ldots,k\}$ for a positive integer $k$ . A $(1+\varepsilon)$ -approximation to $F_{b}^{1/2}$ is equivalently a $(1+\varepsilon)^{2}$ -approximation to $F_{b}$ .

After rank reduction, Theorem 1.5 of Musco et al. [14] uses $\widetilde{O}(r^{4-2\sqrt{2}}\operatorname{poly}(1/\varepsilon))$ queries. We ask for a design-only, preferably nonadaptive query set with linear rank exponent and the joint $(n,r,\varepsilon)$ guarantee

F_{b}(\widehat{x})^{1/2}\leq(1+\varepsilon)\min_{x\in\mathbb{R}^{d}}F_{b}(x)^{1/2}.

(2.2)

The first result supplies such a nonadaptive set; its explicit logarithms concern label complexity and do not imply a running-time bound.

Theorem 2.1 (Nonadaptive upper bound).

Let $A\in\mathbb{R}^{n\times d}$ , let $r=\operatorname{rank}(A)$ , and let $0<\varepsilon<1/2$ . There is a randomized algorithm such that the following holds for every fixed $b\in\mathbb{R}^{n}$ . Its queried coordinates are fixed before any label is read and depend only on $A$ , $\varepsilon$ , and private randomness. It queries at most

\min\left\{n,Cr\left(\log^{6}(2n)+\frac{\log^{4}(2n)}{\varepsilon^{2}}\right)\right\}

(2.3)

distinct coordinates of $b$ and, with probability at least $0.99$ over its private randomness, returns $\widehat{x}$ satisfying

F_{b}(\widehat{x})^{1/2}\leq(1+\varepsilon)\min_{x\in\mathbb{R}^{d}}F_{b}(x)^{1/2}.

In the small-error range below, the upper bound is optimal up to logarithmic factors throughout the $(n,d,r)$ parameter range, even if adaptivity is allowed.

Theorem 2.2 (Matching adaptive lower bound).

There is an absolute constant $c>0$ such that the following holds. For all integers $n, d, r$ with $1\leq r\leq\min\{n,d\}$ and every $0<\varepsilon\leq 1/800$ , there is a fixed matrix $A\in\mathbb{R}^{n\times d}$ of rank exactly $r$ such that every adaptive randomized algorithm that, for every fixed $b\in\mathbb{R}^{n}$ , returns $\widehat{x}$ satisfying $F_{b}(\widehat{x})^{1/2}\leq(1+\varepsilon)\min_{x}F_{b}(x)^{1/2}$ with probability at least $0.99$ obeys

\sup_{b\in\mathbb{R}^{n}}\mathbb{E}_{\mathcal{R}}Q(A,b)\geq c\min\left\{n,\frac{r}{\varepsilon^{2}}\right\}.

(2.4)

Here $Q$ may be a stopping-time query count and $\mathcal{R}$ is the algorithm’s private seed. Specifically, $Q$ counts distinct queried coordinates. Repeated requests are permitted but can be answered from the algorithm’s cache and are not charged twice; set $Q=\infty$ on a run that never returns an output.

Combining the two bounds gives the minimax statement in the common accuracy range. The response remains worst case, while the expectation below is over the algorithm’s private randomness.

Corollary 2.3 (Minimax label complexity).

Fix $0<\varepsilon\leq 1/800$ and $1\leq r\leq\min\{n,d\}$ . Let $\mathfrak{A}$ range over randomized algorithms that, for every fixed pair $(A,b)$ , achieve the $(1+\varepsilon)$ -approximation to $F_{b}^{1/2}$ in (2.2) with probability at least $0.99$ , and define

\mathcal{Q}_{n,d,r}(\varepsilon):=\inf_{\mathfrak{A}}\ \sup_{\begin{subarray}{c}A\in\mathbb{R}^{n\times d}:\,\operatorname{rank}(A)=r\\ b\in\mathbb{R}^{n}\end{subarray}}\mathbb{E}_{\mathcal{R}}Q_{\mathfrak{A}}(A,b),

(2.5)

where the expectation is over all algorithmic randomness. For absolute constants $c,C>0$ ,

	$\displaystyle c\min\left\{n,\frac{r}{\varepsilon^{2}}\right\}$	$\displaystyle\leq\mathcal{Q}_{n,d,r}(\varepsilon)$
		$\displaystyle\leq\min\left\{n,Cr\left(\log^{6}(2n)+\frac{\log^{4}(2n)}{\varepsilon^{2}}\right)\right\}.$		(2.6)

The upper algorithm is nonadaptive, whereas the lower bound holds against adaptive algorithms. Thus the minimax label complexity is $\widetilde{\Theta}(\min\{n,r/\varepsilon^{2}\})$ .

Proof.

Apply Theorem 2.2; for the reverse inequality use Theorem 2.1 and its full-query branch, then take the indicated infimum and supremum. ∎

For a width parameter $s>0$ , we use the fixed-tail-slope convention

H_{s}(t):=sH(t/s)=\begin{cases}t^{2}/(2s),&\left\lvert t\right\rvert\leq s,\\ \left\lvert t\right\rvert-s/2,&\left\lvert t\right\rvert>s.\end{cases}

(2.7)

If $F_{s,A,b}(x):=\sum_{i}H_{s}(a_{i}^{\mathsf{T}}x-b_{i})$ , then

F_{s,A,b}(x)=sF_{1,A/s,b/s}(x).

Thus applying Theorem 2.1 to $(A/s,b/s)$ , or multiplying both the rows and labels in the hard instance of Theorem 2.2 by $s$ , proves the same approximation and query bounds for $H_{s}$ .

Proof mechanism.

One $O(r\log n)$ -mass multiscale score vector controls unshifted Huber balls; after an independent pilot, the same scores preserve centered affine increments and localize the sampled minimizer. The lower bound uses noiseless recovery or biased-Bernoulli blocks with bounded information per queried label.

3 The nonadaptive upper bound

The upper bound has three components. We construct one design-only score vector for every unshifted radius, transfer it to centered affine increments, and combine that transfer with an independent pilot in a two-batch algorithm. The full proof is given here; the deterministic weight construction, endpoint algebra, and attainment details appear in Appendix A.

3.1 Unshifted geometry and label-oblivious scores

We begin with the metric-like square root $\psi_{H}(t):=\sqrt{H(t)}$ . Its triangle and increment inequalities drive both the score construction and the later localization argument.

Lemma 3.1 (Huber triangle and increment inequalities).

For every $s,t\in\mathbb{R}$ ,

$\displaystyle\psi_{H}(s+t)$	$\displaystyle\leq\psi_{H}(s)+\psi_{H}(t),$	(3.1)
$\displaystyle\left\lvert\psi_{H}(s)-\psi_{H}(t)\right\rvert$	$\displaystyle\leq\psi_{H}(s-t),$	(3.2)
$\displaystyle\left\lvert H(s)-H(t)\right\rvert$	$\displaystyle\leq\sqrt{H(s-t)}\bigl(\sqrt{H(s)}+\sqrt{H(t)}\bigr).$	(3.3)

Consequently, for nonnegative weights $w_{i}$ and vectors $y, z$ of the same finite dimension,

\left(\sum_{i}w_{i}H(y_{i}+z_{i})\right)^{1/2}\leq\left(\sum_{i}w_{i}H(y_{i})\right)^{1/2}+\left(\sum_{i}w_{i}H(z_{i})\right)^{1/2}.

(3.4)

Proof.

On $[0,\infty)$ ,

\psi_{H}(u)=\begin{cases}u/\sqrt{2},&0\leq u\leq 1,\\ \sqrt{u-1/2},&u\geq 1\end{cases}

is nonnegative, increasing, concave, and zero at the origin. Its increments are therefore decreasing, so $\psi_{H}(u+v)-\psi_{H}(u)\leq\psi_{H}(v)-\psi_{H}(0)$ for $u,v\geq 0$ . Together with $\left\lvert s+t\right\rvert\leq\left\lvert s\right\rvert+\left\lvert t\right\rvert$ , this proves (3.1). Apply that inequality to $s=t+(s-t)$ , and then exchange $s, t$ , to obtain (3.2). Factoring

\left\lvert H(s)-H(t)\right\rvert=\left\lvert\psi_{H}(s)-\psi_{H}(t)\right\rvert\bigl(\psi_{H}(s)+\psi_{H}(t)\bigr)

gives (3.3). Finally, apply (3.1) coordinatewise and use the weighted Euclidean triangle inequality to obtain (3.4). ∎

For the upper-bound lemmas, take a matrix $A\in\mathbb{R}^{N\times r}$ with full column rank and nonzero rows $a_{i}^{\mathsf{T}}$ . Define the unshifted objective and its sublevel sets by

\Phi(h):=\sum_{i=1}^{N}H(a_{i}^{\mathsf{T}}h),\qquad K_{R}:=\{h\in\mathbb{R}^{r}:\Phi(h)\leq R\}.

(3.5)

Because $c_{A}:=\min_{\left\lVert h\right\rVert_{2}=1}\left\lVert Ah\right\rVert_{1}>0$ and $H(t)\geq\left\lvert t\right\rvert-1/2$ ,

\Phi(h)\geq c_{A}\left\lVert h\right\rVert_{2}-N/2.

(3.6)

Thus every $K_{R}$ is compact, and the suprema of the continuous finite-sample processes below are finite and measurable.

For a metric space $(\mathcal{T},d)$ , let $\gamma_{2}(\mathcal{T},d)$ denote Talagrand’s chaining functional

\inf_{(\mathcal{A}_{k})}\sup_{t\in\mathcal{T}}\sum_{k\geq 0}2^{k/2}\operatorname{diam}_{d}(\mathcal{A}_{k}(t)),

(3.7)

where $(\mathcal{A}_{k})_{k\geq 0}$ ranges over nested partitions of $\mathcal{T}$ , $\mathcal{A}_{k}(t)$ is the cell containing $t$ , $\left\lvert\mathcal{A}_{0}\right\rvert=1$ , and $\left\lvert\mathcal{A}_{k}\right\rvert\leq 2^{2^{k}}$ [19].

We state explicitly the external covering fact used at the transition scales. For $w\in\mathbb{R}_{>0}^{N}$ , write $W=\operatorname{diag}(w)$ and $v_{i}(w)^{2}:=a_{i}^{\mathsf{T}}(A^{\mathsf{T}}WA)^{-1}a_{i}$ .

Lemma 3.2 (Imported multiscale covering primitive).

Fix $\alpha\geq 1$ , and let $\mathcal{I}\subset\mathbb{Z}$ be a finite contiguous interval with $\left\lvert\mathcal{I}\right\rvert\geq 4\log(2N)$ . Suppose that $\{w^{(j)}:j\in\mathcal{I}\}$ is an $\alpha$ -approximate Huber weight scheme, meaning that for every $i$ and $j\in\mathcal{I}$ ,

\frac{2^{j}}{\alpha}\leq\frac{H(v_{i}(w^{(j)}))}{w_{i}^{(j)}v_{i}(w^{(j)})^{2}}\leq\alpha 2^{j},

(3.8)

and $w_{i}^{(j+1)}\leq\alpha w_{i}^{(j)}$ whenever $j,j+1\in\mathcal{I}$ . Put

\lambda_{i}^{(j)}:=w_{i}^{(j)}v_{i}(w^{(j)})^{2},\qquad\tau_{i}^{\mathcal{I}}:=\max_{j\in\mathcal{I}}\lambda_{i}^{(j)},\qquad k_{\mathcal{I}}:=\max\mathcal{I}+1.

(3.9)

Define the associated deterministic metric by

d_{\tau^{\mathcal{I}}}(h,k):=\max_{i\leq N}\sqrt{\frac{H(a_{i}^{\mathsf{T}}(h-k))}{\tau_{i}^{\mathcal{I}}}}.

(3.10)

Then $\sum_{i}\lambda_{i}^{(j)}=r$ , and for a constant $C_{\alpha}$ depending only on $\alpha$ ,

\gamma_{2}\!\left(K_{2^{k_{\mathcal{I}}}},d_{\tau^{\mathcal{I}}}\right)\leq C_{\alpha}2^{k_{\mathcal{I}}/2}\log^{3/2}(2N).

(3.11)

There is a universal numerical $\alpha_{0}$ for which such a scheme has a deterministic finite construction from $(A,\mathcal{I})$ in the exact-real model.

This is the specialization of the weight-scheme covering argument of Jambulapati et al. [12, Definition 1.8 and proof of Theorem 3.14] to $f_{i}=H$ ; the cited bibliography entry identifies the arXiv full version in which those items appear. The assumptions hold because $H$ is even, $\psi_{H}=\sqrt{H}$ is even and one-auto-Lipschitz by (3.2), and $\psi_{H}$ is $1$ -auto-Lipschitz and has lower- $1/2$ , upper- $1$ scaling while $H$ has lower- $1$ , upper- $2$ scaling: for $\lambda\geq 1$ ,

\lambda H(t)\leq H(\lambda t)\leq\lambda^{2}H(t).

(3.12)

The exact construction and its stopping criterion are recorded in Section A.1; no bit-complexity or running-time conclusion is used here.

The smallest and largest Huber radii reduce to $\ell_{2}^{2}$ and $\ell_{1}$ geometry. To avoid conflating Lewis scores with the auxiliary diagonal weights, for $p\in\{1,2\}$ let $\ell^{(p)}\in\mathbb{R}_{>0}^{N}$ satisfy

\ell_{i}^{(p)}=\left(a_{i}^{\mathsf{T}}(A^{\mathsf{T}}L_{p}^{1-2/p}A)^{-1}a_{i}\right)^{p/2},\qquad L_{p}:=\operatorname{diag}(\ell^{(p)}).

(3.13)

Set $w_{i}^{(p)}:=(\ell_{i}^{(p)})^{1-2/p}$ and $(v_{i}^{(p)})^{2}:=a_{i}^{\mathsf{T}}(A^{\mathsf{T}}\operatorname{diag}(w^{(p)})A)^{-1}a_{i}$ . Then the weighted leverage is

\lambda_{i}^{(p)}:=w_{i}^{(p)}(v_{i}^{(p)})^{2}=(v_{i}^{(p)})^{p}=\ell_{i}^{(p)}.

(3.14)

Thus $w^{(2)}\equiv 1$ and $\lambda^{(2)}$ is ordinary leverage, whereas $\lambda^{(1)}$ is the $\ell_{1}$ Lewis score.

Lemma 3.3 (Endpoint coverings).

For $p\in\{1,2\}$ , the scores in (3.14) have total mass $r$ . With

d_{p}(h,k):=\max_{i\leq N}\frac{\left\lvert a_{i}^{\mathsf{T}}(h-k)\right\rvert^{p/2}}{\sqrt{\lambda_{i}^{(p)}}},

(3.15)

they satisfy, for every $S>0$ ,

\gamma_{2}\bigl(\{h:\left\lVert Ah\right\rVert_{p}^{p}\leq S\},d_{p}\bigr)\leq C\sqrt{S}\,\log^{3/2}(2N).

(3.16)

The proof verifies an exact scale scheme using $w_{i}^{(j)}=2^{-2j/p}w_{i}^{(p)}$ ; see Section A.2. We now combine these endpoint scores with a finite transition-scale scheme.

Lemma 3.4 (All-radius label-oblivious Huber scores).

There are scores $\tau_{i}=\tau_{i}(A)>0$ , computable from $A$ alone, such that

T:=\sum_{i=1}^{N}\tau_{i}\leq Cr\log(2N)

(3.17)

and, for

d_{\tau}(h,k):=\max_{i\leq N}\sqrt{\frac{H(a_{i}^{\mathsf{T}}(h-k))}{\tau_{i}}},

(3.18)

one has, simultaneously for every $R>0$ ,

\gamma_{2}(K_{R},d_{\tau})\leq C\sqrt{R}\,\log^{3/2}(2N).

(3.19)

Proof.

Let

L:=\lceil 4\log(2N)\rceil,\qquad\mathcal{J}:=[-2-L,\,2+\lceil\log_{2}(2N)\rceil]\cap\mathbb{Z},

and construct the transition-scale schemes of Lemma 3.2 on $\mathcal{J}$ , denoting their weighted leverages by $\lambda_{i,{\rm tr}}^{(j)}$ . For $p=1,2$ , let $c\geq 1$ be a fixed universal constant and let $\widetilde{\lambda}_{i}^{(p)}$ be a deterministic finite constant-factor approximation to the exact endpoint score in Lemma 3.3, with $\widetilde{\lambda}_{i}^{(p)}\in[\lambda_{i}^{(p)}/c,c\lambda_{i}^{(p)}]$ , and set $\overline{\lambda}_{i}^{(p)}:=c\widetilde{\lambda}_{i}^{(p)}$ . Such approximations follow from the standard Lewis-weight construction [5]; for $p=2$ , ordinary leverage can instead be used exactly. Define

\tau_{i}^{\rm tr}:=\max_{j\in\mathcal{J}}\lambda_{i,{\rm tr}}^{(j)},\qquad\tau_{i}:=\tau_{i}^{\rm tr}+\overline{\lambda}_{i}^{(1)}+\overline{\lambda}_{i}^{(2)}.

Each inflated endpoint vector dominates its exact counterpart and has mass at most $c^{2}r$ . Since every transition leverage vector has mass $r$ ,

\sum_{i}\tau_{i}\leq\left\lvert\mathcal{J}\right\rvert\,r+2c^{2}r=O(r\log(2N)).

Suppose first that $1/2\leq R\leq N/2$ , let $k_{R}:=\lceil\log_{2}R\rceil$ , and put $\mathcal{I}_{R}:=\{k_{R}-L,\ldots,k_{R}-1\}$ . Then $\mathcal{I}_{R}\subseteq\mathcal{J}$ , $K_{R}\subseteq K_{2^{k_{R}}}$ , and $d_{\tau}\leq d_{\tau^{\mathcal{I}_{R}}}$ . Therefore Lemma 3.2 and $2^{k_{R}}<2R$ give

\gamma_{2}(K_{R},d_{\tau})\leq\gamma_{2}(K_{2^{k_{R}}},d_{\tau^{\mathcal{I}_{R}}})\leq C\sqrt{R}\log^{3/2}(2N).

If $R\leq 1/2$ , every coordinate on $K_{R}$ lies in the quadratic region and

K_{R}=\{h:\left\lVert Ah\right\rVert_{2}^{2}\leq 2R\},\qquad d_{\tau}\leq 2^{-1/2}d_{2}.

If $R\geq N/2$ , the bound $H(t)\geq\left\lvert t\right\rvert-1/2$ gives

K_{R}\subseteq\{h:\left\lVert Ah\right\rVert_{1}\leq R+N/2\}\subseteq\{h:\left\lVert Ah\right\rVert_{1}\leq 2R\},\qquad d_{\tau}\leq d_{1},

where the metric inequality uses $H(t)\leq\left\lvert t\right\rvert$ . Applying Lemma 3.3 in both cases completes the proof. ∎

Set $\pi_{i}^{\rm main}:=\tau_{i}/T$ , draw $\nu_{1},\ldots,\nu_{m}$ independently from $\pi^{\rm main}$ , and define

\widehat{\Phi}(h):=\frac{1}{m}\sum_{j=1}^{m}\frac{H(a_{\nu_{j}}^{\mathsf{T}}h)}{\pi_{\nu_{j}}^{\rm main}}.

(3.20)

Sampling from the all-radius scores yields the unshifted estimate that will control the random envelope in the affine transfer.

Lemma 3.5 (Unshifted expectation bound).

There is an absolute constant $C$ such that, whenever

\alpha:=C\sqrt{\frac{T\log^{3}(2N)}{m}}\leq 1,

(3.21)

then, for every $R>0$ ,

\mathbb{E}\sup_{h\in K_{R}}\left\lvert\widehat{\Phi}(h)-\Phi(h)\right\rvert\leq 2\alpha R.

(3.22)

In particular,

\mathbb{E}\sup_{h\in K_{R}}\widehat{\Phi}(h)\leq 3R.

(3.23)

Proof.

Let the left side of (3.22) be $X$ . Ghost-sample symmetrization gives

X\leq 2\mathbb{E}_{\nu,\sigma}\sup_{h\in K_{R}}\left\lvert\frac{1}{m}\sum_{j=1}^{m}\sigma_{j}\frac{H(a_{\nu_{j}}^{\mathsf{T}}h)}{\pi_{\nu_{j}}^{\rm main}}\right\rvert,

where the $\sigma_{j}$ ’s are independent Rademacher signs. Conditional on the indices, the increment metric is

d_{\nu}(h,k)^{2}:=\sum_{j=1}^{m}\frac{[H(a_{\nu_{j}}^{\mathsf{T}}h)-H(a_{\nu_{j}}^{\mathsf{T}}k)]^{2}}{m^{2}(\pi_{\nu_{j}}^{\rm main})^{2}}.

Put $L_{\nu}:=\sup_{u\in K_{R}}\widehat{\Phi}(u)$ . By (3.3), $\pi_{i}^{\rm main}=\tau_{i}/T$ , and (3.18),

d_{\nu}(h,k)^{2}\leq\frac{2T}{m}d_{\tau}(h,k)^{2}\bigl(\widehat{\Phi}(h)+\widehat{\Phi}(k)\bigr)\leq\frac{4TL_{\nu}}{m}d_{\tau}(h,k)^{2}.

The signed process is anchored at zero and has subgaussian increments in $d_{\nu}$ . The standard generic-chaining bound, followed by Lemma 3.4, therefore yields

\mathbb{E}_{\sigma}\sup_{h\in K_{R}}\left\lvert Z_{h}\right\rvert\leq C\gamma_{2}(K_{R},d_{\nu})\leq C\sqrt{\frac{T\log^{3}(2N)}{m}}\sqrt{RL_{\nu}},

where $Z_{h}=m^{-1}\sum_{j}\sigma_{j}H(a_{\nu_{j}}^{\mathsf{T}}h)/\pi_{\nu_{j}}^{\rm main}$ . Taking expectation over the indices and using Jensen gives

X\leq\alpha\sqrt{R}\,\mathbb{E}\sqrt{L_{\nu}}\leq\alpha\sqrt{R}\sqrt{R+X},

because $L_{\nu}\leq R+\sup_{K_{R}}\left\lvert\widehat{\Phi}-\Phi\right\rvert$ . For $R>0$ , writing $y=X/R$ gives $y^{2}\leq\alpha^{2}(1+y)$ ; its positive root is at most $2\alpha$ when $\alpha\leq 1$ . The case $R=0$ is immediate. Consequently $X\leq 2\alpha R$ and $\mathbb{E}L_{\nu}\leq R+X\leq 3R$ . ∎

3.2 Centered affine preservation

The preceding scores control an unshifted empirical process. We now show that the same distribution preserves centered increments around any fixed residual, which is precisely what the second batch will require.

Fix an arbitrary residual vector $z\in\mathbb{R}^{N}$ , and define

F_{z}(h):=\sum_{i=1}^{N}H(z_{i}+a_{i}^{\mathsf{T}}h),\qquad R:=F_{z}(0)=\sum_{i=1}^{N}H(z_{i}).

(3.24)

Using a fresh sample from $\pi^{\rm main}$ , define

\widehat{F}_{z}(h):=\frac{1}{m}\sum_{j=1}^{m}\frac{H(z_{\nu_{j}}+a_{\nu_{j}}^{\mathsf{T}}h)}{\pi_{\nu_{j}}^{\rm main}}.

(3.25)

Only sampled residual coordinates are needed. The same indices define $\widehat{F}_{z}$ and $\widehat{\Phi}$ ; this coupling is used below.

Lemma 3.6 (Centered affine transfer).

Fix $B\geq 1$ , $0<\eta,\delta<1/2$ , and $z$ with $R=F_{z}(0)>0$ . There is a constant $\overline{C}_{B}=O(B^{2})$ , depending only on $B$ , such that if

m\geq\overline{C}_{B}\frac{T\log^{3}(2N)}{\eta^{2}\delta^{2}},

(3.26)

then, with probability at least $1-\delta$ over the fresh main sample,

\sup_{h\in K_{BR}}\left\lvert[\widehat{F}_{z}(h)-\widehat{F}_{z}(0)]-[F_{z}(h)-F_{z}(0)]\right\rvert\leq\eta R.

(3.27)

The distribution depends on $A$ , but not on $z$ .

Proof.

Set $\varphi_{i}(h):=H(z_{i}+a_{i}^{\mathsf{T}}h)-H(z_{i})$ . Since $\varphi_{i}(0)=0$ , signed symmetrization gives

		$\displaystyle\mathbb{E}\sup_{h\in K_{BR}}\left\lvert\frac{1}{m}\sum_{j=1}^{m}\frac{\varphi_{\nu_{j}}(h)}{\pi_{\nu_{j}}^{\rm main}}-\sum_{i=1}^{N}\varphi_{i}(h)\right\rvert$
		$\displaystyle\qquad\leq 2\mathbb{E}_{\nu,\sigma}\sup_{h\in K_{BR}}\left\lvert\frac{1}{m}\sum_{j=1}^{m}\sigma_{j}\frac{\varphi_{\nu_{j}}(h)}{\pi_{\nu_{j}}^{\rm main}}\right\rvert.$

Conditional on the sampled indices, let $d_{\nu,z}$ be the increment metric of this signed process and put $L_{\nu,z}:=\sup_{u\in K_{BR}}\widehat{F}_{z}(u)$ . Exactly as in the unshifted calculation,

d_{\nu,z}(h,k)^{2}\leq\frac{2T}{m}d_{\tau}(h,k)^{2}\bigl(\widehat{F}_{z}(h)+\widehat{F}_{z}(k)\bigr)\leq\frac{4TL_{\nu,z}}{m}d_{\tau}(h,k)^{2}.

The shared-sample weighted triangle inequality gives, pointwise,

\widehat{F}_{z}(u)\leq 2\widehat{F}_{z}(0)+2\widehat{\Phi}(u).

After increasing the sample constant so that Lemma 3.5 applies on $K_{BR}$ , unbiasedness and (3.23) yield

\mathbb{E}L_{\nu,z}\leq(2+6B)R.

Generic chaining and Lemma 3.4, followed by Jensen, now bound the expected centered error by

D_{B}R\sqrt{\frac{T\log^{3}(2N)}{m}},\qquad D_{B}:=C\sqrt{B(2+6B)}=O(B).

Choose $\overline{C}_{B}$ at least $D_{B}^{2}$ times a sufficiently large universal constant, also large enough for the unshifted condition $\alpha\leq 1$ . Under (3.26), the last display is at most $\delta\eta R$ . Markov’s inequality gives (3.27). ∎

Remark 3.7 (Why centering matters).

The conclusion is additive, localized, and centered. It does not claim that $\widehat{F}_{z}$ multiplicatively preserves the full affine objective. An unseen residual may make the common baseline arbitrarily large, but it cannot destroy preservation of the increments needed for optimization.

3.3 Pilot, algorithm, and localization

We next obtain the center needed by the transfer lemma and then state the full nonadaptive procedure. The pilot adapts the constant-factor mechanism of Musco et al. [14, Lemma 5.1], instantiated with the all-radius $A$ -only embedding above and with the finite-scale bookkeeping made explicit.

The finite-range pilot estimate must be extended without using the false implication $H(t)\leq 1\Rightarrow\left\lvert t\right\rvert\leq 1$ . The following Huber-specific lemma uses the sharp quadratic threshold $1/2$ .

Lemma 3.8 (Huber all-scale extension).

Let $N>16$ , $S_{0}:=8N^{3}$ , and $\zeta:=1/16$ . Suppose

G(h):=\sum_{i=1}^{N}\omega_{i}H(a_{i}^{\mathsf{T}}h),\qquad\omega_{i}\geq 0,\qquad\sum_{i}\omega_{i}\leq 2N.

(3.28)

If $\left\lvert G(h)-\Phi(h)\right\rvert\leq\zeta\Phi(h)$ whenever $\Phi(h)\in[1/2,S_{0}]$ , then

\left\lvert G(h)-\Phi(h)\right\rvert\leq 2\zeta\Phi(h)\qquad\text{for every }h.

(3.29)

Proof.

If $\Phi(h)=0$ , then every $a_{i}^{\mathsf{T}}h=0$ , and hence $G(h)=0$ . Suppose $0<\Phi(h)<1/2$ , and set $\beta:=\sqrt{(1/2)/\Phi(h)}>1$ . Since $\beta^{2}H(a_{i}^{\mathsf{T}}h)\leq 1/2$ for every $i$ , both $a_{i}^{\mathsf{T}}h$ and $\beta a_{i}^{\mathsf{T}}h$ lie in the quadratic region. Consequently

\Phi(\beta h)=\beta^{2}\Phi(h)=1/2,\qquad G(\beta h)=\beta^{2}G(h),

and the assumed relative error at $\beta h$ scales back to $h$ .

It remains to consider $\Phi(h)>S_{0}$ . Put

c:=\frac{S_{0}}{2\Phi(h)},\qquad y:=ch,\qquad\beta:=c^{-1}>1.

For every $t\in\mathbb{R}$ and $\beta\geq 1$ , direct inspection of the two Huber pieces gives

0\leq H(\beta t)-\beta H(t)\leq\frac{\beta-1}{2}.

Consequently, using $\sum_{i}\omega_{i}\leq 2N$ for the bound on $G$ ,

	$\displaystyle\beta\Phi(y)$	$\displaystyle\leq\Phi(h)\leq\beta\Phi(y)+\frac{N}{2}(\beta-1),$
	$\displaystyle\beta G(y)$	$\displaystyle\leq G(h)\leq\beta G(y)+N(\beta-1).$

It follows that

\frac{S_{0}-N}{2}\leq\Phi(y)\leq\frac{S_{0}}{2},

so $\Phi(y)\in[1/2,S_{0}]$ . Applying the assumed estimate at $y$ , and comparing the two additive remainders, gives

\left\lvert G(h)-\Phi(h)\right\rvert\leq\zeta\beta\Phi(y)+N(\beta-1)\leq\left(\zeta+\frac{2N}{S_{0}}\right)\Phi(h)\leq 2\zeta\Phi(h),

because $S_{0}=8N^{3}$ , $N>16$ , and $\zeta=1/16$ . ∎

Fix $\delta_{0}:=10^{-3}$ , $\rho:=1/8$ , and $\zeta:=1/16$ . Regularize the main distribution by

\pi_{i}^{\rm pil}:=\frac{\pi_{i}^{\rm main}}{2}+\frac{1}{2N}=\frac{\tau_{i}+T/N}{2T},\qquad T^{\prime}:=2T.

(3.30)

Let

\mathcal{S}:=\{2^{j}:-1\leq j\leq\lceil\log_{2}(8N^{3})\rceil\},\qquad J:=\left\lvert\mathcal{S}\right\rvert,

(3.31)

and choose a universal $C_{\rm pil}$ large enough for Lemma 3.5. Set

m_{0}:=\left\lceil C_{\rm pil}\frac{T^{\prime}\log^{3}(2N)J^{2}}{\zeta^{2}\delta_{0}^{2}}\right\rceil=O\!\left(r\log^{6}(2N)\right).

(3.32)

Lemma 3.9 (Label-oblivious constant-factor pilot).

Fix $b\in\mathbb{R}^{N}$ and set $F_{b}(x):=\sum_{i=1}^{N}H(a_{i}^{\mathsf{T}}x-b_{i})$ . For independent $\mu_{1},\ldots,\mu_{m_{0}}\sim\pi^{\rm pil}$ , define

	$\displaystyle\widetilde{\Phi}_{0}(h)$	$\displaystyle:=\frac{1}{m_{0}}\sum_{j=1}^{m_{0}}\frac{H(a_{\mu_{j}}^{\mathsf{T}}h)}{\pi_{\mu_{j}}^{\rm pil}},$		(3.33)
	$\displaystyle\widetilde{F}_{0}(x)$	$\displaystyle:=\frac{1}{m_{0}}\sum_{j=1}^{m_{0}}\frac{H(a_{\mu_{j}}^{\mathsf{T}}x-b_{\mu_{j}})}{\pi_{\mu_{j}}^{\rm pil}}.$		(3.34)

With probability at least $1-\delta_{0}$ ,

(1-\rho)\Phi(h)\leq\widetilde{\Phi}_{0}(h)\leq(1+\rho)\Phi(h)\qquad\text{for every }h.

(3.35)

Let $x_{c}$ be the unique minimum-Euclidean-norm point in $\arg\min\widetilde{F}_{0}$ , selected using only the pilot indices and labels, and let $x_{*}\in\arg\min F_{b}$ , $F_{*}:=F_{b}(x_{*})$ . Except with total probability $2\delta_{0}$ ,

R:=F_{b}(x_{c})\leq C_{0}F_{*},\qquad C_{0}:=\left(1+\frac{2}{\sqrt{(1-\rho)\delta_{0}}}\right)^{2}.

(3.36)

Proof.

The probabilities in (3.30) correspond to the scores $\tau_{i}^{\prime}:=\tau_{i}+T/N$ , which dominate $\tau_{i}$ and have total mass $T^{\prime}=2T$ . Hence the all-radius metric only decreases, and Lemma 3.5 applies with $T^{\prime}$ . At every $S\in\mathcal{S}$ , Markov’s inequality applied to (3.22), with failure probability $\delta_{0}/J$ , gives

\sup_{h\in K_{S}}\left\lvert\widetilde{\Phi}_{0}(h)-\Phi(h)\right\rvert\leq\frac{\zeta S}{2}.

The ceiling and constant in (3.32) make these bounds hold simultaneously with probability at least $1-\delta_{0}$ . If $\Phi(h)\in[1/2,8N^{3}]$ , choose the least dyadic $S\in\mathcal{S}$ with $S\geq\Phi(h)$ . Since $S<2\Phi(h)$ , the relative error is at most $\zeta$ .

Let $M_{i}:=\#\{j:\mu_{j}=i\}$ and $\widetilde{w}_{i}:=M_{i}/(m_{0}\pi_{i}^{\rm pil})$ . Then

\widetilde{\Phi}_{0}(h)=\sum_{i}\widetilde{w}_{i}H(a_{i}^{\mathsf{T}}h),\qquad\sum_{i}\widetilde{w}_{i}=\frac{1}{m_{0}}\sum_{j=1}^{m_{0}}\frac{1}{\pi_{\mu_{j}}^{\rm pil}}\leq 2N.

The all-scale extension in Lemma 3.8 therefore upgrades the finite-range event to (3.35), with $2\zeta=\rho=1/8$ .

For any fixed optimizer $x_{*}$ , the affine pilot is unbiased. Markov’s inequality gives

\widetilde{F}_{0}(x_{*})\leq F_{*}/\delta_{0}

except with probability $\delta_{0}$ . On this event and the embedding event, sample optimality and (3.4) yield

\sqrt{(1-\rho)\Phi(x_{c}-x_{*})}\leq\sqrt{\widetilde{\Phi}_{0}(x_{c}-x_{*})}\leq\sqrt{\widetilde{F}_{0}(x_{c})}+\sqrt{\widetilde{F}_{0}(x_{*})}\leq 2\sqrt{F_{*}/\delta_{0}}.

A second application of the full-objective triangle inequality gives

\sqrt{F_{b}(x_{c})}\leq\sqrt{F_{*}}+\sqrt{\Phi(x_{c}-x_{*})}\leq\left(1+\frac{2}{\sqrt{(1-\rho)\delta_{0}}}\right)\sqrt{F_{*}},

which is (3.36). If $F_{*}=0$ , sample optimality makes both pilot residuals zero on every sampled row; the embedding then forces $\Phi(x_{c}-x_{*})=0$ , the fact used in the zero-optimum branch of Theorem 2.1. ∎

We now instantiate the generic $N$ -row lemmas for the original theorem input. Set $n_{\rm orig}:=n$ , $I_{\rm nz}:=\{i\in[n_{\rm orig}]:a_{i}\neq 0\}$ , and $n_{\rm nz}:=\left\lvert I_{\rm nz}\right\rvert$ . Enumerate $I_{\rm nz}=\{\iota(1)<\cdots<\iota(n_{\rm nz})\}$ . Fix, as a deterministic function of $A$ , a matrix $U\in\mathbb{R}^{d\times r}$ with orthonormal columns spanning $(\ker A)^{\perp}$ , and put

	$\displaystyle\overline{A}$	$\displaystyle:=A_{I_{\rm nz},:}U,$	$\displaystyle\overline{b}_{j}$	$\displaystyle:=b_{\iota(j)},$		(3.37)
	$\displaystyle\overline{F}(y)$	$\displaystyle:=\sum_{j=1}^{n_{\rm nz}}H\bigl((\overline{A}y)_{j}-\overline{b}_{j}\bigr).$				(3.37)

When $n_{\rm nz}>0$ , $\overline{A}$ has full column rank and no zero row. We apply the preceding lemmas with $N=n_{\rm nz}$ , $A=\overline{A}$ , and $b=\overline{b}$ ; a sampled reduced index $j$ means a query to the original coordinate $\iota(j)$ . All random indices below are drawn before any such query is made.

Two-batch nonadaptive algorithm.

1.
If $n_{\rm nz}=0$ , return zero without querying a label. If $n_{\rm nz}\leq 16$ , query all retained labels, minimize exactly in the reduced coordinates, and lift the result with $U$ . Otherwise compute the scores and the main and pilot probabilities in Lemmas 3.4 and 3.30 for $\overline{A}$ .
2.
Set
$\eta:=\frac{2\varepsilon+\varepsilon^{2}}{2C_{0}},\qquad\delta:=10^{-3},\qquad\overline{C}_{16}:=\left.\overline{C}_{B}\right|_{B=16},\qquad m:=\left\lceil\overline{C}_{16}\frac{T\log^{3}(2n_{\rm nz})}{\eta^{2}\delta^{2}}\right\rceil.$
If $m_{0}+m\geq n_{\rm nz}$ , query all retained labels and return an exact lifted minimizer.
3.
Otherwise, independently draw $m_{0}$ pilot indices from $\pi^{\rm pil}$ and $m$ main indices from $\pi^{\rm main}$ . Query their union; duplicate occurrences reuse the cached label.
4.
Let $y_{c}$ be the unique minimum-Euclidean-norm point of $\arg\min\widetilde{F}_{0}$ , using only $\overline{A}$ , the pilot indices, and the pilot labels—not the main indices or labels. Form $z=\overline{A}y_{c}-\overline{b}$ on the queried main coordinates.
5.
Let $\widehat{h}$ be the unique minimum-Euclidean-norm point of $\arg\min\widehat{F}_{z}$ . Return $\widehat{x}:=U(y_{c}+\widehat{h})\in\mathbb{R}^{d}$ .

Each finite sampled objective attains its minimum on the quotient by the kernel of its sampled rows. Its argmin is a nonempty closed convex set, so it has a unique minimum-norm point. The coercivity and selection details appear in Section A.3.

Proof of Theorem 2.1.

The zero-row and full-query branches are exact. In the two-batch branch, retain the notation $b^{\rm orig}:=b$ , then write $A=\overline{A}$ , $b=\overline{b}$ , and $F_{b}(y)=\sum_{i=1}^{n_{\rm nz}}H(a_{i}^{\mathsf{T}}y-b_{i})$ for the reduced variable objective. Fix $y_{*}\in\arg\min F_{b}$ and set $F_{*}:=F_{b}(y_{*})$ . On the pilot event (3.36), define

z:=Ay_{c}-b,\qquad R:=F_{z}(0)=F_{b}(y_{c}),\qquad h_{*}:=y_{*}-y_{c}.

(3.38)

First suppose $F_{*}>0$ . Then $R\geq F_{*}>0$ , and

\sqrt{\Phi(h_{*})}\leq\sqrt{F_{*}}+\sqrt{R}\leq 2\sqrt{R},\qquad h_{*}\in K_{4R}.

(3.39)

Let $\mathcal{F}_{\rm pil}$ be generated by the pilot indices and their labels. By the pilot-only selection rule, $y_{c},z,R$ are $\mathcal{F}_{\rm pil}$ -measurable, while the main sample remains independent and i.i.d. from $\pi^{\rm main}$ conditionally on $\mathcal{F}_{\rm pil}$ . Thus, for almost every pilot realization with $R>0$ , Lemma 3.6 applies with $B=16$ ; integrating its conditional failure probability gives an unconditional failure probability at most $\delta$ . Neither the scores nor the sample size depends on $R$ .

For any $h$ with $\Phi(h)=16R$ , the reverse Huber triangle inequality gives

\sqrt{F_{z}(h)}\geq\sqrt{\Phi(h)}-\sqrt{F_{z}(0)}=3\sqrt{R},\qquad F_{z}(h)-F_{z}(0)\geq 8R.

(3.40)

On the event (3.27), the sampled centered objective is strictly positive on this boundary because

\widehat{F}_{z}(h)-\widehat{F}_{z}(0)\geq(8-\eta)R>0.

(3.41)

If a global minimizer of $\widehat{F}_{z}$ lay outside $K_{16R}$ , the segment from zero to that minimizer would meet the boundary. Convexity would make the sampled objective there no larger than at zero, contradicting (3.41). Hence

\widehat{h}\in K_{16R}.

(3.42)

Both $h_{*}$ and $\widehat{h}$ are in the preserved set. Sample optimality and two applications of (3.27) yield

F_{z}(\widehat{h})-F_{z}(h_{*})\leq 2\eta R\leq 2\eta C_{0}F_{*}=(2\varepsilon+\varepsilon^{2})F_{*}.

(3.43)

Since $F_{z}(h_{*})=F_{*}$ and $\widehat{x}=U(y_{c}+\widehat{h})$ ,

F_{b}(y_{c}+\widehat{h})=F_{z}(\widehat{h})\leq(1+\varepsilon)^{2}F_{*}.

(3.44)

Taking square roots proves the approximation.

If $F_{*}=0$ , then $b=Ay_{*}$ . The pilot optimum $y_{*}$ has sampled cost zero, so every pilot minimizer has sampled cost zero. On (3.35), the pilot-distance argument in the proof of Lemma 3.9 forces $\Phi(y_{c}-y_{*})=0$ , hence $R=0$ . In the second stage, $h=0$ has sampled cost zero and is the unique minimum-norm point of the argmin, so $\widehat{h}=0$ . The returned prediction is exact, and Lemma 3.6 is not invoked at radius zero.

The pilot embedding, pilot Markov bound, and centered-transfer event fail with total probability at most $3\cdot 10^{-3}<0.01$ . Also, Equations 3.17 and 3.32 give, for a universal $C$ ,

m_{0}+m\leq M(n_{\rm nz}),\qquad M(t):=Cr\left(\log^{6}(2t)+\varepsilon^{-2}\log^{4}(2t)\right).

(3.45)

The full-query branch and monotonicity of $M$ therefore give

Q\leq\min\{n_{\rm nz},M(n_{\rm nz})\}\leq\min\{n_{\rm orig},M(n_{\rm orig})\}.

(3.46)

Both batches were selected before reading labels.

Finally let $C_{\rm zr}:=\sum_{i\notin I_{\rm nz}}H(-b_{i}^{\rm orig})$ . The original objective at a lifted point is $F_{b^{\rm orig}}^{\rm orig}(Uy)=C_{\rm zr}+F_{b}(y)$ , and its optimum is $C_{\rm zr}+F_{*}$ . Hence

F_{b^{\rm orig}}^{\rm orig}(\widehat{x})\leq C_{\rm zr}+(1+\varepsilon)^{2}F_{*}\leq(1+\varepsilon)^{2}(C_{\rm zr}+F_{*}).

Thus zero rows preserve the guarantee and (3.37) provides the promised lift. If $r=0$ , every row is zero and no label is needed to choose an optimizer. ∎

4 Matching lower bound against adaptive queries

This section proves Theorem 2.2, including algorithms with private randomness and stopping-time query counts. We first isolate the scalar Huber gap, then combine binary rate–distortion with a finite adaptive-transcript bound in two block-length regimes.

4.1 Scalar Huber gap

Lemma 4.1 (Exact scalar majority gap).

Let $N\geq 1$ and $0<\gamma\leq 1/2$ , and define

F_{\gamma}(t):=N(1/2-\gamma)H(4t)+N(1/2+\gamma)H(4(t-1)).

(4.1)

Put

q_{\gamma}:=\frac{1/2-\gamma}{1/2+\gamma},\qquad t_{\gamma}^{*}:=1-\frac{q_{\gamma}}{4}.

(4.2)

Then $t_{\gamma}^{*}$ is a global minimizer, and every $t\leq 1/2$ satisfies

F_{\gamma}(t)-F_{\gamma}(t_{\gamma}^{*})\geq 2\gamma N\frac{1+4\gamma}{1+2\gamma}\geq 2\gamma N.

(4.3)

For a negative empirical majority, the symmetric statement holds with $t\mapsto 1-t$ .

Proof.

At $t_{\gamma}^{*}$ , the zero-label residual is $4t_{\gamma}^{*}=4-q_{\gamma}>1$ , while the one-label residual is $4(t_{\gamma}^{*}-1)=-q_{\gamma}\in[-1,0]$ . Hence

F_{\gamma}^{\prime}(t_{\gamma}^{*})=4N\bigl[(1/2-\gamma)-(1/2+\gamma)q_{\gamma}\bigr]=0,

and convexity makes $t_{\gamma}^{*}$ globally optimal. Also $F_{\gamma}^{\prime}(1/2)=-8\gamma N<0$ , so the minimum on the wrong half-line $(-\infty,1/2]$ is attained at $1/2$ . Direct substitution gives

	$\displaystyle F_{\gamma}(1/2)$	$\displaystyle=3N/2,$
	$\displaystyle F_{\gamma}(t_{\gamma}^{*})$	$\displaystyle=N\left[\frac{7}{2}(1/2-\gamma)-\frac{(1/2-\gamma)^{2}}{2(1/2+\gamma)}\right],$
	$\displaystyle F_{\gamma}(1/2)-F_{\gamma}(t_{\gamma}^{*})$	$\displaystyle=2\gamma N\frac{1+4\gamma}{1+2\gamma}.$

This proves (4.3); reflection about $1/2$ gives the negative-majority case. ∎

4.2 Information lemmas for adaptive queries

For discrete random variables, $\mathsf{H}$ , $\mathrm{I}$ , and $\mathrm{D}_{\mathrm{KL}}$ denote Shannon entropy, mutual information, and KL divergence in nats. Define

h_{2}^{\rm nat}(u):=-u\log u-(1-u)\log(1-u),\quad 0\log 0:=0,\qquad d_{H}(s,\widehat{s}):=\sum_{j=1}^{r}\mathbf{1}\{s_{j}\neq\widehat{s}_{j}\}.

(4.4)

Lemma 4.2 (Binary rate–distortion).

Let $S$ be uniform on $\{-1,+1\}^{r}$ , and let $\widehat{S}$ be any $\{-1,+1\}^{r}$ -valued estimate jointly distributed with $S$ . If $\mathbb{E}d_{H}(S,\widehat{S})<0.04r$ , then

\mathrm{I}(S;\widehat{S})\geq c_{\rm RD}r,\qquad c_{\rm RD}:=\log 2-h_{2}^{\rm nat}(0.04)>0.525.

(4.5)

Proof.

For $e_{j}:=\mathbb{P}[\widehat{S}_{j}\neq S_{j}]$ , the entropy chain rule and the binary Fano bound give

\mathsf{H}(S\mid\widehat{S})\leq\sum_{j=1}^{r}h_{2}^{\rm nat}(e_{j})\leq rh_{2}^{\rm nat}\!\left(r^{-1}\sum_{j}e_{j}\right).

Since $\mathsf{H}(S)=r\log 2$ , the claim follows by concavity of $h_{2}^{\rm nat}$ [6]. ∎

The next lemma accounts for the seed, adaptive index choices, caching, and stopping without an infinite transcript. Once repetitions are served from the cache, at most $n$ fresh coordinates can be queried.

Lemma 4.3 (Finite adaptive-transcript bound).

Let $S$ be any random variable, let $B=(B_{1},\ldots,B_{n})$ be a random response vector, and let $\mathcal{R}$ be a private seed independent of $(S,B)$ . Suppose an adaptive algorithm returns almost surely after $Q$ fresh coordinate queries to $B$ . For $t=1,\ldots,n$ , let $Z_{t}=\dagger$ if $Q<t$ , and otherwise let $Z_{t}=(J_{t},B_{J_{t}})$ record the $t$ -th fresh index and response. Put $\mathcal{F}_{t-1}:=\sigma(\mathcal{R},Z_{1},\ldots,Z_{t-1})$ . The active indicator and $J_{t}$ on the active event are $\mathcal{F}_{t-1}$ -measurable. For an active history $h$ , let $I_{h}$ denote mutual information under the regular conditional law given $h$ . If $I_{h}(S;B_{J_{t}(h)})\leq\kappa$ for almost every active history, then

\mathrm{I}(S;\mathcal{R},Z_{1:n})\leq\kappa\,\mathbb{E}Q.

(4.6)

Proof.

The seed is independent of $S$ , and a stopped slot is deterministic. For each slot, the pointwise hypothesis and measurability of its active indicator and index give

\mathrm{I}(S;Z_{t}\mid\mathcal{F}_{t-1})\leq\kappa\mathbb{P}(Q\geq t).

The chain rule therefore gives

\mathrm{I}(S;\mathcal{R},Z_{1:n})=\sum_{t=1}^{n}\mathrm{I}(S;Z_{t}\mid\mathcal{F}_{t-1})\leq\kappa\sum_{t=1}^{n}\mathbb{P}(Q\geq t)=\kappa\,\mathbb{E}Q.

∎

4.3 Proof of the lower bound

Proof of Theorem 2.2.

We prove a distributional lower bound and then average to a fixed response. Fix $n,d,r,\varepsilon$ , put $N:=\lfloor n/r\rfloor$ , and use only the first $r$ columns of the design. If the expected query count under either hard distribution below is infinite, the conclusion is immediate; otherwise the algorithm returns almost surely and Lemma 4.3 applies. For either construction, decode an output by setting $\widehat{S}_{j}=+1$ when $\widehat{x}_{j}>1/2$ and $\widehat{S}_{j}=-1$ otherwise. The decoder is measurable with respect to $(\mathcal{R},Z_{1:n})$ .

Short blocks: $N<160$ .

Let the first $r$ rows of $A$ be the standard basis rows $e_{1}^{\mathsf{T}},\ldots,e_{r}^{\mathsf{T}}$ , and set the remaining rows to zero. Draw $S$ uniformly from $\{-1,+1\}^{r}$ , set $b_{j}=S_{j}$ for $j\leq r$ , and set the padded responses to zero. The optimum is zero, so on the success event a multiplicative approximation must recover every $S_{j}$ . The binary decoder therefore satisfies $\mathbb{E}d_{H}(S,\widehat{S})\leq 0.01r$ . Each fresh informative response carries at most $\log 2$ nats, while padded rows are deterministic. Data processing and Lemmas 4.2 and 4.3 give

\mathbb{E}Q\geq(c_{\rm RD}/\log 2)r.

Because $n<160r$ and $r/\varepsilon^{2}\geq n$ , this is $\Omega(\min\{n,r/\varepsilon^{2}\})$ .

Long blocks: $N\geq 160$ .

Set

\beta:=\max\left\{200\varepsilon,\sqrt{\frac{10}{N}}\right\}.

(4.7)

Then $N\beta^{2}\geq 10$ and $\beta\leq 1/4$ . Conditional on independent uniform signs $S_{1},\ldots,S_{r}$ , draw independent bits

Y_{jk}\sim\operatorname{Ber}(1/2+\beta S_{j}),\qquad j\in[r],\ k\in[N],

and give row $(j,k)$ the design vector $4e_{j}^{\mathsf{T}}$ and response $4Y_{jk}$ . Pad the fewer than $r$ remaining rows with zeros. A block is good when $S_{j}(\overline{Y}_{j}-1/2)\geq\beta/2$ , where $\overline{Y}_{j}:=N^{-1}\sum_{k=1}^{N}Y_{jk}$ ; Hoeffding’s inequality gives $\mathbb{P}(\text{block $j$ is not good}\mid S_{j})\leq e^{-5}$ .

On a good block, Lemma 4.1 charges at least $\beta N$ excess loss for a wrong sign. The vector whose first $r$ coordinates equal $1/2$ has loss $3Nr/2$ . For the realized response put $F_{*}:=\min_{x}F_{b}(x)$ ; on the success event

F_{b}(\widehat{x})-F_{*}\leq(2\varepsilon+\varepsilon^{2})F_{*}\leq\frac{9}{2}\varepsilon Nr.

Since $\beta\geq 200\varepsilon$ , at most $9r/400$ good blocks are decoded incorrectly. Charging all nongood blocks and all blocks on the failure event yields

\mathbb{E}d_{H}(S,\widehat{S})\leq(e^{-5}+9/400+0.01)r<0.04r.

(4.8)

It remains to bound the information in one adaptive response. Let $P_{s}:=\operatorname{Ber}(1/2+\beta s)$ . For $\mathcal{F}_{t-1}$ -almost every active history $h$ , a padded-row response is deterministic and carries zero information. Otherwise the fresh index is the fixed pair $J_{t}(h)=(j,k)$ . Under the corresponding regular conditional law, freshness gives the Markov relation $S_{-j}\to S_{j}\to Y_{jk}$ , and the observed response $4Y_{jk}$ is a bijective function of $Y_{jk}$ . Put $\theta_{s}(h):=\mathbb{P}(S_{j}=s\mid h)$ . Convexity of KL in its second argument gives, under this conditional law,

	$\displaystyle I_{h}(S;Y_{jk})$	$\displaystyle=I_{h}(S_{j};Y_{jk})$
		$\displaystyle\leq\sum_{s,s^{\prime}\in\{-1,+1\}}\theta_{s}(h)\theta_{s^{\prime}}(h)\mathrm{D}_{\mathrm{KL}}(P_{s}\\|P_{s^{\prime}})\leq 16\beta^{2},$		(4.9)

where $\mathrm{D}_{\mathrm{KL}}(P_{+}\|P_{-})=2\beta\log((1+2\beta)/(1-2\beta))\leq 16\beta^{2}$ , and the reverse divergence is identical. Thus Lemma 4.3 applies with $\kappa=16\beta^{2}$ . Data processing, (4.8), and Lemma 4.2 imply

\mathbb{E}Q\geq\frac{c_{\rm RD}}{16\beta^{2}}r.

(4.10)

Finally, since $rN\geq n-r\geq 159n/160$ ,

\frac{r}{\beta^{2}}=\min\left\{\frac{r}{40000\varepsilon^{2}},\frac{rN}{10}\right\}\geq c\min\left\{\frac{r}{\varepsilon^{2}},n\right\}.

(4.11)

In either regime, the hard response distribution has finite support and the algorithm succeeds with probability at least $0.99$ for every fixed response. Moreover, $\mathbb{E}_{S,Y,\mathcal{R}}Q=\mathbb{E}_{b}\mathbb{E}_{\mathcal{R}}Q(A,b)$ , with $Y$ absent in the short regime. Hence some fixed response in the support attains the distributional expected-query lower bound, proving Theorem 2.2. ∎

5 Related work and limitations

Active regression.

For least squares, leverage sampling gives an $O(r\log r)$ constant-accuracy baseline and spectral sparsification reaches linear dependence on the effective dimension [4]. Lewis-weight sampling gives nearly tight guarantees for least absolute deviations [2, 15]. After column-space reduction, the nonadaptive Huber specialization of Musco et al. [14] uses $\widetilde{O}(r^{4-2\sqrt{2}}\operatorname{poly}(1/\varepsilon))$ labels; our gain is the linear rank exponent and the matching joint dependence on $n,r,\varepsilon$ . Stratified, semi-supervised, online, and single-index regression use different models [17, 16, 3, 8, 13, 10]; statistical Huber regression instead studies population risk [9, 18].

Sparsification and the contribution boundary.

Lewis weights and sensitivity sampling underlie subspace and objective summaries [5, 7]. Jambulapati et al. [11] developed common-basepoint signed chaining, and Jambulapati et al. [12] gave multiscale generalized-linear-model sparsifiers, including the unshifted Huber case. Full-data sparsification does not directly give active sampling because the affine augmentation contains hidden labels. The step specific to this paper is Lemma 3.6: after an independent pilot, design-only scores preserve the localized affine increments needed by the optimizer. We do not claim the pilot, localization, common-basepoint chaining, or unshifted sparsification separately. A fixed label-independent weighted proper-subset objective also cannot preserve every affine baseline, and optimizing either endpoint surrogate can be polynomially worse. The similarly titled work of Cavazza and Murino [1] concerns semi-supervised multi-view learning.

Proposition 5.1 (Simple surrogate minimizers can be polynomially bad).

For all sufficiently large $N$ , there are one-dimensional instances on which the exact least-squares minimizer has Huber-norm approximation ratio $\Theta(N^{1/4})$ , and instances on which the exact $\ell_{1}$ -regression minimizer has ratio $\Theta(\sqrt{N})$ .

The explicit constructions are given in Appendix B.

Limitations.

The result counts labels under exact real arithmetic and exact convex optimization; it gives neither a near-linear-time implementation, a strong affine coreset, nor optimal confidence dependence. Markov’s inequality causes the $\delta^{-2}$ factor, while the scale union, chaining, and pilot cause the logarithms. Known Huber sensitivity examples have $\Omega(r\log\log(n/r))$ total sensitivity in some ranges [14], although this is not an active-query lower bound for those logarithms. Reducing the logarithmic and confidence factors, obtaining a fast implementation, and extending the centered transfer to other robust losses remain open.

References

[1] J. Cavazza and V. Murino. Active regression with adaptive Huber loss. arXiv preprint, 2016. arXiv:1606.01568.
[2] X. Chen and M. Dereziński. Query complexity of least absolute deviation regression via robust uniform convergence. In Proceedings of the 34th Conference on Learning Theory (COLT), volume 134 of Proceedings of Machine Learning Research, pages 1144–1179, 2021. arXiv:2102.02322.
[3] C. Chen, Y. Li, and Y. Sun. Online active regression. In Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 3320–3335, 2022. arXiv:2207.05945.
[4] X. Chen and E. Price. Active regression via linear-sample sparsification. In Proceedings of the 32nd Conference on Learning Theory (COLT), volume 99 of Proceedings of Machine Learning Research, pages 663–695, 2019. arXiv:1711.10051.
[5] M. B. Cohen and R. Peng. $\ell_{p}$ row sampling by Lewis weights. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 183–192, 2015. doi:10.1145/2746539.2746567.
[6] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, second edition, 2006.
[7] D. Feldman and M. Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 569–578, 2011. doi:10.1145/1993636.1993712.
[8] A. Gajjar, W. M. Tai, X. Xu, C. Hegde, C. Musco, and Y. Li. Agnostic active learning of single index models with linear sample complexity. In Proceedings of the 37th Conference on Learning Theory (COLT), volume 247 of Proceedings of Machine Learning Research, pages 1715–1754, 2024. arXiv:2405.09312.
[9] P. J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964. doi:10.1214/aoms/1177703732.
[10] C. W. In, Y. Li, W. M. Tai, and X. Wu. Active regression for single-index models with unknown link functions. arXiv preprint, 2026. arXiv:2608.01287.
[11] A. Jambulapati, J. R. Lee, Y. P. Liu, and A. Sidford. Sparsifying sums of norms. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1953–1962, 2023. doi:10.1109/FOCS57990.2023.00119.
[12] A. Jambulapati, J. R. Lee, Y. P. Liu, and A. Sidford. Sparsifying generalized linear models. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1665–1675, 2024. doi:10.1145/3618260.3649684. Full version: arXiv:2311.18145.
[13] Y. Li and W. M. Tai. Near-optimal active regression of single-index models. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR), 2025. arXiv:2502.18213.
[14] C. Musco, C. Musco, D. P. Woodruff, and T. Yasuda. Active linear regression for $\ell_{p}$ norms and beyond. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 744–753, 2022. doi:10.1109/FOCS54457.2022.00076. arXiv:2111.04888.
[15] A. Parulekar, A. Parulekar, and E. Price. $\ell_{1}$ regression with Lewis weights subsampling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), volume 207 of Leibniz International Proceedings in Informatics, article 49, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.49. arXiv:2105.09433.
[16] N. Rajaraman, F. Devvrit, and P. Awasthi. Semi-supervised active linear regression. In Advances in Neural Information Processing Systems 35, pages 1294–1306, 2022. doi:10.52202/068431-0095.
[17] S. Sabato and R. Munos. Active regression by stratification. In Advances in Neural Information Processing Systems 27, pages 469–477, 2014. arXiv:1410.5920.
[18] Q. Sun, W.-X. Zhou, and J. Fan. Adaptive Huber regression. Journal of the American Statistical Association, 115(529):254–265, 2020. doi:10.1080/01621459.2018.1543124.
[19] M. Talagrand. Upper and Lower Bounds for Stochastic Processes. Springer, 2014. doi:10.1007/978-3-642-54075-2.

Appendix A Technical details for the upper bound

This appendix records the construction, endpoint algebra, and attainment details used in Section 3. Throughout, $A\in\mathbb{R}^{N\times r}$ has full column rank and no zero row, and the notation is that of Section 3.1.

A.1 Deterministic weight schemes and endpoint covers

We spell out the exact-real construction asserted in Lemma 3.2. For positive vectors define

d_{\log}(u,w):=\max_{i\leq N}\left\lvert\log(u_{i}/w_{i})\right\rvert

and, at dyadic scale $2^{j}$ , define the exact leverage map

\mathcal{W}_{j}(w)_{i}:=\frac{H(v_{i}(w))}{2^{j}v_{i}(w)^{2}},\qquad v_{i}(w)^{2}=a_{i}^{\mathsf{T}}(A^{\mathsf{T}}\operatorname{diag}(w)A)^{-1}a_{i}.

All coordinates are positive because $A$ has full column rank and no zero row. The log-Lipschitzness of weighted leverage and the lower- $1$ , upper- $2$ scaling of $H$ imply

d_{\log}(\mathcal{W}_{j}(u),\mathcal{W}_{j}(w))\leq\tfrac{1}{2}d_{\log}(u,w),\qquad\mathcal{W}_{j+1}(w)=\tfrac{1}{2}\mathcal{W}_{j}(w).

Let $j_{0}:=\min\mathcal{I}$ , set $u^{[0]}:=\mathbf{1}$ , and iterate $u^{[k+1]}:=\mathcal{W}_{j_{0}}(u^{[k]})$ . The contraction gives

d_{\log}(u^{[k+1]},u^{[k]})\leq 2^{-k}d_{\log}(u^{[1]},u^{[0]}),

and the right-hand side is finite. Stop at the first $k$ for which it is at most $\log 2$ , and set $w^{(j_{0})}:=u^{[k]}$ . Recursively warm-start every later scale by the single update

w^{(j+1)}:=\mathcal{W}_{j+1}(w^{(j)}),\qquad j=j_{0},\ldots,\max\mathcal{I}-1.

(A.1)

If $d_{\log}(\mathcal{W}_{j}(w^{(j)}),w^{(j)})\leq\log 4$ , then

\frac{1}{8}\leq\frac{w_{i}^{(j+1)}}{w_{i}^{(j)}}\leq 2,\qquad d_{\log}\bigl(\mathcal{W}_{j+1}(w^{(j+1)}),w^{(j+1)}\bigr)\leq\tfrac{1}{2}\log 8<\log 4.

Induction therefore gives both inequalities in the weight-scheme definition with the universal choice $\alpha_{0}=4$ . The construction makes finitely many exact-real updates and is deterministic in $(A,\mathcal{I})$ . Moreover, for every scale,

\sum_{i}w_{i}^{(j)}v_{i}(w^{(j)})^{2}=\operatorname{tr}\!\left(A^{\mathsf{T}}\operatorname{diag}(w^{(j)})A(A^{\mathsf{T}}\operatorname{diag}(w^{(j)})A)^{-1}\right)=r.

Finally, the residual bound is exactly

4^{-1}\leq\frac{H(v_{i}(w^{(j)}))}{2^{j}w_{i}^{(j)}v_{i}(w^{(j)})^{2}}\leq 4,

which is (3.8). This establishes the construction claim in Lemma 3.2. If a numerical implementation substitutes scores $\widetilde{\lambda}_{i}\in[\lambda_{i}/c,c\lambda_{i}]$ for a fixed $c\geq 1$ , the safe sampling score is $c\widetilde{\lambda}_{i}$ : it dominates $\lambda_{i}$ coordinatewise and increases total mass by only a constant factor. No approximation is needed for the transition scheme; endpoint approximations are handled below.

We also use the following direct power-function specialization of the same source theorem. For $p\in\{1,2\}$ , let $\mathcal{I}$ be a finite contiguous integer interval of size at least $4\log(2N)$ . If positive weights satisfy

\frac{\left\lvert v_{i}(w^{(j)})\right\rvert^{p}}{w_{i}^{(j)}v_{i}(w^{(j)})^{2}}=2^{j},\qquad w_{i}^{(j+1)}\leq w_{i}^{(j)},

(A.2)

set $\lambda_{i}^{(j)}:=w_{i}^{(j)}v_{i}(w^{(j)})^{2}$ , $\tau_{i}:=\max_{j\in\mathcal{I}}\lambda_{i}^{(j)}$ , and $k_{\mathcal{I}}:=\max\mathcal{I}+1$ . Then

\gamma_{2}\!\left(\{h:\left\lVert Ah\right\rVert_{p}^{p}\leq 2^{k_{\mathcal{I}}}\},(h,k)\mapsto\max_{i}\frac{\left\lvert a_{i}^{\mathsf{T}}(h-k)\right\rvert^{p/2}}{\sqrt{\tau_{i}}}\right)\leq C2^{k_{\mathcal{I}}/2}\log^{3/2}(2N).

(A.3)

This is Jambulapati et al. [12, Definition 1.8 and the proof of Theorem 3.14] with $f_{i}(t)=\left\lvert t\right\rvert^{p}$ ; these functions meet the theorem’s symmetry, scaling, and metric assumptions exactly.

A.2 Endpoint score bounds

Proof of Lemma 3.3.

Fix $p\in\{1,2\}$ and use the notation of (3.13)–(3.14). The trace identity gives

\sum_{i=1}^{N}\lambda_{i}^{(p)}=\operatorname{tr}\!\left(A^{\mathsf{T}}\operatorname{diag}(w^{(p)})A\bigl(A^{\mathsf{T}}\operatorname{diag}(w^{(p)})A\bigr)^{-1}\right)=r.

For an integer scale $j$ , set $w_{i}^{(j)}:=2^{-2j/p}w_{i}^{(p)}$ . If

(v_{i}^{(j)})^{2}:=a_{i}^{\mathsf{T}}(A^{\mathsf{T}}\operatorname{diag}(w^{(j)})A)^{-1}a_{i},

then $v_{i}^{(j)}=2^{j/p}v_{i}^{(p)}$ , and hence

\frac{(v_{i}^{(j)})^{p}}{w_{i}^{(j)}(v_{i}^{(j)})^{2}}=2^{j},\qquad w_{i}^{(j+1)}=2^{-2/p}w_{i}^{(j)},\qquad w_{i}^{(j)}(v_{i}^{(j)})^{2}=\lambda_{i}^{(p)}.

Thus this is an exact weight scheme for the power function $f_{p}(t)=\left\lvert t\right\rvert^{p}$ , with a scale-independent leverage vector. Let $L:=\lceil 4\log(2N)\rceil$ and $\mathcal{I}_{0}:=\{-L,\ldots,-1\}$ , so $k_{\mathcal{I}_{0}}=0$ . Applying (A.3) to this block gives (3.16) for $S=1$ . The substitution $h=S^{1/p}u$ maps the unit ball onto $\{h:\left\lVert Ah\right\rVert_{p}^{p}\leq S\}$ and multiplies $d_{p}$ by $S^{1/2}$ , which proves the stated bound for every $S>0$ . ∎

A.3 Attainment and deterministic selections

For completeness, consider a sampled objective

G(x)=\sum_{i\in S}\omega_{i}H(a_{i}^{\mathsf{T}}x-\beta_{i}),\qquad\omega_{i}>0.

Represent a quotient class $[x]$ by its unique member in the orthogonal complement of the kernel of the sampled rows, and use that representative’s Euclidean norm as $\left\lVert[x]\right\rVert_{2}$ . Injectivity and compactness of the unit sphere give a constant $c_{S}>0$ . With $C_{S}:=\sum_{i\in S}\omega_{i}(\left\lvert\beta_{i}\right\rvert+1/2)$ ,

G(x)\geq\sum_{i\in S}\omega_{i}\left\lvert a_{i}^{\mathsf{T}}x\right\rvert-\sum_{i\in S}\omega_{i}(\left\lvert\beta_{i}\right\rvert+1/2)\geq c_{S}\left\lVert[x]\right\rVert_{2}-C_{S}.

Thus $G$ is coercive on that quotient and attains its minimum. Its argmin in $\mathbb{R}^{r}$ is nonempty, closed, and convex, so the Euclidean projection of the origin onto it exists and is unique. This is the minimum-norm selection used for both batches. Equivalently, it is the limit, as $k\to\infty$ , of the unique minimizers of $G(x)+k^{-1}\left\lVert x\right\rVert_{2}^{2}$ . This characterization makes the selection a measurable deterministic function of the finite sample and its observed labels. In particular, the pilot selection uses only the pilot indices, pilot labels, and fixed design; the independent main sample cannot affect it.

Appendix B Surrogate counterexamples

Proof of Proposition 5.1.

For least squares, take $N$ rows $(a,b)=(1,0)$ and one row $(a,b)=(\sqrt{N},4\sqrt{N})$ . The squared-loss surrogate is $G_{2}(x)=Nx^{2}+N(x-4)^{2}$ , whose unique minimizer is $x=2$ . The Huber objective is $\Psi_{2}(x)=NH(x)+H(\sqrt{N}(x-4))$ . At $x_{*}=N^{-1/2}$ , both terms are differentiable and $\Psi_{2}^{\prime}(x_{*})=N/\sqrt{N}-\sqrt{N}=0$ ; convexity makes $x_{*}$ optimal. Moreover,

\Psi_{2}(2)=\frac{3}{2}N+2\sqrt{N}-\frac{1}{2},\qquad\Psi_{2}(x_{*})=4\sqrt{N}-1,

so the ratio of square-root objectives is $\Theta(N^{1/4})$ .

For $\ell_{1}$ , take $N$ rows $(1,0)$ and one row $(N/2,1)$ . The surrogate $G_{1}(x)=N\left\lvert x\right\rvert+\left\lvert Nx/2-1\right\rvert$ has slopes $-3N/2$ , $N/2$ , and $3N/2$ on its three linear intervals, so zero is its unique minimizer. The Huber objective $\Psi_{1}(x)=NH(x)+H(Nx/2-1)$ is minimized at $x_{*}=2/(N+4)$ , where both residuals are quadratic and the derivative is zero. Finally,

\Psi_{1}(0)=\frac{1}{2},\qquad\Psi_{1}(x_{*})=\frac{2}{N+4},

so the square-root-objective ratio is exactly $\sqrt{(N+4)/4}=\Theta(\sqrt{N})$ . ∎

Near-Optimal Label Complexity for Active Huber Regression

Abstract

1 Introduction

Our results.

Organization.

2 Problem, model, and main results

Theorem 2.1 (Nonadaptive upper bound).

Theorem 2.2 (Matching adaptive lower bound).

Corollary 2.3 (Minimax label complexity).

Proof.

Proof mechanism.

3 The nonadaptive upper bound

3.1 Unshifted geometry and label-oblivious scores

Lemma 3.1 (Huber triangle and increment inequalities).

Proof.

Lemma 3.2 (Imported multiscale covering primitive).

Lemma 3.3 (Endpoint coverings).

Lemma 3.4 (All-radius label-oblivious Huber scores).

Proof.

Lemma 3.5 (Unshifted expectation bound).

Proof.

3.2 Centered affine preservation

Lemma 3.6 (Centered affine transfer).

Proof.

Remark 3.7 (Why centering matters).

3.3 Pilot, algorithm, and localization

Lemma 3.8 (Huber all-scale extension).

Proof.

Lemma 3.9 (Label-oblivious constant-factor pilot).

Proof.

Two-batch nonadaptive algorithm.

Proof of Theorem 2.1.

4 Matching lower bound against adaptive queries

4.1 Scalar Huber gap

Lemma 4.1 (Exact scalar majority gap).

Proof.

4.2 Information lemmas for adaptive queries

Lemma 4.2 (Binary rate–distortion).

Proof.

Lemma 4.3 (Finite adaptive-transcript bound).

Proof.

4.3 Proof of the lower bound

Proof of Theorem 2.2.

Short blocks: N<160.

Long blocks: N≥160.

5 Related work and limitations

Active regression.

Sparsification and the contribution boundary.

Proposition 5.1 (Simple surrogate minimizers can be polynomially bad).

Limitations.

References

Appendix A Technical details for the upper bound

A.1 Deterministic weight schemes and endpoint covers

A.2 Endpoint score bounds

Proof of Lemma 3.3.

A.3 Attainment and deterministic selections

Appendix B Surrogate counterexamples

Proof of Proposition 5.1.

Near-Optimal Label Complexity
for Active Huber Regression

Short blocks: $N<160$ .

Long blocks: $N\geq 160$ .