# Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning

Hugo Cui, Yue M. Lu

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

## To cite this version:

Hugo Cui, Yue M. Lu. Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning. 2026. hal-05488707

HAL Id: hal-05488707

https://hal.science/hal-05488707v1

Preprint submitted on 2 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Asymptotic Theory of Iterated Empirical Risk Minimization, with Applications to Active Learning

Hugo Cui¹ and Yue M. Lu²

¹Université Paris-Saclay, CNRS, Laboratoire de mathématiques d'Orsay, 91405, Orsay, France

²Applied Mathematics, Harvard John A. Paulson School of Engineering and Applied Sciences

## Abstract

We study a class of iterated empirical risk minimization (ERM) procedures in which two successive ERMs are performed on the same dataset, and the predictions of the first estimator enter as an argument in the loss function of the second. This setting, which arises naturally in active learning and reweighting schemes, introduces intricate statistical dependencies across samples and fundamentally distinguishes the problem from classical single-stage ERM analyses. For linear models trained with a broad class of convex losses on Gaussian mixture data, we derive a sharp asymptotic characterization of the test error in the high-dimensional regime where the sample size and ambient dimension scale proportionally. Our results provide explicit, fully asymptotic predictions for the performance of the second-stage estimator despite the reuse of data and the presence of prediction-dependent losses. We apply this theory to revisit a well-studied pool-based active learning problem, removing oracle and sample-splitting assumptions made in prior work. We uncover a fundamental tradeoff in how the labeling budget should be allocated across stages, and demonstrate a double-descent behavior of the test error driven purely by data selection, rather than model size or sample count.

## Contents

<table><tr><td>1 Introduction</td><td>2</td></tr><tr><td>2 High-dimensional asymptotics of iterated ERMs</td><td>4</td></tr><tr><td>2.1 Setting</td><td>5</td></tr><tr><td>2.2 Precise asymptotics in high dimensions</td><td>5</td></tr><tr><td>2.3 Special cases</td><td>7</td></tr><tr><td>3 Applications to active learning</td><td>8</td></tr><tr><td>3.1 Setting</td><td>8</td></tr><tr><td>3.2 Related works in active learning</td><td>9</td></tr><tr><td>3.3 Tradeoff in budget allocation</td><td>10</td></tr><tr><td>3.4 On the selection policy</td><td>12</td></tr><tr><td>3.5 Data pruning</td><td>14</td></tr><tr><td>4 Conclusions</td><td>14</td></tr></table>
<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>A Notations and assumptions</td><td>19</td></tr><tr><td>A.1 First-stage ERM</td><td>20</td></tr><tr><td>A.2 Second-stage ERM</td><td>21</td></tr><tr><td>B Leave-one-out approximation results</td><td>22</td></tr><tr><td>B.1 First-stage estimator</td><td>22</td></tr><tr><td>B.2 Second-stage estimator</td><td>23</td></tr><tr><td>C Concentration of the summary statistics</td><td>28</td></tr><tr><td>D Distribution of the residuals</td><td>44</td></tr><tr><td>D.1 Leave-one-out residuals</td><td>44</td></tr><tr><td>D.2 Surrogate residuals</td><td>48</td></tr><tr><td>E Proof of Theorem 2.1</td><td>55</td></tr><tr><td>E.1 Deterministic equivalents</td><td>55</td></tr><tr><td>E.2 Test metrics</td><td>63</td></tr><tr><td>F Auxiliary lemmas</td><td>65</td></tr><tr><td>F.1 Concentration of empirical averages of first-stage predictions</td><td>65</td></tr><tr><td>F.2 Norm of estimators</td><td>67</td></tr><tr><td>F.3 Sample statistics</td><td>68</td></tr><tr><td>G Comments on data pruning</td><td>71</td></tr></tbody></table>

# 1 Introduction

Let {$x_i, y_i$}$_{i \in [n]}$ be a dataset composed of $n$ data samples $x_i$ in $d$ dimensions, together with the associated labels $y_i$. We consider the problem of two successive Empirical Risk Minimizations (ERMs) performed on the same dataset, where the predictions $\langle \hat{w}_0, x_i \rangle$ of a first ERM estimator

$$ \hat{w}_0 = \arg \min_w \frac{1}{n} \sum_{i=1}^{n} \ell_0(\langle w, x_i \rangle, y_i) + \frac{\lambda_0}{2} \|w\|^2 \quad (1) $$

enter as an argument in the loss function of the second ERM:

$$ \hat{w} = \arg \min_w \frac{1}{n} \sum_{i=1}^{n} \ell(\langle w, x_i \rangle, \langle \hat{w}_0, x_i \rangle, y_i) + \frac{\lambda}{2} \|w\|^2. \quad (2) $$

Such iterated ERMs (and their multi-step generalizations) arise naturally across a wide range of important machine learning applications:

* Many classical optimization algorithms, such as Newton's method or the proximal point method [Rockafellar, 1976], can be framed as a sequence of ERMs, whose risk explicitly involves the predictions of the previous iterate.

* In the first step of an AdaBoost iteration [Freund and Schapire, 1997], samples for which the predictions of the first learner are incorrect are upweighted. The following learner is then trained on the sample-reweighted risk.
* In uncertainty-based active learning [Tong and Koller, 2001, Roth and Small, 2006, Wang and Shang, 2014], an estimator is iteratively trained on growing subsets of the dataset, with the predictions of each estimator leveraged to select additional samples to include in the training set of the following estimator.

Despite its ubiquity, this class of iterated ERMs has not yet been the subject of a thorough theoretical treatment. While the properties of the first-stage estimator $\hat{w}_0$ in (1) are by now well understood in the high-dimensional regime $n \asymp d$ [Karoui, 2013, Donoho and Montanari, 2016, Thrampoulidis et al., 2018], the analysis of the second ERM iteration (2) poses qualitatively new challenges.

A central difficulty stems from the explicit appearance of the first estimator $\hat{w}_0$ inside the loss function of the second ERM (2). This dependence induces intricate correlations between each single-sample loss term $\ell(\langle w, x_j \rangle, \langle \hat{w}_0, x_j \rangle, y_j)$ and the entire dataset $\{x_i, y_i\}_{i \in [n]}$ through the definition of $\hat{w}_0$ in (1). As a result, characterizing the statistical properties of the final estimator $\hat{w}$ requires carefully unraveling and controlling these dependencies. Most existing theoretical works on iterated ERMs instead focus on the sample-splitting (or online) setting, where each ERM is trained on a fresh, independent batch of data [Chandrasekher et al., 2024, Cyffers et al., 2025, Lou et al., 2025, Kaushik et al., 2024].

The challenge of data re-use has been partially addressed in recent theoretical analyses, motivated in part by a stream of works in the statistical physics literature [Saglietti and Zdeborová, 2022, Takahashi, 2022, Takanami et al., 2025, Okajima and Takahashi, 2025] that rely on the non-rigorous replica and Franz-Parisi methods [Franz and Parisi, 1997]. On the rigorous front, [Garg et al., 2025] study iterated ERMs in the specific case of the square loss, exploiting the fact that the corresponding ERM estimators admit closed-form solutions and can be analyzed using tools from random matrix theory. More recently, [Celentano et al., 2025] establish a state-evolution description for a broad class of iterated min-max optimization problems under unimodal isotropic Gaussian data, extending the Gaussian min-max theorem [Gordon, 1985, Thrampoulidis et al., 2018] to the sequential setting. While their framework is, in principle, sufficiently general to encompass the iterated ERM setting considered here, it does not provide explicit, fully asymptotic characterizations of estimator performance in terms of a finite set of scalar order parameters.

**Our main technical contribution** is the following: we establish a sharp and fully asymptotic characterization of the test error of the second-stage estimator for Gaussian mixture data and a broad class of convex loss functions in the high-dimensional regime $n \asymp d$. In contrast to existing rigorous analyses of iterated ERMs, which either focus on quadratic losses or do not yield explicit asymptotic predictions, our results provide asymptotic characterizations in terms of a finite set of scalar order parameters. The proof relies on a new approach based on nested applications of the *leave-one-out technique* [Karoui, 2013], and may be of independent technical interest.

**Instantiation for active learning** — The asymptotic characterization developed above finds a natural and important application in *active learning*. In particular, it allows us to revisit a well-studied problem in pool-based data selection and to remove oracle assumptions that are pervasive in prior analyses. Given $n$ unlabeled data samples $\{x_i\}_{i \in [n]}$, practical constraints often limit labeling to only a fraction $\gamma \in (0, 1)$ of the data, yielding a training set of size $\gamma n$. This setting arises, for instance, in medical applications [Liu, 2004], where labeling is expensive [Roh et al., 2019]. A classical strategy for selecting such a subset relies on training a preliminary base classifier and using its predictions to identify informative samples, most commonly those lying close to the decision boundary. A now sizable body of recent work [Kolossov et al., 2023, Sorscher et al., 2022, Askari-Hemmat et al., 2025, Feng et al., 2024, Dohmatob et al., 2025] has analyzed this approach in the high-dimensional regime $n \asymp d$.

However, these analyses typically rely on a crucial simplification: the base classifier is assumed to be either an oracle or trained on a separate held-out dataset at zero labeling cost. This assumption is restrictive in
several important respects. In realistic budget-constrained settings, any data used to train the base classifier must be taken from the same unlabeled pool and deducted from the labeling budget. Moreover, existing works generally discard the base training set when fitting the final classifier, thereby squandering already labeled samples. As a result, these analyses are partially oracle in nature and do not fully capture the tradeoffs inherent to budget-limited data acquisition.

Our results lift these limitations and enable a principled treatment of the fully budget-constrained setting. Given a budget $\gamma \in (0, 1)$, a fraction $\psi \in (0, \gamma)$ of the samples is first allocated to train a base classifier, whose predictions are then used to select the remaining $(\gamma - \psi)n$ samples within the budget constraint $\gamma n$. The final classifier is trained on all $\gamma n$ selected and labeled samples, allowing the initial training set of $\psi n$ samples to be fully or partially re-used. We find that this refined analysis unveils several novel phenomena of interest.

Our main findings are:

* **Budget-allocation tradeoff.** In the case of separable data and margin-based selection [Kolossov et al., 2023, Sorscher et al., 2022], the analysis reveals that the test error exhibits a non-monotonic dependence on the fraction of data $\psi$ allocated to training the base classifier, for a fixed total budget $\gamma$. In particular, there exists an optimal allocation $\psi^*$ for which the test error is minimized. This behavior reflects a fundamental tradeoff between allocating sufficiently many samples $\psi$ to obtain an accurate base classifier that can guide informative sample selection, and preserving a sufficient remaining budget $\gamma - \psi$ to label and include such informative samples in the final training set.

* **Real-data validation.** We illustrate that this tradeoff is not merely a theoretical artifact by demonstrating it on real datasets, using pneumonia diagnosis from chest X-rays as a representative example [Kermany et al., 2018].

* **Selection-driven double-descent.** We further observe a double-descent behavior of the test error as a function of $\psi$. In contrast to classical double-descent phenomena studied in prior work [Belkin et al., 2019, Geiger et al., 2020, Nakkiran, 2019], this effect arises at fixed model capacity and fixed total sample size $\gamma n$, and is driven purely by changes in the composition of the selected training set.

The rest of the manuscript is organized as follows. Section 2 presents our main technical result, namely a sharp and rigorous asymptotic characterization of the test error of the final estimator $\hat{w}$ in the two-stage iterated ERM (2), in the high-dimensional limit $n \asymp d$. In Section 3, we instantiate this result in the context of margin-based data selection for active binary classification [Kolossov et al., 2023, Sorscher et al., 2022, Askari-Hemmat et al., 2025, Feng et al., 2024, Dohmatob et al., 2025]. In particular, our framework allows us to lift oracle and sample-splitting assumptions made in prior work, enabling a principled study of the fully budget-constrained setting. Subsections 3.3 and 3.4 explore the implications of our results in this setting.

# 2 High-dimensional asymptotics of iterated ERMs

In this section, we present the main technical result of the manuscript, namely a sharp asymptotic characterization of the estimator $\hat{w}$ obtained from a two-stage iterated ERM in the high-dimensional regime $n \asymp d$. We begin by precisely defining the class of problems covered by our analysis.
## 2.1 Setting

**Data distribution** — We consider a collection of $n$ identically and independently distributed covariate–label pairs $\{(x_i, y_i)\}_{i \in [n]}$, where the labels take the form

$$y_i = \phi(\langle \beta, x_i \rangle, c_i, \epsilon_i),$$

for a given link function $\phi$ and a vector $\beta \in \mathbb{R}^d$. The variables $c_i$ and $\epsilon_i$ respectively denote the class label of sample $x_i$ and a stochastic noise term. The class labels $\{c_i\}_{i \in [n]}$ are drawn i.i.d. from an arbitrary probability measure on a finite set $\mathcal{V}$.

To each class $c \in \mathcal{V}$, we associate a vector $\mu_c \in \mathbb{R}^d$, and conditionally on $c_i$, the covariates are sampled as $x_i \sim N(\mu_{c_i}, I_d)$. The latent variables $c_i$ thus induce a random partition of the dataset into $|\mathcal{V}|$ classes. These classes may, for instance, correspond to mixture components in Gaussian mixture models, in which case the vectors $\mu_c$ represent cluster centroids, and may also encode which samples are used in the first ERM, the second ERM, or both. Finally, let $\{\epsilon_i\}_{i \in [n]}$ be a collection of i.i.d. random variables capturing possible noise in the problem, and assume that all moments of $\epsilon_i$ are finite. We further assume that there exist deterministic quantities $\nu \in \mathbb{R}^{|\mathcal{V}|}$, $\rho \in \mathbb{R}^{|\mathcal{V}| \times |\mathcal{V}|}$, and $\varrho \in \mathbb{R}_+$ such that the inner products

$$\langle \beta, \mu_c \rangle = \nu_c, \qquad \langle \mu_c, \mu_{c'} \rangle = \rho_{cc'}, \qquad \|\beta\|^2 = \varrho$$

are fixed for all $d$ as the limit $n, d \to \infty$ is taken.

**Iterated ERMs** — Given $\{x_i, c_i, \epsilon_i\}_{i \in [n]}$, we consider the following two successive ERM problems. In the first stage, we train a base estimator $\hat{w}_0$ defined as $\hat{w}_0 = \arg \min_{w \in \mathbb{R}^d} \hat{\mathcal{R}}_0(w)$, where the empirical risk is given by

$$\hat{\mathcal{R}}_0(w) = \frac{1}{n} \sum_{i \in [n]} \ell_0(\langle w, x_i \rangle, \langle \beta, x_i \rangle, c_i, \epsilon_i) + \frac{\lambda_0}{2} \|w\|^2. \quad (3)$$

The loss function $\ell_0: \mathbb{R}^2 \times \mathcal{V} \times \mathbb{R} \to \mathbb{R}_+$ is assumed to be convex and four times differentiable in its first argument, with derivatives bounded by $O(\text{polylog}(d))$. In the second stage, the final estimator is obtained as $\hat{w} = \arg \min_{w \in \mathbb{R}^d} \hat{\mathcal{R}}(w)$, with empirical risk

$$\hat{\mathcal{R}}(w) = \frac{1}{n} \sum_{i \in [n]} \ell(\langle w, x_i \rangle, \langle \hat{w}_0, x_i \rangle, \langle \beta, x_i \rangle, c_i, \epsilon_i) + \frac{\lambda}{2} \|w\|^2. \quad (4)$$

Here, the loss $\ell: \mathbb{R}^3 \times \mathcal{V} \times \mathbb{R} \to \mathbb{R}_+$ is convex in its first argument and admits derivatives up to order four in its first two arguments, with all such derivatives bounded by $O(\text{polylog}(d))$. We refer the interested reader to Appendix A for a detailed list of technical assumptions, of which we only highlight the main ones here.

## 2.2 Precise asymptotics in high dimensions

The principal difficulty of the problem lies in the explicit dependence of the second-stage loss on the base prediction term $\langle \hat{w}_0, x_i \rangle$, which induces nontrivial correlations between each individual loss term in $\hat{\mathcal{R}}(w)$ and the entire dataset $\{x_j\}_{j \in [n]}$ through the estimator $\hat{w}_0$ trained in (3). Our main theorem characterizes test metrics associated with the second-stage estimator $\hat{w}$.

**Theorem 2.1.** Consider any test metric

$$\mathcal{E}_{\text{gen}} = \mathbb{E}_{x,c,\epsilon} \left[ L \left( \langle \hat{w}, x \rangle, \langle \beta, x \rangle, c, \epsilon \right) \right], \quad (5)$$
where L is O(polylog(n))-Lipschitz in its first variable, and there exists a polynomial $Q_L$ of O(1) degree with O(polylog(n)) coefficients such that $\forall s, c, \epsilon$, $|L(0, s, c, \epsilon)| \le |Q_L(s, \epsilon)|$. As $n, d \to \infty$ with $\alpha = n/d = \Theta_d(1)$, the test metric $\mathcal{E}_{\text{gen}}$ converges in $L_1$ to

$$ \mathcal{E}_{\text{gen}} = \mathbb{E}[L(g_1, g_3, c, \epsilon)] + \tilde{O}_{L_1}(n^{-1/4}), $$

where the $\tilde{O}$ notation hides polylog(n) factors. Here, $g_1$ and $g_3$ are components of a $(3 + |V|)$-dimensional Gaussian random vector $g \sim \mathcal{N}(\Psi_c, \Phi)$, with mean and covariance

$$ \Psi_c = \begin{bmatrix} m_c \\ m_{0,c} \\ \nu_c \\ \rho_c \end{bmatrix}, \qquad \Phi = \begin{bmatrix} q & t & \theta & m \\ t & q_0 & \theta_0 & m_0 \\ \theta & \theta_0 & \varrho & \nu \\ m & m_0 & \nu & \rho \end{bmatrix}, $$

conditionally on c. The summary statistics $q, t, \theta, m, m_0, q_0, \theta_0$ verify the self-consistent equations

$$ \begin{aligned} \theta &= -1/\lambda \mathbb{E} [\partial_r \ell(r, u, g_3, c, \epsilon) g_3] + \tilde{O}(n^{-1/4}), \\ q &= -1/\lambda \mathbb{E} [\partial_r \ell(r, u, g_3, c, \epsilon) r] + \tilde{O}(n^{-1/4}), \\ t &= -1/\lambda \mathbb{E} [\partial_r \ell(r, u, g_3, c, \epsilon) u] + \tilde{O}(n^{-1/4}), \\ m_c &= -1/\lambda \mathbb{E} [\partial_r \ell(r, u, g_3, c, \epsilon) g_c] + \tilde{O}(n^{-1/4}), \end{aligned} $$

and

$$ \begin{aligned} \theta_0 &= -1/\lambda_0 \mathbb{E} [\partial_u \ell_0(u, g_3, c, \epsilon) g_3] + \tilde{O}(n^{-1/4}), \\ q_0 &= -1/\lambda_0 \mathbb{E} [\partial_u \ell_0(u, g_3, c, \epsilon) u] + \tilde{O}(n^{-1/4}), \\ m_{0,c} &= -1/\lambda_0 \mathbb{E} [\partial_u \ell_0(u, g_3, c, \epsilon) g_c] + \tilde{O}(n^{-1/4}). \end{aligned} $$

We defined the random variables

$$ \begin{aligned} r &= \text{prox}_{V\ell(\cdot, u, g_3, c, \epsilon)} (g_1 + \chi \partial_u \ell_0(u, g_3, c, \epsilon)), && (6) \\ u &= \text{prox}_{V_0\ell_0(\cdot, g_3, c, \epsilon)}(g_2), \end{aligned} $$

and introduced the auxiliary statistics $V, V_0, \chi$ that satisfy

$$ \begin{aligned} \frac{1}{\frac{n}{d}V} &= \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 + \tilde{O}(n^{-1/4}), \\ \frac{1}{\frac{n}{d}V_0} &= \mathbb{E} \left[ \frac{\partial_u^2 \ell_0(u, g_3, c, \epsilon)}{1 + V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon)} \right] + \lambda_0 + \tilde{O}(n^{-1/4}), \\ \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^2 \ell(r, u, g_3, c, \epsilon) \partial_r \partial_u \ell(r, u, g_3, c, \epsilon) V_0 V}{1 + V_0 \partial_u^2 \ell_0(u, g_3, c, \epsilon)} \right]} - \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] \\ &= \frac{\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]}{\lambda_0 + \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]} + \tilde{O}(n^{-1/4}). \end{aligned} $$

In the above displays, $\partial_u$ (resp. $\partial_r, \partial_u$) denote the derivatives of $\ell_0$ (resp. $\ell$) with respect to its first (resp. first two) argument.
Theorem 2.1 provides an explicit expression for any test metric $\mathcal{E}_{\text{gen}}$ of the form (5) in terms of a collection of scalar summary statistics $q, t, \theta, m_c, q_0, \theta_0, m_{0,c}$, characterized as the solutions of a system of coupled equations. An attentive reader will recognize that the equations governing the statistics $q_0, \theta_0, m_{0,c}$ associated with the first ERM estimator $\hat{w}_0$ recover the now classical asymptotic results for single-stage ERMs developed in, e.g., [Karoui, 2013, Donoho and Montanari, 2016, Thrampoulidis et al., 2018]. The characterization of the statistics $q, \theta, m, t$ associated with the second ERM estimator $\hat{w}$ takes a remarkably similar form, and likewise involves expectations over a scalar random variable $r$ defined through a proximal map (6), in direct analogy with the role played by the variable $u$ for the first ERM. What is fundamentally new in the iterated setting is that the argument of this proximal map is no longer simply Gaussian. Instead, it consists of the sum of a Gaussian term $g_1$ and an additional correction term $\chi \partial_u \ell_0(u, g_3, c, \epsilon)$. This latter term compactly captures the intricate statistical correlations induced by the presence of the first ERM estimator $\hat{w}_0$ in the second ERM (4), whereby each individual single-sample loss term becomes correlated with the entire dataset through the training of $\hat{w}_0$ in (3).

The proof of Theorem 2.1 is provided in Appendices B-E. Recent work by [Celentano et al., 2025] develops a state-evolution analysis of iterative min-max optimization problems involving unimodal isotropic Gaussian data, providing an extension of the convex Gaussian min-max theorem (CGMT) [Gordon, 1985, Thrampoulidis et al., 2018] to a sequential setting. Much like the CGMT itself, this approach is broadly applicable and, in principle, could be specialized—through additional technical work—to the iterated ERM setting considered here. However, such a specialization is not carried out in [Celentano et al., 2025]. In particular, their results do not yield explicit, fully asymptotic characterizations of estimator performance in terms of a finite collection of scalar order parameters. By contrast, the characterization of Theorem 2.1 is explicitly fully asymptotic, involves only scalar quantities, and accommodates Gaussian mixture data. This explicitness enables direct quantitative predictions of generalization performance despite data re-use and prediction-dependent losses.

From a technical standpoint, our analysis follows a different proof strategy based on nested applications of the leave-one-out approach developed in, e.g., [Karoui, 2013, El Karoui, 2018]. We expect this methodology to extend naturally to multi-stage iterated ERMs beyond the two-stage setting studied here.

A subtle yet crucial technical point is that the assumption of $O(\text{polylog}(d))$-bounded loss derivatives does not, in its current form, allow a direct application of Theorem 2.1 to the square loss or to non-differentiable test metrics $L$. This restriction is purely technical and stems from the proof technique rather than from any intrinsic limitation of the result. Indeed, such losses and metrics can be approximated arbitrarily well as $d \to \infty$ by smooth functions satisfying the required assumptions, for instance via routine mollification arguments. In the next section, we nonetheless illustrate in Figs. 1 and 3 that even for the quadratic loss, for losses with non-continuous dependence on the second argument of $\ell$, and for non-differentiable test metrics, the characterization of Theorem 2.1 captures numerical experiments with high accuracy in large but finite dimensions. Finally, we note that commonly used losses such as the logistic loss fully satisfy the assumptions of the theorem without modification.

## 2.3 Special cases

The problem formulation (7)–(8) provides a flexible framework that encompasses several settings of interest, of which we briefly highlight a subset. As discussed in the introduction, the two-stage iterated ERM formulation can model the initial steps of several standard optimization algorithms. Of particular interest are settings in which the loss function factorizes as $\ell(r, u, c, s, \epsilon) = \pi(u, c, s, \epsilon) \tilde{\ell}(r, c, s, \epsilon)$, that is, as a base loss $\tilde{\ell}$ that is *reweighted* by a function $\pi$ depending on the base predictions. Active learning problems, such as the one
described in Section 3, correspond to the case where $\pi$ takes values in $\{0, 1\}$ and indicates whether a given sample is included in the training subset. We discuss this example in detail in Section 3. Allowing $\pi$ to take more general values in $\mathbb{R}_+$ naturally leads to a broader class of sample reweighting schemes. A particularly relevant instance in binary classification corresponds to choices of the form $\pi(u, s, c, \epsilon) = \pi(1_{y \neq \text{sign}(u)})$, whereby samples incorrectly classified by the base model are up-weighted. This can be viewed as a stylized model for the first step of an AdaBoost-type reweighting procedure [Freund and Schapire, 1997]. Finally, while we focus on classification tasks in the remainder of this manuscript, we emphasize that Theorem 2.1 also applies to regression settings.

# 3 Applications to active learning

Theorem 2.1 affords a tight characterization of iterated ERMs that sharply captures the intricate correlations induced by prediction-dependent losses and data re-use. As discussed above, this class of problems arises across a wide range of machine learning tasks. In the remainder of this manuscript, we focus on a particularly notable application in the context of *pool-based active learning*. The theoretical results of Theorem 2.1 place us in a position to revisit a well-studied problem in data selection for binary classification, previously analyzed in a stream of recent works [Sorscher et al., 2022, Kolossov et al., 2023, Feng et al., 2024, Askari-Hemmat et al., 2025, Dohmatob et al., 2025] under oracle or sample-splitting assumptions. By contrast, our framework fully removes these assumptions and enables a principled treatment of the fully data-reuse, budget-constrained setting. This refined analysis further reveals several novel phenomena of interest. We begin by describing the problem in detail and situating it within the related literature.

## 3.1 Setting

Consider a simple data distribution on the sample-label pairs $(x, y) \in \mathbb{R}^d \times \{-1, 1\}$ where the samples are drawn from an isotropic Gaussian distribution $x \sim N(0, I_d)$, and where there exists a fixed vector $\beta \in \mathbb{R}^d$ such that the labels $y$ are deterministically given as $y = \text{sign}(\langle x, \beta \rangle)$. We assume the availability of $n$ independently drawn samples $\{x_i\}_{i \in [n]}$. Importantly, the associated labels are unknown, and the cost of their acquisition is supposed to be high, motivating the *budget constraint* that only a fraction $\gamma \in (0, 1)$ of the $n$ samples may be labeled. The goal of the active learning problem is then to *select an informative subset $S \subset [n]$ of size $|S|/n = \gamma$* to label and use for training. Multiple active selection strategies exist [Settles, 2009], that aim at constructing a training subset $S$ leading to a final test error smaller than that achieved for a subset naively sampled at random. In this work, following [Kolossov et al., 2023, Sorscher et al., 2022, Askari-Hemmat et al., 2025, Feng et al., 2024, Dohmatob et al., 2025], we focus on the following margin-based strategy.

**Base classifier** — Since it is difficult to discern informative samples from the sole knowledge of the unlabeled data $\{x_i\}_{i \in [n]}$, a natural first step consists in training a first estimator, allowing to obtain a prediction of the unknown labels, that can in turn be leveraged for selection. In order to constitute a training set on which this classifier may be trained, a first training set $S_0 \subset [n]$ is uniformly subsampled from $[n]$, with each sample independently included at random according to a Bernoulli law $c_i = 1_{i \in S_0} \sim B(\psi)$, so that $E[|S_0|/n] = \psi$. The associated labels $\{y_i\}_{i \in S_0}$ are then queried, thereby spending a first fraction $\psi \in (0, \gamma)$ of the budget. A linear base classifier with weights $\hat{w}_0$ can then be trained on the thus constituted dataset $\{x_i, y_i\}_{i \in S_0}$ through the ERM $\hat{w}_0 = \arg \min_{w \in \mathbb{R}^d} \hat{R}_0(w)$, with risk

$$ \hat{R}_0(w) = \frac{1}{\psi n} \sum_{i \in [n]} c_i \tilde{\ell}_0(\langle w, x_i \rangle, y_i) + \frac{\lambda_0}{2} \|w\|^2, \quad (7) $$
using a convex loss $\tilde{\ell}_0$, and a $\ell_2$ regularization of strength $\lambda_0$. Note importantly that only the queried labels $\{y_i\}_{i \in S_0}$ actually appear in the risk with non-zero weight $c_i$.

**Data selection** — The base classifier predictions $\langle \hat{w}_0, x_i \rangle$ can then be used as the argument of a selection policy $\pi: \mathbb{R} \to \{0, 1\}$ to select the remaining $(\gamma - \psi)n$ samples allowed by the budget, since $|S_0| = \psi n$ samples have already been labeled. For $j \in [n] \setminus S_0$, the sample $x_j$ is added to the final set $S$ if and only if $\pi(\langle \hat{w}_0, x_j \rangle) = 1$. We choose $\pi$ so that the budget constraint is satisfied on average, namely

$$ \mathbb{E} \left[ \frac{1}{n} \sum_{j \in [n] \setminus S_0} \pi(\langle \hat{w}_0, x_j \rangle) \right] = \gamma - \psi, $$

where the expectation bears over the draw of $\{x_i\}_{i \in [n]}$ and the sampling of $S_0$. Although the budget constraint is satisfied only in expectation, we show in Lemma F.1 of Appendix F that the quantity within the expectation in fact concentrates in the considered asymptotic limit under technical assumptions on $\pi$, implying that the budget constraint is in fact also satisfied with high probability. To give a concrete example, in the following, we for example discuss margin-based policies of the form $\pi(u) = \mathbb{1}_{|u| \le \kappa}$, for some adjustable threshold $\kappa$, with the intuition that samples closest to the decision boundary are hardest to classify, and will therefore bring the most information once labeled. At the end of the selection step, the labels of the selected samples $\{j \in [n] \setminus S_0 | \pi(\langle \hat{w}_0, x_j \rangle) = 1\}$ are queried, saturating the labeling budget.

**Training** — Finally, a second linear classifier can be trained on the selected dataset $S = S_0 \cup \{j \in [n] \setminus S_0 | \pi(\langle \hat{w}_0, x_j \rangle) = 1\}$, composed of the union of the base training set $S_0$ and of the newly selected data. This ERM $\hat{w} = \arg \min_{w \in \mathbb{R}^d} \mathcal{R}(w)$ can be written in terms of a reweighted risk

$$ \mathcal{R}(w) = \frac{1}{\gamma n} \sum_{i \in [n]} \left( (1 - c_i) \pi(\langle \hat{w}_0, x_i \rangle) + c_i \right) \tilde{\ell}(\langle w, x_i \rangle, y_i) + \frac{\lambda}{2} \|w\|^2, \quad (8) $$

using a convex loss $\tilde{\ell}$, and a $\ell_2$ regularization of strength $\lambda$. Note that the multiplicative factor $(1 - c_i)\pi(\langle \hat{w}_0, x_i \rangle) + c_i$ in the summand allocates a weight of 1 (resp. 0) to samples in $S$ (resp. in $[n] \setminus S$). Finally, the accuracy of the trained classifier $\hat{w}$ is quantified by its test error, defined as the probability to misclassify an unseen test sample

$$ \mathcal{E}_{\text{gen}} = \mathbb{E}_{(x,y) \sim \mathcal{P}} \left[ \mathbb{1}_{\text{sign}(\langle \hat{w}, x \rangle) \neq y} \right]. $$

## 3.2 Related works in active learning

**Theory of active learning and subsampling** — The problem of data selection has been the object of a vast line of works in statistical learning theory, surveyed in e.g. [Settles, 2009] and [Hanneke, 2014]. The majority of these works prove worst-case bounds which become void as the dimension of the data grows, and thus do not capture typical high-dimensional problems. A large body of works has similarly been devoted to the closely related problem of subsampling, with optimal subsampling probabilities derived in e.g. [Drineas et al., 2006, Ma et al., 2015, 2022] for linear regression, and [Wang et al., 2018] for logistic regression. Almost all these studies however focus on the low-dimensional regime $n \gg d$, leaving the regime $n \lesssim d$ largely uncharted.

**High-dimensional analyses of active learning** — The high-dimensional case $n \asymp d$ was studied in a number of studies, with a particular focus on supervised active binary classification with linear models. The seminal work of [Seung et al., 1992] studies a disagreement-based active learning method, assuming
the learner can freely query *any* sample. In contrast, in many real applications, the sample rather needs to be *chosen from a pre-existing pool* of available data. In the latter scenario, [Cui et al., 2021] conjecture a tight information-theoretic lower-bound on a notion of test error when the subset is optimally selected, but do not analyze a concrete algorithm. Closer to the present work, [Sorscher et al., 2022, Kolossov et al., 2023, Askari-Hemmat et al., 2025, Dohmatob et al., 2025] analyze the binary classification task described Subsection 3.1. However, these works all make the significant simplification that the base classifier is either an *oracle*, or trained on a *separate held-out dataset* at zero label cost. In real settings however, such a dataset would instead need to be carved out from the pool of available data, and labeled at the expense of a fraction of the budget. Furthermore, these works do not consider re-using the base training set, in addition to the selected data, when training the final classifier — thereby misspending already labeled data. The eager reader may take an anticipated look at Fig. 1 (inset), which shows how holding out the base training set (dashed lines), instead of re-employing it (solid lines), may result in a significant loss in accuracy for the final model. Theorem 2.1 enables the removal of those assumptions, and the treatment of the fully budget-constrained problem.

**Margin-based active learning with linear classifiers** — Let us mention that outside of the pool-based setting investigated in the present work, the problem of margin-based methods for binary classification with linear classifiers has traditionally constituted a central question in uncertainty-based active learning. [Dasgupta, 2004] analyze a greedy algorithm, assuming access to oracle knowledge on the prior of the separating hyperplane. The literature on streaming (online) active learning algorithms [Dasgupta et al., 2005, Cesa-Bianchi et al., 2009, Dekel et al., 2010, Orabona et al., 2011, Raj and Bach, 2022, Wang and Singh, 2016] in particular contains many non-asymptotic guarantees, for the square or hinge loss and specific selection policies $\pi$. We focus in the present work on the pool-based case where all unlabeled samples are available at once, and prove sharp error characterizations for a generic classes of convex loss functions and selection policies under smoothness assumptions. [Balcan et al., 2007, Balcan and Long, 2013] report non-asymptotic sample complexity guarantees, but consider the case where the data distribution can be freely sampled, instead of assuming a fixed pre-existing pool.

## 3.3 Tradeoff in budget allocation

An attentive reader might have already realized that the budget-constrained active binary classification task described in Subsection 3.1 in fact constitutes a special instantiation of the generic class of iterated ERM problems (1), (2) described in Section 2, with first loss $\ell_0(u, s, c, \epsilon) = c\tilde{\ell}_0(u, \text{sign}(s))$ and second loss $\ell(r, u, s, c, \epsilon) = ((1-c)\pi(u)+c)\tilde{\ell}(r, \text{sign}(s))$. As such, the test error of the final classifier is sharply described in the high-dimensional regime $n \asymp d$ by Theorem 2.1, in the generic case with data re-use and without making sample-splitting or oracle assumptions, thereby lifting a core limitation of [Sorscher et al., 2022, Kolossov et al., 2023, Feng et al., 2024, Dohmatob et al., 2025, Askari-Hemmat et al., 2025]. In this Subsection, we explore the rich implications of this characterization.

Fig. 1 presents the theoretical predictions of Theorem 2.1 for the active learning example of Section 3, and contrast them to numerical experiments in large but finite dimension $d = 1000$, revealing good agreement. The illustrated setting corresponds to quadratic losses $\ell(y, z)$, $\ell_0(y, z) = 1/2(y-z)^2$, regularizations $\lambda = \lambda_0 = 0.01$, and a margin-based selection policy $\pi(u) = 1_{|u|<\kappa^{-}(\gamma, \psi)}$, with a threshold $\kappa^{-}(\gamma, \psi) = \sqrt{2q_0\text{erf}^{-1}(\gamma-\psi/1-\psi)}$ chosen so as to saturate the budget constraint with high probability. Fig. 1 represents the test error $\mathcal{E}_{\text{gen}}$ of the final classifier, as a function of fraction of the budget $\psi$ allocated to training the base classifier, with different curves corresponding to different total budget $\gamma$. In particular, the rightmost point $\psi = \gamma$ of each curve corresponds to the performance of a classifier trained on a passively (i.e. randomly) selected subset $S$ of size $\gamma n$, and exhibits higher test error than most cases where $S$ is in contrast actively chosen ($\psi < \gamma$).
<figure><img src="image_3.png" /><figcaption>Figure 1: Test error $\mathcal{E}_{\text{gen}}$ of the classifier $\hat{w}$ (8) trained on the subset $S$, selected using a base classifier $\hat{w}_0$ (7) trained on a fraction $\psi \in (0, \gamma)$ of the $n$ samples for $\alpha = 8, \lambda = 0.01$, losses $\ell(y, z)$, $\ell_0(y, z) = 1/2(y-z)^2$, and policy $\pi(u) = 1_{|u|<\kappa-(\gamma, \psi)}$. Different curves correspond to different total budgets $\gamma \in (0, 1)$. Solid lines: theoretical predictions. Dots: numerical experiments in dimension $d = 2000$; error bars represent one standard deviation over 20 trials. Dashed line: test error of the base classifier. Inset: for $\gamma = 0.7$, the dashed line represents the test error when only the newly selected subset $S \setminus S_0$ is used for the second ERM, with the base training set $S_0$ being held-out.</figcaption></figure>

**A tradeoff in budget allocation** — A first striking feature of the learning curves is their non-monotonicity, revealing the existence of an optimal budget allocation $\psi^*$ (red star in Fig. 1) for which the test error $\mathcal{E}_{\text{gen}}$ is minimized. This U-shape results from a fundamental tradeoff in the allocation $\psi, \gamma - \psi$ of the labeling budget $\gamma$ across the two ERMs (7) and (8):

* If $\psi$ is chosen too small, the base classifier will yield poor predictions, which results in turn in the selection of scarcely informative samples to include in $S$.

* Conversely, if too much budget $\psi$ is spent on constituting the training set $S_0$ of the base classifier, while the accurate base classifier does allow to correctly identify the most valuable samples among the remaining unlabeled samples, only a few of those can be labeled and included in $S$, due to the scarce $\gamma - \psi$ budget remaining. As a result, the selected subset $S$ will be in majority composed of the randomly subsampled $S_0$, with only a few actually selected samples, eventually yielding marginally better-than-passive performance.

This fundamental tension between these two effects was absent from prior works [Kolossov et al., 2023, Sorscher et al., 2022, Feng et al., 2024, Askari-Hemmat et al., 2025, Dohmatob et al., 2025].

**A selection-driven double-descent** — The learning curves in Fig. 1 also exhibit a characteristic double-descent shape, where two successive phases of decrease of the test error $\mathcal{E}_{\text{gen}}$ are separated by an interpolation peak. Double-descent phenomena have been the object of renewed interest in recent years, and extensively described in a rich body of literature, see e.g. [Belkin et al., 2019, Geiger et al., 2020, Nakkiran, 2019]. Such double-descent are however classically observed as a function of the number of parameters of the classifier, or the number of training samples. In stark contrast, in the present setting, both the number of model parameters ($d$ for linear methods) and number of training samples ($|S| = \gamma n$) are fixed, and only the composition of the training set $S \subset [n]$ varies along the curves of Fig. 1. The double-descent is here in fact
<figure><img src="image_4.png" /><figcaption>Figure 2: Test error as a function of the fraction $\psi \in (0, \gamma)$ allocated to the first stage of ERM, for the pneumonia diagnosis task on the chest X-ray dataset [Kermany et al., 2018], pre-processed through a scattering transform with scale 4 and 6 angles [Andreux et al., 2020]. The logistic loss $\ell(z, y) = \ell_0(z, y) = \log(1 + \exp(-yz))$ was employed, with $\alpha = 5.41, \lambda = 0.01$. The samples closest to the decision boundary of the first classifier were retained, until the budget was saturated. Different curves represent different total budget $\gamma$. Shades represent one standard deviation over 100 trials.</figcaption></figure>

driven by the way the selected subset $S$ is constructed. Close to $\psi = 1/\alpha$, the base classifier overfits, causing
in turn a biased selection of samples, eventually resulting in a poor accuracy.

**Real data validation** — While Theorem 2.1 describes the precision-budget tradeoff in simple synthetic settings for Gaussian data, the phenomenon can also be observed for real datasets. We illustrate this point in Fig. 2, for the task of pneumonia diagnosis on a dataset of chest X-ray images [Kermany et al., 2018]. This dataset furthermore illustrates in timely fashion an application case where the labeling of the samples was in fact expensive and carried out by several human clinicians, and for which active learning is therefore directly relevant. The images were processed using scattering transform [Andreux et al., 2020], and a subset selected using the same procedure as the one described in Section 3, using logistic regression. A final classifier was fitted on the selected set using logistic regression. The code for this experiment is provided on this [online repository](https://github.com/kevin2819/ERM-pneumonia). The resulting learning curve displays a clear U-shape, strongly suggesting the presence of the tradeoff described above.

## 3.4 On the selection policy

Having explored the effect of the choice of the budget allocation $\psi$ for the training of the base estimator, we now discuss the second aspect of the active learning algorithm, namely the choice of the selection policy $\pi$. In the likeness of many prior works, [Kolossov et al., 2023, Sorscher et al., 2022], the previous section focused on the particular case of margin-based selection, where samples whose label prediction by the base classifier were smallest in absolute value were retained. This natural choice for linear classifiers corresponds to the intuition that labeling samples closest to the base estimator's decision boundary, and thus a priori hardest and most uncertain, lead to greater information gain when labeled.

While [Dohmatob et al., 2025] prove for linear regression in the population case $\alpha \to \infty$ that selecting small-margin samples is optimal, the answer is more nuanced at finite sample complexity. [Sorscher et al., 2022] have shown that there exist regimes where conversely, selecting *larger* margin samples far from the
<figure><img src="image_5.png" /><figcaption>Figure 3: Same setting as Fig. 1, with $\alpha = 1$. Dashed curves represent the selection policy $\pi(u) = 1_{|u|>\kappa^+(\gamma, \psi)}$, where $\kappa^+(\gamma, \psi) = \sqrt{2q_0}\text{erf}^{-1}(1-\gamma/1-\psi)$, corresponding to selecting the samples with higher margin. Solid lines still represent the small-margin selection policy $\pi(u) = 1_{|u|<\kappa^-(\gamma, \psi)}$. The inset represents the case where oracle access of $\beta$ is available, so that no budget $\psi = 0$ needs to be used to train the base classifier, and the data can be selected directly using the true margins as $\pi(\langle\beta, x_i\rangle)$.</figcaption></figure>

decision boundary can prove beneficial. This was found to be the case in particular for small budget regimes with small values of $\alpha\gamma$, provided a good estimate $\hat{w}_0$ remains available from a held-out dataset, or from an oracle. In such settings, the large margin samples indeed provide a clearer sketch of the geometry of the target function, and aid the alignment of the final weights $\hat{w}$ with $\hat{w}_0$ and $\beta$. These conclusions, which also echo the findings of [Hacohen et al., 2022] for a related problem, however need to be nuanced in truly budget-constrained settings, where a small budget rules out the constitution of a large held-out set on which a base estimator may be trained up to satisfactory accuracy. In such a case, selecting large-margin samples might reversely detrimentally bias the final classifier towards learning an erroneous direction $\hat{w}_0$, rather than the ground-truth $\beta$. This is illustrated in Fig. 3, where the large-margin policy (dashed) consistently leads to worse accuracy than the small-margin policy (solid lines), despite performing better in the oracle case where a good base estimator is available despite the limited data budget (inset). The latter case corresponds to the observations of [Sorscher et al., 2022, Kolossov et al., 2023, Hacohen et al., 2022]. This comparison highlights fundamental discrepancies between the fully budget-constrained setting characterized by Theorem 2.1, and cases where an oracle or an additional held-out set is available.

These observations naturally prompt the question : for given models $\tilde{l}_0, \lambda_0, \tilde{l}, \lambda$ and budgets $\gamma, \psi$, what is then the optimal selection policy $\pi$? The answer to this question is generically complex. Fig. 4 evidences that for certain choices of $\gamma, \psi$, a mixed strategy of the form $\pi(u) = 1_{|u|<\kappa^-} + 1_{|u|>\kappa^+}$ that retains a mixture of samples both far and close to the decision boundary can achieve a better accuracy than naively selecting only the farthest or closest samples. This finding echoes similar observations from [Kolossov et al., 2023, Hacohen and Weinshall, 2023].

Looking ahead, the theoretical characterization of Theorem 2.1 provides an explicit expression of the test error $\mathcal{E}_{\text{gen}}$ as a functional of the selection policy $\pi$, which can in principle be optimized over. While this analytical objective represents a first step forward since it removes the need for expensive empirical search, this optimization remains very challenging, since it involves a functional minimization over a discrete-valued function. Solving this problem constitutes an open question of significant interest for future research.
<figure><img src="image_6.png" /><figcaption>Figure 4: Test error $\mathcal{E}_{\text{gen}}$ achieved by the second classifier, with $\alpha = 8$, $\gamma = 0.3$, $\psi = 0.1$, $\lambda_0 = \lambda = 0.001$, and square loss. A selection policy $\pi(u) = \mathbb{1}_{|u|<\kappa^-} + \mathbb{1}_{|u|>\kappa^+}$ was used, for $\kappa^- \in (0, \kappa^-(\gamma, \psi))$, and $\kappa^+$ determined from $\kappa^-$ by requiring that the budget constraint should be saturated. Solid lines: characterization of Theorem 2.1. Dots: numerical experiments in dimension $d = 3000$. Error bars represent one standard deviation over 50 trials.</figcaption></figure>

## 3.5 Data pruning

For completeness, and in an effort to build further connections with prior works [Kolossov et al., 2023, Askari-Hemmat et al., 2025, Dohmatob et al., 2025, Hacohen et al., 2022] we briefly discuss in this last subsection the case of *data pruning*. In this paragraph only, we assume all labels are available, and the base classifier is trained on the whole dataset, namely $S_0 = [n]$, then used to select a final and *smaller* training subset $S \subset [n]$ through a selection (pruning) policy $\pi$. Several of the above works report settings in which training a model on the smaller subset $S \subset [n]$ can yield *better* accuracy than training on the full dataset, when an oracle base classifier is used for selection. In Appendix G, we show by instantiating Theorem 2.1 in two examples (see Fig. 5 and Fig. 6) that this phenomenon can still be observed in the more realistic setting when the base classifier is used to prune the *same* dataset it was trained on.

## 4 Conclusions

We study two iterated ERMs on the same dataset, where the predictions of the first ERM estimator enter the loss function of the second ERM. The dependence of the loss on the predictions and the re-use of the data introduce intricate statistical correlations across samples which fundamentally set the problem apart from the now mature study of single-stage ERM. For Gaussian mixture data and a large class of convex losses, in the asymptotic regime where the number of samples $n$ and the dimension of the covariates $d$ diverge at proportional rate $n \asymp d$, we prove a sharp asymptotic characterization of the statistics of the second-stage ERM estimator. Our proof builds on a sequential version of the standard leave-one-out method [Karoui, 2013]. These results find a notable application in the theory of pool-based active learning. Our analysis lets us revisit a well-studied problem in active binary classification [Sorscher et al., 2022, Kolossov et al., 2023, Feng et al., 2024, Askari-Hemmat et al., 2025, Dohmatob et al., 2025], and fully remove sample splitting and oracle assumptions made in prior work. The analysis of the budget-constrained case further uncovers a tradeoff in the allocation of the data acquisition budget, which is also observed in real-data experiments. It also unveils a double-descent behavior of the test error as a function of the budget allocation, which in
contrast to prior studies occurs at fixed sample and model size.

## Acknowledgements

The work of Y.M.L. is supported by a Harvard College Professorship, by the Harvard FAS Dean's Fund for Promising Scholarship, and by DARPA under grant DIAL-FP-038.

## References

Mathieu Andreux, Tomás Angles, Georgios Exarchakis, Roberto Leonarduzzi, Gaspar Rochette, Louis Thiry, John Zarka, Stéphane Mallat, Joakim Andén, Eugene Belilovsky, et al. Kymatio: Scattering transforms in python. Journal of Machine Learning Research, 21(60):1–6, 2020.

Reyhane Askari-Hemmat, Mohammad Pezeshki, Elvis Dohmatob, Florian Bordes, Pietro Astolfi, Melissa Hall, Jakob Verbeek, Michal Drozdzal, and Adriana Romero-Soriano. Improving the scaling laws of synthetic data with deliberate practice. arXiv preprint arXiv:2502.15588, 2025.

Maria-Florina Balcan and Phil Long. Active and passive learning of linear separators under log-concave distributions. In Conference on Learning Theory, pages 288–316. PMLR, 2013.

Maria-Florina Balcan, Andrei Broder, and Tong Zhang. Margin based active learning. In International Conference on Computational Learning Theory, pages 35–50. Springer, 2007.

Nicholas Barnfield, Hugo Cui, and Yue M Lu. High-dimensional analysis of single-layer attention for sparse-token classification. arXiv preprint arXiv:2509.25153, 2025.

Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 15849–15854, 2019.

Michael Celentano, Chen Cheng, Ashwin Pananjady, and Kabir Aladin Verchand. State evolution beyond first-order methods i: Rigorous predictions and finite-sample guarantees. arXiv preprint arXiv:2507.19611, 2025.

Nicolo Cesa-Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th annual international conference on machine learning, pages 121–128, 2009.

Kabir Aladin Chandrasekher, Mengqi Lou, and Ashwin Pananjady. Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization. Information and Inference: A Journal of the IMA, 13(3):iaae025, 2024.

Hugo Cui, Luca Saglietti, and Lenka Zdeborová. Large deviations in the perceptron model and consequences for active learning. Machine Learning: Science and Technology, 2(4):045001, 2021.

Edwige Cyffers, Alireza Mirrokni, and Marco Mondelli. Optimal regularization for performative learning. arXiv preprint arXiv:2510.12249, 2025.

Sanjoy Dasgupta. Analysis of a greedy active learning strategy. Advances in neural information processing systems, 17, 2004.
Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based active learning. In *International conference on computational learning theory*, pages 249–263. Springer, 2005.

Ofer Dekel, Claudio Gentile, Karthik Sridharan, et al. Robust selective sampling from single and multiple teachers. In *COLT*, pages 346–358, 2010.

Elvis Dohmatob, Mohammad Pezeshki, and Reyhane Askari-Hemmat. Why less is more (sometimes): A theory of data curation. arXiv preprint arXiv:2511.03492, 2025.

David Donoho and Andrea Montanari. High dimensional robust m-estimation: Asymptotic variance via approximate message passing. *Probability Theory and Related Fields*, 166(3):935–969, 2016.

Petros Drineas, Michael W Mahoney, and Shan Muthukrishnan. Sampling algorithms for 1 2 regression and applications. In *Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm*, pages 1127–1136, 2006.

Bradley Efron and Charles Stein. The jackknife estimate of variance. *The Annals of Statistics*, pages 586–596, 1981.

Noureddine El Karoui. On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators. *Probability Theory and Related Fields*, 170(1): 95–175, 2018.

Yunzhen Feng, Elvis Dohmatob, Pu Yang, Francois Charton, and Julia Kempe. Beyond model collapse: Scaling up with synthesized data requires reinforcement. In *ICML 2024 workshop on theoretical foundations of foundation models*, 2024.

Silvio Franz and Giorgio Parisi. Phase diagram of coupled glassy systems: A mean-field study. *Physical review letters*, 79(13):2486, 1997.

Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. *Journal of computer and system sciences*, 55(1):119–139, 1997.

Anvit Garg, Sohom Bhattacharya, and Pragya Sur. Preventing model collapse under overparametrization: Optimal mixing ratios for interpolation learning and ridge regression. arXiv preprint arXiv:2509.22341, 2025.

Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number of parameters in deep learning. *Journal of Statistical Mechanics: Theory and Experiment*, 2020(2):023401, 2020.

Yehoram Gordon. Some inequalities for gaussian processes and applications. *Israel Journal of Mathematics*, 50(4):265–289, 1985.

Guy Hacohen and Daphna Weinshall. How to select which active learning strategy is best suited for your specific problem and budget. *Advances in Neural Information Processing Systems*, 36:13395–13407, 2023.

Guy Hacohen, Avihu Dekel, and Daphna Weinshall. Active learning on a budget: Opposite strategies suit high and low budgets. arXiv preprint arXiv:2202.02794, 2022.

Steve Hanneke. Theory of active learning. *Foundations and Trends in Machine Learning*, 7(2-3), 2014.
Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators: rigorous results. arXiv preprint arXiv:1311.2445, 2013.

Chiraag Kaushik, Justin Romberg, and Vidya Muthukumar. Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks. Advances in Neural Information Processing Systems, 37:123755-123786, 2024.

Daniel S Kermany, Michael Goldbaum, Wenjia Cai, Carolina CS Valentim, Huiying Liang, Sally L Baxter, Alex McKeown, Ge Yang, Xiaokang Wu, Fangbing Yan, et al. Identifying medical diagnoses and treatable diseases by image-based deep learning. cell, 172(5):1122-1131, 2018.

Germain Kolossov, Andrea Montanari, and Pulkit Tandon. Towards a statistical theory of data selection under weak supervision. arXiv preprint arXiv:2309.14563, 2023.

Ying Liu. Active learning with support vector machine applied to gene expression data for cancer classification. Journal of chemical information and computer sciences, 44(6):1936-1941, 2004.

Mengqi Lou, Kabir Aladin Verchand, and Ashwin Pananjady. Hyperparameter tuning via trajectory predictions: stochastic prox-linear methods in matrix sensing. M. lou et al. Mathematical Programming, pages 1-61, 2025.

Ping Ma, Michael W Mahoney, and Bin Yu. A statistical perspective on algorithmic leveraging. The Journal of Machine Learning Research, 16(1):861-911, 2015.

Ping Ma, Yongkai Chen, Xinlian Zhang, Xin Xing, Jingyi Ma, and Michael W Mahoney. Asymptotic analysis of sampling estimators for randomized numerical linear algebra algorithms. Journal of Machine Learning Research, 23(177):1-45, 2022.

Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv preprint arXiv:1912.07242, 2019.

Koki Okajima and Takashi Takahashi. Asymptotic dynamics of alternating minimization for bilinear regression. Journal of Statistical Mechanics: Theory and Experiment, 2025(5):053301, 2025.

Francesco Orabona, Nicolo Cesa-Bianchi, et al. Better algorithms for selective sampling. In Proceedings of the 28th international conference on machine learning: Bellevue, Washington, USA, june 28. july 2, 2011, pages 433-440. Omnipress, 2011.

Robert T Powers and Erling Størmer. Free states of the canonical anticommutation relations. Communications in Mathematical Physics, 16(1):1-33, 1970.

Anant Raj and Francis Bach. Convergence of uncertainty sampling for active learning. In International conference on machine learning, pages 18310-18331. PMLR, 2022.

R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877-898, 1976.

Yuji Roh, Geon Heo, and Steven Euijong Whang. A survey on data collection for machine learning: a big data-ai integration perspective. IEEE Transactions on Knowledge and Data Engineering, 33(4):1328-1347, 2019.

Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In European conference on machine learning, pages 413-424. Springer, 2006.
Luca Saglietti and Lenka Zdeborová. Solvable model for inheriting the regularization through knowledge distillation. In *Mathematical and Scientific Machine Learning*, pages 809–846. PMLR, 2022.

Burr Settles. Active learning literature survey. 2009.

H Sebastian Seung, Manfred Opper, and Haim Sompolinsky. Query by committee. In *Proceedings of the fifth annual workshop on Computational learning theory*, pages 287–294, 1992.

Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. *Advances in Neural Information Processing Systems*, 35:19523–19536, 2022.

Takashi Takahashi. The role of pseudo-labels in self-training linear classifiers on high-dimensional gaussian mixture data. arXiv preprint arXiv:2205.07739, 2022.

Kaito Takanami, Takashi Takahashi, and Ayaka Sakata. The effect of optimal self-distillation in noisy gaussian mixture model. arXiv preprint arXiv:2501.16226, 2025.

Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Precise error analysis of regularized *m*-estimators in high dimensions. *IEEE Transactions on Information Theory*, 64(8):5592–5628, 2018.

Simon Tong and Daphne Koller. Support vector machine active learning with applications to text classification. *Journal of machine learning research*, 2(Nov):45–66, 2001.

Dan Wang and Yi Shang. A new active labeling method for deep learning. In *2014 International joint conference on neural networks (IJCNN)*, pages 112–119. IEEE, 2014.

HaiYing Wang, Rong Zhu, and Ping Ma. Optimal subsampling for large sample logistic regression. *Journal of the American Statistical Association*, 113(522):829–844, 2018.

Yining Wang and Aarti Singh. Noise-adaptive margin-based active learning and lower bounds under tsybakov noise condition. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 30, 2016.
# A Notations and assumptions

## Notations

* For two random variables $a, b$ and a integer $k \in \mathbb{N}$, we write $a = O_{L_k}(b)$ if $\mathbb{E}[|a|^k] \le \mathbb{E}[|b|^k]$. If $k$ is not specified in the statement, the latter is understood to hold for any $k \in \mathbb{N}$.

* In the following, for $a, b \in \mathbb{R}$, $(a, b)$ denotes the unordered interval.

* For $i \in [n]$, we denote $X_{\setminus i} \in \mathbb{R}^{(n-1) \times d}$ the leave-one-row-out matrix constructed by removing the $i$-th row from the full data matrix $X$.

* $\|\cdot\|$ denotes the 2-norm for vectors, and the operator norm for matrices.

**Remark A.1 (Properties of $O_{L_k}$).** We remind for convenience the following properties of the $O_{L_k}$ notation.

* If $\alpha = O_{L_{2k}}(a_n)$, $\beta = O_{L_{2k}}(b_n)$, for $a_n, b_n$ two positive sequences, it follows from Minkowski's inequality that $\alpha\beta = O_{L_k}(a_n b_n)$.

* Let $\alpha, \beta$ be two positive random variables bounded as $\alpha = O_{L_k}(a_n)$, $\beta = O_{L_k}(b_n)$, for $a_n, b_n$ two positive sequences. Then it follows from Hölder's inequality that $\alpha + \beta = 2O_{L_k}(a_n \vee b_n)$. As a consequence, from the identity $\sqrt{x} \le 1+x$ for all $x \ge 0$, it follows that $\sqrt{\alpha} = 2O_{L_k}(\sqrt{a_n})$.

**Assumption A.2 (First-stage loss $\ell_0$).** Let $\ell_0 : \mathbb{R} \times \mathbb{R} \times \mathcal{V} \times \mathcal{E} \to \mathbb{R}_+$ denote the loss used for the first-stage estimator. We assume,

(A.1) $\ell_0$ is everywhere three times differentiable in its first argument. We denote by $\partial_u$ the derivative with respect to the latter.

(A.2) $\ell_0$ is convex in its first argument, namely $\partial_u^2 \ell_0$ is everywhere positive.

(A.3) The derivatives $\partial_u \ell_0$, $\partial_u^2 \ell_0$, $\partial_u^3 \ell_0$ are everywhere well defined and bounded by $O(\text{polylog}(n))$.

(A.4) The reduced function $\tilde{\ell}_0 : s, c, \epsilon \to \ell_0(0, s, c, \epsilon)$ is bounded by an $O(\text{polylog}(n))$.

**Assumption A.3 (Second-stage loss $\ell$).** Let $\ell : \mathbb{R} \times \mathbb{R} \times \mathbb{R} \times \mathcal{V} \times \mathcal{E} \to \mathbb{R}_+$ denote the loss used for the second-stage problem.

(B.1) The derivatives $\partial_r \ell$, $\partial_r^2 \ell$, $\partial_r^3 \ell$, $\partial_r^4 \ell$, $\partial_r \partial_u \ell$, $\partial_r \partial_u^2 \ell$, $\partial_r^2 \partial_u \ell$, $\partial_r^3 \partial_u \ell$, $\partial_r^2 \partial_u^2 \ell$ are everywhere well defined, and bounded by $O(\text{polylog}(n))$. We denoted by $\partial_r$, $\partial_u$ the derivatives with respect to the first and second arguments of $\ell$.

(B.2) $\ell$ is convex in its first argument, namely $\partial_r^2 \ell$ is everywhere positive.

(B.3) The reduced function $\tilde{\ell} : u, s, c, \epsilon \to \ell(0, u, s, c, \epsilon)$ is bounded by $O(\text{polylog}(n))$.

In the following, for conciseness, we adopt the shorthands $\ell_i(r_i, u_i) = \ell(r_i, u_i, s_i, c_i, \epsilon_i)$ and $\ell_{0,i}(u_i) = \ell_0(u_i, s_i, c_i, \epsilon_i)$.

**Assumption A.4 (Data distribution).** We make the following assumptions on the sample distribution.

(C.1) The latent classes $\{c_i\}_{i \in [n]}$ are drawn i.i.d from an arbitrary distribution on a finite set $\mathcal{V}$.

(C.2) Likewise, the stochastic noises $\{\epsilon_i\}_{i \in [n]}$ follow a distribution on $\mathcal{E} \subset \mathbb{R}$, with all moments being finite.
(C.3) Conditional on {$c_i$}$_{i\in[n]}$, the samples $z_i = x_i - \mu_{c_i}$ have i.i.d unit variance Gaussian entries.

(C.4) We further assume that the inner products $\rho_{c,k} = \langle \mu_c, \mu_k \rangle$, $\nu_c = \langle \mu_c, \beta \rangle$, $\rho = \|\beta\|^2$ are fixed absolute constants. In particular, there thus exist absolute constants $M, B$ such that $\|\mu_c\| \le M$, $\|\beta\| \le B$ for all $c \in \mathcal{V}$ and for all $n$. Furthermore, the Gram matrix

$$A = \begin{bmatrix} \varrho & \nu \\ \nu & \rho \end{bmatrix}.$$

has a minimal eigenvalue bounded away from 0 by an absolute constant. It will also prove convenient to introduce the matrix $\mathcal{M} \in \mathbb{R}^{|\mathcal{V}| \times d}$ with rows $\mu_1, \dots, \mu_{|\mathcal{V}|}$.

Finally, we assume throughout the proof that the regularizations are strictly positive, namely $\lambda, \lambda_0 > 0$.

## A.1 First-stage ERM

We remind the first-stage ERM

$$\hat{w}_0 = \underset{w}{\operatorname{argmin}} \hat{\mathcal{R}}_0(w), \qquad \hat{\mathcal{R}}_0(w) = \frac{1}{n} \sum_{j \in [n]} \ell_{0,j}(\langle w, x_j \rangle) + \frac{\lambda_0}{2} \|w\|_2^2$$

and for any $i \in [n]$ the leave-one out surrogate

$$\hat{w}_{0,\setminus i} = \underset{w}{\operatorname{argmin}} \hat{\mathcal{R}}_{0,\setminus i}(w), \qquad \hat{\mathcal{R}}_{0,\setminus i}(w) = \frac{1}{n} \sum_{j \neq i} \ell_{0,j}(\langle w, x_j \rangle) + \frac{\lambda_0}{2} \|w\|_2^2.$$

We define the full and leave-one-out residuals

$$u_j = \langle \hat{w}_0, x_j \rangle, \qquad u_{j,\setminus i} = \langle \hat{w}_{0,\setminus i}, x_j \rangle,$$

as well as the surrogate estimator

$$\tilde{w}_{0,i} = \hat{w}_{0,\setminus i} - \frac{1}{n} \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_i$$

where we introduced the leave-i out Hessian $H_{0,\setminus i}$ as

$$H_{0,\setminus i} = \frac{1}{n} \sum_{j \neq i} \partial_u^2 \ell_{0,j}(u_{j,\setminus i}) x_j x_j^\top + \lambda_0 I_d$$

and denoted

$$\tilde{u}_{i,i} = \operatorname{prox}_{\gamma_{0,i} \ell_{0,i}(\cdot)}(u_{i,\setminus i}), \qquad \gamma_{0,i} = \frac{1}{n} x_i^\top H_{0,\setminus i}^{-1} x_i.$$

Finally, for $j \neq i$, we similarly define the surrogate residual

$$\tilde{u}_{j,i} = \langle \tilde{w}_{0,i}, x_j \rangle.$$

For simplicity, we will also adopt the shorthand

$$\xi_i = -\frac{1}{n} \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_i,$$

so that $\tilde{w}_{0,i}$ may be more compactly rewritten as $\tilde{w}_{0,i} = \hat{w}_{0,\setminus i} + \xi_i$. It will finally also prove convenient to introduce the surrogate Hessian

$$\tilde{H}_{0,i} = \frac{1}{n} \sum_{j \in [n]} \partial_u^2 \ell_{0,j}(\tilde{u}_{j,i}) x_j x_j^\top + \lambda I_d.$$
## A.2 Second-stage ERM

By the same token, for the second-stage problem

$$ \hat{w} = \underset{w}{\operatorname{argmin}} \mathcal{R}(w), $$

$$ \mathcal{R}(w) = \frac{1}{n} \sum_{j \in [n]} \ell_j(\langle w, x_j \rangle, u_j) + \frac{\lambda}{2} \|w\|_2^2 $$

we define the leave-one out problem

$$ \hat{w}_{\setminus i} = \underset{w}{\operatorname{argmin}} \mathcal{R}_{\setminus i}(w), $$

$$ \mathcal{R}_{\setminus i}(w) = \frac{1}{n} \sum_{j \neq i} \ell_j(\langle w, x_j \rangle, u_{j, \setminus i}) + \frac{\lambda}{2} \|w\|_2^2. $$

Let us also introduce the surrogate risk

$$ \tilde{\mathcal{R}}_i(w) = \frac{1}{n} \sum_{j \in [n]} \ell_j(\langle w, x_j \rangle, \tilde{u}_j) + \frac{\lambda}{2} \|w\|_2^2. $$

Note that despite the close notations, $\tilde{w}_i$ is not the minimizer of $\tilde{\mathcal{R}}_i$. We define the full and leave-one-out residuals

$$ r_j = \langle \hat{w}, x_j \rangle, $$

$$ r_{j, \setminus i} = \langle \hat{w}_{\setminus i}, x_j \rangle, $$

as well as the surrogate estimator

$$ \tilde{w}_i = \hat{w}_{\setminus i} - \frac{1}{n} \partial_r \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) H_{\setminus i}^{-1} x_i + \frac{1}{n} \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{\setminus i}^{-1} G_{\setminus i} H_{0, \setminus i}^{-1} x_i $$

where we introduced the leave-i out Hessians $H_{\setminus i}$, $G_{\setminus i}$ as

$$ H_{\setminus i} = \frac{1}{n} \sum_{j \neq i} \partial_r^2 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) x_j x_j^{\top} + \lambda I_d, $$

$$ G_{\setminus i} = \frac{1}{n} \sum_{j \neq i} \partial_u \partial_r \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) x_j x_j^{\top} $$

and denoted

$$ \tilde{r}_{i,i} = \operatorname{prox}_{\gamma_i \ell_i(\cdot, \tilde{u}_{i,i})} (r_{i,\setminus i} + \partial_u \ell_{0,i}(\tilde{u}_{i,i}) v_i), $$

$$ \gamma_i = \frac{1}{n} x_i^{\top} H_{\setminus i}^{-1} x_i, $$

$$ v_i = \frac{1}{n} x_i^{\top} H_{\setminus i}^{-1} G_{\setminus i} H_{0, \setminus i}^{-1} x_i. $$

We also introduce the full Hessian

$$ H = \frac{1}{n} \sum_{j \in [n]} \partial_r^2 \ell_j(r_j, u_j) x_j x_j^{\top} + \lambda I_d, $$

and the surrogate Hessians

$$ \tilde{H}_i = \frac{1}{n} \sum_{j \in [n]} \partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j x_j^{\top} + \lambda I_d, $$

$$ \tilde{G}_i = \frac{1}{n} \sum_{j \in [n]} \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j x_j^{\top} $$

In the following, we adopt the shorthands

$$ \eta_i = -\frac{1}{n} \partial_r \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) H_{\setminus i}^{-1} x_i, $$

$$ \zeta_i = \frac{1}{n} \partial_u \ell_{0,i}(\tilde{u}_{i,i}) H_{\setminus i}^{-1} G_{\setminus i} H_{0, \setminus i}^{-1} x_i, $$

so that $\tilde{w}_i$ may be more compactly written as $\tilde{w}_i = \hat{w}_{\setminus i} + \eta_i + \zeta_i$. Finally, for $j \neq i$, we similarly define the surrogate residual

$$ \tilde{r}_{j,i} = \langle \tilde{w}_i, x_j \rangle. $$
# B Leave-one-out approximation results

## B.1 First-stage estimator

In this first part of the proof, we show that the surrogates $\tilde{w}_i$ (resp. $\tilde{w}_{0,i}$) provide $O(\text{polylog}(n)/n)$ approximations of the full minimizers $\hat{w}$ (resp. $\hat{w}_0$) in Euclidean norm. We start from the following approximation results for the first-stage estimator:

**Proposition B.1.** (Approximations of the first-stage estimator) For any $k \in \mathbb{N}$,

$$ \sup_{i \in [n]} \|\hat{w}_0 - \tilde{w}_{0,i}\| = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right). $$

We also have

$$ \sup_{i \in [n]} \|\tilde{w}_{0,i} - \hat{w}_{0, \setminus i}\| = \sup_{i \in [n]} \|\xi_i\| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

Furthermore, at the level of the residuals,

$$ \sup_{i \in [n]} \sup_{j \neq i} |u_{j, \setminus i} - u_j| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

and

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

and finally

$$ \sup_{i \in [n]} \sup_{j \neq i} |\tilde{u}_{j, i} - u_{j, \setminus i}| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

The following Lemma is a direct consequence of Proposition B.1, and complements it for the cross terms

**Lemma B.2.** We have

$$ \sup_{i \in [n]} \sum_{j \neq i} (u_j - \tilde{u}_{j, i})^2 = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right). $$

*Proof.* Note that we can rewrite more compactly

$$ \begin{aligned} \sqrt{\sup_{i \in [n]} \sum_{j \neq i} (u_j - \tilde{u}_{j, i})^2} &= \sup_{i \in [n]} \|X_{\setminus i}(\hat{w}_0 - \tilde{w}_{0, i})\| \le \sup_{i \in [n]} \frac{\|X_{\setminus i}\|}{\sqrt{n}} \sqrt{n} \sup_{i \in [n]} \|\hat{w}_0 - \tilde{w}_{0, i}\| \\ &= \sup_{i \in [n]} \frac{\|X_{\setminus i}\|}{\sqrt{n}} O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) \end{aligned} $$

using Proposition B.1 for the last step. The control of the remaining term follows from Lemma F.5 and yields $\sup_{i \in [n]} \|X_{\setminus i}\|/\sqrt{n} = O_{L_k}(\text{polylog}(n))$, completing the proof. □

Note that Proposition B.1 does not immediately follow from El Karoui [2018], as the latter in particular assumes the samples to have zero mean, and a simpler structure of the losses.
Remark B.3. It is an important observation that the proof of Proposition B.1 in fact follows from the one reported below for the second-stage ERM. To see this, formally introduce an additional trivial ERM with zero loss $\ell_{-1,j}(\cdot) = 0$ and $\lambda_{-1} = 1$. In particular, this loss satisfies the set of assumptions A.2. The resulting weight minimizer is trivially zero $\hat{w}_{-1} = 0_d$. The first-stage ERM can then be viewed as a ERM which depends on the (vanishing) predictions of this trivial ERM, and the proof below applies, exchanging the roles of the first-stage / second-stage ERM sequence with the trivial/first-stage ERM sequence. Note that there is no circularity in this argument, as Proposition B.1 trivially holds for $\ell_{-1,j}(\cdot) = 0$ and $\lambda_{-1} = 1$. Therefore the following proof can be applied first to prove Proposition B.1 for the first-stage estimator, which can then in turn be used as a starting point for the second-stage estimator, following a direct re-application of the proof.

## B.2 Second-stage estimator

We now turn to establishing a similar approximation result between the second-stage estimator $\hat{w}$ and its surrogate $\tilde{w}_i$ and leave-one-out $\hat{w}_{\setminus i}$ approximations.

**Lemma B.4.** The distance between the full and surrogate estimators admits the upper bound

$$ \sup_{i \in [n]} \|\hat{w} - \tilde{w}_i\| \le \frac{1}{\lambda} \sup_{i \in [n]} \left\| \nabla \tilde{\mathcal{R}}_i(\tilde{w}_i) \right\| + \frac{1}{\lambda} \|\partial_r \partial_u \ell\|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) $$

*Proof.* We have

$$ \begin{aligned} \nabla \tilde{\mathcal{R}}_i(\tilde{w}_i) &= \nabla \tilde{\mathcal{R}}_i(\tilde{w}_i) - \nabla \tilde{\mathcal{R}}_i(\hat{w}) \\ &= \frac{1}{n} \sum_{j \in [n]} \left[ \partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) \langle \tilde{w}_i - \hat{w}, x_j \rangle + \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_j) \right] x_j + \lambda(\tilde{w}_i - \hat{w}), \end{aligned} $$

for some $(\tilde{r}_{j,i}, \tilde{u}_{j,i})$ lying on the segment connecting $(\tilde{r}_{j,i}, \tilde{u}_{j,i})$ and $(r_{j,\setminus i}, u_{j,\setminus i})$. Introducing

$$ \tilde{H} = \frac{1}{n} \sum_{j \in [n]} \partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j x_j^\top + \lambda I_d $$

one can write

$$ \tilde{w}_i - \hat{w} = \tilde{H}^{-1} \left[ \nabla \tilde{\mathcal{R}}_i(\tilde{w}_i) + \frac{1}{n} \partial_r \partial_u \ell_j(\tilde{r}_{i,i}, \tilde{u}_{i,i}) (\tilde{u}_{i,i} - u_i) x_i + \frac{1}{n} \sum_{j \neq i} \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_j) x_j \right] $$

The first term can be simply controlled as

$$ \sup_{i \in [n]} \left\| \tilde{H}^{-1} \nabla \tilde{\mathcal{R}}_i(\tilde{w}_i) \right\| \le \frac{1}{\lambda} \sup_{i \in [n]} \left\| \nabla \tilde{\mathcal{R}}_i(\tilde{w}_i) \right\|. $$

The second term can be upper-bounded as

$$ \sup_{i \in [n]} \left\| \frac{1}{n} \partial_r \partial_u \ell_j(\tilde{r}_{i,i}, \tilde{u}_{i,i}) (\tilde{u}_{i,i} - u_i) \tilde{H}^{-1} x_j \right\| \le \frac{1}{\sqrt{n}\lambda} \|\partial_r \partial_u \ell\|_{\infty} \sup_{i \in [n]} \frac{\|x_i\|}{\sqrt{n}} O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

using Proposition B.1. Using Lemma F.5, $\sup_{i \in [n]} \|x_i\|/\sqrt{n} = O_{L_k}(\text{polylog}(n))$. Thus,

$$ \sup_{i \in [n]} \left\| \frac{1}{n} \partial_r \partial_u \ell_j(\tilde{r}_{i,i}, \tilde{u}_{i,i}) (\tilde{u}_{i,i} - u_i) \tilde{H}^{-1} x_j \right\| = \frac{1}{\lambda} \|\partial_r \partial_u \ell\|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right). $$
Finally, defining $h_i \in \mathbb{R}^{(n-1) \times d}$ with entries $h_{i,j} = \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i})(\tilde{u}_{j,i} - u_j)$, the third term can be written as

$$ \sup_{i \in [n]} \left\| \frac{1}{n} \sum_{j \neq i} \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_j) \tilde{H}^{-1} x_j \right\| = \frac{1}{n} \left\| \tilde{H}^{-1} X_{\setminus i}^{\top} h_i \right\| \le \frac{1}{\sqrt{n} \lambda} \sup_{i \in [n]} \frac{\| X_{\setminus i} \|}{\sqrt{n}} \sup_{i \in [n]} \| h_i \|. $$

From Lemma F.5, $\sup_{i \in [n]} \|X_{\setminus i}\| / \sqrt{n} = O_{L_k}(\text{polylog}(n))$. Furthermore,

$$ \sup_{i \in [n]} \|h_i\| \le \|\partial_r \partial_u \ell\|_{\infty} \sqrt{\sup_{i \in [n]} \sum_{j \neq i} (\tilde{u}_{j,i} - u_j)^2} = \|\partial_r \partial_u \ell\|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

Thus,

$$ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_j) \tilde{H}^{-1} x_j \right\| = \frac{1}{\lambda} \| \partial_r \partial_u \ell \|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right), $$

which concludes the proof. □

**Lemma B.5.** We have $\nabla \tilde{\mathcal{R}}(\tilde{w}_i) = \Delta_i^{(1)} + \Delta_i^{(2)}$ where

$$ \Delta_i^{(1)} = \frac{1}{n} \sum_{j \neq i} \left[ \partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r^2 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \right] x_j x_j^{\top} (\eta_i + \zeta_i), $$

$$ \Delta_i^{(2)} = \frac{1}{n} \sum_{j \neq i} \left[ \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \right] (\tilde{u}_{j,i} - u_{j,\setminus i}) x_j, $$

where $\tilde{r}_{j,i}$ (resp. $\tilde{u}_{j,i}$) belongs to the unordered interval $(\tilde{r}_{j,i}, r_{j,\setminus i})$ (resp. $(\tilde{u}_{j,i}, u_{j,\setminus i})$).

*Proof.* Starting from the identity $\nabla \hat{\mathcal{R}}_{\setminus i}(\hat{w}_{\setminus i})$, one reaches

$$ \begin{aligned} \nabla \hat{\mathcal{R}}(\tilde{w}_i) &= \nabla \hat{\mathcal{R}}(\tilde{w}_i) - \nabla \hat{\mathcal{R}}_{\setminus i}(\hat{w}_{\setminus i}) \\ &= \frac{1}{n} \partial_r \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) x_i + \frac{1}{n} \sum_{j \neq i} \left[ \partial_r \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \right] x_j + \lambda(\eta_i + \zeta_i) \end{aligned} $$

From a Taylor expansion, the second term reads

$$ \begin{aligned} & \frac{1}{n} \sum_{j \neq i} \left[ \partial_r \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \right] x_j \\ &= \frac{1}{n} \sum_{j \neq i} \left[ \partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) \langle x_j, \eta_i + \zeta_i \rangle + \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_{j,\setminus i}) \right] x_j \\ &= \frac{1}{n} \sum_{j \neq i} \left[ \partial_r^2 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \langle x_j, \eta_i + \zeta_i \rangle + \partial_r \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{u}_{j,i} - u_{j,\setminus i}) \right] x_j + \Delta_i^{(1)} + \Delta_i^{(2)}, \end{aligned} $$

with $(\tilde{r}_{j,i}, \tilde{u}_{j,i})$ lying on the segment connecting $(\tilde{r}_{j,i}, \tilde{u}_{j,i})$ and $(r_{j,\setminus i}, u_{j,\setminus i})$. Thus

$$ \begin{aligned} \nabla \hat{\mathcal{R}}(\tilde{w}_i) &= \frac{1}{n} \partial_r \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) x_i + \Delta_i^{(1)} + \Delta_i^{(2)} + H_{\setminus i}(\eta_i + \zeta_i) - \frac{1}{n} \partial_u \ell_{0,i}(\tilde{u}_{i,i}) G_{\setminus i} H_{0,\setminus i}^{-1} x_i \\ &= \Delta_i^{(1)} + \Delta_i^{(2)}, \end{aligned} $$

using the definitions of $\eta_i, \zeta_i$. □
**Control of** $\sup_{i \in [n]} ||\Delta_i^{(1)}||$ — We first aim to bound the first correction $\sup_{i \in [n]} ||\Delta_i^{(1)}||$. Introducing the diagonal matrix $\Lambda \in \mathbb{R}^{(n-1) \times (n-1)}$ with elements $\Lambda_{jj} = \partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r^2 \ell_j(r_{j,\setminus i}, u_{j,\setminus i})$, one has

$$ 
\begin{align*}
& \sup_{i \in [n]} ||\Delta_i^{(1)}|| \\
& \le \sup_{i \in [n]} \frac{1}{n} ||X_{\setminus i}^{\top} \Lambda X_{\setminus i}|| (||\eta_i|| + ||\zeta_i||) \\
& \le \sup_{i \in [n]} \frac{||X_{\setminus i}||^2}{n} \sup_{i \in [n]} \sup_{j \ne i} ||\partial_r^2 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r^2 \ell_j(r_{j,\setminus i}, u_{j,\setminus i})|| \left( \sup_{i \in [n]} ||\eta_i|| + \sup_{i \in [n]} ||\zeta_i|| \right) \\
& \le \left( ||\partial_r^3 \ell||_{\infty} \vee ||\partial_r^2 \partial_u \ell||_{\infty} \right) \sup_{i \in [n]} \frac{||X_{\setminus i}||^2}{n} \left( \sup_{i \in [n]} \sup_{j \ne i} |r_{j,\setminus i} - \tilde{r}_{j,i}| + \sup_{i \in [n]} \sup_{j \ne i} |u_{j,\setminus i} - \tilde{u}_{j,i}| \right) \left( \sup_{i \in [n]} ||\eta_i|| + \sup_{i \in [n]} ||\zeta_i|| \right) \tag{9}
\end{align*}
$$

Lemma F.5 provides control of the first term as $\sup_{i \in [n]} ||X_{\setminus i}||^2/n = O_{L_k}(\text{polylog}(n))$. The control of the last follows from the following lemma.

**Lemma B.6.** We have

$$ \sup_{i \in [n]} ||\eta_i|| \le \frac{||\partial_r \ell||_{\infty}}{\lambda} O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

and

$$ \sup_{i \in [n]} ||\zeta_i|| \le \frac{||\partial_u \ell_0||_{\infty} ||\partial_r \partial_u \ell||_{\infty}}{\lambda_0 \lambda} O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

*Proof.* One has

$$ \sup_{i \in [n]} ||\eta_i|| \le \frac{1}{\sqrt{n}\lambda} ||\partial_r \ell||_{\infty} \sup_{i \in [n]} \frac{||x_i||}{\sqrt{n}} = \frac{||\partial_r \ell||_{\infty}}{\lambda} O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

using Lemma F.5. By the same token, $||\zeta_i||$ can be controlled as

$$ \sup_{i \in [n]} ||\zeta_i|| \le \frac{1}{\sqrt{n}} ||\partial_u \ell_0||_{\infty} \frac{1}{\lambda_0 \lambda} \sup_{i \in [n]} ||G_{\setminus i}|| \sup_{i \in [n]} \frac{||x_i||}{\sqrt{n}}. $$

But

$$ 
\begin{align*}
\sup_{i \in [n]} ||G_{\setminus i}|| &= \sup_{i \in [n]} \left\| \frac{1}{n} \sum_{j \ne i} \partial_r \partial_u \ell(r_{j,\setminus i}, u_{j,\setminus i}) x_j x_j^{\top} \right\| \\
&\le ||\partial_r \partial_u \ell||_{\infty} \sup_{i \in [n]} \frac{||X_{\setminus i}||^2}{n} = ||\partial_r \partial_u \ell||_{\infty} O_{L_k}(\text{polylog}(n)),
\end{align*}
$$

using again Lemma F.5. $\square$

Finally, one needs control of the middle term in (9). The control of $\sup_{i \in [n]} \sup_{j \ne i} |u_{j,\setminus i} - \tilde{u}_{j,i}|$ follows from Lemma C.4 of El Karoui [2018], or equivalently the following proof on a surrogate problem with zero loss, as remarked above.

**Lemma B.7.** For any $k \in [[2 \log(n)])$,

$$ \sup_{i \in [n]} \sup_{j \ne i} |r_{j,\setminus i} - \tilde{r}_{j,i}| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$
Proof. Let us first note that

$$
\begin{align*}
\sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - \tilde{r}_{j, i}| &\le \sup_{i \in [n]} \sup_{j \neq i} |\langle x_j, \eta_i \rangle| + \sup_{i \in [n]} \sup_{j \neq i} |\langle x_j, \zeta_i \rangle| \\
&\le \|\partial_r \ell\|_{\infty} \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{n} \langle x_j, H_{\setminus i}^{-1} x_i \rangle \right| + \|\partial_u \ell_0\|_{\infty} \sup_{i \in [n]} \sup_{j \neq i} \left| \frac{1}{n} \langle x_j, H_{\setminus i}^{-1} G_{\setminus i} H_{0, \setminus i}^{-1} x_i \rangle \right| \tag{10}
\end{align*}
$$

It follows from Lemma F.6 that

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

The second term of (10) admits the same upper bound, since from Lemma F.5 and the proof of Lemma B.6,
on again has
$$ \|H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1}\| = O_{L_k}(\text{polylog}(n)). \text{ Hence returning to (10)}, $$

$$
\sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - \tilde{r}_{j, i}| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

This concludes the proof.

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

Returning to (9) and assembling these intermediary results finally allows to control $\sup_{i \in [n]} \|\Delta_i^{(1)}\|$. This is summarized in the following lemma.

**Lemma B.8.** For any $k \in [\lceil 1/2 \log(n) \rceil]$,

$$
\sup_{i \in [n]} \| \Delta_i^{(1)} \| = O_{L_k} \left( \frac{\text{polylog}(n)}{n^2} \right).
$$

**Control of** $\sup_{i \in [n]} \|\Delta_i^{(2)}\| - $ We now turn to the second correction $\sup_{i \in [n]} \|\Delta_i^{(2)}\|$. It can similarly be bounded along the same steps as $\sup_{i \in [n]} \|\Delta_i^{(1)}\|$.

**Lemma B.9.** For any $k \in [\lceil 1/2 \log(n) \rceil]$,

$$
\sup_{i \in [n]} \| \Delta_i^{(2)} \| = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right).
$$

Proof. Introducing the diagonal matrix $\Lambda \in \mathbb{R}^{(n-1) \times (n-1)}$ with elements $\Lambda_{jj} = \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i})$,

$$
\begin{align*}
\sup_{i \in [n]} \| \Delta_i^{(2)} \| &\le \sup_{i \in [n]} \frac{1}{n} \| X_{\setminus i}^{\top} \Lambda X_{\setminus i} \| \| \partial_u \ell_0 \|_{\infty} \| H_{0, \setminus i}^{-1} x_i \| \\
&\le \sup_{i \in [n]} \frac{\| X_{\setminus i} \|^2}{n} \sup_{i \in [n]} \sup_{j \neq i} \left| \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) - \partial_r \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \right| \sup_{i \in [n]} \| \partial_u \ell_0 \|_{\infty} \frac{1}{n} \| H_{0, \setminus i}^{-1} x_i \| \\
&\le \left( \| \partial_r^2 \partial_u \ell \|_{\infty} \lor \| \partial_r \partial_u^2 \ell \|_{\infty} \right) \sup_{i \in [n]} \frac{\| X_{\setminus i} \|^2}{n} \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j,\setminus i} - \tilde{r}_{j,i}| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j,\setminus i} - \tilde{u}_{j,i}| \right) \\
&\qquad \| \partial_u \ell_0 \|_{\infty} \sup_{i \in [n]} \frac{1}{n} \| H_{0,\setminus i}^{-1} x_i \|
\end{align*}
$$

From Lemma F.5,

$$
\sup_{i \in [n]} \frac{1}{n} \| H_{0, \setminus i}^{-1} x_i \| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), \quad \sup_{i \in [n]} \frac{\| X_{\setminus i} \|^2}{n} = O_{L_k} \left( \text{polylog}(n) \sqrt{n} \right)
$$
From the proof of Lemma B.8, for any $k \in [[2\log(n)])$

$$ \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - \tilde{r}_{j, i}| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j, \setminus i} - \tilde{u}_{j, i}| \right) = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

The result follows from combining these bounds.

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

One is finally in a position to write the equivalent of Proposition B.1 for the residuals of the second-stage problem.

**Proposition B.10** (Approximations of the second-stage estimator). For any $k \in \mathbb{N}$,

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

Furthermore, at the level of the residuals,

$$ \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - r_j| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

and

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

*Proof.* The first point follows from combining Lemma B.2, Lemma B.5, Lemma B.8 and Lemma B.9. The second point follows from Lemma F.5 and the Cauchy-Schwartz inequality as

$$ \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - r_j| \le \sup_{j \in [n]} \|x_j\| \sup_{i \in [n]} \|\hat{w} - \tilde{w}_i\| + \sup_{i \in [n]} \sup_{j \neq i} |\langle x_j, \eta_i + \zeta_i \rangle| \\ = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

We remind that the term $\sup_{j \neq i} |\langle x_j, \eta_i + \zeta_i \rangle|$ was bounded in Lemma B.7. The last point follows from Lemma F.5 and the Cauchy-Schwartz inequality:

$$ \sup_{i \in [n]} |r_i - \tilde{r}_{i, i}| \le \sup_{i \in [n]} \|x_i\| \sup_{i \in [n]} \|\hat{w} - \tilde{w}_i\| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

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

*Remark B.11.* One also has

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

and

$$ \sup_{i \in [n]} \|\hat{w} - \tilde{w}_{\setminus i}\| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

*Proof.* The first point follows from $\|\tilde{w}_i - \hat{w}_{\setminus i}\| \le \|\eta_i\| + \|\zeta_i\|$ and Lemma B.6. The second point follows from the first and Proposition B.10 with the triangle inequality. □

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

As for the base case, the following Lemma follows from Proposition B.10 as a corollary.

**Lemma B.12.** We have

$$ \sup_{i \in [n]} \sum_{j \neq i} (r_j - \tilde{r}_{j, i})^2 = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right). $$

*Proof.* The proof is identical to that of Lemma B.2. □

<figure><img src="image_11.png" /></figure>
C Concentration of the summary statistics

We now show the concentration of the summary statistics $\mathfrak{m}_c = \langle \hat{w}, \mu_c \rangle$, $\mathfrak{h} = \langle \hat{w}, \beta \rangle$, $\mathfrak{t} = \langle \hat{w}, \hat{w}_0 \rangle$, $\mathfrak{q} = \|\hat{w}\|^2$ and $\gamma_i = 1/nx_i^\top H_{\backslash i}^{-1} x_i$, $\mathfrak{V} = 1/n \text{tr}[H_{\backslash i}^{-1}]$, $v_i = 1/n H_{\backslash i}^{-1} G_{\backslash i} H_{0, \backslash i}^{-1} x_i$, $\mathfrak{X} = 1/n \text{tr}[H^{-1} G H_0^{-1}]$. We reserve the gothic letters to denote random variables, and will later adopt normal font for their respective deterministic equivalents in $L_2$.

**Lemma C.1** ($\mathfrak{m}_c$ concentrates). For any $c \in \mathcal{V}$, $\mathfrak{m}_c = \langle \hat{w}, \mu_c \rangle$ concentrates in $L_2$, namely

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

*Proof.* From the Efron-Stein lemma [Efron and Stein, 1981],

$$ \begin{aligned} \mathrm{Var}[\mathfrak{m}_c] &\le \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \hat{w} - \hat{w}_{\backslash i}, \mu_c \rangle \right)^2 \right] \\ &\le 2 \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \hat{w} - \tilde{w}_i, \mu_c \rangle \right)^2 \right] + 2 \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \tilde{w}_i - \hat{w}_{\backslash i}, \mu_c \rangle \right)^2 \right] \end{aligned} $$

The first term can be controlled using the Cauchy-Schwartz inequality and Proposition B.10.

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \hat{w} - \tilde{w}_i, \mu_c \rangle \right)^2 \right] \le \sum_{i \in [n]} \mathbb{E} \left[ M \| \hat{w} - \tilde{w}_i \|^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right). $$

Now recalling that

$$ \langle \tilde{w}_i - \hat{w}_{\backslash i}, \mu_c \rangle^2 \le 2 \langle \eta_i, \mu_c \rangle^2 + 2 \langle \zeta_i, \mu_c \rangle^2, $$

we focus on bounding $\langle \eta_i, \mu_c \rangle$, $\langle \zeta_i, \mu_c \rangle$. Since

$$ \langle \eta_i, \mu_c \rangle^2 \le \| \partial_r \ell \|_{\infty}^2 \frac{1}{n^2} \mu_c^{\top} H_{\backslash i}^{-1} x_i x_i^{\top} H_{\backslash i}^{-1} \mu_c, $$

one has

$$ \mathbb{E} \left[ \langle \eta_i, \mu_c \rangle^2 \right] \le \| \partial_r \ell \|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{\backslash i}^{-1} \mu_c \right\|^2 \right] \le \| \partial_r \ell \|_{\infty}^2 \frac{M}{\lambda^2 n^2}. $$

By the same token,

$$ \mathbb{E} \left[ \langle \zeta_i, \mu_c \rangle^2 \right] \le \| \partial_u \ell_0 \|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{0 \backslash i}^{-1} G_{\backslash i} H_{\backslash i}^{-1} \mu_c \right\|^2 \right] \le \frac{M \| \partial_u \ell_0 \|_{\infty}^2}{\lambda^2 \lambda_0^2 n_2} \mathbb{E} \left[ \left\| G_{\backslash i} \right\|^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n^2} \right), $$

since we showed in Lemma B.6 that $\|G_{\backslash i}\| = O_{L_k}(\mathrm{polylog}(n))$. Thus,

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left\langle \tilde{w}_i - \hat{w}_{\backslash i}, \mu_c \right\rangle^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right), $$

completing the proof. $\square$

The following concentration result for $\mathfrak{h}$ can be established using an identical proof, substituting $\mu_c$ for $\beta$.

**Lemma C.2** ($\mathfrak{h}$ concentrates). $\mathfrak{h} = \langle \hat{w}, \beta \rangle$ concentrates in $L_2$, namely

$$ \mathrm{Var}[\mathfrak{h}] = O\left(\frac{\mathrm{polylog}(n)}{n}\right). $$
Establishing a similar result for t requires a more careful analysis, since $\hat{w}_0$ is a stochastic vector that depends on the samples.

**Lemma C.3 (t concentrates).** $t = \langle \hat{w}, \hat{w}_0 \rangle$ concentrates in $L_2$, namely

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

*Proof.* From the Efron-Stein lemma,

$$ \begin{aligned} \mathrm{Var}[t] &\le \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \hat{w}, \hat{w}_0 \rangle - \langle \hat{w}_{\setminus i}, \hat{w}_{0, \setminus i} \rangle \right)^2 \right] \\ &\le 5 \sum_{i \in [n]} \mathbb{E} \left[ \langle \hat{w} - \tilde{w}_i, \hat{w}_{0, \setminus i} \rangle^2 + \langle \hat{w}_{\setminus i} - \tilde{w}_i, \hat{w}_{0, \setminus i} \rangle^2 + \langle \hat{w}_{\setminus i}, \hat{w}_0 - \tilde{w}_{0, i} \rangle^2 + \langle \hat{w}_{\setminus i}, \hat{w}_{0, \setminus i} - \tilde{w}_{0, i} \rangle^2 + \langle \hat{w}_{0, \setminus i} - \tilde{w}_0, \hat{w}_{\setminus i} - \tilde{w}_i \rangle^2 \right] \end{aligned} $$

From the Cauchy-Schwartz inequality, Proposition B.10 and Lemma F.2,

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \hat{w} - \tilde{w}_i, \hat{w}_{0, \setminus i} \rangle \right)^2 \right] \le \sum_{i \in [n]} \mathbb{E} \left[ \left\| \hat{w}_{0, \setminus i} \right\|^2 \| \hat{w} - \tilde{w}_i \|^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right). $$

From the Cauchy-Schwartz inequality, Proposition B.1 and Lemma F.3,

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left( \langle \hat{w}_0 - \tilde{w}_{0,i}, \hat{w}_{\setminus i} \rangle \right)^2 \right] \le \sum_{i \in [n]} \mathbb{E} \left[ \left\| \hat{w}_{\setminus i} \right\|^2 \| \hat{w}_0 - \tilde{w}_{0,i} \|^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right). $$

The last term can simply be controlled from the Cauchy-Schwartz inequality, and Remark B.11:

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left\langle \hat{w}_{0, \setminus i} - \hat{w}_0, \hat{w}_{\setminus i} - \hat{w} \right\rangle^2 \right] \le \sum_{i \in [n]} \mathbb{E} \left[ \left\| \hat{w}_{0, \setminus i} - \hat{w}_0 \right\|^2 \left\| \hat{w}_{\setminus i} - \hat{w} \right\|^2 \right] = O \left( \frac{1}{n} \right) $$

Now recalling that

$$ \langle \tilde{w}_i - \hat{w}_{\setminus i}, \hat{w}_{0, \setminus i} \rangle^2 \le 2 \langle \eta_i, \hat{w}_{0, \setminus i} \rangle^2 + 2 \langle \zeta_i, \hat{w}_{0, \setminus i} \rangle^2, $$

we focus on bounding $\langle \eta_i, \hat{w}_{0, \setminus i} \rangle, \langle \zeta_i, \hat{w}_{0, \setminus i} \rangle$. Since

$$ \langle \eta_i, \hat{w}_{0, \setminus i} \rangle^2 \le \| \partial_r \ell \|_{\infty}^2 \frac{1}{n^2} \hat{w}_{0, \setminus i}^{\top} H_{\setminus i}^{-1} x_i x_i^{\top} H_{\setminus i}^{-1} \hat{w}_{0, \setminus i}, $$

one has from Lemma F.2

$$ \mathbb{E} \left[ \left\langle \eta_i, \hat{w}_{0, \setminus i} \right\rangle^2 \right] \le \| \partial_r \ell \|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{\setminus i}^{-1} \hat{w}_{0, \setminus i} \right\|^2 \right] \le \| \partial_r \ell \|_{\infty}^2 \frac{1}{\lambda^2 n^2} O(\mathrm{polylog}(n)). $$

By the same token,

$$ \begin{aligned} \mathbb{E} \left[ \left\langle \zeta_i, \hat{w}_{0, \setminus i} \right\rangle^2 \right] &\le \| \partial_u \ell_0 \|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{0, \setminus i}^{-1} G_{\setminus i} H_{\setminus i}^{-1} \hat{w}_{0, \setminus i} \right\|^2 \right] \\ &\le \frac{\| \partial_u \ell_0 \|_{\infty}^2}{\lambda^2 \lambda_0^2 n_2} \mathbb{E} \left[ \left\| G_{\setminus i} \right\|^2 \left\| \hat{w}_{0, \setminus i} \right\|^2 \right] \\ &= O \left( \frac{\mathrm{polylog}(n)}{n^2} \right), \end{aligned} $$

since we showed in Lemma B.6 that $\|G_{\setminus i}\| = O_{L_k}(\mathrm{polylog}(n))$. Thus,

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left\langle \tilde{w}_i - \hat{w}_{\setminus i}, \hat{w}_{0, \setminus i} \right\rangle^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right). $$
Finally, let us analyze similarly the last term

$$ \langle \hat{w}_{\setminus i}, \hat{w}_0 - \tilde{w}_{0,i} \rangle^2 = \langle \hat{w}_{\setminus i}, \frac{1}{n} \partial_u \ell_0(\tilde{u}_{i,i}) H_{0,\setminus i}^{-1} x_i \rangle^2 $$

Thus,

$$ \mathbb{E} \left[ \left\langle \hat{w}_{\setminus i}, \hat{w}_0 - \tilde{w}_{0,i} \right\rangle^2 \right] \le \|\partial_u \ell_0\|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{0,\setminus i}^{-1} \hat{w}_{\setminus i} \right\|^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n^2} \right). $$

Therefore, finally,

$$ \sum_{i \in [n]} \mathbb{E} \left[ \left\langle \hat{w}_{\setminus i}, \hat{w}_0 - \tilde{w}_{0,i} \right\rangle^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n} \right), $$

completing the proof.

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

**Lemma C.4 (q concentrates).** $q = \|\hat{w}\|^2$ concentrates in $L_2$, namely

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

*Proof.* Once more appealing to the Efron-Stein lemma,

$$ \begin{aligned} \mathrm{Var}[q] &\le \sum_{i \in [n]} \mathbb{E} \left[ \left( \|\hat{w}\|^2 - \|\hat{w}_{\setminus i}\|^2 \right)^2 \right] \\ &\le 2 \sum_{i \in [n]} \mathbb{E} \left[ \left( \|\hat{w}\|^2 - \|\tilde{w}_i\|^2 \right)^2 \right] + \mathbb{E} \left[ \left( \|\tilde{w}_i\|^2 - \|\hat{w}_{\setminus i}\|^2 \right)^2 \right]. \end{aligned} $$

But

$$ \left( \|\hat{w}\|^2 - \|\tilde{w}_i\|^2 \right)^2 \le \|\hat{w} - \tilde{w}_i\|^2 \left( \|\hat{w}\| + \|\tilde{w}_i\| \right)^2 = O_{L_k} \left( \frac{\mathrm{polylog}(n)}{n^2} \right), $$

using Proposition B.10 and Lemma F.3. By the same token,

$$ \|\tilde{w}_i\|^2 - \|\hat{w}_{\setminus i}\|^2 \le 2\|\eta_i\|^2 + 2\|\zeta_i\|^2 + 2 \langle \hat{w}_{\setminus i}, \eta_i + \zeta_i \rangle = 2 \langle \hat{w}_{\setminus i}, \eta_i + \zeta_i \rangle + O_{L_k} \left( \frac{\mathrm{polylog}(n)}{n} \right), $$

using Lemma B.6. Furthermore, one has

$$ \mathbb{E} \left[ \left\langle \eta_i, \hat{w}_{\setminus i} \right\rangle^2 \right] \le \|\partial_r \ell\|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{\setminus i}^{-1} \hat{w}_{\setminus i} \right\|^2 \right] \le \|\partial_r \ell\|_{\infty}^2 \frac{1}{\lambda^2 n^2} O_{L_k} (\mathrm{polylog}(n)) $$

and By the same token,

$$ \begin{aligned} \mathbb{E} \left[ \left\langle \zeta_i, \hat{w}_{\setminus i} \right\rangle^2 \right] &\le \|\partial_u \ell_0\|_{\infty}^2 \frac{1}{n^2} \mathbb{E} \left[ \left\| H_{0,\setminus i}^{-1} G_{\setminus i} H_{\setminus i}^{-1} \hat{w}_{\setminus i} \right\|^2 \right] \\ &\le \frac{\|\partial_u \ell_0\|_{\infty}^2}{\lambda^2 \lambda_0^2 n_2} \mathbb{E} \left[ \left\| G_{\setminus i} \right\|^2 \left\| \hat{w}_{\setminus i} \right\|^2 \right] \\ &= O \left( \frac{\mathrm{polylog}(n)}{n^2} \right), \end{aligned} $$

Thus,

$$ \mathbb{E} \left[ \left( \|\tilde{w}_i\|^2 - \|\hat{w}_{\setminus i}\|^2 \right)^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n^2} \right), $$

concluding the proof.

<figure><img src="image_13.png" /></figure>
**Lemma C.5 (V concentrates).** We remind $\gamma_i = 1/nx_i^\top H_{\backslash i}^{-1}x_i$, $\mathfrak{V} = \frac{1}{n}\text{tr}[H^{-1}]$. $\gamma_i$ admits an equivalent

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

Furthermore, $\mathfrak{V}$ concentrates, with

$$ \text{Var}[\mathfrak{V}] = O\left(\frac{\text{polylog}(n)}{n}\right). $$

*Proof.* We begin by proving the first point. First note that the means bring negligible contributions to $\gamma_i$:

$$ \gamma_i = \frac{\mu_{c_i}^\top H_{\backslash i}^{-1} \mu_{c_i}}{n} + \frac{z_i^\top H_{\backslash i}^{-1} \mu_{c_i}}{n} + \frac{z_i^\top H_{\backslash i}^{-1} z_i}{n} = \frac{z_i^\top H_{\backslash i}^{-1} z_i}{n} + O_{L_k}\left(\frac{\text{polylog}(n)}{\sqrt{n}}\right), $$

using Cauchy-Schwartz bounds and the bound on $\sup_{i \in [n]} \|x_i\|/\sqrt{n}$ of Lemma F.5. From Lemma G.2 of El Karoui [2018], defining $\mathfrak{V}_{\backslash i} = \frac{1}{n}\text{tr}[H_{\backslash i}^{-1}]$, one has the bound

$$ \sup_{i \in [n]} \left| \frac{z_i^\top H_{\backslash i}^{-1} z_i}{n} - \mathfrak{V}_{\backslash i} \right| = O_{L_k}\left( \frac{\text{polylog}(n)}{\lambda \sqrt{n}} \right). $$

It now remains to control $|\mathfrak{V}_{\backslash i} - \mathfrak{V}|$. We start from the identity

$$ \begin{aligned} \mathfrak{V} - \mathfrak{V}_{\backslash i} &= \frac{1}{n} \text{tr} \left[ H^{-1} \left( H_{\backslash i}^{-1} - H^{-1} \right) H_{\backslash i}^{-1} \right] \\ &= -\frac{1}{n} \partial_r^2 \ell_i(r_i, u_i) \frac{x_i^\top H_{\backslash i}^{-1} H^{-1} x_i}{n} - \frac{1}{n} \sum_{j \neq i} \left( \partial_r^2 \ell_j(r_j, u_j) - \partial_r^2 \ell_j(r_{j, \backslash i}, u_{j, \backslash i}) \right) \frac{x_j^\top H_{\backslash i}^{-1} H^{-1} x_j}{n}. \end{aligned} $$

The first term can be simply controlled as

$$ \left| \frac{1}{n} \partial_r^2 \ell_i(r_i, u_i) \frac{x_i^\top H_{\backslash i}^{-1} H^{-1} x_i}{n} \right| \le \left\| \partial_r^2 \ell \right\|_{\infty} \frac{1}{\lambda^2} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right), $$

using Lemma F.5. The second term can be bounded as

$$ \left| \frac{1}{n} \sum_{j \neq i} \left( \partial_r^2 \ell_j(r_j, u_j) - \partial_r^2 \ell_j(r_{j, \backslash i}, u_{j, \backslash i}) \right) \frac{x_j^\top H_{\backslash i}^{-1} H^{-1} x_j}{n} \right| \\ \le \left( \left\| \partial_r^3 \ell \right\|_{\infty} \lor \left\| \partial_r^2 \partial_u \ell \right\|_{\infty} \right) \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \backslash i} - r_j| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j, \backslash i} - u_j| \right) \frac{1}{\lambda^2} \sup_{j \in [n]} \frac{\|x_j\|^2}{n} = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

using in the last step Proposition B.1, Proposition B.10 and Lemma F.5. This concludes the proof of the first point. Establishing the second point requires to reach a finer control of $|\mathfrak{V}_{\backslash i} - \mathfrak{V}|$. The reasoning follows closely that of Lemma 11 in Barnfield et al. [2025]. Starting again from the Efron-Stein lemma,

$$ \text{Var}[\mathfrak{V}] \le \sum_{i \in [n]} \mathbb{E} \left[ (\mathfrak{V} - \mathfrak{V}_{\backslash i})^2 \right] \le 2 \sum_{i \in [n]} \left( \mathbb{E} \left[ (\mathfrak{V} - \tilde{\mathfrak{V}}_i)^2 \right] + \mathbb{E} \left[ (\tilde{\mathfrak{V}}_i - \mathfrak{V}_{\backslash i})^2 \right] \right), $$
we introduce $\tilde{\mathfrak{W}}_i = 1/n \operatorname{tr}[\tilde{H}_i]$ as the normalized trace of the surrogate Hessian. We first focus on $\mathbb{E}[(\mathfrak{W} - \tilde{\mathfrak{W}}_i)^2]$.

$$
\begin{aligned}
\mathfrak{W} - \tilde{\mathfrak{W}}_i &= \operatorname{tr} \left[ H^{-1} \left( \tilde{H}_i^{-1} - H^{-1} \right) \tilde{H}_i^{-1} \right] \\
&= \frac{1}{n} \sum_{j \in [n]} \left( \partial_r^2 \ell_j (r_j, u_j) - \partial_r^2 \ell_j (\tilde{r}_{j,i}, \tilde{u}_{j,i}) \right) \frac{x_j^\top \tilde{H}_i^{-1} H^{-1} x_j}{n} \\
&= \frac{1}{n} \sum_{j \in [n]} \left( \partial_r^3 \ell_j (\tilde{r}_{j,i}, \tilde{u}_{j,i}) (r_j - \tilde{r}_{j,i}) + \partial_r^2 \partial_u \ell_j (\tilde{r}_{j,i}, \tilde{u}_{j,i}) (u_j - \tilde{u}_{j,i}) \right) \frac{x_j^\top \tilde{H}_i^{-1} H^{-1} x_j}{n}
\end{aligned}
$$

for some $\tilde{r}_{j,i}, \tilde{u}_{j,i}$ lying on the segment connecting $\tilde{r}_{j,i}, \tilde{u}_{j,i}$ and $r_j, u_j$, from the mean value theorem. Let us introduce the vectors $h^r \in \mathbb{R}^n, h^u \in \mathbb{R}^n$, with entries $h_j^r = \partial_r^3 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j^\top \tilde{H}_i^{-1} H^{-1} x_j/n$ and $h_j^u = \partial_r^2 \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j^\top \tilde{H}_i^{-1} H^{-1} x_j/n$. Similarly, let $\delta_r, \delta_u \in \mathbb{R}^n$ with entries $\delta_{r,j} = (r_j - \tilde{r}_{j,i})$ and $\delta_{u,j} = (u_j - \tilde{u}_{j,i})$. Then $\mathfrak{W} - \tilde{\mathfrak{W}}_i$ can be more compactly rewritten as

$$ |\mathfrak{W} - \tilde{\mathfrak{W}}_i| \le \frac{1}{n} |\langle h^r, \delta_r \rangle| + \frac{1}{n} |\langle h^u, \delta_u \rangle| \le \frac{1}{n} (\|h^r\|\|\delta^r\| + \|h^u\|\|\delta^u\|) $$

From Lemma B.2 and Lemma B.12, $\|\delta^r\|, \|\delta^u\| = O_{L_k}(\operatorname{polylog}(n)/\sqrt{n})$. In parallel,

$$
\begin{aligned}
\|h^r\| &\le \sqrt{n} \frac{\|\partial_r^3 \ell\|_{\infty}}{\lambda^2} \sup_{j \in [n]} \frac{\|x_j\|}{\sqrt{n}} = O_{L_k}(\sqrt{n}\operatorname{polylog}(n)), \\
\|h^u\| &\le \sqrt{n} \frac{\|\partial_r^2 \partial_u \ell\|_{\infty}}{\lambda^2} \sup_{j \in [n]} \frac{\|x_j\|}{\sqrt{n}} = O_{L_k}(\sqrt{n}\operatorname{polylog}(n)).
\end{aligned}
$$

Thus $|\mathfrak{W} - \tilde{\mathfrak{W}}_i| = O_{L_k}(\operatorname{polylog}(n)/n)$ and

$$ 2 \sum_{i \in [n]} \mathbb{E}[(\mathfrak{W} - \tilde{\mathfrak{W}}_i)^2] = O_{L_k} \left( \frac{\operatorname{polylog}(n)}{n} \right). $$

We now turn to the term $\mathbb{E}[(\tilde{\mathfrak{W}}_i - \mathfrak{W}_{\setminus i})^2]$. $\tilde{\mathfrak{W}}_i - \mathfrak{W}_{\setminus i}$ can be decomposed as

$$
\begin{aligned}
\tilde{\mathfrak{W}}_i - \mathfrak{W}_{\setminus i} &= \frac{1}{n} \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \frac{x_i^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_i}{n} \\
&\quad + \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j (r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{r}_{j,i} - r_{j,\setminus i}) + \partial_r^2 \partial_u \ell_j (r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{u}_{j,i} - u_{j,\setminus i}) \right) \frac{x_j^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_j}{n} \\
&\quad + \frac{1}{2n} \sum_{j \neq i} \left( \partial_r^4 \ell_j (\tilde{r}_{j,i}, \tilde{u}_{j,i})^2 (\tilde{r}_{j,i} - r_{j,\setminus i})^2 + \partial_r^2 \partial_u^2 \ell_j (\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_{j,\setminus i})^2 \right. \\
&\qquad \left. + 2 \partial_r^3 \partial_u \ell_j (\tilde{r}_{j,i}, \tilde{u}_{j,i}) (\tilde{u}_{j,i} - u_{j,\setminus i}) (\tilde{r}_{j,i} - r_{j,\setminus i}) \right) \frac{x_j^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_j}{n}.
\end{aligned}
\quad (11)
$$

using a second-order Taylor expansion, for $(\tilde{r}_{j,i}, \tilde{u}_{j,i})$ lying on the line connecting $\tilde{r}_{j,i}, \tilde{u}_{j,i}$ and $r_{j,\setminus i}, u_{j,\setminus i}$. The control of the first term follows from classical arguments

$$ \left| \frac{1}{n} \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \frac{x_i^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_i}{n} \right| = \left\| \partial_r^2 \ell \right\|_{\infty} \frac{1}{\lambda^2} O_{L_k} \left( \frac{\operatorname{polylog}(n)}{n} \right). $$
The control of the last term follows from Propositions B.1 and B.10 and Lemma 10:

$$ \left| \frac{1}{2n} \sum_{j \neq i} \partial_r^4 \ell_j (r_{j, \setminus i}, u_{j, \setminus i})^2 (\tilde{r}_{j, i} - r_{j, \setminus i})^2 \frac{x_j^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_j}{n} \right| \le \| \partial_r^4 \ell \|_{\infty} \frac{1}{2\lambda^2} \left( \sup_{j \neq i} \frac{\|x_j\|}{\sqrt{n}} \sup_{j \neq i} |\tilde{r}_{j, i} - r_{j, \setminus i}| \right)^2 \\ = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) $$

and

$$ \left| \frac{1}{2n} \sum_{j \neq i} \partial_r^2 \partial_u^2 \ell_j (r_{j, \setminus i}, u_{j, \setminus i})^2 (\tilde{u}_{j, i} - u_{j, \setminus i})^2 \frac{x_j^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_j}{n} \right| \le \| \partial_r^2 \partial_u^2 \ell \|_{\infty} \frac{1}{2\lambda^2} \left( \sup_{j \neq i} \frac{\|x_j\|}{\sqrt{n}} \sup_{j \neq i} |\tilde{u}_{j, i} - u_{j, \setminus i}| \right)^2 \\ = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) $$

and

$$ \left| \frac{1}{2n} \sum_{j \neq i} \partial_r^3 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i})^2 (\tilde{u}_{j, i} - u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) \frac{x_j^\top \tilde{H}_i^{-1} H_{\setminus i}^{-1} x_j}{n} \right| \\ \le \| \partial_r^2 \partial_u^2 \ell \|_{\infty} \frac{1}{2\lambda^2} \left( \sup_{j \neq i} \frac{\|x_j\|}{\sqrt{n}} \sup_{j \neq i} |\tilde{u}_{j, i} - u_{j, \setminus i}| \sup_{j \neq i} |\tilde{r}_{j, i} - r_{j, \setminus i}| \right) = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right). $$

We finally focus on the second term in (11). Following Barnfield et al. [2025], we first approximate $\tilde{H}_i$ by the $x_i$- independent Hessian $H_{\setminus i}$ to make explicit all statistical dependencies on $x_i$, which we subsequently carefully analyze. The corresponding correction term reads

$$ \left| \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) + \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{u}_{j, i} - u_{j, \setminus i}) \right) \frac{x_j^\top (\tilde{H}_i^{-1} - H_{\setminus i}^{-1}) H_{\setminus i}^{-1} x_j}{n} \right| \\ \le (\| \partial_r^3 \ell \|_{\infty} \vee \| \partial_r^2 \partial_u \ell \|_{\infty}) \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - \tilde{r}_{j, i}| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j, \setminus i} - \tilde{u}_{j, i}| \right) \frac{1}{\lambda} \sup_{j \in [n]} \frac{\|x_j\|^2}{n} \sup_{i \in [n]} \| \tilde{H}_i^{-1} - H_{\setminus i}^{-1} \| \\ \le O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) \frac{1}{\lambda^2} \| \tilde{H}_i - H_{\setminus i} \|. $$

The difference of the Hessians can further be bounded as

$$ \| \tilde{H}_i - H_{\setminus i} \| = \left\| \frac{1}{n} \partial_r^2 \ell_i (\tilde{r}_{i, i}, \tilde{u}_{i, i}) \frac{x_i x_i^\top}{n} + \frac{1}{n} \sum_{j \neq i} \left( \partial_r^2 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) - \partial_r^2 \ell_j (\tilde{r}_{j, i}, \tilde{u}_{j, i}) \right) \frac{x_j x_j^\top}{n} \right\| \\ \le \| \partial_r^2 \ell \|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) \\ + (\| \partial_r^3 \ell \|_{\infty} \vee \| \partial_r^2 \partial_u \ell \|_{\infty}) \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - \tilde{r}_{j, i}| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j, \setminus i} - \tilde{u}_{j, i}| \right) \sup_{j \in [n]} \frac{\|x_j\|^2}{n} \\ = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

Therefore, in summary, at the price of a correction of order $\text{polylog}(n)/n$ in $L_k$, the surrogate Hessian $\tilde{H}_i$ in the
second term of (11) may be replaced by the leave-i out Hessian $H_{\backslash i}$. It thus suffices to study the quantity

$$
\begin{align}
& \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) + \partial_r^2 \partial_u \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{u}_{j, i} - u_{j, \setminus i}) \right) \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] \nonumber \\
& \le 3 \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \eta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] + 3 \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \zeta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] \nonumber \\
& \quad + 3 \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^2 \partial_u \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \xi_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] \tag{12}
\end{align}
$$

with the aim of establishing $O(1/n^2)$ control. We successively examine the three terms, leveraging the explicit expressions of $\eta_i, \zeta_i, \xi_i$.

$$
\begin{align*}
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \eta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right]
&= \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r \ell(\tilde{r}_{i, i}) \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} x_j x_j^\top H_{\setminus i}^{-1}}{n^2} x_i \right)^2 \right] \\
&\le \|\partial_r \ell\|_{\infty}^2 \mathbb{E} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} x_j H_{\setminus i}^{-1} x_j}{n^2} \right\|^2 \right],
\end{align*}
$$

where we took the expectation over $x_i$ only. The norm can be controlled as

$$
\left\| \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} x_j H_{\setminus i}^{-1} x_j}{n^2} \right\| = \left\| \frac{1}{n^2} h^\top X_{\setminus i} H_{\setminus i}^{-1} \right\| \le \frac{1}{n\lambda} \frac{\|X_{\setminus i}\|}{\sqrt{n}} \frac{\|h\|}{\sqrt{n}}.
$$

We have introduced the vector $h \in \mathbb{R}^{n-1}$ with entries $h_j = \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) x_j^\top H_{\setminus i}^{-2} x_j / n$. From Lemma F.5, $\frac{\|X_{\setminus i}\|}{\sqrt{n}} = O_{L_k}(\text{polylog}(n))$. Finally,

$$
\|h\| \le \sqrt{n} \|\partial_r^3 \ell\|_{\infty} \frac{1}{\lambda^2} \sup_{j \in [n]} \frac{\|x_j\|^2}{n} = O_{L_k}(\sqrt{n}\text{polylog}(n)).
$$

Thus,

$$
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \eta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] = O_{L_k} \left( \frac{\text{polylog}(n)}{n^2} \right).
$$

We follow the same lines for the remaining terms of (12). On the one hand,

$$
\begin{align*}
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \zeta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right]
&\le \|\partial_u \ell_0\|_{\infty}^2 \mathbb{E} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} x_j H_{0, \setminus i}^{-1} G_{\setminus i} H_{\setminus i}^{-1} x_j}{n^2} \right\|^2 \right] \\
&\le \|\partial_u \ell_0\|_{\infty}^2 \frac{1}{\lambda^6 \lambda_0^2} \|\partial_r^3 \ell\|_{\infty}^2 \|\partial_r \partial_u \ell\|_{\infty}^2 O \left( \frac{\text{polylog}(n)}{n^2} \right).
\end{align*}
$$
On the other hand

$$
\begin{align*}
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \xi_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] &\le \| \partial_u \ell_0 \|_{\infty}^2 \mathbb{E} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} x_j H_{0, \setminus i}^{-1} x_j}{n^2} \right\|^2 \right] \\
&\le \| \partial_u \ell_0 \|_{\infty}^2 \frac{1}{\lambda^4 \lambda_0^2} \| \partial_r^2 \partial_u \ell \|_{\infty}^2 O \left( \frac{\mathrm{polylog}(n)}{n^2} \right).
\end{align*}
$$

Returning to (12) finally allows one to reach the bound

$$
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) + \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{u}_{j, i} - u_{j, \setminus i}) \right) \frac{x_j^\top H_{\setminus i}^{-2} x_j}{n} \right)^2 \right] = O \left( \frac{\mathrm{polylog}(n)}{n^2} \right)
$$

Thus, putting all the intermediary results together,

$$
2 \sum_{i \in [n]} \mathbb{E} \left[ (\mathfrak{V}_{\setminus i} - \tilde{\mathfrak{V}}_{i})^2 \right] = O_{L_k} \left( \frac{\mathrm{polylog}(n)}{n} \right).
$$

The Efron-Stein lemma then guarantees that

$$
\mathrm{Var}[\mathfrak{V}] = O\left(\frac{\mathrm{polylog}(n)}{n}\right),
$$

thereby concluding the proof.

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

We now prove a similar concentration inequality for $v_i$, $\mathcal{X}$.

**Lemma C.6 ($\mathcal{X}$ concentrates).** We remind $v_i = 1/n x_i^\top H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1} x_i$, $\mathcal{X} = \frac{1}{n} \mathrm{tr}[H^{-1} G H_0^{-1}]$. $v_i$ admits an equivalent

$$
\sup_{i \in [n]} |v_i - \mathcal{X}| = O_{L_k} \left( \frac{\mathrm{polylog}(n)}{\lambda \sqrt{n}} \right).
$$

Furthermore, $\mathcal{X}$ concentrates, with

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

*Proof.* The proof proceeds similarly to that for $\mathfrak{V}$. From Lemma G.2 of El Karoui [2018] applied to the symmetrized matrix $1/2(H_{\setminus i}^{-1}G_{\setminus i}H_{0,\setminus i}^{-1} + H_{0,\setminus i}^{-1}G_{\setminus i}H_{\setminus i}^{-1})$,

$$
\sup_{i \in [n]} |v_i - \mathcal{X}_{\setminus i}| = O_{L_k} \left( \frac{\mathrm{polylog}(n)}{\lambda \sqrt{n}} \right),
$$

where $\mathcal{X}_{\setminus i} = 1/n \mathrm{tr}[H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1}]$. To complete the derivation of the first point, one now needs to bound $|\mathcal{X}_{\setminus i} - \mathcal{X}|$. Developing the difference,

$$
\begin{align}
\mathcal{X}_{\setminus i} - \mathcal{X} = & \frac{1}{n} \mathrm{tr} [H^{-1}(H_{\setminus i} - H) H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1}] + \frac{1}{n} \mathrm{tr} [H^{-1}(G - G_{\setminus i}) H_{0,\setminus i}^{-1}] \tag{13} \\
& + \frac{1}{n} \mathrm{tr} [H^{-1} G_{\setminus i} H_0^{-1} (H_{0,\setminus i} - H_0) H_{0,\setminus i}^{-1}] + \frac{1}{n} \mathrm{tr} [H^{-1}(H_{\setminus i} - H) H_{\setminus i}^{-1} G_{\setminus i} H_0^{-1} (H_{0,\setminus i} - H_0) H_{0,\setminus i}^{-1}] \nonumber \\
& + \frac{1}{n} \mathrm{tr} [H^{-1}(G - G_{\setminus i}) H_0^{-1} (H_{0,\setminus i} - H_0) H_{0,\setminus i}^{-1}] + \frac{1}{n} \mathrm{tr} [H^{-1}(H_{\setminus i} - H) H_{\setminus i}^{-1} (G - G_{\setminus i}) H_0^{-1} H_{0,\setminus i}^{-1}] \nonumber \\
& + \frac{1}{n} \mathrm{tr} [H^{-1}(H_{\setminus i} - H) H_{\setminus i}^{-1} (G - G_{\setminus i}) H_0^{-1} (H_{0,\setminus i} - H_0) H_{0,\setminus i}^{-1}] \nonumber
\end{align}
$$
The control of each of these seven terms proceeds in much the same way. We illustrate the reasoning on the more complex last term.

$$
\begin{align}
& \left| \frac{1}{n} \operatorname{tr} \left[ H^{-1}(H_{\setminus i} - H) H_{\setminus i}^{-1} (G - G_{\setminus i}) H_0^{-1} (H_{0,\setminus i} - H_0) H_{0,\setminus i}^{-1} \right] \right| \tag{14} \\
& \le a_1 \frac{\|x_i\|^6}{\lambda^2 \lambda_0^2 n^4} + a_2 \sup_{j \ne i} |u_j - u_{j,\setminus i}| \sup_{j \ne i} \frac{\|x_i\|^4 \|x_j\|^2}{\lambda^2 \lambda_0^2 n^3} + a_3 (\sup_{j \ne i} |u_j - u_{j,\setminus i}| + \sup_{j \ne i} |r_j - r_{j,\setminus i}|) \sup_{j \ne i} \frac{\|x_i\|^4 \|x_j\|^2}{\lambda^2 \lambda_0^2 n^3} \nonumber \\
& \quad + a_4 (\sup_{j \ne i} |u_j - u_{j,\setminus i}| + \sup_{j \ne i} |r_j - r_{j,\setminus i}|) \sup_{j \ne i} \frac{\|x_i\|^4 \|x_j\|^2}{\lambda^2 \lambda_0^2 n^3} \nonumber \\
& \quad + a_5 (\sup_{j \ne i} |u_j - u_{j,\setminus i}| + \sup_{j \ne i} |r_j - r_{j,\setminus i}|) \sup_{j \ne i} |u_j - u_{j,\setminus i}| \nonumber \\
& \quad + a_6 (\sup_{j \ne i} |u_j - u_{j,\setminus i}| + \sup_{j \ne i} |r_j - r_{j,\setminus i}|) \sup_{j \ne i} |u_j - u_{j,\setminus i}| \nonumber \\
& \quad + a_7 (\sup_{j \ne i} |u_j - u_{j,\setminus i}| + \sup_{j \ne i} |r_j - r_{j,\setminus i}|)^2 \left[ \sup_{j \ne i \ k \ne i, j} \sup_{k \ne i, j} \frac{|x_j^\top H_{\setminus i}^{-1} x_i x_i^\top H_0^{-1} x_k x_k^\top H_{0,\setminus i}^{-1} H^{-1} x_j|}{n^2} + \frac{1}{n^3} \sup_{j \ne i} \frac{\|x_i\|^2 \|x_j\|^4}{\lambda^2 \lambda_0^2} \right] \nonumber \\
& \quad + a_8 (\sup_{j \ne i} |u_j - u_{j,\setminus i}| + \sup_{j \ne i} |r_j - r_{j,\setminus i}|)^2 \sup_{j \ne i} |u_j - u_{j,\setminus i}| \nonumber \\
& \quad + a_9 (\sup_{j \ne i} \sup_{k \ne i, j \ne i, k \ne j, l \ne i, j \ne k} \frac{|x_j^\top H_{\setminus i}^{-1} x_k x_k^\top H_0^{-1} x_l x_l^\top H_{0,\setminus i}^{-1} H^{-1} x_j|}{n}) + \frac{3}{n^2} \sup_{j \ne i} \sup_{k \ne i, j} \frac{\|x_k\|^2 \|x_j\|^4}{\lambda^2 \lambda_0^2} + \frac{1}{n^3} \sup_{j \ne i} \frac{\|x_j\|^6}{\lambda^2 \lambda_0^2} \nonumber
\end{align}
$$

The absolute constants $a_m$ are simple products or maxima of the $\ell_\infty$ norms $\|\partial_r^2 \ell\|_\infty$, $\|\partial_u^2 \ell_0\|_\infty$, $\|\partial_r^3 \ell\|_\infty$, $\|\partial_r \partial_u \ell\|_\infty$, $\|\partial_r^2 \partial_u \ell\|_\infty$, $\|\partial_r \partial_u^2 \ell\|_\infty$, $\|\partial_u^3 \ell_0\|_\infty$. In the above, we resorted to a coarse Cauchy-Schwartz bound wherever it proved sufficient. It follows from Lemma F.6 that when $j \ne i$,

$$
\sup_{j \ne i} |x_i^\top H_{\setminus i}^{-1} x_j| \le O_{L_k} (\sqrt{n}\operatorname{polylog}(n)).
$$

We now turn to the other terms. Let $i \ne j$, and let us focus on bounding the quadratic term $|x_i^\top H_0^{-1} x_j|$. We first note that

$$
\left\| H_0^{-1} - \left( H_{0,\setminus i} + \frac{\partial_u^2 \ell_{0,i}(u_i)}{n} x_i x_i^\top \right)^{-1} \right\| \le \frac{1}{\lambda_0^2} \left\| \partial_u^2 \ell_0 \right\|_{\infty} \sup_{j \ne i} |u_j - u_{j,\setminus i}| \frac{\left\| X_{\setminus i} \right\|^2}{n} = O_{L_k} \left( \frac{\operatorname{polylog}(n)}{\sqrt{n}} \right),
$$

using Lemma F.5 and Proposition B.1. Using Woodbury's inversion lemma to make $H_{0,\setminus i}$ appear,

$$
\begin{align*}
\sup_{j \ne i} |x_i^\top H_0^{-1} x_j| &= \sup_{j \ne i} \left| x_i^\top \left( H_{0,\setminus i}^{-1} - \frac{\partial_u^2 \ell_{0,i}(u_i)}{n} \frac{1}{1 + \frac{\partial_u^2 \ell_{0,i}(u_i)}{n} x_i^\top H_{0,\setminus i}^{-1} x_i} H_{0,\setminus i}^{-1} x_i x_i^\top H_{0,\setminus i}^{-1} \right) x_j \right| \\
&\quad + O_{L_k} (\sqrt{n}\operatorname{polylog}(n)) \\
&\le \sup_{j \ne i} |x_i^\top H_{0,\setminus i}^{-1} x_j| + \frac{\|\partial_u^2 \ell_0\|_\infty}{\lambda_0} \frac{\|x_i\|^2}{n} \sup_{j \ne i} |x_i^\top H_{0,\setminus i}^{-1} x_j| + O_{L_k} (\sqrt{n}\operatorname{polylog}(n)) \\
&= O_{L_k} (\sqrt{n}\operatorname{polylog}(n)),
\end{align*}
$$
again using Lemma F.6. Similarly,

$$ \left\| H^{-1} - \left( H_{\setminus i} + \frac{\partial_r^2 \ell_i(r_i, u_i)}{n} x_i x_i^\top \right)^{-1} \right\| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

from which it follows that for $j \neq i$,

$$ \begin{aligned} \sup_{j \neq i} |x_j^\top H_{0,\setminus i}^{-1} H^{-1} x_i| &= \sup_{j \neq i} \left| x_j^\top H_{0,\setminus i}^{-1} \left( H_{\setminus i}^{-1} - \frac{\partial_r^2 \ell_i(r_i, u_i)}{n} \frac{1}{1 + \frac{\partial_r^2 \ell_i(r_i, u_i)}{n} x_i^\top H_{\setminus i}^{-1} x_i} H_{\setminus i}^{-1} x_i x_i^\top H_{\setminus i}^{-1} \right) x_j \right| \\ &\quad + O_{L_k} (\sqrt{n} \text{polylog}(n)) \\ &\le \sup_{j \neq i} |x_i^\top H_{0,\setminus i}^{-1} x_j| + \frac{\|\partial_u^2 \ell_0\|_{\infty}}{\lambda_0} \frac{\|x_i\|^2}{n} \sup_{j \neq i} |x_i^\top H_{0,\setminus i}^{-1} x_j| + O_{L_k} (\sqrt{n} \text{polylog}(n)) \\ &\quad = O_{L_k} (\sqrt{n} \text{polylog}(n)). \end{aligned} $$

Finally, one needs to control $\sup_{j \neq i} \sup_{k \neq i, j} |x_j^\top H_{0,\setminus i}^{-1} H^{-1} x_k|$ for $k \neq j$ and $k, j \neq i$. To this end, we will approximate both $H_{0,\setminus j}^{-1}$ and $H^{-1}$ by their leave-$j$ out versions. We have already controlled the difference between $H^{-1}$ and $(H_{\setminus i} + \partial_r^2 \ell_j(r_j, u_j)/nx_j x_j^\top)^{-1}$. By the same token,

$$ \begin{aligned} \sup_{j \neq i} \left\| H_{0,\setminus i}^{-1} - \left( H_{0,\setminus i,\setminus j} + \frac{\partial_u^2 \ell_{0,j}(u_{j,\setminus i})}{n} x_j x_j^\top \right)^{-1} \right\| &\le \frac{1}{\lambda_0^2} \left\| \partial_u^3 \ell_0 \right\|_{\infty} \sup_{k \neq i, j} |u_{k,\setminus i} - u_{k,\setminus i,\setminus j}| \sup_{j \neq i} \frac{\|X_{\setminus i,\setminus j}\|^2}{n} \\ &= O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), \end{aligned} $$

We denoted $X_{\setminus i, \setminus j} \in \mathbb{R}^{(n-2) \times d}$ the matrix with rows $\{x_k\}_{k \neq i, j}$ and

$$ H_{0,\setminus i, \setminus j} = \frac{1}{n} \sum_{k \neq i, j} \partial_u^2 \ell_0(u_{k,\setminus i,\setminus j}) x_k x_k^\top + \lambda_0 I_d, $$

using the fact that Proposition B.1 and Lemma F.5 directly apply to $X_{\setminus i}$, yielding control over the leave-two-out quantities. Thus,

$$ \begin{aligned} & \sup_{j \neq i} \sup_{k \neq i, j} |x_j^\top H_{0,\setminus i}^{-1} H^{-1} x_k| \\ &= \sup_{j \neq i} \sup_{k \neq i, j} \left| x_j^\top \left( H_{\setminus j}^{-1} - \frac{\partial_r^2 \ell_j(r_j, u_j)}{n} \frac{1}{1 + \frac{\partial_r^2 \ell_j(r_j, u_j)}{n} x_j^\top H_{\setminus j}^{-1} x_j} H_{\setminus j}^{-1} x_j x_j^\top H_{\setminus j}^{-1} \right) \right| \\ & \quad \left( H_{0,\setminus i,\setminus j}^{-1} - \frac{\partial_u^2 \ell_{0,j}(u_{j,\setminus i})}{n} \frac{1}{1 + \frac{\partial_u^2 \ell_{0,j}(u_{j,\setminus i})}{n} x_j^\top H_{0,\setminus i,\setminus j}^{-1} x_j x_j^\top H_{0,\setminus i,\setminus j}^{-1} \right) x_k \right| \\ & \quad + O_{L_k} (\text{polylog}(n)\sqrt{n}) \\ &= \sup_{j \neq i} \sup_{k \neq i, j} |x_j^\top H_{\setminus j}^{-1} H_{0,\setminus i,\setminus j}^{-1} x_k| + \left\| \partial_u^2 \ell_0 \right\|_{\infty} \sup_{j \neq i} \frac{\|x_j\|^2}{\lambda \lambda_0 n} \sup_{j \neq i} \sup_{k \neq i, j} |x_j^\top H_{0,\setminus i,\setminus j}^{-1} x_k| \\ & \quad + \left\| \partial_r^2 \ell \right\|_{\infty} \sup_{j \neq i} \frac{\|x_j\|^2}{\lambda n} \sup_{j \neq i} \sup_{k \neq i, j} |x_j^\top H_{\setminus j}^{-1} H_{0,\setminus i,\setminus j}^{-1} x_k| \\ & \quad + \left\| \partial_r^2 \ell \right\|_{\infty} \left\| \partial_u^2 \ell_0 \right\|_{\infty} \sup_{j \neq i} \frac{\|x_j\|^4}{\lambda^2 \lambda_0 n^2} \sup_{j \neq i} \sup_{k \neq i, j} |x_j^\top H_{0,\setminus i,\setminus j}^{-1} x_k| + O_{L_k} (\text{polylog}(n)\sqrt{n}) \\ &= O_{L_k} (\text{polylog}(n)\sqrt{n}), \end{aligned} $$
using repeatedly the bound offered by Lemma F.6 in the last step. The same strategy shows

$$ \sup_{j \neq i} \sup_{k \neq i, j} \left| x_j^\top H_{\setminus i}^{-1} x_k \right| = O_{L_k} (\text{polylog}(n) \sqrt{n}). $$

Putting all these results together finally leads to the bounds

$$ \sup_{j \neq i} \sup_{k \neq i, j} \frac{|x_i^\top H_{\setminus i}^{-1} x_j x_j^\top H_0^{-1} x_k x_k^\top H_{0, \setminus i}^{-1} H^{-1} x_i|}{n^2} = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

$$ \sup_{j \neq i} \sup_{k \neq i, j} \frac{|x_j^\top H_{\setminus i}^{-1} x_k x_k^\top H_0^{-1} x_i x_i^\top H_{0, \setminus i}^{-1} H^{-1} x_j|}{n^2} = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

$$ \sup_{j \neq i} \sup_{k \neq i, j} \frac{|x_j^\top H_{\setminus i}^{-1} x_i x_i^\top H_0^{-1} x_k x_k^\top H_{0, \setminus i}^{-1} H^{-1} x_j|}{n^2} = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

$$ \sup_{j \neq i} \sup_{k \neq i, j} \sup_{l \neq i, j, k} \frac{|x_j^\top H_{\setminus i}^{-1} x_k x_k^\top H_0^{-1} x_l x_l^\top H_{0, \setminus i}^{-1} H^{-1} x_j|}{n} = O_{L_k} (\text{polylog}(n) \sqrt{n}). $$

Incorporating these bounds into (14), and using Proposition B.1 and Proposition B.10 to bound the differences of residuals, allows one to reach

$$ \left| \frac{1}{n} \text{tr} \left[ H^{-1} (H_{\setminus i} - H) H_{\setminus i}^{-1} (G - G_{\setminus i}) H_0^{-1} (H_{0, \setminus i} - H_0) H_{0, \setminus i}^{-1} \right] \right| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

An identical proof may be repeated for each of the other terms of (13), and finally yield

$$ |\mathbf{x}_{\setminus i} - \mathbf{x}| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

implying the first claim.

We now turn to the second claim. Starting again from the Efron-Stein lemma,

$$ \text{Var}[\mathbf{x}] \leq \sum_{i \in [n]} \mathbb{E}[(\mathbf{x} - \mathbf{x}_{\setminus i})^2] \leq 2 \sum_{i \in [n]} \left( \mathbb{E}[(\mathbf{x} - \tilde{\mathbf{x}}_i)^2] + \mathbb{E}[(\tilde{\mathbf{x}}_i - \mathbf{x}_{\setminus i})^2] \right), $$

We defined $\tilde{\mathbf{x}}_i = 1/n \text{tr}[\tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1}]$. We focus on the first term $\mathbb{E}[(\mathbf{x} - \tilde{\mathbf{x}}_i)^2]$. We can decompose

$$ \mathbf{x} - \tilde{\mathbf{x}}_i = \frac{1}{n} \text{tr} \left[ (H^{-1} - \tilde{H}_i^{-1}) \tilde{G}_i \tilde{H}_{0,i}^{-1} \right] + \frac{1}{n} \text{tr} \left[ H^{-1} (G - \tilde{G}_i) \tilde{H}_{0,i}^{-1} \right] + \frac{1}{n} \text{tr} \left[ H^{-1} G (H_0^{-1} - \tilde{H}_{0,i}^{-1}) \right]. $$

The first term can be explicitly written as

$$ \begin{aligned} & \left| \frac{1}{n} \text{tr} \left[ (H^{-1} - \tilde{H}_i^{-1}) \tilde{G}_i \tilde{H}_{0,i}^{-1} \right] \right| \\ &= \left| \frac{1}{n} \sum_{j \in [n]} \left[ \partial_r^3 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (r_j - \tilde{r}_{j,i}) + \partial_r^2 \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) (u_j - \tilde{u}_{j,i}) \right] \frac{x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H^{-1} x_j}{n} \right| \\ &\leq \frac{1}{n} \left| \langle h^r, \delta_r \rangle \right| + \frac{1}{n} \left| \langle h^u, \delta_u \rangle \right| \leq \frac{1}{n} \left( \|h^r\| \|\delta^r\| + \|h^u\| \|\delta^u\| \right) \end{aligned} $$

for some $\tilde{r}_{j,i}, \tilde{u}_{j,i}$ lying on the segment connecting $\tilde{r}_{j,i}, \tilde{u}_{j,i}$ and $r_j, u_j$, from the mean value theorem. We introduced the vectors $h^r \in \mathbb{R}^n, h^u \in \mathbb{R}^n$, with entries $h_j^r = \partial_r^3 \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H^{-1} x_j/n$ and $h_j^u = \partial_r^2 \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) x_j^\top \tilde{G}_i \tilde{H}_{0,i}^{-1} x_j/n$, alongside $\delta_r, \delta_u \in \mathbb{R}^n$ with entries $\delta_{r,j} = (r_j - \tilde{r}_{j,i})$ and $\delta_{u,j} = (u_j - \tilde{u}_{j,i})$. Lemma
B.2 and Lemma B.12 ensure that $||\delta_r||$, $||\delta_u|| = O_{L_k}(\text{polylog}(n)/\sqrt{n})$. We now aim to establish $O_{L_k}(\text{polylog}(n)\sqrt{n})$ control of $||h^u||$, $||h^r||$. These follow from the bounds

$$ \begin{aligned} \|h^r\| &\le \sqrt{n} \|\partial_r^3 \ell\|_{\infty} \sup_{j \in [n]} \frac{\|x_j\|^2}{\lambda_0 \lambda^2 n} \|\tilde{G}_i\|, \\ \|h^u\| &\le \sqrt{n} \|\partial_r^2 \partial_u \ell\|_{\infty} \sup_{j \in [n]} \frac{\|x_j\|^2}{\lambda_0 \lambda^2 n} \|\tilde{G}_i\|, \end{aligned} $$

Lemma F.5 and the bound $||\tilde{G}_i|| \le ||\partial_r \partial_u \ell||_{\infty} \|X\|^2/n = O_{L_k}(\text{polylog}(n))$. Similarly, one can establish

$$ \frac{1}{n} \text{tr}[(H^{-1} - \tilde{H}_i^{-1})\tilde{G}_i \tilde{H}_{0,i}^{-1}], \frac{1}{n} \text{tr}[H^{-1}(G - \tilde{G}_i)\tilde{H}_{0,i}^{-1}], \frac{1}{n} \text{tr}[H^{-1}G(H_0^{-1} - \tilde{H}_{0,i}^{-1})] = O_{L_k}\left(\frac{\text{polylog}(n)}{n}\right), $$

from which it follows that

$$ \mathbb{E}[(\mathfrak{X} - \tilde{\mathfrak{X}}_i)^2] = O\left(\frac{\text{polylog}(n)}{n^2}\right). $$

We now turn to controlling the second term $\mathbb{E}[(\mathfrak{X}_{\setminus i} - \tilde{\mathfrak{X}}_i)^2]$ in the Efron-Stein upper bound. We start from a similar decomposition

$$ (\mathfrak{X}_{\setminus i} - \tilde{\mathfrak{X}}_i)^2 \le \frac{3}{n^2} \text{tr}[(H_{\setminus i}^{-1} - \tilde{H}_i^{-1})\tilde{G}_i \tilde{H}_{0,i}^{-1}]^2 + \frac{3}{n} \text{tr}[H_{\setminus i}^{-1}(G_{\setminus i} - \tilde{G}_i)\tilde{H}_{0,i}^{-1}]^2 + \frac{3}{n} \text{tr}[H_{\setminus i}^{-1}G_{\setminus i}(H_{0,\setminus i}^{-1} - \tilde{H}_{0,i}^{-1})]^2. \quad (15) $$

Let us examine the first term; the two other terms can be controlled using identical steps. The strategy follows very closely that of the corresponding step in the proof of the concentration of $\mathfrak{Y}$. Using a second-order Taylor expansion:

$$ \begin{aligned} & \frac{\text{tr}[(H_{\setminus i}^{-1} - \tilde{H}_i^{-1})\tilde{G}_i \tilde{H}_{0,i}^{-1}]}{n} \\ &= \frac{1}{n} \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \frac{x_i^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_i}{n} \\ & \quad + \frac{1}{n} \sum_{j \ne i} \left( \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i})(\tilde{r}_{j,i} - r_{j,\setminus i}) + \partial_r^2 \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i})(\tilde{u}_{j,i} - u_{j,\setminus i}) \right) \frac{x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_j}{n} \\ & \quad + \frac{1}{2n} \sum_{j \ne i} \left( \partial_r^4 \ell_j(r_{j,\setminus i}, u_{j,\setminus i})^2 (\tilde{r}_{j,i} - r_{j,\setminus i})^2 + \partial_r^2 \partial_u^2 \ell_j(r_{j,\setminus i}, u_{j,\setminus i})(\tilde{u}_{j,i} - u_{j,\setminus i})^2 \right. \\ & \qquad \left. + 2 \partial_r^3 \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i})(\tilde{u}_{j,i} - u_{j,\setminus i})(\tilde{r}_{j,i} - r_{j,\setminus i}) \right) \frac{x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_j}{n}. \end{aligned} \quad (16) $$

The first term can be bounded as

$$ \left| \frac{1}{n} \partial_r^2 \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \frac{x_i^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_i}{n} \right| = \frac{\|\partial_r^2 \ell\|_{\infty} \|\partial_r \partial_u \ell\|_{\infty}}{\lambda^2 \lambda_0} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right). $$

The control of the last term follows from Propositions B.1 and B.10 and Lemma 10:

$$ \begin{aligned} \left| \frac{1}{2n} \sum_{j \ne i} \partial_r^4 \ell_j (r_{j,\setminus i}, u_{j,\setminus i})^2 (\tilde{r}_{j,i} - r_{j,\setminus i})^2 \frac{x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_j}{n} \right| &\le \frac{\|\partial_r^4 \ell\|_{\infty} \|\partial_r \partial_u \ell\|_{\infty}}{2\lambda^2\lambda_0} \left( \sup_{j \ne i} \frac{\|x_j\|}{\sqrt{n}} \sup_{j \ne i} |\tilde{r}_{j,i} - r_{j,\setminus i}| \right)^2 \\ &= O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) \end{aligned} $$
and

$$
\left| \frac{1}{2n} \sum_{j \neq i} \partial_r^2 \partial_u^2 \ell_j (r_{j, \setminus i}, u_{j, \setminus i})^2 (\tilde{u}_{j, i} - u_{j, \setminus i})^2 \frac{x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_j}{n} \right| &\le \frac{\| \partial_r^2 \partial_u^2 \ell \|_{\infty} \| \partial_r \partial_u \ell \|_{\infty}}{2 \lambda^2 \lambda_0} \left( \sup_{j \neq i} \frac{\| x_j \|}{\sqrt{n}} \sup_{j \neq i} |\tilde{u}_{j, i} - u_{j, \setminus i}| \right) \\
&= O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right)
$$

and

$$
\left| \frac{1}{2n} \sum_{j \neq i} \partial_r^3 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i})^2 (\tilde{u}_{j, i} - u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) \frac{x_j^\top \tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} H_{\setminus i}^{-1} x_j}{n} \right| \\
\le \frac{\| \partial_r \partial_u \ell \|_{\infty} \| \partial_r^2 \partial_u^2 \ell \|_{\infty}}{2 \lambda^2 \lambda_0} \left( \sup_{j \neq i} \frac{\| x_j \|}{\sqrt{n}} \sup_{j \neq i} |\tilde{u}_{j, i} - u_{j, \setminus i}| \sup_{j \neq i} |\tilde{r}_{j, i} - r_{j, \setminus i}| \right) = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right).
$$

The control of the second term of (16) requires a finer analysis of the statistical dependencies on $x_i$. As for the proof of the concentration of $\mathfrak{V}$, the key step is to approximate the matrices $\tilde{G}_i, \tilde{H}_{0,i}^{-1}$ by their leave-i out approximations, in order to unravel all statistical correlations with $x_i$. On the one hand,

$$
\left| \frac{1}{n} \sum_{j \neq i} (\partial_r^3 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) + \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{u}_{j, i} - u_{j, \setminus i})) \frac{x_j^\top (\tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1} - H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1}) H_{\setminus i}^{-1} x_j}{n} \right| \\
\le a_1 \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j, \setminus i} - \tilde{r}_{j, i}| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j, \setminus i} - \tilde{u}_{j, i}| \right) \frac{1}{\lambda \lambda_0} \sup_{j \in [n]} \frac{\|x_j\|^2}{n} \\
\left[ b_1 \sup_{i \in [n]} \|\tilde{H}_i^{-1} - H_{\setminus i}^{-1}\| + b_2 \sup_{i \in [n]} \|\tilde{G}_i - G_{\setminus i}\| + b_3 \sup_{i \in [n]} \|\tilde{H}_{0,i}^{-1} - H_{0,\setminus i}^{-1}\| + b_4 \sup_{i \in [n]} \|\tilde{H}_i^{-1} - H_{\setminus i}^{-1}\| \|\tilde{H}_{0,i}^{-1} - H_{0,\setminus i}^{-1}\| \right. \\
\left. + b_5 \sup_{i \in [n]} \|\tilde{H}_i^{-1} - H_{\setminus i}^{-1}\| \|\tilde{G}_i - G_{\setminus i}\| + b_6 \sup_{i \in [n]} \|\tilde{G}_i - G_{\setminus i}\| \|\tilde{H}_{0,i}^{-1} - H_{0,\setminus i}^{-1}\| + b_7 \sup_{i \in [n]} \|\tilde{H}_i^{-1} - H_{\setminus i}^{-1}\| \|\tilde{G}_i - G_{\setminus i}\| \|\tilde{H}_{0,i}^{-1} - H_{0,\setminus i}^{-1}\| \right]
$$

with $a_1 = (\|\partial_r^3 \ell\|_{\infty} \vee \|\partial_r^2 \partial_u \ell\|_{\infty}) \|\partial_r \partial_u \ell\|_{\infty}$, and $b_1, b_2, b_3, b_4, b_5, b_6, b_7 = O_{L_k}(\text{polylog}(n))$. We recall from the proof of Lemma C.5 that

$$
\| \tilde{H}_i - H_{\setminus i} \| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
$$

Similarly,

$$
\begin{align*}
\| \tilde{H}_{0,i} - H_{0,\setminus i} \| &= \left\| \frac{1}{n} \partial_u^2 \ell_{0,i} (\tilde{u}_{i,i}) \frac{x_i x_i^\top}{n} + \frac{1}{n} \sum_{j \neq i} \left( \partial_u^2 \ell_{0,j} (u_{j,\setminus i}) - \partial_u^2 \ell_{0,j} (\tilde{u}_{j,i}) \right) \frac{x_j x_j^\top}{n} \right\| \\
&\le \| \partial_u^2 \ell_0 \|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) + \| \partial_u^3 \ell_0 \|_{\infty} \sup_{i \in [n]} \sup_{j \neq i} |u_{j,\setminus i} - \tilde{u}_{j,i}| \sup_{j \in [n]} \frac{\|x_j\|^2}{n} \\
&= O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right).
\end{align*}
$$

and
$$
\begin{align*}
\| \tilde{G}_i - G_{\setminus i} \| &= \left\| \frac{1}{n} \partial_r \partial_u \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \frac{x_i x_i^\top}{n} + \frac{1}{n} \sum_{j \neq i} \left( \partial_r \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) - \partial_r \partial_u \ell_j(\tilde{r}_{j,i}, \tilde{u}_{j,i}) \right) \frac{x_j x_j^\top}{n} \right\| \\
&\le \| \partial_r \partial_u \ell \|_{\infty} O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right) \\
&\quad + \left( \| \partial_r^2 \partial_u \ell \|_{\infty} \vee \| \partial_r \partial_u^2 \ell \|_{\infty} \right) \left( \sup_{i \in [n]} \sup_{j \neq i} |r_{j,\setminus i} - \tilde{r}_{j,i}| + \sup_{i \in [n]} \sup_{j \neq i} |u_{j,\setminus i} - \tilde{u}_{j,i}| \right) \sup_{j \in [n]} \frac{\|x_j\|^2}{n} \\
&= O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right)
\end{align*}
$$

Thus,

$$
\left| \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{r}_{j,i} - r_{j,\setminus i}) + \partial_r^2 \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{u}_{j,i} - u_{j,\setminus i}) \right) \frac{x_j^\top H_{\setminus i}^{-1} (\tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,\setminus i}^{-1} - H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1}) x_j}{n} \right| = O_{L_k} \left( \frac{\text{polylog}(n)}{n} \right),
$$

and one can replace the product $\tilde{H}_i^{-1} \tilde{G}_i \tilde{H}_{0,i}^{-1}$ in the second term of (16) by the leave-one-out approximation $H_{\setminus i}^{-1} G_{\setminus i} H_{0,\setminus i}^{-1}$, at the price of a $O_{L_k}(\text{polylog}(n)/n)$ correction. One can thus focus on studying

$$
\begin{align}
& \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{r}_{j,i} - r_{j,\setminus i}) + \partial_r^2 \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) (\tilde{u}_{j,i} - u_{j,\setminus i}) \right) \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j}{n} \right)^2 \right] \nonumber \\
& \le 3 \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \langle x_j, \eta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j}{n} \right)^2 \right] \nonumber \\
& \quad + 3 \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \langle x_j, \zeta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j}{n} \right)^2 \right] \nonumber \\
& \quad + 3 \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^2 \partial_u \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \langle x_j, \xi_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j}{n} \right)^2 \right] \tag{17}
\end{align}
$$

with the aim of establishing $O(1/n^2)$ control. The remainder of the reasoning proceeds in exactly the same way as the corresponding step in the proof of Lemma C.5, where the corresponding quantity (17) is controlled. We have

$$
\begin{align*}
& \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \langle x_j, \eta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j}{n} \right)^2 \right] \\
&= \mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r \ell(\tilde{r}_{i,i}) \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j H_{\setminus i}^{-1} x_i}{n^2} \right)^2 \right] \\
&\le \|\partial_r \ell\|_{\infty}^2 \mathbb{E} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j(r_{j,\setminus i}, u_{j,\setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0,\setminus i}^{-1} x_j H_{\setminus i}^{-1} x_j}{n^2} \right\|^2 \right] \\
&\le \|\partial_r \ell\|_{\infty}^2 \|\partial_r \partial_u \ell\|_{\infty}^2 \|\partial_r^3 \ell\|_{\infty}^2 \frac{1}{\lambda^6 \lambda_0^2} \|\partial_r \ell\|_{\infty}^2 O_{L_k} \left( \frac{\text{polylog}(n)}{n^2} \right).
\end{align*}
$$
and

$$
\begin{align*}
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \zeta_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0, \setminus i}^{-1} x_j}{n} \right)^2 \right] &\le \|\partial_u \ell_0\|_{\infty}^2 \mathbb{E} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r^3 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0, \setminus i}^{-1} x_j H_{0, \setminus i}^{-1} G_{\setminus i} H_{\setminus i}^{-1} x_j}{n^2} \right\|^2 \right] \\
&\le \|\partial_u \ell_0\|_{\infty}^2 \frac{1}{\lambda^6 \lambda_0^2} \|\partial_r^3 \ell\|_{\infty}^2 \|\partial_r \partial_u \ell\|_{\infty}^4 O \left( \frac{\text{polylog}(n)}{n^2} \right).
\end{align*}
$$

and finally

$$
\begin{align*}
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) \langle x_j, \xi_i \rangle \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0, \setminus i}^{-1} x_j}{n} \right)^2 \right] &\le \|\partial_u \ell_0\|_{\infty}^2 \mathbb{E} \left[ \left\| \frac{1}{n} \sum_{j \neq i} \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0, \setminus i}^{-1} x_j H_{0, \setminus i}^{-1} x_j}{n^2} \right\|^2 \right] \\
&\le \|\partial_u \ell_0\|_{\infty}^2 \frac{1}{\lambda^4 \lambda_0^4} \|\partial_r^2 \partial_u \ell\|_{\infty}^2 \|\partial_r \partial_u \ell\|_{\infty}^2 O \left( \frac{\text{polylog}(n)}{n^2} \right).
\end{align*}
$$

Returning to (12) finally allows one to reach the bound

$$
\mathbb{E} \left[ \left( \frac{1}{n} \sum_{j \neq i} \left( \partial_r^3 \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{r}_{j, i} - r_{j, \setminus i}) + \partial_r^2 \partial_u \ell_j (r_{j, \setminus i}, u_{j, \setminus i}) (\tilde{u}_{j, i} - u_{j, \setminus i}) \right) \frac{x_j^\top H_{\setminus i}^{-2} G_{\setminus i} H_{0, \setminus i}^{-1} x_j}{n} \right)^2 \right] = O \left( \frac{\text{polylog}(n)}{n^2} \right)
$$

Thus, putting all the intermediary results together,

$$
\frac{3}{n^2} \mathbb{E} \left[ \text{tr} \left[ (H_{\setminus i}^{-1} - \tilde{H}_i^{-1}) \tilde{G}_i \tilde{H}_{0,i}^{-1} \right]^2 \right] = O_{L_k} \left( \frac{\text{polylog}(n)}{n^2} \right).
$$

This takes care of the first term in (15). The remaining two terms can be controlled as

$$
\frac{3}{n} \mathbb{E} \left[ \text{tr} \left[ H_{\setminus i}^{-1} (G_{\setminus i} - \tilde{G}_i) \tilde{H}_{0,i}^{-1} \right] \right]^2 = O_{L_k} \left( \frac{\text{polylog}(n)}{n^2} \right),
$$

$$
\frac{3}{n} \mathbb{E} \left[ \text{tr} \left[ H_{\setminus i}^{-1} G_{\setminus i} (H_{0,\setminus i}^{-1} - \tilde{H}_{0,i}^{-1}) \right]^2 \right] = O_{L_k} \left( \frac{\text{polylog}(n)}{n^2} \right),
$$

using an identical proof strategy. Returning to (15), one thus has the bound

$$
\mathbb{E} \left[ (\mathcal{X}_{\setminus i} - \tilde{\mathcal{X}}_i)^2 \right] = O \left( \frac{\text{polylog}(n)}{n^2} \right).
$$

The Efron-Stein lemma finally guarantees that

$$
\mathrm{Var}[\mathcal{X}] = O\left(\frac{\mathrm{polylog}(n)}{n}\right),
$$

which concludes the proof.

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

Before concluding this subsection, we state one last concentration result, regarding the quantity $\omega_i = 1/n x_i^\top G_{\setminus i} H_{0,\setminus i}^{-1} x_i$ and $\mathfrak{W} = 1/n \text{Tr}[GH_0^{-1}]$. Although this quantity does not directly appear in the final characterization, it will prove instrumental in establishing a characterization for $\mathbb{E}[\mathcal{X}]$ in the later subsection E.1.

**Lemma C.7** ($\mathfrak{W}$ concentrates). We remind $\omega_i = 1/n x_i^\top G_{\setminus i} H_{0,\setminus i}^{-1} x_i$, $\mathfrak{W} = \frac{1}{n} \text{tr}[GH_0^{-1}]$. $\omega_i$ admits an equivalent

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

Furthermore, $\mathfrak{W}$ concentrates, with

$$
\mathrm{Var}[\mathfrak{W}] = O \left( \frac{\mathrm{polylog}(n)}{n} \right).
$$
*Proof*. The proof is identical to that of Lemma C.5. One can check that in all steps, the matrix $H^{-1}$ in Lemma C.5 can be replaced by the identity, with all steps remaining valid. $\square$
## D Distribution of the residuals

We showed in Appendix C that the summary statistics $m_c = \langle \hat{w}, \mu_c \rangle$, $\mathfrak{h} = \langle \hat{w}, \beta \rangle$, $\mathfrak{t} = \langle \hat{w}, \hat{w}_0 \rangle$, $\mathfrak{q} = \| \hat{w} \|^2$ and $\mathfrak{V} = 1/n \text{tr}[H_{\setminus i}^{-1}]$, $\mathfrak{X} = 1/n \text{tr}[H^{-1}GH_0^{-1}]$ concentrate in $L_2$, making it hence sufficient to evaluate their expectations, which we denote $m_c$, $\theta$, $t$, $q$, $V$, $\chi$. To do so, it remains to ascertain the asymptotic distribution of the residuals $r_i$, $r_{i,\setminus i}$ and $\tilde{r}_{i,i}$, which is the objective of the present subsection. We start with the leave-one-out residuals $r_{i,\setminus i}$. It is possible to show, such as in Barnfield et al. [2025], that the leave-on-out residual are Gaussian up to vanishing corrections in $L_2$. For later convenience, we rather state the convergence of the expectations of certain functions, which we define in the following, to the corresponding Gaussian averages.

**Definition D.1.** Let us define $\mathcal{F}$ the class of sequences of functions $\varphi : \mathbb{R}^{|\mathcal{V}|+3} \times \mathcal{V} \times \mathcal{E} \to \mathbb{R}^1$ which are Lipschitz-continuous in its first two variables up to linear functions, and polynomially bounded in the others. Namely, $\varphi \in \mathcal{F}$ if (a) on the one hand there exists $L_\varphi = O(\text{polylog}(n))$ such that for any $R, R' \in \mathbb{R}^{|\mathcal{V}|+3}$ that coincide everywhere except the first two entries ($R_l = R'_l$ for all $l \ge 3$), and any $\epsilon \in \mathcal{E}, c \in \mathcal{V}$,

$$ |\varphi(R, c, \epsilon) - \varphi(R', c, \epsilon)| \le L_{\varphi}(1 + |R_1| + |R'_1| + |R_2| + |R'_2|) \sqrt{(R_1 - R'_1)^2 + (R_2 - R'_2)^2}, \quad (18) $$

and (b) on the other hand there exists a polynomial $Q_\varphi$ in $|\mathcal{V}| + 1$ variables, with $O(\text{polylog}(n))$ coefficients and $O(1)$ degree, such that for all $R \in \mathbb{R}^{|\mathcal{V}|+3}$ with vanishing first two entries $R_1 = R_2 = 0$

$$ |\varphi(R, c, \epsilon)| \le |Q_{\varphi}(R_{[3:\mathcal{V}|+3]}, \epsilon)|, $$

where $R_{[3:\mathcal{V}|+3]} = (R_i)_{i \ge 3}$ denotes the entries of $R$ starting from the third.

### D.1 Leave-one-out residuals

**Lemma D.2 (Distribution of the leave-one-out residuals).** For any $i \in [n]$, introduce $R_{i,\setminus i} \in \mathbb{R}^{|\mathcal{V}|+3}$ as

$$ R_{i, \setminus i} = \begin{bmatrix} r_{i, \setminus i} \\ u_{i, \setminus i} \\ \langle x_i, \beta \rangle \\ \mathcal{M}x_i \end{bmatrix}. $$

Then for any function $\varphi : \mathbb{R}^{|\mathcal{V}|+3} \in \mathcal{F}$, one has the convergence

$$ \left| \mathbb{E} \left[ \varphi \left( R_{i, \setminus i}, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_c + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \right| = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right), $$

with $g \sim \mathcal{N}(0, I_{|\mathcal{V}|+3})$. The first average bears over the training set; the second over $g, c, \epsilon$. We defined the mean and covariance $\Psi \in \mathbb{R}^{|\mathcal{V}|+3}$, $\Phi \in R^{(|\mathcal{V}|+3) \times (|\mathcal{V}|+3)}$ as

$$ \Psi_c = \begin{bmatrix} m_c \\ m_{0,c} \\ \frac{\nu_c}{\rho_c} \\ \rho_c \end{bmatrix}, \qquad \Phi = \begin{bmatrix} q & t & \theta & m \\ t & q_0 & \theta_0 & m_0 \\ \theta & \theta_0 & \varrho & \nu \\ m & m_0 & \nu & \rho \end{bmatrix}, $$

<footnote n="1">¹For conciseness of notations, we keep the dependence of $\varphi$ on $n$ is implicit.</footnote>
where we denoted $\rho_c$ the c-th row of $\rho$. We recall that the definitions of $\rho \in \mathbb{R}^{|V| \times |V|}$, $\nu \in \mathbb{R}^{|V|}$ can be found in Assumption A.4.

*Proof.* Let us introduce the stochastic mean and covariance

$$ \mathfrak{M}_{\backslash i, c} = \begin{bmatrix} \mathfrak{m}_{c, \backslash i} \\ \mathfrak{m}_{0, c, \backslash i} \\ \nu_c \\ \rho_c \end{bmatrix}, $$

$$ \mathfrak{G}_{\backslash i} = \begin{bmatrix} \mathfrak{q}_{\backslash i} & \mathfrak{t}_{\backslash i} & \mathfrak{h}_{\backslash i} & \mathfrak{m}_{\backslash i} \\ \mathfrak{t}_{\backslash i} & \mathfrak{q}_{0, \backslash i} & \mathfrak{h}_{0, \backslash i} & \mathfrak{m}_{0, \backslash i} \\ \mathfrak{h}_{\backslash i} & \mathfrak{h}_{0, \backslash i} & \varrho & \nu \\ \mathfrak{m}_{\backslash i} & \mathfrak{m}_{0, \backslash i} & \nu & \rho \end{bmatrix}. $$

We used the shorthands $\mathfrak{m}_{c, \backslash i} = \langle \hat{w}_{\backslash i}, \mu_c \rangle$, $\mathfrak{h}_{\backslash i} = \langle \hat{w}_{\backslash i}, \beta \rangle$, $\mathfrak{t}_{\backslash i} = \langle \hat{w}_{\backslash i}, \hat{w}_{0, \backslash i} \rangle$, $\mathfrak{q}_{\backslash i} = \| \hat{w}_{\backslash i} \|^2$ and $\mathfrak{m}_{0, c, \backslash i} = \langle \hat{w}_{0, \backslash i}, \mu_c \rangle$, $\mathfrak{h}_{0, \backslash i} = \langle \hat{w}_{0, \backslash i}, \beta \rangle$, $\mathfrak{t}_{\backslash i} = \langle \hat{w}_{0, \backslash i}, \hat{w}_{0, \backslash i} \rangle$, $\mathfrak{q}_{0, \backslash i} = \| \hat{w}_{0, \backslash i} \|^2$. We start from the identity

$$ \left| \mathbb{E} \left[ \varphi \left( R_{i, \backslash i}, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_c + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \right| = \left| \mathbb{E} \left[ \varphi \left( \mathfrak{M}_{\backslash i, c} + \mathfrak{G}_{\backslash i}^{\frac{1}{2}} g, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_c + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \right| \quad (19) $$

which follows from the independence of $z_i$ from $\hat{w}_i$. To control the right-hand side, we first show that the leave-one-out statistics $\mathfrak{m}_{c, \backslash i}$, $\mathfrak{t}_{\backslash i}$, $\mathfrak{q}_{\backslash i}$, $\mathfrak{m}_{0, c, \backslash i}$, $\mathfrak{h}_{0, \backslash i}$, $\mathfrak{t}_{\backslash i}$, $\mathfrak{q}_{0, \backslash i}$ are close to the full statistics $\mathfrak{m}_c$, $\mathfrak{t}$, $\mathfrak{q}$, $\mathfrak{m}_{0, c}$, $\mathfrak{h}_0$, $\mathfrak{t}$, $\mathfrak{q}_0$. We have shown in the proof of Lemma C.4 that

$$ \begin{aligned} \mathfrak{q}_{\backslash i} &= \mathfrak{q} + O_{L_2} \left( \frac{\text{polylog}(n)}{n} \right) = q + O_{L_2} \left( \frac{\text{polylog}(n)}{n} \right) + \sqrt{O_{L_2} \left( \frac{\text{polylog}(n)}{n} \right)} \\ &= q + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), \end{aligned} $$

using the concentration result of Lemma C.4 in the last step. By the same token,

$$ \begin{aligned} \mathfrak{t}_{\backslash i} &= \mathfrak{t} + \langle \hat{w}_{\backslash i} - \hat{w}, \hat{w}_0 \rangle + \langle \hat{w}, \hat{w}_{0, \backslash i} - \hat{w}_0 \rangle + \langle \hat{w}_{\backslash i} - \hat{w}, \hat{w}_{0, \backslash i} - \hat{w}_0 \rangle \\ &= \mathfrak{t} + O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) \\ &= \mathfrak{t} + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). \end{aligned} $$

We used Proposition B.1 and Proposition B.10 in the first step, and Lemma C.3 in the last. Similarly,

$$ \mathfrak{h}_{\backslash i} = \mathfrak{h} + O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) = \theta + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right), $$

and for any $c \in \mathcal{V}$,

$$ \mathfrak{m}_{c, \backslash i} = \mathfrak{m}_c + O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) = m_c + O_{L_2} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

The same controls hold for the first-stage statistics $\mathfrak{m}_{0, c, \backslash i}$, $\mathfrak{h}_{0, \backslash i}$, $\mathfrak{t}_{\backslash i}$, $\mathfrak{q}_{0, \backslash i}$. Thus, the differences $\mathfrak{M}_{\backslash i, c} - \Psi_c$ and $\mathfrak{G}_{\backslash i, c} - \Phi_{c_i}$ have $O_{L_2}(\text{polylog}(n)/\sqrt{n})$ entries. We are now in a position to bound

$$ \left| \mathbb{E} \left[ \varphi \left( \mathfrak{M}_{\backslash i, c} + \mathfrak{G}_{\backslash i}^{\frac{1}{2}} g, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_c + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \right| $$
A fine analysis of the different arguments is required, as $\varphi$ is only Lipschitz in its first two variables. Let us denote $g^{\mathfrak{S}} = \mathfrak{S}_{\backslash i}^{\frac{1}{2}}g, g^{\Phi} = \Phi^{\frac{1}{2}}g$ the anisotropic Gaussian variables. Because $\mathfrak{S}_{\backslash i}, \Phi$ coincide in their lower right $(|V|+1) \times (|V|+1)$ minor $A$, the entries $g_{[3:\cdot]}^{\mathfrak{S}}, g_{[3:\cdot]}^{\Phi}$ from the third on are identically distributed. Thus, making explicit the Gaussian conditioning, one can write

$$ \mathbb{E} \left[ \varphi \left( \mathfrak{M}_{\backslash i, c} + \mathfrak{S}_{\backslash i}^{\frac{1}{2}} g, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_c + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \\ = \mathbb{E}_{X_{\backslash i}} \mathbb{E}_{g_A} \left[ \mathbb{E}_{g_2} \left[ \varphi \left( \mathfrak{M}_{\backslash i, c} + \left[ \frac{\mathfrak{B}g_A + \mathfrak{C}^{\frac{1}{2}}g_2}{g_A} \right], c_i, \epsilon_i \right) \right] - \mathbb{E}_{g_2} \left[ \varphi \left( \Psi_c + \left[ \frac{Bg_A + C^{\frac{1}{2}}g_2}{g_A} \right], \epsilon, c \right) \right] \right] $$

where $g_A \sim \mathcal{N}(0, A)$ is a $(|V|+1)$-dimensional Gaussian vector, and $g_2 \sim \mathcal{N}(0, I_2)$ is an independent variable. We denoted

$$ A = \Phi_{[3:\cdot], [3:\cdot]} = \mathfrak{S}_{[3:\cdot], [3:\cdot]}, \quad B = \Phi_{[1:2], [3:\cdot]} A^{-1}, \quad C = \Phi_{[1:2], [1:2]} - BAB^{\top}, $$

and

$$ \mathfrak{B} = \mathfrak{S}_{[1:2], [3:\cdot]} A^{-1}, \qquad \mathfrak{C} = \mathfrak{S}_{[1:2], [1:2]} - \mathfrak{B}A\mathfrak{B}^{\top} $$

Noting that $\mathfrak{M}_{\backslash i, c, [3:\cdot]} = \Psi_{c, [3:\cdot]}$, we thus have that the arguments of the two $\varphi$ functions coincide on all entries except the first two. Leveraging the Lipschitzness of $\varphi$ in its first two variables, and further using the independence of $\mathfrak{M}_{\backslash i, c}, \mathfrak{S}_{\backslash i}$ with respect to $\epsilon_i, c_i$,

$$ \begin{aligned} & \left| \mathbb{E} \left[ \varphi \left( \mathfrak{M}_{\backslash i, c} + \mathfrak{S}_{\backslash i}^{\frac{1}{2}} g, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_c + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \right| \\ & \leq L_{\varphi} \mathbb{E}_{X_{\backslash i}} \mathbb{E}_{g_A} \mathbb{E}_{g_2} \left[ \left( 1 + \left\| \mathfrak{M}_{\backslash i, c, [1:2]} \right\|_1 + \left\| \Psi_{c, [1:2]} \right\|_1 + \left\| \mathfrak{B}g_A + \mathfrak{C}^{\frac{1}{2}}g_2 \right\|_1 + \left\| Bg_A + C^{\frac{1}{2}}g_2 \right\|_1 \right) \right. \\ & \qquad \left. \left( \left\| \mathfrak{M}_{\backslash i, c, [1:2]} - \Psi_{c, [1:2]} \right\| + \left\| (\mathfrak{B} - B)g_A + (\mathfrak{C}^{\frac{1}{2}} - C^{\frac{1}{2}})g_2 \right\| \right) \right] \\ & \leq L_{\varphi} \mathbb{E} \left[ \left( 1 + \left\| \mathfrak{M}_{\backslash i, c, [1:2]} \right\|_1 + \left\| \Psi_{c, [1:2]} \right\|_1 + \left\| \mathfrak{B}g_A + \mathfrak{C}^{\frac{1}{2}}g_2 \right\|_1 + \left\| Bg_A + C^{\frac{1}{2}}g_2 \right\|_1 \right) \right]^{\frac{1}{2}} \\ & \qquad \left. \mathbb{E} \left[ \left( \left\| \mathfrak{M}_{\backslash i, c, [1:2]} - \Psi_{c, [1:2]} \right\| + \left\| (\mathfrak{B} - B)g_A + (\mathfrak{C}^{\frac{1}{2}} - C^{\frac{1}{2}})g_2 \right\| \right) \right]^{\frac{1}{2}} \end{aligned} $$

But

$$ \mathbb{E} \left[ \left( \left\| \mathfrak{M}_{\backslash i, c, [1:2]} - \Psi_{c, [1:2]} \right\| + \left\| (\mathfrak{B} - B)g_A + (\mathfrak{C}^{\frac{1}{2}} - C^{\frac{1}{2}})g_2 \right\| \right) \right]^2 \\ \leq 2L_{\varphi} \mathbb{E} \left[ \left\| \mathfrak{M}_{\backslash i, c} - \Psi_{c_i} \right\|^2 \right] + 2L_{\varphi} \mathbb{E} \left[ \text{tr}[(\mathfrak{B} - B)A(\mathfrak{B} - B)^{\top}] + \text{tr}[(\mathfrak{C}^{\frac{1}{2}} - C^{\frac{1}{2}})^2] \right] $$

From the observation above,

$$ \mathbb{E} \left[ \left\| \mathfrak{M}_{\backslash i, c} - \Psi_c \right\|^2 \right] = O \left( \frac{\text{polylog}(n)}{n} \right). $$
Turning to the second term,

$$
\begin{aligned}
\mathbb{E}\left[\operatorname{tr}\left[(\mathfrak{B}-B)A(\mathfrak{B}-B)^{\top}\right]\right] &\le 2\mathbb{E}\left[\operatorname{tr}\left[(\mathfrak{S}_{[1:2],[3:]} - \Phi_{[1:2],[3:]})(A^{-1}(\mathfrak{S}_{[1:2],[3:]} - \Phi_{[1:2],[3:]}))^{\top}\right]\right] \\
&\le 4\left\|A^{-1}\right\|_{\mathbb{E}}\left[\left\|\mathfrak{S}_{[1:2],[3:]} - \Phi_{[1:2],[3:]}\right\|_{F}^{2}\right] = O\left(\frac{\operatorname{polylog}(n)}{n}\right)
\end{aligned}
$$

We can bound the third term using the Powers-Størmer inequality [Powers and Størmer, 1970]

$$
\begin{aligned}
\operatorname{tr}\left[\left(\mathfrak{C}^{\frac{1}{2}} - C^{\frac{1}{2}}\right)^2\right] &\le \|\mathfrak{C} - C\|_{*} \\
&\le \sqrt{2} \left( \left\| \Phi_{[1:2],[1:2]} - \mathfrak{S}_{[1:2],[1:2]} \right\|_{F} + \left\| \Phi_{[1:2],[3:]} A^{-1} \Phi_{[1:2],[3:]}^{\top} - \mathfrak{S}_{[1:2],[3:]} A^{-1} \mathfrak{S}_{[1:2],[3:]}^{\top} \right\|_{F} \right) \\
&\le \sqrt{2} \left( \left\| \Phi_{[1:2],[1:2]} - \mathfrak{S}_{[1:2],[1:2]} \right\|_{F} + 2 \left\| (\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]})(A^{-1}\Phi_{[1:2],[3:]}^{\top}) \right\|_{F} \right) \\
&\quad + \sqrt{2} \left\| (\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]})(A^{-1}(\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]})) \right\|_{F}
\end{aligned}
$$

But

$$
\mathbb{E}\left[\left\|\Phi_{[1:2],[1:2]} - \mathfrak{S}_{[1:2],[1:2]}\right\|_F^2\right] \le \mathbb{E}\left[\left\|\Phi_{[1:2],[1:2]} - \mathfrak{S}_{[1:2],[1:2]}\right\|_F^2\right]^{\frac{1}{2}} = O\left(\frac{\operatorname{polylog}(n)}{\sqrt{n}}\right)
$$

and

$$
\begin{aligned}
\mathbb{E}\left[\left\| (\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]})(A^{-1}\Phi_{[1:2],[3:]}^{\top}) \right\|_{F}\right] &\le \left\|\Phi_{[1:2],[3:]}\right\|_{F}^2 \|A^{-1}\|_{\mathbb{E}} \left[\left\|\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]}\right\|_{F}\right] \\
&= O\left(\frac{\operatorname{polylog}(n)}{\sqrt{n}}\right),
\end{aligned}
$$

using Lemma F.3 and Lemma F.2 to bound $\|\Phi_{[1:2],[3:]}\|_F$. since $\mathfrak{S}_{\setminus i, c_i} - \Phi_{c_i}$ has $O_{L_2}(\operatorname{polylog}(n)/\sqrt{n})$ entries.
Finally,

$$
\begin{aligned}
\mathbb{E}\left[\left\| (\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]})(A^{-1}\Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]})(A^{\top}) \right\|_{F}\right] &\le 2\|A^{-1}\|_{\mathbb{E}} \left[\left\| \Phi_{[1:2],[3:]} - \mathfrak{S}_{[1:2],[3:]} \right\|_{F}\right]^2 \\
&= O\left(\frac{\operatorname{polylog}(n)}{n}\right),
\end{aligned}
$$

Thus,

$$
\mathbb{E}\left[\left(\left\|\mathfrak{M}_{\setminus i, c, [1:2]} - \Psi_{c, [1:2]}\right\| + \left\| (\mathfrak{B} - B)g_A + (\mathfrak{C}^{\frac{1}{2}} - C^{\frac{1}{2}})g_2 \right\|\right)^2\right]^{\frac{1}{2}} = O\left(\frac{\operatorname{polylog}(n)}{n^{\frac{1}{4}}}\right).
$$

It now remains to bound

$$
\begin{aligned}
& \mathbb{E}\left[\left(1 + \left\|\mathfrak{M}_{\setminus i, c, [1:2]}\right\|_1 + \left\|\Psi_{c, [1:2]}\right\|_1 + \left\|\mathfrak{B}g_A + \mathfrak{C}^{\frac{1}{2}}g_2\right\|_1 + \left\|Bg_A + C^{\frac{1}{2}}g_2\right\|_1\right)^2\right] \\
& \le 4\mathbb{E}\left[1 + \left\|\mathfrak{M}_{\setminus i, c, [1:2]}\right\|^2 + \left\|\Psi_{c, [1:2]}\right\|^2 + \left\|g_{[1:2]}^{\mathfrak{S}}\right\|^2 + \left\|g_{[1:2]}^{\Phi}\right\|^2\right] \\
& \le 4 + O\left(\frac{\operatorname{polylog}(n)}{n}\right) + 12\left\|\Psi_{c, [1:2]}\right\|^2 + 4\mathbb{E}\left[\left\|g_{[1:2]}^{\mathfrak{S}}\right\|^2 + \left\|g_{[1:2]}^{\Phi}\right\|^2\right] \\
& \le 4 + O\left(\frac{\operatorname{polylog}(n)}{n}\right) + 12(m_c^2 + m_{0,c}^2) + 8\mathbb{E}\left[\operatorname{tr}\left[\Phi_{[:2,:2]}\right] + O_{L_2}\left(\frac{\operatorname{polylog}(n)}{\sqrt{n}}\right)\right] \\
& = 4 + O\left(\frac{\operatorname{polylog}(n)}{\sqrt{n}}\right) + 12(m_c^2 + m_{0,c}^2) + 8(q + q_0).
\end{aligned}
$$
It follows directly from Lemma F.3 and Lemma F.2 and the Cauchy-Schwartz inequality that the sequences $m_c, m_{0,c}, q, q_0$ are bounded $O(\text{polylog}(n))$. Thus, returning to (19),

$$ \left| \mathbb{E} \left[ \varphi \left( \mathfrak{M}_{\setminus i, c} + \mathfrak{S}_{\setminus i}^{\frac{1}{2}} g, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \Psi_{c_i} + \Phi^{\frac{1}{2}} g, c, \epsilon \right) \right] \right| = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right), $$

which concludes the proof. □

## D.2 Surrogate residuals

We are now in a position to prove a similar distributional statement for the surrogate residuals

$$ \begin{aligned} \tilde{r}_{i,i} &= \text{prox}_{\gamma_i \ell_i(\cdot, \tilde{u}_{i,i})} (r_{i,\setminus i} + \partial_u \ell_{0,i}(\tilde{u}_{i,i}) v_i), \\ \tilde{u}_{i,i} &= \text{prox}_{\gamma_{0,i} \ell_{0,i}(\cdot)} (u_{i,\setminus i}). \end{aligned} $$

The goal is to use the convergence result of Lemma D.2, leveraging the regularity of the proximal operators, and the concentration results of Lemmas C.5 and C.6.

**Lemma D.3 (Distribution of the surrogate residuals).** For any $i \in [n]$, introduce $\tilde{R}_{i,\setminus i} \in \mathbb{R}^{|V|+3}$ as

$$ \tilde{R}_{i, \setminus i} = \begin{bmatrix} \tilde{r}_{i, \setminus i} \\ \tilde{u}_{i, \setminus i} \\ \langle x_i, \beta \rangle \\ M x_i \end{bmatrix}. $$

Then for any function $\varphi: \mathbb{R}^{|V|+3} \in \mathcal{F}$, one has the convergence

$$ \left| \mathbb{E} \left[ \varphi \left( \tilde{R}_{i, \setminus i}, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi (G, c, \epsilon) \right] \right| = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right), $$

where

$$ G = \begin{bmatrix} \text{prox}_{V\ell(\cdot, \text{prox}_{V_0\ell_0(\cdot, g_3, c, \epsilon)}(g_2), g_3, c, \epsilon)} (g_1 + \chi \partial_u \ell_0(\text{prox}_{V_0\ell_0(\cdot, g_3, c, \epsilon)}(g_2), g_3, c, \epsilon), g_3, c, \epsilon)) \\ \text{prox}_{V_0\ell_0(\cdot, g_3, c, \epsilon)}(g_2) \\ g_3 \\ g[4:|V|+3] \end{bmatrix}. $$

where $g_1, g_2, g_3, g[4:|V|+3] = (g_i)_{i \ge 4}$ designate the entries of a Gaussian vector $g \in \mathbb{R}^{|V|+3}$ with law

$$ g \sim \mathcal{N}(\Psi_c, \Phi), $$

conditionally on c. $\Psi_c, \Phi$ were defined in Lemma D.2.

**Proof.** To alleviate the notations, we will in this proof use the shorthands

$$ f_{v_1, v_2, v_3}(r, u) = \text{prox}_{v_1 \ell(\cdot, \text{prox}_{v_2 \ell_0(\cdot, \langle x_i, \beta \rangle, c_i, \epsilon)}(u), \langle x_i, \beta \rangle, c_i, \epsilon_i)} \left( r + v_3 \partial_u \ell_0(\text{prox}_{v_2 \ell_0(\cdot, \langle x_i, \beta \rangle, c_i, \epsilon)}(u), \langle x_i, \beta \rangle, c_i, \epsilon_i) \right), $$

$$ h_{v_2}(u) = \text{prox}_{v_2 \ell_0(\cdot, \langle x_i, \beta \rangle, c_i, \epsilon_i)}(u). $$
We can decompose the objective as

$$
\begin{align}
& \left| \mathbb{E} \left[ \varphi \left( \tilde{R}_{i, \setminus i}, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi (G, c, \epsilon) \right] \right| \nonumber \\
&= \left| \mathbb{E} \left[ \varphi \left( \left( \begin{array}{c} f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right) , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi (G, c, \epsilon) \right] \right| \nonumber \\
&\le \left| \mathbb{E} \left[ \varphi \left( \left( \begin{array}{c} f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right) , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \left( \begin{array}{c} f_{V, V_0, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{V_0}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right) , c_i, \epsilon_i \right) \right] \right| \nonumber \\
&\quad + \left| \mathbb{E} \left[ \varphi \left( \left( \begin{array}{c} f_{V, V_0, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{V_0}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right) , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi (G, c, \epsilon) \right] \right| . \tag{20}
\end{align}
$$

In words, we first replace the stochastic statistics $\gamma_i, \gamma_{0,i}, v_i$ by their deterministic equivalents $V, V_0, \chi$. The associated error is controlled by the first term of the right-hand side. Then, the second term bounds the approximation when replacing the expectations over the leave-one-out residuals $r_{i,\setminus i}, u_{i,\setminus i}$ by the associated Gaussian averages. We first examine the latter. One can guarantee that the associated error term vanishes as $n \to \infty$ from Lemma D.2, provided one establishes beforehand that the compound function

$$
\tilde{\varphi} : \left[ \begin{array}{c} r \\ u \\ s \\ \omega \end{array} \right] , c, \epsilon \rightarrow \varphi \left( \left[ \begin{array}{c} f_{V,V_0,\chi}(r, u) \\ h_{V_0}(u) \\ s \\ \omega \end{array} \right] , c, \epsilon \right) .
$$

belongs to $\mathcal{F}$, namely is pseudo-Lipschitz in its first two arguments and admits a polynomial majorant in the others. For that purpose, it is sufficient to show that $h_{V_0}$ and $f_{V,V_0,\chi}$ are pseudo-Lipschitz. The first claim follows from the contractivity of the proximal operator. Examining the second claim, let us take $(u_1, r_1), (u_2, r_2) \in \mathbb{R}^2$ and bound

$$
|f_{V,V_0,\chi}(r_1, u_1) - f_{V,V_0,\chi}(r_2, u_2)| \le |f_{V,V_0,\chi}(r_1, u_1) - f_{V,V_0,\chi}(r_2, u_1)| + |f_{V,V_0,\chi}(r_2, u_1) - f_{V,V_0,\chi}(r_2, u_2)|.
$$
It follows from the contractivity of the proximal operator that

$$|f_{V,V_0,\chi}(r_1, u_1) - f_{V,V_0,\chi}(r_2, u_1)| \le |r_1 - r_2|.$$

On the other hand,

$$ 
\begin{aligned}
& f_{V,V_0,\chi}(r_2, u_1) - f_{V,V_0,\chi}(r_2, u_2) \\
&= \chi \left( \partial_u \ell_0(\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_1), s, c, \epsilon) - \partial_u \ell_0(\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_2), s, c, \epsilon) \right) \\
&\quad + V \left[ \partial_r \ell \left( f_{V,V_0,\chi}(r_2, u_2), \operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_2), s, c, \epsilon) - \partial_r \ell \left( f_{V,V_0,\chi}(r_2, u_1), \operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_1), s, c, \epsilon) \right) \right] \\
&= \chi \left( \partial_u \ell_0(\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_1), s, c, \epsilon) - \partial_u \ell_0(\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_2), s, c, \epsilon) \right) \\
&\quad + V \left[ \partial_r^2 \ell (\tilde{r}, \tilde{u}, s, c, \epsilon) (f_{V,V_0,\chi}(r_2, u_2) - f_{V,V_0,\chi}(r_2, u_1)) \right. \\
&\qquad \left. + \partial_r \partial_u \ell (\tilde{r}, \tilde{u}, s, c, \epsilon) (\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_2) - \operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_1)) \right],
\end{aligned}
$$

for some $(\tilde{r}, \tilde{u})$ lying on the line connecting $f_{V,V_0,\chi}(r_2, u_2)$, $\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_2)$ and $f_{V,V_0,\chi}(r_2, u_1)$, $\operatorname{prox}_{V_0\ell_0(\cdot, \cdot, c, \epsilon)}(u_1)$, leveraging the mean-value theorem. Thus,

$$ 
\begin{aligned}
|f_{V,V_0,\chi}(r_2, u_1) - f_{V,V_0,\chi}(r_2, u_2)| &\le \frac{1}{1 + V \partial_r^2 \ell (\tilde{r}, \tilde{u}, y, c_i, \epsilon)} \left[ \left( |\chi| \|\partial_u^2 \ell_0\|_{\infty} + V \|\partial_r \partial_u \ell\|_{\infty} \right) |u_2 - u_1| \right] \\
&\le \left( |\chi| \|\partial_u^2 \ell_0\|_{\infty} + \frac{1}{\lambda} \|\partial_r \partial_u \ell\|_{\infty} \right) |u_2 - u_1|,
\end{aligned}
$$

using again the contractivity of the proximal operator and the rough bound $V = 1/n\mathbb{E}[\operatorname{tr}[H^{-1}]] \le \mathbb{E}[\|H^{-1}\|] \le 1/\lambda$. It now remains to bound $\chi = 1/n\mathbb{E}[\operatorname{tr}[H^{-1}GH_0^{-1}]]$. One has

$$ 
\begin{aligned}
\chi &= \frac{1}{n} \mathbb{E} \left[ \operatorname{tr} [H^{-1} G H_0^{-1}] \right] \le \frac{1}{\lambda \lambda_0} \mathbb{E} [\|G\|] \\
&\le \frac{1}{\lambda \lambda_0} \|\partial_r \partial_u \ell\|_{\infty} \mathbb{E} \left[ \|\hat{\Sigma}\| \right] \le O(\operatorname{polylog}(n))
\end{aligned}
$$

using Lemma F.4. Thus,

$$|f_{V,V_0,\chi}(r_1, u_1) - f_{V,V_0,\chi}(r_2, u_2)| \le O(\operatorname{polylog}(n))(|r_1 - r_2| + |u_1 - u_2|),$$

which shows that $f_{V,V_0,\chi}$ is Lipschitz, and thus so is $\tilde{\varphi}$. To complete the demonstration that $\tilde{\varphi} \in \mathcal{F}$, we now need to construct a polynomial majorant in its remaining variables. We note that

$$ \tilde{\varphi} \left( \begin{bmatrix} 0 \\ 0 \\ \frac{s}{\omega} \\ \end{bmatrix}, c, \epsilon \right) = \varphi \left( \begin{bmatrix} f_{V,V_0,\chi}(0,0) \\ h_{V_0}(0) \\ \frac{s}{\omega} \\ \end{bmatrix}, c, \epsilon \right) \le L_{\varphi} (|f_{V,V_0,\chi}(0,0)| + |h_{V_0}(0)|) + Q_{\varphi} \left( \begin{bmatrix} \frac{s}{\omega} \\ \end{bmatrix}, \epsilon \right) $$
But on the one hand

$$|h_{V_0}(0)| \leq \frac{1}{\lambda_0} \|\partial_u \ell_0\|_{\infty},$$

while on the other hand

$$|f_{V,V_0,\chi}(0,0)| \leq \chi \|\partial_u \ell_0\|_{\infty} + \frac{1}{\lambda} \|\partial_r \ell\|_{\infty}.$$

One can thus bound the test function as

$$\tilde{\varphi}\left(\left[\begin{array}{c} 0 \\ 0 \\ \frac{s}{\omega} \\ \end{array}\right], c, \epsilon\right) \leq O(\text{polylog}(n)) + \left|Q_{\varphi}\left(\left[\begin{array}{c} \frac{s}{\omega} \\ \end{array}\right], c, \epsilon\right)\right| \\ \leq 1 + O(\text{polylog}(n)) + Q_{\varphi}\left(\left[\begin{array}{c} \frac{s}{\omega} \\ \end{array}\right], \epsilon\right)^2,$$

yielding a polynomial majorant (recall that we allow coefficients to be $O(\text{polylog}(n))$). Thus, we have established that $\tilde{\varphi} \in \mathcal{F}$. One can thus apply Lemma D.2, and approximate the expectation over leave-one-out residuals by the corresponding Gaussian expectation

$$\left| \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}) \\ h_{V_0}(u_{i,\setminus i}) \\ \langle x_i, \beta \rangle \\ \end{array} \right] , c_i, \epsilon_i \right) \middle| \mathcal{M} x_i \right] - \mathbb{E} \left[ \varphi(G, c, \epsilon) \right] \right| = O \left( \frac{\text{polylog}(n)}{n^{\frac{1}{4}}} \right).$$

Returning to (20), we now aim to bound the first term in the decomposition (20). We decompose it into
three error terms, which we sequentially control:

$$
\begin{aligned}
& \left\| \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V, V_0, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{V_0}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] \right\| \\
\le & \left\| \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] \right\| \\
& \left\| \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V, \gamma_{0,i}, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V, V_0, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{V_0}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] \right\| \\
& \left\| \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V, \gamma_{0,i}, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{\gamma_{0,i}}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V, V_0, \chi}(r_{i, \setminus i}, u_{i, \setminus i}) \\ h_{V_0}(u_{i, \setminus i}) \\ \langle x_i, \beta \rangle \\ \mathcal{M} x_i \end{array} \right] , c_i, \epsilon_i \right) \right] \right\|.
\end{aligned}
$$

Because $\varphi$ is $L_\varphi$- Lipschitz in its first variable up to linear terms, the first error can be controlled by

$$
L_{\varphi} \mathbb{E} [R(r_{i, \setminus i}, u_{i, \setminus i}) | f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i, \setminus i}, u_{i, \setminus i}) - f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i, \setminus i}, u_{i, \setminus i})] \le L_{\varphi} \|\partial_u \ell_0\|_{\infty} \mathbb{E} [|\chi - v_i|^2|^{1/2} \mathbb{E} [R(r_{i, \setminus i}, u_{i, \setminus i})^2|^{1/2}
$$

We used Hölder's inequality, and introduced the linear Lipschitz majorant

$$
\begin{aligned}
R(r_{i, \setminus i}, u_{i, \setminus i}) = & 1 + |f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i, \setminus i}, u_{i, \setminus i})| + |f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i, \setminus i}, u_{i, \setminus i})| \\
& + |f_{V, \gamma_{0,i}, \chi}(r_{i, \setminus i}, u_{i, \setminus i})| + |f_{V, V_0, \chi}(r_{i, \setminus i}, u_{i, \setminus i})| + |h_{\gamma_{0,i}}(u_{i, \setminus i})| + |h_{V_0}(u_{i, \setminus i})|.
\end{aligned}
$$

So as not to repeat several times the analysis, we chose to include more terms than required by the property (18), so that the bound we establish for $R(r_{i,\setminus i}, u_{i,\setminus i})$ can be reemployed for the other two error terms.

Since Lemma C.6 guarantees $\mathbb{E}[|\chi - v_i|^2]^{1/2} = O(\text{polylog}(n)/\sqrt{n})$, we only need to bound $\mathbb{E}[R(r_{i,\setminus i}, u_{i,\setminus i})^2]$ by
$O(\text{polylog}(n))$. We have

$$
\begin{aligned}
\frac{1}{7} R(r_{i,\setminus i}, u_{i,\setminus i})^2 &\le 1 + 12r_{i,\setminus i}^2 + 3(v_i^2 + 3\chi^2) \|\partial_u \ell_0\|_{\infty}^2 + 3(2\gamma_i^2 + 2V^2) \|\partial_r \ell\|_{\infty}^2 + 4u_{i,\setminus i}^2 + 2(\gamma_{0,i}^2 + V_0^2) \|\partial_u \ell_0\|_{\infty}^2 \\
&\le 1 + 12(\sup_{i \in [n]} |r_{i,\setminus i}|)^2 + 12\chi^2 \|\partial_u \ell_0\|_{\infty}^2 + 12V^2 \|\partial_r \ell\|_{\infty}^2 + 4(\sup_{i \in [n]} |u_{i,\setminus i}|)^2 \\
&\quad + 4V_0^2 \|\partial_u \ell_0^2\|_{\infty}^2 + O_{L_1} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right)
\end{aligned}
$$

Lemma F.7 ensures that $\sup_{i \in [n]} |r_{i,\setminus i}|, \sup_{i \in [n]} |u_{i,\setminus i}| + O_{L_k}(\text{polylog}(n))$. Finally, we established above that $\chi, V, V_0$ are bounded by $O(\text{polylog}(n))$. Thus

$$ \mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i})^2]^{\frac{1}{2}} = O(\text{polylog}(n)). $$

Hence

$$ \mathbb{L}_{\varphi} \mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i}) | f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i})] \le \mathbb{L}_{\varphi} \|\partial_u \ell_0\|_{\infty} O \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

The second error term is similarly controlled by

$$ \mathbb{L}_{\varphi} \mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i}) | f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i})]. $$

Since

$$
\begin{aligned}
& f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) \\
&= -\gamma_i \partial_r \ell \left( f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}), \text{prox}_{\gamma_{0,i}, \ell_0(\cdot, \langle \beta, x_i \rangle, c_i, \epsilon)}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right) \\
&\quad + V \partial_r \ell \left( f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}), \text{prox}_{\gamma_{0,i}, \ell_0(\cdot, \langle \beta, x_i \rangle, c_i, \epsilon)}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right) \\
&= -V \partial_r^2 \ell \left( \tilde{r}, \text{prox}_{\gamma_{0,i}, \ell_0(\cdot, \langle \beta, x_i \rangle, c_i, \epsilon)}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right) \left( f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) \right) \\
&\quad + (V - \gamma_i) \partial_r \ell \left( f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}), \text{prox}_{\gamma_{0,i}, \ell_0(\cdot, \langle \beta, x_i \rangle, c_i, \epsilon)}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right),
\end{aligned}
$$

for some $\tilde{r}$ in the unordered interval $(f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}), f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}))$, from the mean value theorem. Thus

$$ \left| f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) \right| \le \left| \frac{(V - \gamma_i) \partial_r \ell \left( f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}), \text{prox}_{\gamma_{0,i}, \ell_0(\cdot, \langle \beta, x_i \rangle, c_i, \epsilon)}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right)}{1 + V \partial_r^2 \ell \left( \tilde{r}, \text{prox}_{\gamma_{0,i}, \ell_0(\cdot, \langle \beta, x_i \rangle, c_i, \epsilon)}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right)} \right|, $$

from which the bound follows:

$$
\begin{aligned}
\mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i}) | f_{\gamma_i, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i})] &\le \|\partial_r \ell\|_{\infty} \mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i})^2]^{\frac{1}{2}} \mathbb{E} [|V - \gamma_i|^2]^{\frac{1}{2}} \\
&\le \|\partial_r \ell\|_{\infty} O \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right),
\end{aligned}
$$

using Hölder's inequality and the concentration result C.5. The last error term is controlled by

$$ \mathbb{L}_{\varphi} \mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i}) | f_{V, \gamma_{0,i}, \chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V, V_0, \chi}(r_{i,\setminus i}, u_{i,\setminus i})] + \mathbb{L}_{\varphi} \mathbb{E} [R(r_{i,\setminus i}, u_{i,\setminus i}) | h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i})]. $$
Using the same reasoning as above, there exists $\tilde{u} \in (h_{\gamma_{0,i}}(u_{i,\setminus i}), h_{V_0}(u_{i,\setminus i}))$ such that

$$h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i}) = \frac{1}{1 + V_0 \partial_u^2 \ell_0(\tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i)} \partial_u \ell_0(h_{\gamma_{0,i}}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i)(V_0 - \gamma_{0,i}).$$

Using Lemma C.5, it follows that

$$\mathbb{E} \left[ R(r_{i,\setminus i}, u_{i,\setminus i}) | h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i}) \right] \le \|\partial_u \ell\|_{\infty} \mathcal{O} \left( \frac{\mathrm{polylog}(n)}{\sqrt{n}} \right).$$

Finally, control of $\mathbb{E} \left[ |f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i})| \right]$ can be obtained as follows:

$$\begin{align*}
& f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}) \\
&= \chi \left( \partial_u \ell_0(h_{\gamma_{0,i}}(u_{i,\setminus i}), \langle x_i, \beta \rangle, c_i, \epsilon_i) - \partial_u \ell_0(h_{V_0}(u_{i,\setminus i}), \langle x_i, \beta \rangle, c_i, \epsilon_i) \right) \\
&\quad - V \left( \partial_r \ell \left( f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}), h_{\gamma_{0,i}}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right) - \partial_r \ell \left( f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}), h_{\gamma_{0,i}}(u_{i,\setminus i}), \langle \beta, x_i \rangle, c_i, \epsilon_i \right) \right) \\
&= \chi \partial_u^2 \ell_0(\tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i) (h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i})) \\
&\quad - V \partial_r^2 \ell (\tilde{r}, \tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i) (f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i})) \\
&\quad - V \partial_r \partial_u \ell (\tilde{r}, \tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i) (h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i})),
\end{align*}$$

for some $\tilde{u}, \tilde{u} \in (h_{\gamma_{0,i}}(u_{i,\setminus i}), h_{V_0}(u_{i,\setminus i}))$ and $\tilde{r} \in (f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}), f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}))$, applying the mean value theorem. One can thus express $f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i})$ as

$$f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}) = \frac{(\chi \partial_u^2 \ell_0(\tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i) - V \partial_r \partial_u \ell(\tilde{r}, \tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i))(h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i}))}{1 + V \partial_r^2 \ell(\tilde{r}, \tilde{u}, \langle \beta, x_i \rangle, c_i, \epsilon_i)},$$

from which it follows that

$$|f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i})| \le \left[ \chi \left\| \partial_u^2 \ell_0 \right\|_{\infty} + \frac{1}{\lambda} \| \partial_r \partial_u \ell \|_{\infty} \right] |h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i})|.$$

Thus, from Hölder's inequality and the previous bound on $|h_{\gamma_{0,i}}(u_{i,\setminus i}) - h_{V_0}(u_{i,\setminus i})|$,

$$\mathbb{E} \left[ R(r_{i,\setminus i}, u_{i,\setminus i}) | f_{V,\gamma_{0,i},\chi}(r_{i,\setminus i}, u_{i,\setminus i}) - f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}) \right] = O \left( \frac{\mathrm{polylog}(n)}{\sqrt{n}} \right).$$

Putting these three bounds together finally yields

$$\left| \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} \left( \begin{array}{c} f_{\gamma_i, \gamma_{0,i}, v_i}(r_{i,\setminus i}, u_{i,\setminus i}) \\ h_{\gamma_{0,i}}(u_{i,\setminus i}) \\ \hline y_i \end{array} \right] \middle| \mathcal{M} x_i \end{array} \right) , c_i, \epsilon_i \right] \right) - \mathbb{E} \left[ \varphi \left( \left[ \begin{array}{c} f_{V,V_0,\chi}(r_{i,\setminus i}, u_{i,\setminus i}) \\ h_{V_0}(u_{i,\setminus i}) \\ \hline y_i \end{array} \right] \middle| \mathcal{M} x_i \end{array} \right) , c_i, \epsilon_i \right] \right| = O \left( \frac{\mathrm{polylog}(n)}{\sqrt{n}} \right).$$

Returning to the original objective (20), one finally reaches

$$\left| \mathbb{E} \left[ \varphi \left( \tilde{R}_{i,\setminus i}, c_i, \epsilon_i \right) \right] - \mathbb{E} \left[ \varphi (G, c, \epsilon) \right] \right| = O \left( \frac{\mathrm{polylog}(n)}{n^{1/4}} \right),$$

which completes the proof. $\square$
# E Proof of Theorem 2.1

Equipped with the results of Appendices B, C and D, we are now in a position to conclude the proof of Theorem 2.1.

## E.1 Deterministic equivalents

To summarize the proof so far, we have shown in Appendix C that the summary statistics $m_c = \langle \hat{w}, \mu_c \rangle$, $h = \langle \hat{w}, \beta \rangle$, $t = \langle \hat{w}, \hat{w}_0 \rangle$, $q = \|\hat{w}\|^2$ and $\mathfrak{M} = 1/n \text{tr}[H_{\backslash i}^{-1}]$, $\mathfrak{X} = 1/n \text{tr}[H^{-1}GH_0^{-1}]$ concentrate in $L_2$ to their expectations $m_c$, $\theta$, $t$, $q$, $V$, $\chi$. In this subsection, we compute the latter, leveraging the results of Appendix D that characterize the distribution of the involved residuals. Throughout this section $g \sim \mathcal{N}(\Psi_c, \Phi)$ denotes a Gaussian variable with mean and covariance

$$ \Psi_c = \begin{bmatrix} m_c \\ m_{0,c} \\ \nu_c \\ \rho_c \end{bmatrix}, $$

$$ \Phi = \begin{bmatrix} q & t & \theta & m \\ t & q_0 & \theta_0 & m_0 \\ \theta & \theta_0 & \varrho & \nu \\ m & m_0 & \nu & \rho \end{bmatrix}, $$

conditionally on c. We will also use the shorthands

$$ r = \text{prox}_{V\ell(\cdot, u, g_3, c, \epsilon)} (g_1 + \chi \partial_u \ell_0(u, g_3, c, \epsilon), g_3, c, \epsilon), $$

$$ u = \text{prox}_{V_0 \ell_0(\cdot, g_3, c, \epsilon)}(g_2), $$

where the values of $\epsilon$, $c$ are understood from the expectations inside which $r$, $u$ appear. All expectations are understood to bear over $c$, $\epsilon$, $g$. We will also employ the shorthand $s_i = \langle x_i, \beta \rangle$, so that $y_i = \phi(s_i, c_i, \epsilon_i)$.

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

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

*Proof.* We start from the optimality identity

$$ \hat{w} = -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \partial_r \ell_i(r_i, u_i) x_i. $$

Taking an inner product with $\beta$,

$$ \langle \hat{w}, \beta \rangle = -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \partial_r \ell_i(r_i, u_i) s_i. \quad (21) $$

Before taking an expectation, we first approximate the full residuals $r_i, u_i$ by the surrogates $\tilde{r}_{i,i}, \tilde{u}_{i,i}$. The associated correction can be controlled as

$$ \left| \frac{1}{n} \sum_{i \in [n]} \left( \partial_r \ell_i(r_i, u_i) - \partial_r \ell_i(\tilde{r}_{i,i}, \tilde{u}_{i,i}) \right) s_i \right| \\ \le \left( \left\| \partial_r^2 \ell \right\|_{\infty} \vee \left\| \partial_r \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) \sup_{i \in [n]} |s_i| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$
We used Proposition B.1, Proposition B.10 and Lemma F.7. Thus, taking expectation in (21),

$$ \theta = -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \mathbb{E} \left[ \partial_r \ell(\tilde{r}_{i,i}, \tilde{u}_{i,i}, y_i, c_i, \epsilon_i) s_i \right] + O \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right) $$

By permutation symmetry of the problem, all expectations are equal, and

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

Note that $\partial_r \ell \in \mathcal{F}$ from Assumption A.3. Thus, one can apply Lemma D.3, from which it follows that

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

This proves the Lemma.

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

A similar characterization for $m_c$ follows from identical steps.

**Lemma E.2 (Characterization of $m_c$).** For any $c \in \mathcal{V}$, the summary statistic $m_c = \mathbb{E}[\mathbf{m}_c]$ is asymptotically characterized by the self-consistent equation

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

where $g_c$ is the entry of g associated to c.

*Proof.* The proof proceeds in identical fashion to that of Lemma E.1. Taking an inner product on the optimality condition,

$$ \langle \hat{w}, \mu_c \rangle = -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \partial_r \ell(r_i, u_i, y_i, c_i, \epsilon_i) \langle x_i, \mu_c \rangle. $$

Once more, we approximate the full residuals $r_i, u_i$ by the surrogates $\tilde{r}_{i,i}, \tilde{u}_{i,i}$. The associated correction can be controlled as

$$ \left| \frac{1}{n} \sum_{i \in [n]} \left( \partial_r \ell(r_i, u_i, y_i, c_i, \epsilon_i) - \partial_r \ell(\tilde{r}_{i,i}, \tilde{u}_{i,i}, y_i, c_i, \epsilon_i) \right) \langle x_i, \mu_c \rangle \right| \\ \le \left( \left\| \partial_r^2 \ell \right\|_{\infty} \vee \left\| \partial_r \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) \sup_{i \in [n]} |\langle x_i, \mu_c \rangle| = O_{L_k} \left( \frac{\text{polylog}(n)}{\sqrt{n}} \right). $$

We used Proposition B.1, Proposition B.10 and Lemma F.7 on the normalized vector $\mu_c/\|\mu\|_c$. The remainder of the proof is identical to that of Lemma E.1.

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

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

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

*Proof.* We again follow the lines of Lemma E.1. Taking an inner product on the optimality condition,

$$ \langle \hat{w}, \hat{w}_0 \rangle = -\frac{1}{\lambda} \frac{1}{n} \sum_{i \in [n]} \partial_r \ell(r_i, u_i, y_i, c_i, \epsilon_i) u_i. $$
Once more, we approximate the full residuals $r_i, u_i$ by the surrogates $\tilde{r}_{i,i}, \tilde{u}_{i,i}$. The associated correction can be controlled as

$$ \left| \frac{1}{n} \sum_{i \in [n]} \left( \partial_r \ell(r_i, u_i, y_i, c_i, \epsilon_i) - \partial_r \ell(\tilde{r}_{i,i}, \tilde{u}_{i,i}, y_i, c_i, \epsilon_i) \right) u_i + \partial_r \ell(\tilde{r}_{i,i}, \tilde{u}_{i,i}, y_i, c_i, \epsilon_i) (u_i - \tilde{u}_{i,i}) \right| \\ \le \left( \left\| \partial_r^2 \ell \right\|_{\infty} \vee \left\| \partial_r \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) \sup_{i \in [n]} |u_i| + \left\| \partial_r \ell \right\|_{\infty} \sup_{i \in [n]} |u_i - \tilde{u}_{i,i}|. $$

Controlling $\sup_{i \in [n]} |u_i|$ requires slightly more work. One has

$$ \sup_{i \in [n]} |u_i| \le \sup_{i \in [n]} |u_i - u_{i, \setminus i}| + \sup_{i \in [n]} |u_{i, \setminus i}| \le O_{L_k} \left( \frac{\mathrm{polylog}(n)}{\sqrt{n}} \right) + O_{L_k} (\mathrm{polylog}(n)). $$

We used Proposition B.1 with Lemma B.6 with a Cauchy-Schwartz bound for the first term, and Lemma F.7 in conjunction with Lemma F.2 for the second. Thus,

$$ \left| \frac{1}{n} \sum_{i \in [n]} \left( \partial_r \ell(r_i, u_i, y_i, c_i, \epsilon_i) - \partial_r \ell(\tilde{r}_{i,i}, \tilde{u}_{i,i}, y_i, c_i, \epsilon_i) \right) u_i \right| = O_{L_k} \left( \frac{\mathrm{polylog}(n)}{\sqrt{n}} \right). $$

Thus, taking expectations and by symmetry,

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

It remains to check that the function $\varphi: r, u, s, c, \epsilon \to \partial_r \ell(r, u, \phi(s, c, \epsilon), c, \epsilon)u$ belongs to the class $\mathcal{F}$. For any pairs $(r_1, u_1), (r_2, u_2)$, the mean value theorem guarantees the existence of $(\tilde{r}, \tilde{u})$ on the line connecting the points such that

$$ |\varphi(r_1, u_1, s, c, \epsilon) - \varphi(r_2, u_2, s, c, \epsilon)| \le \|\nabla_{r,u}\varphi(\tilde{r}, \tilde{u}, s, c, \epsilon)\| \sqrt{(r_1 - r_2)^2 + (u_1 - u_2)^2} $$

where $\|\nabla_{r,u}\varphi(\tilde{r}, \tilde{u}, s, c, \epsilon)\|$ denotes the norm of the gradient of $\varphi$ with respect to its first two arguments, evaluated at $(\tilde{r}, \tilde{u})$. This norm can in turn be bounded as

$$ \begin{aligned} \| \nabla_{r,u} \varphi(\tilde{r}, \tilde{u}, s, c, \epsilon) \| &= \sqrt{\left( \partial_r^2 \ell(\tilde{r}, \tilde{u}, \phi(s, c, \epsilon), c, \epsilon) \tilde{u} \right)^2 + \left( \partial_r \partial_u \ell(\tilde{r}, \tilde{u}, \phi(s, c, \epsilon), c, \epsilon) \tilde{u} + \partial_r \ell(\tilde{r}, \tilde{u}, \phi(s, c, \epsilon), c, \epsilon) \right)^2} \\ &\le \sqrt{\| \partial_r^2 \ell \|_{\infty}^2 \tilde{u}^2 + 2 \| \partial_r \partial_u \ell \|_{\infty}^2 \tilde{u}^2 + 2 \| \partial_r \ell \|_{\infty}^2} \\ &\le \sqrt{\| \partial_r^2 \ell \|_{\infty}^2 + 2 \| \partial_r \partial_u \ell \|_{\infty}^2 (|u_1| + |u_2|) + \sqrt{2 \| \partial_r \ell \|_{\infty}^2}}. \end{aligned} $$

Thus $\varphi$ satisfies the local Lipschitz property (18). Furthermore, $\varphi$ vanishes when evaluated at 0, implying trivially the existence of a polynomial majorant. 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{u}_{1,1} \right] - \mathbb{E} \left[ \partial_r \ell(r, u, g_3, c, \epsilon) u \right] \right| \xrightarrow{n \to \infty} 0. $$

This proves the Lemma.

□

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

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