Proof. We again follow the lines of Lemma E.1. Taking an inner product on the optimality condition, and from steps identical to those of the previous Lemmas,

$$
\begin{align*}
\|\hat{w}\|^2 &= -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \partial_r \ell(r_i, u_i, y_i, c_i, \epsilon_i) r_i \\
&= -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \partial_r \ell(\tilde{r}_{i,i}, \tilde{u}_{i,i}, y_i, c_i, \epsilon_i) \tilde{r}_{i,i} + O_{L_k}(\text{polylog}(n)).
\end{align*}
$$

Thus, taking expectations and by symmetry,

$$
q = -\frac{1}{\lambda} \mathbb{E} \left[ \partial_r \ell(\tilde{r}_{1,1}, \tilde{u}_{1,1}, y_1, c_1, \epsilon_1) \tilde{r}_{1,1} \right] + O \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right)
$$

Again, before applying Lemma D.3, one needs to check that the function $\varphi: r, u, s, c, \epsilon \to \partial_r \ell(r, u, \phi(s, c, \epsilon), c, \epsilon)r$
belongs to the class $\mathcal{F}$. It suffices similarly to the proof of Lemma E.3 to bound the norm of the gradient
$\|\nabla_{r,u}\varphi(\tilde{r}, \tilde{u}, s, c, \epsilon)\|$ evaluated at $(\tilde{r}, \tilde{u})$ on the line connecting $(r_1, u_1)$, $(r_2, u_2)$. This norm can in turn be
bounded as

$$
\begin{align*}
\| \nabla_{r,u} \varphi(\tilde{r}, \tilde{u}, s, c, \epsilon) \| &= \sqrt{ (\partial_r \partial_u \ell(\tilde{r}, \tilde{u}, \phi(s, c, \epsilon), c, \epsilon) \tilde{r})^2 + (\partial_r^2 \ell(\tilde{r}, \tilde{u}, \phi(s, c, \epsilon), c, \epsilon) \tilde{r} + \partial_r \ell(\tilde{r}, \tilde{r}, \phi(s, c, \epsilon), c, \epsilon))^2 } \\
&\le \sqrt{ \| \partial_r \partial_u \ell \|_{\infty}^2 + 2 \| \partial_r \ell \|_{\infty}^2 (|r_1| + |r_2|) + 2 \| \partial_r \ell \|_{\infty}^2 }.
\end{align*}
$$

Thus, $\varphi \in \mathcal{F}$, and from Lemma D.3,

$$
\left| \mathbb{E} \left[ \partial_r \ell(\tilde{r}_{1,1}, \tilde{u}_{1,1}, y_1, c_1, \epsilon_1) \tilde{r}_{1,1} \right] - \mathbb{E} \left[ \partial_r \ell(r, u, g_3, c, \epsilon) r \right] \right| \xrightarrow{n \to \infty} 0.
$$

This proves the Lemma.

<figure><img src="image_18.png" /></figure>

**Lemma E.5 (Characterization of V).** The summary statistic $V = \mathbb{E}[\mathfrak{V}]$ is asymptotically characterized by
the self-consistent equation

$$
\left| -\frac{1}{n/dV} + \mathbb{E} \left[ \frac{\partial_r^2 \ell(r, u, g_3, c, \epsilon)}{1 + V \partial_r^2 \ell(r, u, g_3, c, \epsilon)} \right] + \lambda \right| = O \left( \frac{\text{polylog}(n)}{n^{1/4}} \right).
$$

Proof. The proof strategy follows closely that of Lemma 15 in Barnfield et al. [2025]. By definition of H, the identity

$$
\frac{1}{n^2} \sum_{i \in [n]} \partial_r^2 \ell_i(r_i, u_i) x_i^\top H^{-1} x_i + \lambda \mathfrak{V} = \frac{d}{n}
$$

follows. Applying the matrix inversion lemma yields the more compact expression

$$
\frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(r_i, u_i) \hat{\gamma}_i}{1 + \partial_r^2 \ell_i(r_i, u_i) \hat{\gamma}_i} + \lambda \mathfrak{V} = \frac{d}{n}, \quad (22)
$$

where we defined $\hat{\gamma}_i = 1/n x_i^\top \hat{H}_i^{-1} x_i$ and

$$
\hat{H}_i = \frac{1}{n} \sum_{j \neq i} \partial_r^2 \ell_j(r_j, u_j) x_j x_j^\top + \lambda I_d = H - \frac{1}{n} \partial_r^2 \ell_i(r_i, u_i) x_i x_i^\top.
$$
To use Lemma C.5, we first establish that $\hat{\gamma}_i \approx \gamma_i$. To see this, we start from a coarse Cauchy-Schwartz bound

$$
\begin{align*}
\sup_{i \in [n]} |\hat{\gamma}_i - \gamma_i| &\le \sup_{i \in [n]} \frac{\|x_i\|^2}{n} \frac{1}{\lambda^2} \sup_{i \in [n]} \|\hat{H}_i - H_{\setminus i}\| \\
&= \sup_{i \in [n]} \frac{\|x_i\|^2}{n} \frac{1}{\lambda^2} \sup_{i \in [n]} \frac{1}{n} \|X_{\setminus i}^\top \Lambda X_{\setminus i}\| \\
&\le \sup_{i \in [n]} \frac{\|x_i\|^2}{n} \frac{1}{\lambda^2} \sup_{i \in [n]} \frac{\|X_{\setminus i}\|^2}{n} \sup_{i \in [n]} \|\Lambda_i\|,
\end{align*}
$$

introducing the diagonal matrix $\Lambda_i \in \mathbb{R}^{(n-1) \times (n-1)}$ with entries $\Lambda_{i,jj} = \partial_r^2 \ell_j(r_j, u_j) - \partial_r^2 \ell_j(r_{j,\setminus i}, u_{j,\setminus i})$.
Proposition B.1 and Proposition B.10 allow to bound the norm of $\Lambda$ as

$$
\sup_{i \in [n]} \|\Lambda_i\| \le \left( \left\| \partial_r^3 \ell \right\|_{\infty} \vee \left\| \partial_r^2 \partial_u \ell \right\|_{\infty} \right) \left( \sup_{i \in [n]} \sup_{j \ne i} |r_j - r_{j,\setminus i}| + \sup_{i \in [n]} \sup_{j \ne i} |u_j - u_{j,\setminus i}| \right) = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Thus

$$
\sup_{i \in [n]} |\hat{\gamma}_i - \gamma_i| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

As a consequence,

$$
\left| \frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(r_i, u_i) \hat{\gamma}_i}{1 + \partial_r^2 \ell_i(r_i, u_i) \hat{\gamma}_i} - \frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(r_i, u_i) V}{1 + \partial_r^2 \ell_i(r_i, u_i) V} \right| \le \left\| \partial_r^2 \ell \right\|_{\infty} \left( \sup_{i \in [n]} |\hat{\gamma}_i - \gamma_i| + \sup_{i \in [n]} |\mathfrak{W} - \gamma_i| + |\mathfrak{W} - V| \right) \\
= O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

using the concentration results of Lemma C.5. It now remains to approximate the full residuals $r_i, u_i$ by the
surrogates $\tilde{r}_{i,i}, \tilde{u}_{i,i}$. The difference can be bounded as

$$
\sup_{i \in [n]} \left| \partial_r^2 \ell_i(r_i, u_i) - \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \right| \le \left( \left\| \partial_r^3 \ell \right\|_{\infty} \vee \left\| \partial_r^2 \partial_u \ell \right\|_{\infty} \right) \left( \sup_{i \in [n]} |r_i - \tilde{r}_{i,i}| + \sup_{i \in [n]} |u_i - \tilde{u}_{i,i}| \right) \\
= O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right),
$$

using Proposition B.10. Thus,

$$
\left| \frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(r_i, u_i) V}{1 + \partial_r^2 \ell_i(r_i, u_i) V} - \frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) V}{1 + \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) V} \right| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Returning to (22),

$$
\frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) V}{1 + \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) V} + \lambda V + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) = \frac{d}{n}.
$$

Taking expectations, and again appealing to the permutation symmetry of the samples,

$$
\mathbb{E} \left[ \frac{\partial_r^2 \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1}, y_1, c_1, \epsilon_1) V}{1 + \partial_r^2 \ell(\tilde{r}_{1,1}, \tilde{u}_{1,1}, y_1, c_1, \epsilon_1) V} \right] + \lambda V + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) = \frac{d}{n}.
$$
Since $\varphi : r, u, s, c, \epsilon \to 1/1 + \partial_r^2 \ell(r, u, \phi(s, c, \epsilon), c, \epsilon)V$ is Lipschitz and bounded, it belongs to $\mathcal{F}$. Thus, applying Lemma D.3,

$$ \left| \mathbb{E} \left[ \frac{\partial_r^2 \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1}, y_1, c_1, \epsilon_1)}{1 + \partial_r^2 \ell(\tilde{r}_{1,1}, \tilde{u}_{1,1}, y_1, c_1, \epsilon_1) V} \right] - \mathbb{E} \left[ \frac{\partial_r^2 \ell(r, u, g_3, c, \epsilon)}{1 + V \partial_r^2 \ell(r, u, g_3, c, \epsilon)} \right] \right| = O \left( \frac{\text{polylog}(n)}{n^{1/4}} \right). $$

This completes the proof.

<figure><img src="image_19.png" /></figure>

Before moving on to characterizing $\chi$, we first need to establish, as an intermediary step, a similar result for $\Omega = \mathbb{E}[\mathfrak{W}]$.

**Lemma E.6 (Characterization of $\Omega$).** The summary statistic $\Omega = \mathbb{E}[\mathfrak{W}]$ is asymptotically characterized by the equation

$$ \left| \Omega - \frac{d}{n} \frac{\mathbb{E} \left[ \frac{\partial_r \partial_u \ell(r, u, g_3, c, \epsilon)}{1 + V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon)} \right]}{\lambda_0 + \mathbb{E} \left[ \frac{\partial_r^2 \ell_0(u, g_3, c, \epsilon)}{1 + V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon)} \right]} \right| = O \left( \frac{\text{polylog}(n)}{n^{1/4}} \right). $$

*Proof.* We start from the identity

$$ G = \frac{1}{n} \sum_{i \in [n]} \partial_r \partial_u \ell_i(r_i, u_i) x_i x_i^\top H_0^{-1} G + \lambda_0 H_0^{-1} G. $$

Taking the trace and denoting $\mathfrak{G} = 1/n \text{tr}[G]$,

$$ \mathfrak{G} = \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) x_i^\top \left( \hat{H}_{0,i} + \partial_u^2 \ell_{0,i}(u_i) \frac{x_i x_i^\top}{n} \right)^{-1} \left( \hat{G}_i + \partial_r \partial_u \ell_i(r_i, u_i) \frac{x_i x_i^\top}{n} \right) x_i + \lambda_0 \mathfrak{W}, $$

where we defined

$$ \hat{H}_0 = \frac{1}{n} \sum_{j \neq i} \partial_u^2 \ell_{0,j}(u_j) x_j x_j^\top + \lambda_0 I_d, $$

$$ G = \frac{1}{n} \sum_{j \neq i} \partial_r \partial_u \ell_j(r_j, u_j) x_j x_j^\top. $$

Denoting $\hat{\gamma}_{0,i} = 1/n x_i^\top \hat{H}_{0,i}^{-1} x_i$, $\hat{\omega}_i = 1/n x_i^\top \hat{H}_{0,i}^{-1} \hat{G}_i x_i$, and using the matrix inversion lemma, one has

$$ \mathfrak{G} = \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) \left[ \hat{\omega}_i - \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + \partial_u^2 \ell_{0,i}(u_i) \hat{\gamma}_{0,i}} \hat{\gamma}_{0,i} \hat{\omega}_i + \frac{d}{n} \partial_r \partial_u \ell_i(r_i, u_i) \hat{\gamma}_{0,i} - \frac{d}{n} \hat{\gamma}_{0,i}^2 \frac{\partial_u^2 \ell_{0,i}(u_i) \partial_r \partial_u \ell_i(r_i, u_i)}{1 + \partial_u^2 \ell_{0,i}(u_i) \hat{\gamma}_{0,i}} \right] + \lambda_0 \mathfrak{G}. $$

Using the same line of reasoning as the proof of Lemma E.5, one reaches the approximations

$$ \sup_{i \in [n]} |\hat{\gamma}_{0,i} - \omega_i| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

$$ \sup_{i \in [n]} |\hat{\omega}_i - \omega_i| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

Thus,

$$ \left| \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) \hat{\omega}_i - \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) \Omega \right| \le \| \partial_r \partial_u \ell \|_{\infty} \left( \sup_{i \in [n]} |\hat{\omega}_i - \omega_i| + \sup_{i \in [n]} |\mathfrak{W} - \omega_i| + |\mathfrak{W} - \Omega| \right) \\ = O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$
By the same token

$$
\left| \frac{1}{n} \sum_{i \in [n]} \frac{\partial_u^2 \ell_{0,i}(u_i)^2}{1 + \partial_u^2 \ell_{0,i}(u_i) \hat{\gamma}_{0,i}} \hat{\gamma}_{0,i} \hat{\omega}_i - \frac{1}{n} \sum_{i \in [n]} \frac{\partial_u^2 \ell_{0,i}(u_i)^2}{1 + \partial_u^2 \ell_{0,i}(u_i) V_0} V_0 \Omega \right| = O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right)
$$
$$
\left| \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) \partial_r \partial_u \ell_i(r_i, u_i) \hat{\gamma}_{0,i} - \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) \partial_r \partial_u \ell_i(r_i, u_i) V_0 \right| = O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right)
$$
$$
\left| \frac{1}{n} \sum_{i \in [n]} \hat{\gamma}_{0,i}^2 \frac{\partial_u^2 \ell_{0,i}(u_i)^2 \partial_r \partial_u \ell_i(r_i, u_i)}{1 + \partial_u^2 \ell_{0,i}(u_i) \hat{\gamma}_{0,i}} - \frac{1}{n} \sum_{i \in [n]} V_0^2 \frac{\partial_u^2 \ell_{0,i}(u_i)^2 \partial_r \partial_u \ell_i(r_i, u_i)}{1 + \partial_u^2 \ell_{0,i}(u_i) V_0} \right| = O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Thus,

$$
\mathfrak{G} = \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(u_i) \left[ \Omega - \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + \partial_u^2 \ell_{0,i}(u_i) V_0} V_0 \Omega + \frac{d}{n} \partial_r \partial_u \ell_i(r_i, u_i) V_0 - \frac{d}{n} V_0^2 \frac{\partial_u^2 \ell_{0,i}(u_i) \partial_r \partial_u \ell_i(r_i, u_i)}{1 + \partial_u^2 \ell_{0,i}(u_i) V_0} \right] \\
+ \lambda_0 \mathfrak{W} + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Now using the approximations

$$
\sup_{i \in [n]} \left| \partial_r \partial_u \ell_i(r_i, u_i) - \partial_r \partial_u \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \right| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right),
$$

$$
\sup_{i \in [n]} \left| \partial_u^2 \ell_{0,i}(u_i) - \partial_u^2 \ell_{0,i}(\tilde{u}_{i,i}) \right| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right),
$$

that follow from Proposition B.1 and B.10, one has (using that $\Omega = O(\text{polylog}(n))$):

$$
\mathfrak{G} = \frac{1}{n} \sum_{i \in [n]} \partial_u^2 \ell_{0,i}(\tilde{u}_{i,i}) \left[ \frac{\Omega}{1 + \partial_u^2 \ell_{0,i}(\tilde{u}_{i,i}) V_0} + \frac{d}{n} \frac{\partial_r \partial_u \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) V_0}{1 + \partial_u^2 \ell_{0,i}(\tilde{u}_{i,i}) V_0} \right] + \lambda_0 \mathfrak{W} + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Taking the expectation, and using again the argument of symmetry between sample indices, yields

$$
\Gamma = \mathbb{E} \left[ \partial_u^2 \ell_{0,i}(\tilde{u}_{1,1}) \left[ \frac{\Omega}{1 + \partial_u^2 \ell_{0,i}(\tilde{u}_{1,1}) V_0} + \frac{d}{n} \frac{\partial_r \partial_u \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1}) V_0}{1 + \partial_u^2 \ell_{0,i}(\tilde{u}_{1,1}) V_0} \right] \right] - \lambda_0 \Omega + O \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right),
$$

denoting $\Gamma = \mathbb{E}[\mathfrak{G}]$. One can readily verify that all the functions in the expectation are Lipschitz with respect to $\tilde{r}_{1,1}, \tilde{u}_{1,1}$. Applying Lemma D.3,

$$
\Gamma - \mathbb{E} \left[ \partial_u^2 \ell_0(u, g_3, c, \epsilon) \left[ \frac{\Omega}{1 + \partial_u^2 \ell_0(u, g_3, c, \epsilon) V_0} + \frac{d}{n} \frac{\partial_r \partial_u \ell(r, u, g_3, c, \epsilon) V_0}{1 + \partial_u^2 \ell_0(u, g_3, c, \epsilon) V_0} \right] \right] + \lambda_0 \Omega = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right).
$$

It remains to compute $\Gamma$. By definition

$$
\mathfrak{G} = \frac{1}{n} \sum_{j \neq i} \partial_r \partial_u \ell_j(r_j, u_j) \frac{\|x_i\|^2}{n} = \frac{d}{n^2} \sum_{j \neq i} \partial_r \partial_u \ell_j(r_j, u_j) + O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Since using Lemma F.6, $\sup_{i \in [n]} \|x_i\|^2/d - 1 = O_{L_k}(\text{polylog}(n)/\sqrt{n})$. Taking expectation, and following the same steps as above yields

$$
\Gamma = \frac{d}{n} \mathbb{E} \left[ \partial_r \partial_u \ell(r, u, g_3, c, \epsilon) \right].
$$
Thus, finally

$$ \Omega \left( \lambda_0 + \mathbb{E} \left[ \frac{\partial_u^2 \ell_0(u, g_3, c, \epsilon)}{1 + \partial_u^2 \ell_0(u, g_3, c, \epsilon) V_0} \right] \right) - \mathbb{E} \left[ \frac{\partial_r \partial_u \ell(u, g_3, c, \epsilon)}{1 + \partial_u^2 \ell_0(u, g_3, c, \epsilon) V_0} \right] = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right), $$

proving the Lemma.

<figure><img src="image_20.png" /></figure>

**Lemma E.7 (Characterization of $\chi$).** The summary statistic $\chi = \mathbb{E}[\mathfrak{X}]$ is asymptotically characterized by the equation

$$ \left| \chi - \frac{\frac{d}{n} \mathbb{E} \left[ \frac{\partial_r \partial_u \ell(r, u, g_3, c, \epsilon)}{1+V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon)} \right]}{\lambda_0 + \mathbb{E} \left[ \frac{\partial_r \partial_u \ell_0(u, g_3, c, \epsilon)}{1+V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon)} \right]} - \frac{\mathbb{E} \left[ \frac{\partial_r^2 \ell(r, u, g_3, c, \epsilon) \partial_r \partial_u \ell(r, u, g_3, c, \epsilon) V_0 V}{(1+V \partial_r^2 \ell(r, u, g_3, c, \epsilon))(1+V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon))} \right]}{\lambda + \mathbb{E} \left[ \frac{\partial_r^2 \ell(r, u, g_3, c, \epsilon)}{(1+V \partial_r^2 \ell(r, u, g_3, c, \epsilon))(1+V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon))} \right]} \right| = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right). $$

*Proof.* We again adopt the same proof strategy, taking as a starting point the identity

$$ GH_0^{-1} = \frac{1}{n} \sum_{i \in [n]} \partial_r^2 \ell_i(r_i, u_i) x_i x_i^\top H^{-1} GH_0^{-1} + \lambda H^{-1} GH_0^{-1}, $$

namely, by taking a normalized trace

$$ \mathfrak{W} = \frac{1}{n} \sum_{i \in [n]} \partial_r^2 \ell_i(r_i, u_i) \frac{1}{n} x_i^\top H^{-1} GH_0^{-1} x_i + \lambda \mathfrak{X}. $$

Using the matrix inversion lemma,

$$ \mathfrak{W} = \frac{1}{n} \sum_{i \in [n]} \partial_r^2 \ell_i(r_i, u_i) \left[ \hat{v}_i - \frac{\partial_r^2 \ell_i(r_i, u_i)}{1 + \hat{\gamma}_i \partial_r^2 \ell_i(r_i, u_i)} \hat{v}_i \hat{\gamma}_i - \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + \hat{\gamma}_{0,i} \partial_u^2 \ell_{0,i}(u_i)} \hat{\gamma}_{0,i} \hat{v}_i + \partial_r \partial_u \ell_i(r_i, u_i) \hat{\gamma}_{0,i} \hat{\gamma}_i \right. \\ - \frac{\partial_r \partial_u \ell_i(r_i, u_i) \partial_r^2 \ell_i(r_i, u_i)}{1 + \hat{\gamma}_i \partial_r^2 \ell_i(r_i, u_i)} \hat{\gamma}_{0,i} \hat{\gamma}_i^2 - \frac{\partial_r \partial_u \ell_i(r_i, u_i) \partial_u^2 \ell_{0,i}(u_i)}{1 + \hat{\gamma}_{0,i} \partial_u^2 \ell_{0,i}(u_i)} \hat{\gamma}_{0,i}^2 \hat{\gamma}_i \\ + \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + \hat{\gamma}_{0,i} \partial_u^2 \ell_{0,i}(u_i)} \frac{\partial_r^2 \ell_i(r_i, u_i)}{1 + \hat{\gamma}_i \partial_r^2 \ell_i(r_i, u_i)} \hat{\gamma}_{0,i} \hat{v}_i \hat{\gamma}_i \\ \left. + \partial_r \partial_u \ell_i(r_i, u_i) \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + \hat{\gamma}_{0,i} \partial_u^2 \ell_{0,i}(u_i)} \frac{\partial_r^2 \ell_i(r_i, u_i)}{1 + \hat{\gamma}_i \partial_r^2 \ell_i(r_i, u_i)} \hat{\gamma}_{0,i}^2 \hat{\gamma}_i^2 \right] + \lambda \mathfrak{X} $$

defining $\hat{v}_i = 1/n \text{tr}[\hat{H}_i^{-1} \hat{G}_i \hat{H}_{0,i}^{-1}]$. Using the concentration Lemmas C.5 and C.6,

$$ \begin{aligned} \mathfrak{W} &= \frac{1}{n} \sum_{i \in [n]} \partial_r^2 \ell_i(r_i, u_i) \left[ \chi - \frac{\partial_r^2 \ell_i(r_i, u_i)}{1 + V \partial_r^2 \ell_i(r_i, u_i)} \chi V - \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + V_0 \partial_u^2 \ell_{0,i}(u_i)} V_0 \chi + \partial_r \partial_u \ell_i(r_i, u_i) V_0 V \right. \\ &\quad - \frac{\partial_r \partial_u \ell_i(r_i, u_i) \partial_r^2 \ell_i(r_i, u_i)}{1 + V \partial_r^2 \ell_i(r_i, u_i)} V_0 V^2 - \frac{\partial_r \partial_u \ell_i(r_i, u_i) \partial_u^2 \ell_{0,i}(u_i)}{1 + V_0 \partial_u^2 \ell_{0,i}(u_i)} V_0^2 V + \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + V_0 \partial_u^2 \ell_{0,i}(u_i)} \frac{\partial_r^2 \ell_i(r_i, u_i)}{1 + V \partial_r^2 \ell_i(r_i, u_i)} V_0 \chi V \\ &\quad \left. + \partial_r \partial_u \ell_i(r_i, u_i) \frac{\partial_u^2 \ell_{0,i}(u_i)}{1 + V_0 \partial_u^2 \ell_{0,i}(u_i)} \frac{\partial_r^2 \ell_i(r_i, u_i)}{1 + V \partial_r^2 \ell_i(r_i, u_i)} V_0^2 V^2 \right] + \lambda \mathfrak{X} + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) \\ &= \chi \frac{1}{n} \sum_{i \in [n]} \partial_r^2 \ell_i(r_i, u_i) \frac{1}{1 + V \partial_r^2 \ell_i(r_i, u_i)} \frac{1}{1 + V_0 \partial_u^2 \ell_{0,i}(u_i)} \\ &\quad + V V_0 \frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(r_i, u_i) \partial_r \partial_u \ell_i(r_i, u_i)}{1 + V \partial_r^2 \ell_i(r_i, u_i)} \frac{1}{1 + V_0 \partial_u^2 \ell_{0,i}(u_i)} + \lambda \mathfrak{X} + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) \end{aligned} $$
Using Proposition B.1 and Proposition B.10, one can replace the full residuals by the surrogates $\tilde{r}_{i,i}, \tilde{u}_{i,i}$ at the price of a $O_{L_k}(\text{polylog}(n)/\sqrt{n})$ correction:

$$ \mathfrak{W} = \chi \frac{1}{n} \sum_{i \in [n]} \frac{\partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i})}{1 + V \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i})} \frac{1}{1 + V_0 \partial_u^2 \ell_{0,i}(\tilde{u}_{i,i})} \\ + V V_0 \frac{1}{n} \sum_{i \in [n]} \frac{\frac{\partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \partial_r \partial_u \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i})}{1 + V \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i})}}{1 + V_0 \partial_u^2 \ell_{0,i}(\tilde{u}_{i,i})} + \lambda \mathfrak{X} + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

Taking an expectation,

$$ \Omega = \chi \mathbb{E} \left[ \frac{\partial_r^2 \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1})}{1 + V \partial_r^2 \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1})} \frac{1}{1 + V_0 \partial_u^2 \ell_{0,i}(\tilde{u}_{1,1})} \right] \\ + V V_0 \mathbb{E} \left[ \frac{\frac{\partial_r^2 \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1}) \partial_r \partial_u \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1})}{1 + V \partial_r^2 \ell_i(\tilde{r}_{1,1}, \tilde{u}_{1,1})}}{1 + V_0 \partial_u^2 \ell_{0,i}(\tilde{u}_{1,1})} \right] + \lambda \chi + O \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

One can verify that all functions appearing on the right-hand side are in the class $\mathcal{F}$. Thus, using Lemma D.3,

$$ \Omega - \chi \left( \lambda + \mathbb{E} \left[ \frac{\partial_r^2 \ell(r, u, g_3, c, \epsilon)}{(1 + V \partial_r^2 \ell(r, u, g_3, c, \epsilon))(1 + V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon))} \right] \right) \\ - V V_0 \mathbb{E} \left[ \frac{\partial_r^2 \ell(r, u, g_3, c, \epsilon) \partial_r \partial_u \ell(r, u, g_3, c, \epsilon)}{(1 + V \partial_r^2 \ell(r, u, g_3, c, \epsilon))(1 + V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon))} \right] \xrightarrow{n \to \infty} 0. $$

This completes the proof. □

## E.2 Test metrics

Having established a characterization of all summary statistics, we now detail how they can be used to access a characterization of test metrics, such as the generalization error.

**Lemma E.8.** Consider any test metric

$$ \mathcal{E}_{\text{gen}} = \mathbb{E}_{x,y,c,\epsilon} \left[ L \left( \langle \hat{w}, x \rangle, s, c, \epsilon \right) \right], \qquad (23) $$

where $L$ is $O(\text{polylog}(n))$-Lipschitz in its first variable, and $s, \epsilon \to L(0, s, c, \epsilon)$ admits a polynomial majorant with $O(1)$ degree and $O(\text{polylog}(n))$ coefficients. In (23), $(x, y, c, \epsilon)$ is a test sample from the same distribution as the training samples, and thus satisfies in particular Assumption A.4. Then $\mathcal{E}_{\text{gen}}$ converges in $L_1$ to

$$ \mathcal{E}_{\text{gen}} = \mathbb{E} [L(g_1, g_3, c, \epsilon)] + O_{L_1} \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right). $$

*Proof.* Let us introduce $\tilde{g} \sim \mathcal{N}(0_2, \tilde{\mathcal{S}})$, $\tilde{g} \sim \mathcal{N}(0_2, \tilde{\Phi})$, where

$$ \tilde{\mathcal{S}} = \begin{bmatrix} q & h \\ h & \varrho \end{bmatrix}, \qquad \tilde{\Phi} = \begin{bmatrix} q & \theta \\ \theta & \varrho \end{bmatrix}. $$

We will also need, for $c \in \mathcal{V}$,

$$ \tilde{\mathfrak{M}}_c = \begin{bmatrix} \mathfrak{m}_c \\ \nu_c \end{bmatrix}, \qquad \tilde{\Psi}_c = \begin{bmatrix} m_c \\ \nu_c \end{bmatrix}. $$
To ease notations, we will also denote $\varphi: \mathbb{R}^2 \times \mathcal{V} \times \mathcal{E} \to \mathbb{R}$, with

$$ \varphi(R, c, \epsilon) = L(R_1, R_2, c, \epsilon). $$

Note in particular $\mathbb{E}[\varphi(\tilde{\Psi}_c + \tilde{g}, c, \epsilon)] = \mathbb{E}[L(g_1, g_3, c, \epsilon)]$. We are now in a position to start the proof. We have

$$ \left| \mathcal{E}_{\text{gen}} - \mathbb{E}[L(g_1, g_3, c, \epsilon)] \right| = \left| \mathbb{E}[\varphi(\tilde{\mathfrak{M}}_c + \tilde{g}, c, \epsilon)] - \mathbb{E}[\varphi(\tilde{\Psi}_c + \tilde{g}, c, \epsilon)] \right|. $$

First notice that $\tilde{g}_2 \stackrel{d}{=} \tilde{g}_2 = g_\varrho$. Conditioning on this component, and using the Lipschitzness of $\varphi$ in its first variable, yields

$$ \begin{aligned} & \left| \mathbb{E}[\varphi(\tilde{\mathfrak{M}}_c + \tilde{g}, c, \epsilon)] - \mathbb{E}[\varphi(\tilde{\Psi}_c + \tilde{g}, c, \epsilon)] \right| \\ & \le \|L\|_{\text{Lip}} \mathbb{E}_{g_\varrho, \tilde{g}} \left[ \left| (\tilde{h} - \theta/\varrho)g_\varrho + \left(\sqrt{\tilde{q} - \tilde{h}^2/\varrho} - \sqrt{q - \theta^2/\varrho}\right) \tilde{g} \right| + \sup_c |\mathbf{m}_c - m_c| \right] \\ & \le \|L\|_{\text{Lip}} \mathbb{E}_{g_\varrho, \tilde{g}} \left[ \left| (\tilde{h} - \theta/\varrho)g_\varrho + \left(\sqrt{\tilde{q} - \tilde{h}^2/\varrho} - \sqrt{q - \theta^2/\varrho}\right) \tilde{g} \right|^2 \right]^{\frac{1}{2}} + \|L\|_{\text{Lip}} \sup_c |\mathbf{m}_c - m_c| \\ & \le \|L\|_{\text{Lip}} \left( \frac{(\tilde{h} - \theta)^2}{\varrho} + \left(\sqrt{\tilde{q} - \tilde{h}^2/\varrho} - \sqrt{q - \theta^2/\varrho}\right)^2 \right)^{\frac{1}{2}} + \|L\|_{\text{Lip}} \sup_c |\mathbf{m}_c - m_c| \\ & \le \|L\|_{\text{Lip}} \left( \frac{(\tilde{h} - \theta)^2}{\varrho} + \left| \tilde{q} - q - \frac{(\tilde{h} - \theta)(\tilde{h} + \theta)}{\varrho} \right| \right)^{\frac{1}{2}} + \|L\|_{\text{Lip}} \sup_c |\mathbf{m}_c - m_c| \end{aligned} $$

where $\tilde{g} \sim \mathcal{N}(0, 1)$. From Lemma C.4 and Lemma C.2,

$$ \frac{(\tilde{h} - \theta)^2}{\varrho} + |\tilde{q} - q| = O_{L_1} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

On the other hand, since $\tilde{h}, \theta \le \varrho \sqrt{\|\tilde{\tilde{e}}\|_\infty/\lambda}$ from Lemma F.3, Lemma C.2 guarantees the control

$$ |\tilde{h} - \theta|(\tilde{h} + \theta) = O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

Finally, from the concentration result of Lemma C.1,

$$ \sup_c |\mathbf{m}_c - m_c| = O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

Therefore,

$$ \left| \mathbb{E}[\varphi(\tilde{\mathfrak{M}} + \tilde{g}, c, \epsilon)] - \mathbb{E}[\varphi(\tilde{\Psi} + \tilde{g}, c, \epsilon)] \right| = O_{L_1} \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right) $$

This proves the Lemma.

<figure><img src="image_21.png" /></figure>

Putting all these results together finally yields Theorem 2.1.

<figure><img src="image_22.png" /></figure>
# F Auxiliary lemmas

This subsection regroups for ease of reading miscellaneous auxiliary lemmas that do not directly belong to the main body of the proof of Theorem 2.1.

## F.1 Concentration of empirical averages of first-stage predictions

The first result formalizes the intuition discussed in Section 3 in the main text that the number of acquired samples $n = 1/n \sum_{j \in [n]} \pi_j(u_j)$ selected by a policy $\pi$ concentrates in $L_2$, under some smoothness conditions on $\pi$.

**Lemma F.1.** For any function $\pi: \mathbb{R} \to \mathbb{R}_+$ such that $\pi$ is everywhere twice differentiable in its first argument, and with $\pi, \partial_u \pi, \partial_u^2 \pi$ are bounded as $O(\text{polylog}(n))$, the empirical average

$$ \mathbf{n} = \frac{1}{n} \sum_{j \in [n]} \pi_j(u_j) $$

concentrates, namely

$$ \mathrm{Var}[\mathbf{n}] = O\left(\frac{\mathrm{polylog}(n)}{n}\right). $$

*Proof.* From the Efron-Stein lemma,

$$ \begin{aligned} \mathrm{Var}[\mathbf{n}] &\le \sum_{i \in [n]} \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \in [n]} \pi_j(u_j) - \frac{1}{n} \sum_{j \ne i} \pi_j(u_{j, \setminus i}) \right)^2 \right] \\ &\le \frac{3}{n^2} \sum_{i \in [n]} \left[ \mathbb{E}[\pi_i(u_i)^2] + \mathbb{E} \left[ \left( \sum_{j \ne i} (\pi_j(\tilde{u}_{j,i}) - \pi_j(u_j)) \right)^2 \right] + \mathbb{E} \left[ \left( \sum_{j \ne i} (\pi_j(u_{j, \setminus i}) - \pi_j(\tilde{u}_{j,i})) \right)^2 \right] \right] \end{aligned} $$

By assumption, the first term is bounded as

$$ 3 \sum_{i \in [n]} \frac{1}{n^2} \mathbb{E} [\pi_i(u_i)^2] \le \frac{3 \|\pi\|_{\infty}}{n}. $$

We now turn to the second term.

$$ \left| \sum_{j \ne i} (\pi_j(\tilde{u}_{j,i}) - \pi_j(u_j)) \right| \le \|\partial_u \pi\|_{\infty} \|\tilde{u}_{,i} - u\|_1 \le \|\partial_u \pi\|_{\infty} \sqrt{n} \|\tilde{u}_{,i} - u\|_2 = O_{L_k} \left( \frac{\|\partial_u \pi\|_{\infty} \sqrt{n} \text{polylog}(n)}{\sqrt{n}} \right). $$

In the last line, we viewed $\tilde{u}_{,i} = (\tilde{u}_{j,i})_{j \ne i}$, $u = (u_j)_{j \ne i}$ as vectors in $\mathbb{R}^{n-1}$ and used Lemma B.2. Hence,

$$ \frac{3}{n^2} \sum_{i \in [n]} \mathbb{E} \left[ \left( \sum_{j \ne i} (\pi_j(\tilde{u}_{j,i}) - \pi_j(u_j)) \right)^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right). $$

We finally turn to the third term. From a Taylor expansion,

$$ \left( \sum_{j \ne i} (\pi_j(u_{j, \setminus i}) - \pi_j(\tilde{u}_{j,i})) \right)^2 \le 2 \left( \sum_{j \ne i} \partial_u \pi_j(u_{j, \setminus i}) (u_{j, \setminus i} - \tilde{u}_{j,i}) \right)^2 + \frac{1}{2} \left( \sum_{j \ne i} \partial_u^2 \pi_j(\tilde{u}_{j,i}) (u_{j, \setminus i} - \tilde{u}_{j,i})^2 \right)^2 $$
for some $\tilde{u}_{j,i} \in (u_{j,\setminus i}, \tilde{u}_{j,i})$. The last term is bounded as

$$ \frac{1}{2} \left( \sum_{j \neq i} \partial_u^2 \pi_j(\tilde{u}_{j,i}) (u_{j,\setminus i} - \tilde{u}_{j,i})^2 \right)^2 \leq \frac{\|\partial_u^2 \pi\|_{\infty}^2 \|\partial_u \ell_0\|_{\infty}^2}{2} \left( n \sup_{j \neq i} \left| \frac{x_j^\top H_{0,\setminus i} x_i}{n} \right|^2 \right)^2 . $$

Note that from Lemma C.4 in El Karoui [2018],

$$ \sup_{j \neq i} \left| \frac{x_j^\top H_{0,\setminus i} x_i}{n} \right| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

Thus,

$$ \frac{1}{2} \left( \sum_{j \neq i} \partial_u^2 \pi_j(\tilde{u}_{j,i}) (u_{j,\setminus i} - \tilde{u}_{j,i})^2 \right)^2 = O_{L_k}(\text{polylog}(n)). $$

Finally,

$$ \sum_{j \neq i} \partial_u \pi_j(u_{j,\setminus i})(u_{j,\setminus i} - \tilde{u}_{j,i}) = \left\langle \frac{1}{n} \sum_{j \neq i} \partial_u \pi_j(u_{j,\setminus i}) \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_j, x_i \right\rangle $$

Thus

$$ \mathbb{E} \left[ \left( \sum_{j \neq i} \partial_u \pi_j(u_{j,\setminus i})(u_{j,\setminus i} - \tilde{u}_{j,i}) \right)^2 \right] = \mathbb{E}_{\{x_j\}_{j \neq i}} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_u \pi_j(u_{j,\setminus i}) \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_j \right\|^2 \right] $$

Introducing $h \in \mathbb{R}^{n-1}$ with components $h_j = \partial_u \pi_j(u_{j,\setminus i}) \partial_u \ell_{0,i}(\tilde{u}_{i,i})$, and $X_{\setminus i} \in \mathbb{R}^{(n-1) \times d}$ the matrix with rows $\{x_j\}_{j \neq i}$, one can compactly rewrite the norm as

$$ \left\| \frac{1}{n} \sum_{j \neq i} \partial_u \pi_j(u_{j,\setminus i}) \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_j \right\| = \frac{1}{n} \left\| h^\top X_{\setminus i} H_{0,\setminus i}^{-1} \right\| \\ \leq \|\partial_u \pi\|_{\infty} \|\partial_u \ell_0\|_{\infty} \frac{1}{\lambda_0} \frac{\|X_{\setminus i}\|}{\sqrt{n}}. $$

Using Lemma F.4 and putting all these results together yields

$$ \mathbb{E} \left[ \left( \sum_{j \neq i} \partial_u \pi_j(u_{j,\setminus i})(u_{j,\setminus i} - \tilde{u}_{j,i}) \right)^2 \right] = O(\text{polylog}(n)) $$

and finally that

$$ \frac{3}{n^2} \sum_{i \in [n]} \mathbb{E} \left[ \left( \sum_{j \neq i} (\pi_j(u_{j,\setminus i}) - \pi_j(\tilde{u}_{j,i})) \right)^2 \right] = O \left( \frac{\text{polylog}(n)}{n} \right), $$

implying

$$ \text{Var}[\mathbf{n}] = O\left(\frac{\text{polylog}(n)}{n}\right), $$

concluding the proof.

<figure><img src="image_23.png" /></figure>
## F.2 Norm of estimators

**Lemma F.2 (Norm of the base estimators).** For any $k \in \mathbb{N}$, the norm of the estimators $\hat{w}_0, \hat{w}_{0,\setminus i}, \tilde{w}_{0,i}$ are bounded as

$$ \begin{aligned} \|\hat{w}_0\| &\le \sqrt{\frac{1}{\lambda_0} \|\tilde{\ell}_0\|_{\infty}}, \\ \sup_{i \in [n]} \|\hat{w}_{0,\setminus i}\| &\le \sqrt{\frac{1}{\lambda_0} \|\tilde{\ell}_0\|_{\infty}}, \\ \sup_{i \in [n]} \|\tilde{w}_{0,i}\| &= O_{L_k}(\text{polylog}(n)). \end{aligned} $$

*Proof.* From the definition of $\hat{w}_0$,

$$ \frac{\lambda_0}{2} \|\hat{w}_0\|^2 + \frac{1}{n} \sum_{j \in [n]} \ell_{0,j}(u_j) \le \hat{\mathcal{R}}_0(0_d) = \frac{1}{n} \sum_{j \in [n]} \ell_{0,j}(0). $$

Thus

$$ \|\hat{w}\|^2 \le \frac{1}{\lambda_0} \|\tilde{\ell}_0\|_{\infty}. $$

The same bound holds for $\sup_{i \in [n]} \|\hat{w}_{0,\setminus i}\|$, following the same reasoning. Finally

$$ \begin{aligned} \sup_{i \in [n]} \|\tilde{w}_{0,i}\| &\le \sup_{i \in [n]} \|\hat{w}_{0,\setminus i}\| + \sup_{i \in [n]} \left\| \frac{1}{n} \partial_u \ell_0(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_i \right\| \\ &\le \sqrt{\frac{1}{\lambda} \|\tilde{\ell}_0\|_{\infty}} + \|\partial_u \ell_0\|_{\infty} \frac{1}{\lambda_0 \sqrt{n}} \sup_{i \in [n]} \frac{\|x_i\|}{\sqrt{n}} = O_{L_k}(\text{polylog}(n)), \end{aligned} $$

using Lemma F.5. □

Establishing the equivalent Lemma for the reweighted estimators warrants a finer analysis.

**Lemma F.3 (Norm of the reweighted estimators).** The norm of the estimators $\hat{w}, \hat{w}_{\setminus i}, \tilde{w}_i$ are bounded as

$$ \begin{aligned} \|\hat{w}\| &\le \sqrt{\frac{1}{\lambda} \|\tilde{\ell}\|_{\infty}}, \\ \sup_{i \in [n]} \|\hat{w}_{\setminus i}\| &\le \sqrt{\frac{1}{\lambda} \|\tilde{\ell}\|_{\infty}}, \\ \sup_{i \in [n]} \|\tilde{w}_i\| &= O_{L_k}(\text{polylog}(n)). \end{aligned} $$

*Proof.* From the definition of $\hat{w}$,

$$ \frac{\lambda}{2} \|\hat{w}\|^2 + \frac{1}{n} \sum_{j \in [n]} \ell_j(r_j, u_j) \le \hat{\mathcal{R}}_0(0_d) = \frac{1}{n} \sum_{j \in [n]} \ell_j(0, u_j). $$

Thus

$$ \|\hat{w}\|^2 \le \frac{1}{\lambda} \frac{1}{n} \sum_{j \in [n]} |\ell_j(0, u_j)| \le \frac{1}{\lambda} \|\tilde{\ell}\|_{\infty}. $$

The bound on $\sup_{i \in [n]} \|\hat{w}_{\setminus i}\|$ follows identically. Finally

$$ \sup_{i \in [n]} \|\tilde{w}_i\| \le \sup_{i \in [n]} \|\hat{w}_{\setminus i}\| + \sup_{i \in [n]} \|\zeta_i\| + \sup_{i \in [n]} \|\eta_i\| = O_{L_k}(\text{polylog}(n)) $$

using Lemma B.6 to bound the second and third term. □
## F.3 Sample statistics

The following Lemmas describe properties of the data. While most of these results are very close to classical result, we state them here for the present setting for self-containedness. For simplicity, we state them for any random variables $z = x - \mu_c$ (see Assumption A.4) satisfying the tail bound

$$ \mathbb{P}(|\varphi(z) - \mathbb{E}[\varphi(z)]| > t) \le C_n e^{-c_n t^2} $$

for any convex $1$-Lipschitz function $\varphi$ and any $t > 0$, with $C_n < C, 1/c_n = O(\text{polylog}(n))$, where $C$ is an absolute constant. In the main proof, we apply those results in the Gaussian case of $z \sim \mathcal{N}(0, I_d)$, with $C_n = 2, c_n = 1/2$.

**Lemma F.4 (Operator norm of the empirical covariance).** Let $\hat{\Sigma} = \frac{X^\top X}{n}$ be the empirical covariance matrix.

Then

$$ \|\hat{\Sigma}\| \le O_{L_k} \left( \frac{\text{polylog}(n)}{c_n} \right). $$

and

$$ \frac{\|X\|}{\sqrt{n}} \le O_{L_k} \left( \frac{\text{polylog}(n)}{c_n} \right). $$

The same bounds hold for the leave-one-row-out matrix $X_{\setminus i}$.

*Proof.* Let $P \in \mathbb{R}^{n \times d}$ be the matrix with rows $\{\mu_{c_i}\}_{i \in [n]}$. Then $\|X\| = \|P + Z\|$, decomposing the samples into their mean plus random part. Then

$$ \|X\| \le \|P\|_F + \sqrt{\|Z^\top Z\|} \le \sqrt{n} M + \sqrt{O_{L_k}\left(\frac{npolylog(n)}{c_n}\right)} = \sqrt{n} O_{L_k}\left(\frac{polylog(n)}{c_n}\right). $$

We used Lemma G.1 of El Karoui [2018] to bound the operator norm of the empirical covariance. $\square$

**Lemma F.5 (Norm of the samples).** One can control the sample norms as

$$ \sup_{i \in [n]} \frac{\|x_i\|}{\sqrt{n}} = O_{L_k}(\text{polylog}(n)). $$

Furthermore,

$$ \sup_{i \in [n]} \frac{\|X_{\setminus i}\|}{\sqrt{n}} = O_{L_k}(\text{polylog}(n)) $$

*Proof.* The lemma follows from a very minor adaptation of El Karoui [2018] for data with non-zero mean.

$$ \sup_{i \in [n]} \frac{\|x_i\|}{\sqrt{n}} \le \frac{M}{\sqrt{n}} + \sup_{i \in [n]} \frac{\|z_i\|}{\sqrt{n}} = \frac{M}{\sqrt{n}} + O_{L_k}(\text{polylog}(n)). $$

The last steps follows from El Karoui [2018]. It remains to control the norm $\sup_{i \in [n]} \|X_{\setminus i}\|/\sqrt{n}$. Note that

$$ \sup_{i \in [n]} \frac{\|X_{\setminus i}\|}{\sqrt{n}} = \sqrt{\sup_{i \in [n]} \|\hat{\Sigma}_{\setminus i}\|} = \sqrt{\sup_{i \in [n]} \left\| \hat{\Sigma} - \frac{x_i x_i^\top}{n} \right\|} \le \sqrt{\|\hat{\Sigma}\| + \left( \sup_{i \in [n]} \frac{\|x_i\|}{\sqrt{n}} \right)^2}. $$

The control of the two terms follow from Lemma F.4 and the first point. $\square$
**Lemma F.6. (Quadratic forms)** Let $M_{\setminus i} \in \mathbb{R}^{d \times d}$ be a matrix which does not depend on $x_i$, but generically depends on all other samples. Then for any $k \in [\lceil 4 \log(n) \rceil]$,

$$ \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{n} \langle x_j, M_{\setminus i} x_i \rangle \right| = O_{L_k} \left( \frac{\sup_{i \in [n]} \| M_{\setminus i} \|_{\text{polylog}(n)}}{\sqrt{n}} \right). $$

*Proof.* We first decompose

$$ \begin{aligned} \left| \frac{1}{n} \langle x_j, M_{\setminus i} x_i \rangle \right| & \le \left| \frac{1}{n} \langle \mu_{c_j}, M_{\setminus i} \mu_{c_i} \rangle \right| + \left| \frac{1}{n} \langle \mu_{c_j}, M_{\setminus i} z_i \rangle \right| + \left| \frac{1}{n} \langle z_j, M_{\setminus i} \mu_{c_i} \rangle \right| + \left| \frac{1}{n} \langle z_j, M_{\setminus i} z_i \rangle \right| \\ & \le \frac{1}{n} M^2 \| M_{\setminus i} \| + 2M \| M_{\setminus i} \| O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) + \left| \frac{1}{n} \langle z_j, M_{\setminus i} z_i \rangle \right|, \end{aligned} $$

using Lemma F.5. It thus suffices to control the last term. Introduce

$$ L = \sup_{j \in [n]} \frac{\sup_{i \in [n]} \| M_{\setminus i} \|_{\| z_j \|}}{\sqrt{n}}. $$

Observe that from a union bound

$$ \mathbb{P} \left[ \frac{1}{L} \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{\sqrt{n}} \langle z_j, M_{\setminus i} z_i \rangle \right| > t \right] \le 1 \wedge \sum_{i \in [n]} \sum_{j \neq i} \mathbb{P} \left[ \frac{1}{L} \left| \frac{1}{n} \langle z_j, M_{\setminus i} z_i \rangle \right| > t \right] $$

Thus for any $u > 0$, $k \in \mathbb{N}$ satisfying $k \le 4 \log(n) + 1$, it follows that

$$ \begin{aligned} \mathbb{E} \left[ \left( \frac{1}{L} \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{\sqrt{n}} \langle z_j, M_{\setminus i} z_i \rangle \right| \right)^k \right] & \le u^k + \sum_{i \in [n]} \sum_{j \neq i} \int_u^\infty kt^{k-1} \mathbb{P} \left[ \left| \frac{1}{L} \frac{1}{\sqrt{n}} \langle z_j, M_{\setminus i} z_i \rangle \right| > t \right] \\ & \le u^k + n(n-1)C_n \int_u^\infty kt^{k-1} e^{-c_n t^2}, \end{aligned} $$

using the fact that $\varphi: z_i \to 1/L\sqrt{n} \langle z_j, M_{\setminus i} z_i \rangle$ is 1-Lipschitz with $\mathbb{E}[\varphi(x_i)] = 0$, and using Assumption A.4. Note the identity

$$ \int_u^\infty kt^{k-1} e^{-c_n t^2} \le \frac{1}{2c_n} u^{k-2} e^{-c_n u^2} + \frac{k-2}{2c_n u^2} \int_u^\infty kt^{k-1} e^{-c_n t^2}, $$

which follows from an integration by parts. Thus for any $u > \sqrt{k-2/2c_n}$,

$$ \mathbb{E} \left[ \left( \frac{1}{L} \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{\sqrt{n}} \langle z_j, M_{\setminus i} z_i \rangle \right| \right)^k \right] \le u^k + \frac{kn(n-1)C_n}{1 - \frac{k-2}{2c_n u^2}} \frac{1}{2c_n} u^{k-2} e^{-c_n u^2}. $$

Choosing $u = \sqrt{\log(n^2)/c_n}$, which satisfies the condition $u > \sqrt{k-2/2c_n}$ by assumption on $k$,

$$ \begin{aligned} \mathbb{E} \left[ \left( \frac{1}{L} \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{\sqrt{n}} \langle z_j, M_{\setminus i} z_i \rangle \right| \right)^k \right] & \le \left( \frac{\log(n^2)}{c_n} \right)^{\frac{k}{2}} \left[ 1 + \frac{kC_n}{2\log(n^2) - k + 2} \right] \\ & \le \left( \frac{\log(n^2)}{c_n} \right)^{\frac{k}{2}} \left[ 1 + 4C \log(n) \right] \\ & \le \left( \frac{\log(n^2)(1 + 4C \log(n))^2}{c_n} \right)^{\frac{k}{2}} \end{aligned} $$
Thus for any $k \in [[4 \log(n)]]$

$$ \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{n} \langle z_j, M_{\setminus i} z_i \rangle \right| = \mathrm{LO}_{L_k} (\mathrm{polylog}(n)) = \sup_{i \in [n]} \left\| M_{\setminus i} \right\| \mathrm{O}_{L_k} \left( \frac{\mathrm{polylog}(n)}{\sqrt{n}} \right). \quad \square $$

**Lemma F.7 (Sup of one-dimensional projections).** Le $v_{\setminus i}$ be vectors that do not depend on $x_i$, but can generically depend on all other samples. Then for any $k \in [[2 \log(n)]]$,

$$ \sup_{i \in [n]} |\langle v_{\setminus i}, x_i \rangle| = O_{L_k} \left( \sup_{i \in [n]} \|v_{\setminus i}\| \sqrt{\frac{\mathrm{polylog}(n)}{c_n}} \right). $$

*Proof.* Since

$$ \sup_{i \in [n]} |\langle v_{\setminus i}, x_i \rangle| \le M \sup_{i \in [n]} \|v_{\setminus i}\| + \sup_{i \in [n]} |\langle v_{\setminus i}, z_i \rangle|, $$

it is sufficient to bound $\sup_{i \in [n]} |\langle v_{\setminus i}, z_i \rangle|$. We start from the union bound, for any $u > \sqrt{k-2/2c_n}$,

$$ \begin{aligned} \mathbb{E} \left[ \left( \frac{\sup_{i \in [n]} |\langle v_{\setminus i}, z_i \rangle|}{\sup_{i \in [n]} \|v_{\setminus i}\|} \right)^k \right] &\le u^k + n \int_u^\infty k t^{k-1} C_n e^{-c_n t^2} \\ &\le u^k + \frac{knC_n}{1 - \frac{k-2}{2c_n u^2}} \frac{1}{2c_n} u^{k-2} e^{-c_n u^2}. \end{aligned} $$

We choose $u = \sqrt{\log(n)/c_n}$, which satisfies the condition $u > \sqrt{k-2/2c_n}$ by assumption on $k$. Then,

$$ \begin{aligned} \mathbb{E} \left[ \left( \frac{\sup_{i \in [n]} |\langle v_{\setminus i}, z_i \rangle|}{\sup_{i \in [n]} \|v_{\setminus i}\|} \right)^k \right] &\le \left( \frac{\log(n)}{c_n} \right)^{\frac{k}{2}} \left[ 1 + \frac{kC_n}{2\log(n) - k + 1} \right] \\ &\le \left( \frac{\log(n)}{c_n} \right)^{\frac{k}{2}} \left[ 1 + 2C \log(n) \right] \le \left( \frac{\log(n)(1 + 2C \log(n))^2}{c_n} \right)^{\frac{k}{2}}, \end{aligned} $$

which completes the proof. □
<figure><img src="image_24.png" /><figcaption>Figure 5: Test error, as a function of the normalized number of samples $\alpha = n/d$, of a logistic classifier ($\tilde{\ell}(y, z) = \log(1 + e^{-yz})$, $\lambda = 0.01$) trained on a subset $S \subset [n]$ pruned using a large-margin selection policy $\pi(u) = \mathbb{1}_{|u|>\kappa^+}$. The base estimator was trained on the whole dataset ($S_0 = [n]$), also with $\tilde{\ell}(y, z) = \log(1 + e^{-yz})$, $\lambda = 0.01$. The data is a binary isotropic Gaussian mixture with centroid norm $\|\mu\| = 0.8$. Different curves represent different thresholds $\kappa^+$, with higher values implying smaller training subsets $|S|$. Solid lines: theoretical predictions of Theorem 2.1. Dots: numerical experiments in dimension $d = 2000$. Error bars represent one standard deviation over 30 trials.</figcaption></figure>

## G Comments on data pruning

In this Appendix, we depart from the active learning framework of Section 3, in order to connect with and revisit some observations of related prior works Sorscher et al. [2022], Kolossov et al. [2023], Askari-Hemmat et al. [2025] regarding data pruning. In this section only, we assume all labels are available, and the base classifier is trained on the whole dataset, namely $S_0 = [n]$, then used to construct a final and smaller training set $S \subset [n]$ through a policy $\pi$. Several of the above works report settings in which training a model on a smaller subset $S \subset [n]$ can yield better accuracy than training on the full dataset. These conclusions hold in some cases even accounting for the data used in the held-out dataset. We show through two examples that these observations can also be made in the more realistic setting where the base classifier is trained on the whole dataset, then used to prune it, namely with data re-use, leveraging Theorem 2.1.

**Example 1** — Fig. 5 illustrates the test error achieved by logistic regression trained on a binary Gaussian mixture classification task with only a subset of the full training set, keeping only larger margin samples using a policy $\pi(u) = \mathbb{1}_{|u|>\kappa^+}$. Interestingly, strategies with $\kappa^+ > 0$ can outperform the model trained on the full dataset (red), despite using less data. Intuitively, large margin samples contain clear information on the centroid of the mixture, affording the model an easy grasp on the data structure. This observation echoes closely related findings in Sorscher et al. [2022], Kolossov et al. [2023], Hacohen et al. [2022] for a different task.

**Example 2** — Fig. 6 also illustrate a binary Gaussian mixture classification task with logistic regression. The labels $c_i = \pm 1$, indicating the cluster membership, were corrupted by a flipping noise $\epsilon_i = \pm 1$ with probability $P(\epsilon = -1) = 0.2$, complicating the task. Directly fitting a classifier on the whole dataset yields mediocre accuracy (red). In order to mitigate the effect of the noise, it is possible to leverage a data pruning strategy as a mean of regularization: a base estimator is trained on the whole dataset, and the samples it incorrectly classifies are discarded. This selection process is motivated by the intuition that a large fraction of misclassified samples are, in fact, flipped. The final classifier is trained on the resulting pruned subset $S$ (blue), and displays improved accuracy. This observation was also made by Feng et al. [2024] in a simpler setting.

It is seminal to nuance that all these observations, and those reported in prior works Sorscher et al. [2022],
<figure><img src="image_25.png" /><figcaption>Figure 6: Test error of a logistic classifier ($\tilde{\ell}(y, z) = \log(1 + e^{-yz}), \lambda = 0.01$) trained on a subset $S$ constructed with a base estimator with the same loss and regularization, trained on the whole dataset ($S_0 = [n]$), as a function of the normalized number of samples $\alpha = n/d$. The data is a binary isotropic Gaussian mixture centered at $\pm\mu$, with centroid norm $\|\mu\| = 0.8$, and class labels $c_i \in -1, +1$. The labels are corrupted by a random flipping noise $\epsilon \in \{-1, +1\}$, which with $P(\epsilon = -1) = 0.2$, as $y_i = \epsilon_i c_i$. The selection policy $\pi(u, c, \epsilon) = \mathbb{1}_{\text{sign}(u)=c\epsilon}$ only retains samples correctly classified by the base estimator. Solid lines: theoretical predictions of Theorem 2.1. The green line represents the test error of a oracle classifier trained only on samples whose labels were not flipped. Dots: numerical experiments in dimension $d = 2000$. Error bars represent one standard deviation over 30 trials.</figcaption></figure>

Kolossov et al. [2023], Feng et al. [2024], Dohmatob et al. [2025], have been made for a fixed model choice $\tilde{\ell}$, $\lambda$. A precise study of whether and when these phenomena still hold true when for instance the regularization $\lambda$ is optimized over is still very largely missing, and an important direction for future investigations.