Influence Diagnostics in High-dimensional M-estimation: Precise Asymptotics

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

Influence Diagnostics in High-dimensional M-estimation: Precise Asymptotics

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

Influence Diagnostics in High-dimensional M-estimation: Precise Asymptotics Hugo Cui Université Paris-Saclay, CNRS, Laboratoire de mathématiques d’Orsay, 91405, Orsay, France

arXiv:2607.09250v1 [stat.ML] 10 Jul 2026

Abstract The impact of a given training point on a statistical model is classically measured through its leave-one-out influence, which quantifies the effect of its removal from the training set on the model accuracy. While the statistics of leave-one-out influences are well understood in the low-dimensional, large sample limit n ! ∞, d = O(1), they become more intricate in high dimensions, as the influence of a given sample develops non-trivial dependencies on all other training samples. For convex M-estimation under Gaussian design, in the high-dimensional limit n ≍ d, we show that the distribution of the influences across the training set converges to a limiting measure which we sharply characterize. Building on these results, we provide evidence that influential samples tend to lie close to the decision boundary, thereby making contact with a standard data selection heuristic in active learning.

Contents 1 Introduction 1.1 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 3

2 High-dimensional asymptotics of leave-one-out influences 2.1 ERM under Gaussian design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Influence metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Asymptotics of leave-one-out influences . . . . . . . . . . . . . . . . . . . . . . . 2.4 Main technical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5 5 6 7 8 13

3 Consequences for active learning 3.1 Related works on data selection . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Conditional influence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 15 17

4 Conclusion

19 1

A Assumptions and reminders A.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Leave-one-out approximation results . . . . . . . . . . . . . . . . . . . . . . . .

27 27 28 31

B Concentration of summary statistics B.1 Pointwise concentration of functional statistics . . . . . . . . . . . . . . . . . . B.2 Concentration of Cauchy integrals . . . . . . . . . . . . . . . . . . . . . . . . .

33 33 40

C Deterministic equivalents C.1 Asymptotic residual distribution . . . . . . . . . . . . . . . . . . . . . . . . . . C.2 Computation of the deterministic equivalents . . . . . . . . . . . . . . . . . . .

50 50 56

D Convergence of influence distributions D.1 Comments on the risk normalization . . . . . . . . . . . . . . . . . . . . . . . . D.2 Proof of Theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.3 Proof of Proposition 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69 69 72 74

E Auxiliary lemmas

F Extensions

G Details on numerical experiments

Introduction

How does a given training sample ultimately shape the predictions of a statistical model? Given a dataset D = {xi , yi }i∈JnK with n covariate/label pairs, the relevance of the i−th sample (xi , yi ) may be most naturally captured by its leave-one-out influence IFi , defined as the difference in test error or model parameters when training on D \ (xi , yi ) (from which the sample was deleted), rather than D. The leave-one-out influence thus isolates the impact of a sample on the trained model, affording a highly interpretable measure of importance. Perhaps then unsurprisingly, influences constitute a fundamental explainability metric at the confluence of several fields. Initially formalized in the seminal works of Hampel [1974], Cook [1979], Cook and Weisberg [1982, 1980], Hampel et al. [1986] as a diagnostic to probe model robustness or identify outliers, influence diagnostics are also used for data selection [Ting and Brochu, 2018] as a natural proxy for informativeness. In applied machine learning, influence metrics are leveraged to explicate black-box neural network predictions [Koh and Liang, 2017, Barshan et al., 2020] across a broad section of modern deep learning, from diffusion models [Mlodozeniec et al., 2025] to large language models [Schioppa et al., 2022]. From a mathematical standpoint, the properties of leave-one-out influences are rather well understood in the classical low-dimensional, large sample limit n ! ∞, d = O(1), in which 2

the influence of a given data point converges to a deterministic function (the influence function [Hampel, 1974, Hampel et al., 1986, Avella-Medina, 2017]), that depends solely on the considered sample. In stark contrast, many modern machine learning models rather operate in a high-dimensional regime where the ambient dimension d of the covariates is typically comparably large to the number of samples n. These regimes pose unique statistical challenges [Johnstone and Titterington, 2009, Maleki et al., 2026, Sur and Candès, 2019]. In particular, the standard convergence of leave-one-out influences breaks down, as the influence of an individual sample develops intricate statistical dependencies on all the other training samples. As a simple illustration of this distinct behavior, in contrast to the d ≪ n regime, the influence of a given point crucially retains when d ≳ n a non-trivial dependence on the sample complexity n/d. These complex correlations make the statistical analysis of influences in high dimensions a challenging task, and the latter has thus remained a largely uncharted question. The present work addresses this question in the context of the classical problem of highdimensional M-estimation with convex loss, under isotropic Gaussian design [El Karoui, 2013, 2018, Donoho and Montanari, 2016, Thrampoulidis et al., 2018, Sur and Candès, 2019]. In this framework, we precisely characterize the distribution of leave-one-out influences within the training set. More precisely, our main contributions are the following: • In the high-dimensional regime d ≍ n, we prove that the distribution of the leave-one-out influence of a data point on the final test error weakly converges to a limiting distribution, which we sharply characterize. The latter can be compactly expressed as the pushforward of a four-dimensional Gaussian distribution through a non-linear map that we specify. • We derive a stronger result for the DFBETA metric [Belsley et al., 1980], which quantifies the change in model parameters induced by the deletion of a given sample from the training set. The empirical distribution of DFBETAs across the training set is shown in the limit n ≍ d to concentrate to a limiting measure, which we again precisely characterize. • These results suggest that the average influence of a sample decreases with its distance to the decision boundary, putting on a principled footing well-known heuristics in active learning [Tong and Koller, 2001, Roth and Small, 2006, Wang and Shang, 2014]. We further qualitatively validate these findings in real-data experiments.

1.1

Related works

Influence functions — Leave-one-out deletion diagnostics find their roots in the robust statistics literature, where they were first developed in the seminal works of Cook [1979], Belsley et al. [1980], Cook and Weisberg [1980, 1982] for outlier detection in linear regression, and later extended by Johnson [1985] for logistic regression. Asymptotically as n ! ∞, these sample leave-one-out estimators converge to influence functions [Hampel et al., 1986], which formalize the notion of a first derivative, when perturbing the (population) data distribution along the direction of the probed sample [Hampel, 1974, Chatterjee and Hadi, 1986]. This formalism also 3

makes particularly clear the connection with re-weighting diagnostics [Pregibon, 1981, Cook, 1986, Thomas and Cook, 1990] (where a sample is infinitesimally downweighted in the empirical risk, rather than deleted), which in turn inspired methods for the computationally efficient approximation of leave-one-out influences in deep learning models, impulsed in particular by the work of Koh and Liang [2017]. Scarcer on the other hand is the understanding of the statistical properties of leave-one-out influences in high-dimensional regimes d ≳ n, in which case the aforementioned convergence to influence functions ceases to hold. We refer the interested reader to Fisher et al. [2022] for non-asymptotic bounds in the re-weighting case. Since many problems in applied statistics and machine learning are set in such high-dimensional regimes [Johnson, 1985, Maleki et al., 2026], this gap in comprehension poses significant barriers to a principled understanding and usage of influence diagnostics in such settings. The need for high-dimensional analyses of influence and related questions was, in fact, underlined as early as Huber [1973], and we refer the interested reader to Sur and Candès [2019] for additional discussion on a few surprises that arise in high-dimensional statistics, as opposed to the classical n ≫ d regime. The present manuscript contributes to bridging this gap in the proportional regime n ≍ d, for the celebrated problem of high-dimensional convex M-estimation under Gaussian design. High-dimensional M-estimation — A now rather mature body of works has been devoted to the study of M-estimators, namely Empirical Risk Minimization (ERM) problems over linear models, in the proportional high-dimensional regime n ≍ d, for Gaussian-distributed data (for instance [El Karoui, 2013, 2018, Donoho and Montanari, 2016, Thrampoulidis et al., 2018, Dobriban and Wager, 2018, Sur and Candès, 2019, Bellec, 2025]), making it a particularly natural testbed to investigate the high-dimensional behavior of leave-one-out influences. Further even, from a technical standpoint, leave-one-out procedures in fact constitute one of the key proof methods in the analysis of such problems. Formalized in particular in the works of El Karoui [2013], El Karoui et al. [2013], El Karoui [2018], leave-one-out techniques are formally leveraged to disentangle the statistical dependency of the estimator on any individual data point. These studies hence naturally lay the groundwork for the analysis of influence functions. The present work builds upon these foundations, and develops these ideas to characterize the high-dimensional distribution of leave-one-out influence. The remainder of the manuscript is organized as follows. Section 2 expounds our main technical contribution, namely a sharp characterization of the limiting influence distribution in the high-dimensional regime n ≍ d, for convex M-estimators under Gaussian design. The implications of these results are subsequently explored in section 3, where the limiting distributions are marginalized to determine how the influence depends, on average, on simpler geometric descriptors, such as the distance to the decision boundary, uncovering in which regions influential data points tend to lie. In doing so, we underline connections with well-known data selection strategies in active learning, which seek to identify informative samples.

High-dimensional asymptotics of leave-one-out influences

2.1

ERM under Gaussian design

We consider throughout the manuscript the problem of ERM with a linear model on a training set D = {xi , yi }i∈JnK , with n data points. Following a long stream of works in high-dimensional M-estimation [El Karoui et al., 2013, Donoho and Montanari, 2016, Thrampoulidis et al., 2018, Sur and Candès, 2019], we assume that the samples follow a Gaussian distribution xi ∼ N (0d , Id ) in dimension d, while the corresponding labels are given by yi = ϕ(⟨xi , β⟩),

(1)

for a unit-norm ground-truth vector β ∈ Sd−1 , and a link function ϕ : R ! R. For simplicity, we assume that the labels depend deterministically on the covariate, and defer a discussion of stochastic or noisy settings to Appendix F. Given the training set D, we now consider the ridge-regularized M-estimator ŵ = arg min w∈Rd

1 X λ 2 ℓ(⟨xi , w⟩ , yi ) + ∥w∥ , n 2

(2)

i∈JnK

where ℓ : R2 ! R+ is a loss function convex in its first variable, and λ > 0 designates the regularization strength. ℓ is further assumed to admit bounded derivatives up to order four. The performance of the learned model may then be quantified by the test error 2 Egen [ŵ] = Ex,y L(⟨x, ŵ⟩ , y) =: E(∥ŵ∥ , ⟨ŵ, β⟩), (3) which measures the average discrepancy between the model prediction ⟨x, ŵ⟩ and the true label y on a fresh test sample (x, y), according to a cost metric L : R2 ! R+ . The second equality builds on the observation that since x is Gaussian-distributed, the test error Egen is in fact a function 2 E : R+ × R ! R+ of the sole statistics ∥ŵ∥ , ⟨ŵ, β⟩. In the following, when considering binary classification, the test error Egen (3) is understood to be the misclassification error, namely the probability that a fresh test sample is wrongly classified by the trained model. Formally, L(z, y) = 1[sign(z) ̸= y], and correspondingly E(q, m) = 1/π arccos m/√q. When considering regression tasks, we instead adopt the standard mean squared error metric L(z, y) = (z − y)2 , for which E(q, m) = 1 + q − 2m. We refer the interested reader to subsection A.1 for a detailed list of technical assumptions on the loss function ℓ(·, ·) (2) and the test error metric E(·, ·) (3), of which we highlighted above only the most salient few. For any index i ∈ JnK, one may similarly define the leave-i-out estimator ŵ(i) , which minimizes the empirical risk ŵ(i) = arg min w∈Rd

X 1 λ 2 ℓ( xj , w , yj ) + ∥w∥ , n−1 2

(4)

j∈JnK\i

on the dataset D \ (xi , yi ) from which the i−th sample (xi , yi ) has been deleted. Observe that the sum of individual losses in the leave-i-out ERM (4) now needs to be normalized by 1/n − 1, 5

instead of 1/n as in the full ERM (2), so as to reflect the actual number of training samples, after deletion of (xi , yi ). Albeit subtle, this change does induce non-negligible contributions to influence metrics. We refer interested readers to additional related comments in Walker and Birch [1988]. We similarly denote by Egen [ŵ(i) ] the test error achieved by the leave−i− out estimator.

2.2

Influence metrics

Test error influence — The leave-one-out influence of the i−th sample on the accuracy of the learned model may then be evaluated by comparing the achieved test errors when (xi , yi ) is included in, or conversely excluded from, the training set. The sample leave-one-out influence of sample i on the test error IFi may then be defined as IFi = n Egen [ŵ] − Egen [ŵ(i) ] . (5) In the above display, the normalization by n in the definition of IFi makes it an order one quantity, as the effect of the deletion of a sample among the n comprised in the dataset is generically expected to be of order 1/n. The error influence IFi measures the loss (or gain) in accuracy caused by the removal of the sample (xi , yi ) from the training set : • A negative IFi indicates that the i−th sample is helpful in the learning of the model, as its deletion leads to an increase in test error. • Conversely, a positive IFi signals that the sample is misguiding the model, and its deletion allows for a decrease in test error. DFBETA — The test error influence IF (5) measures the sensitivity of the accuracy of the estimator on individual samples. For completeness, the present manuscript also covers another standard deletion diagnostic, the difference in betas (DFBETA), initially introduced for linear regression by Belsley et al. [1980]. DFBETAs measure the magnitude of the change in estimator, in Euclidean distance, following the deletion of a sample. For any i ∈ JnK, it is concisely defined as 2

DFBETAi = n ŵ − ŵ(i)

(6)

Cook’s distance — Finally, we briefly mention the existence of another standard deletion diagnostic, namely Cook’s distance [Cook, 1979], which measures the change in train-set predictions when a sample is deleted, normalized by the squared training error. Formally: 2 n X ŵ − ŵ(i) Ci =

∥X ŵ − y∥

(7)

denoting by X ∈ Rn×d the data matrix of vertically stacked {xi }i∈JnK , and y ∈ Rn the vector of associated labels. Because Cook’s distance is tailored for the special case of linear regression, we choose not to discuss it in depth, and postpone its study to Remark 2.3. 6

2.3

Asymptotics of leave-one-out influences

In order to analyze the influence metrics (5) and (6), it is hence essential tofirst develop a fine understanding of the joint statistics of the full ERM estimator ŵ (2), and the leave-iout estimate ŵ(i) (4), for any index i ∈ JnK. A closed-form expression of the corresponding discrepancy ŵ − ŵ(i) is known since the foundational works of El Karoui [2013], El Karoui et al. [2013], El Karoui [2018], with earlier related results emanating from the works of Hampel [1974], Pregibon [1981], Cook and Weisberg [1982]. In the notations of the present work, and incorporating minor additional technical results developed in Appendix D, this expression can be compactly written as 1 polylog(n) −1 ŵ = ŵ(i) − ∂ℓ(⟨ŵ, xi ⟩ , yi )H(i) xi + OLk . (8) n n In the above display, the OLk polylog(n)/n notation hides a random vector whose norm possesses k a k−th moment bounded by polylog(n)/n , for any integer k. We introduced the leave-i−out Hessian matrix D E X 1 H(i) = ∂2ℓ ŵ(j) , xi , yi xj x⊤ j + λId , n−1 j∈JnK\i

where ∂ denotes the derivative of the loss ℓ(·, ·) with respect to its first argument. In simple terms, the leave-one-out relation (8) captures the effect of adding (or equivalently, removing) a data point xi to the training set. This effect is proportional to the change in loss induced by this addition, as measured by the first derivative ∂ℓ(⟨ŵ, xi ⟩ , yi ), and is mediated by the Hessian matrix H(i) , which captures the geometry of the local loss landscape around the estimate ŵ(i) . Perturbation aligning with flatter directions (namely eigendirections of largest −1 eigenvalue of the inverse Hessian H(i) ) are thus conducive to the largest change in estimate −1 ŵ − ŵ(i) . The probabilistic behavior of the leave-i−out correction 1/n∂ℓ(⟨ŵ, xi ⟩ , yi )H(i) xi (8) varies sizably depending on the relative scalings of the number of samples n (which dictates the value of the normalization 1/n), and the ambient dimension d (which controls the size of −1 the random variables H(i) , xi ). It thus proves instructive to contrast briefly at this point the different asymptotic regimes, and highlight the challenges of high-dimensional settings.

Finite dimensions, large sample limit — In the classical large sample asymptotics n ! ∞ with finite covariate dimension d = On (1), the estimator ŵ tends to the minimizer of the population risk, while the Hessian H(i) converges to a deterministic limit. Both random variables thus become asymptotically deterministic, and lose all dependency on the realization or size of the training set D = {xj , yj }j∈JnK . As a result, the leave-one-out correction ŵ − ŵ(i) (8) becomes a simple, deterministic function of xi , yi alone, amenable to easy characterization [Hampel, 1974]. Its norm besides vanishes at a fast On (1/n) rate with high probability. Most earlier analyses of influence [Hampel et al., 1986, Tsiatis, 2006, Ting and Brochu, 2018] were 7

developed with this large-sample asymptotic regime in mind.

High-dimensional asymptotics — The situation is starkly different in the high-dimensional proportional regime where both n, d diverge n, d ! ∞, while remaining comparable, namely α := n/d = Θ(1). This asymptotic limit is a somewhat more accurate reflection of the regime in which a number of modern machine learning models operate, and is the object of a growing body of works, reviewed in e.g. Maleki et al. [2026]. Among those, El Karoui [2013, 2018], Donoho and Montanari [2016], Thrampoulidis et al. [2018] notably laid the foundations for the study of ERM −1 problems as n ≍ d. In this regime, the random variable 1/n∂ℓ(⟨ŵ, xi ⟩ , yi )H(i) xi (8) notably √ 1 becomes of order O( / n) in norm, and displays a richer probabilistic behavior. On the one hand, the estimator ŵ is generically biased [Sur and Candès, 2019] and bounded away from the population estimator at O(1) distance, and retains at leading order a non-trivial dependence on the realization of the training set D. By the same token, the rich statistics of random matrices such as the Hessian H(i) in the limit n ≍ d have been highlighted in a long stream of works, of which we can for instance mention [Marčenko and Pastur, 1967, Silverstein and Bai, 1995, −1 Dobriban and Wager, 2018]. The leave-i−out correction 1/n∂ℓ(⟨ŵ, xi ⟩ , yi )H(i) xi thus remains at leading order a random variable that retains a dependency on the full dataset D, as opposed to the sole sample xi in the finite-dimensional regime. As a consequence, it depends in particular on the size of the training set, a feature absent in the classical regime. As we shall establish more precisely below, the leave-i−out correction are characterized by a complex distribution, resulting from the intricate interaction between the random vectors ŵ, ŵ(i) , xi , mediated by the random matrix H(i) . These complex statistics in turn induce a non-trivial distribution for the sample influences {IFi , DFBETAi }i∈JnK (5),(6). Unraveling those intertwined correlations and sharply characterizing the limiting distribution of the sample influences constitutes the main technical contribution of the present work, which we expound in the following subsection.

2.4

Main technical results

We are now in a position to state our main technical result, namely a sharp characterization of the limiting distribution of the leave-one-out influences IFi (5) and DFBETAi (6), in the high-dimensional regime n ≍ d, for convex M-estimation under Gaussian design (2). The first result describes the marginal distribution of the test error influence IF, and answers the following question: what is the law of the test error influence of a data point sampled uniformly at random from the training set ? The following Theorem establishes that this marginal distribution converges weakly to a limiting measure, which can be compactly expressed as the pushforward of a Gaussian distribution in dimension four. Theorem 2.1 (Weak convergence of the influence distribution). Let {xi , yi }i∈JnK be the dataset, and {IFi }i∈JnK the corresponding leave-one-out influences on the test error (5) for the ERM (2). For any sequence of indices in ∈ JnK, in the asymptotic limit n, d ! ∞ with fixed ratio α := n/d, 8

the marginal distribution of IFin converges weakly to (9)

νIF ⇀ φIF ♯ N (04 , Q), in the sense that for any Lipschitz test function f : R ! R, Ez∼νIF f (z) = Ez∼φIF ♯N (04 ,Q) f (z) + O

polylog(n) 1

In the above displays, the map φIF : R4 ! R is defined as φIF (g) = proxV (1) ℓ(·,g2 ) (g1 ) − g1 V (1)

(0)

 (0) (0) (0) ∂1 E(Q(0) 12 , Q11 )g4 + ∂2 E(Q12 , Q11 )

(1)

(0)

2g3 +

proxV ℓ(·,g2 ) (g1 ) − g1 V (1)

(1)

! V (2) 

(10)

− 2λ∂2 E(Q12 , Q11 )Q11 − λ∂1 E(Q12 , Q11 )Q12 . The covariance Q ∈ R4 denotes the block matrix " Q(0) Q= Q(1)

Q(1) Q(2)

# .

The matrices Q(k) and scalars V (k) for k = 0, 1, 2 are related through I −1 1 −n/2 Q(k) = Ω(z)dz + O polylog(n)e , 2πi Γ z k I −1 1 −n/2 V (k) = V(z)dz + O polylog(n)e , 2πi Γ z k

(11)

(12) (13)

to resolvents Ω : C ! C2 and V : C ! C. In (12), Γ is chosen in {z ∈ (13), the contour p 2 2 C : Re{z} > 0} so as to enclose the interval J = λ, λ + ∂ ℓ ∞ 2 + 1/α at a distance dist (Γ, J) ≥ λ/2, while also satisfying dist (Γ, 0) ≥ λ/2. The resolvent Ω(·) furthermore converges pointwise for any z ∈ Γ with Im{z} ̸= 0 as    " # h i g   ∂ 2 ℓ(r, g2 )(Q(0) )+ 1 r g2     g2    Ω(z)  (λ − z)I + E (14)   2  2   1 + ∂ ℓ(r, g2 )V(z)      

r g2  ∂ 2 ℓ(r, g2 )∂ℓ(r, g2 )  0 0  = Q(0) + χ(z)E   1 + ∂ 2 ℓ(r, g2 )V(z) 

#   polylog(n)  , +O 1  n4 

where (Q(0) )+ denotes the Moore-Penrose pseudo-inverse of Q(0) . In the above display, V (1)

χ(z) =

(λ − z) + E

∂ 2 ℓ(r,g2 ) (1+V (1) ∂ 2 ℓ(r,g2 ))(1+V(z)∂ 2 ℓ(r,g2 ))

polylog(n) 1

(15)

and the Stieltjes transform V(·) satisfies for all z ∈ Γ, Im{z} ̸= 0 the self-consistent equation " # 1 ∂ 2 ℓ (r, g2 ) V(z) polylog(n) = O . (16) − (λ − z)V(z) − E 1 α 1 + ∂ 2 ℓ (r, g2 ) V(z) n4 Across the above displays, we employed the shorthand r = proxV (1) ℓ(·,g2 ) (g1 ). In words, the marginal probability distribution of the test error influence IF (5) can be concisely expressed in the n ≍ d limit as the pushforward of a four-dimensional Gaussian density with zero mean and covariance Q (11) through a non-linear map φIF (10). Both the map φIF and the covariance Q are shaped by a small set of 2 × 2 matrices Q(k) (k = 0, 1, 2) (12), and two scalars V (1) , V (2) (13), which capture key statistical and geometric descriptors of the ERM minimizer. For instance, for any given i ∈ JnK, "  # h i ⊤ ŵ polylog(n) −k  √ Q(k) = E  (i) H + O ŵ β (i) (i) n β⊤ captures the alignment of the leave-i-out estimator ŵ(i) with the ground truth vector β, in the geometry induced by the Hessian matrix H(i) . On the other hand, the statistics 1 h −k i polylog(n) √ V (k) = E tr H(i) +O n n describe the tracial moments of the inverse Hessian matrix, intuitively giving a sense of the local flatness/sharpness of the landscape around the ERM minimizer. The set of finite-dimensional parameters Q(k) , V (k) thus succintly subsume the asymptotic behavior of the ERMs (2) and (4) in the high-dimensional limit n ≍ d, and are consequently classically referred to under the umbrella of summary statistics in the exact asymptotics literature. The summary statistics Q(k) , V (k) can in turn be characterized in terms of functional statistics Ω : C ! C2 and V : C ! C. These complex-valued resolvents allow one to compactly encapsulate the statistics of the random Hessian matrix, in close likeness to the Stieltjes transform in random matrix theory, see e.g. Silverstein and Bai [1995]. We note that V(·) is in fact precisely the Stieltjes transform of the Hessian H(i) . Again analogously, the resolvents V(·), Ω(·) are characterized through self-consistent functional equations (14), (15) and (16). The four-dimensional Gaussian distribution N (04 , Q) which underlies the limiting influence distribution in fact corresponds to the weak limit (in a sense in Lemma D made E precise D E D C.2 in ApE −1 −1 pendix C) of the joint law of the random variables ⟨β, xi ⟩ , ŵ(i) , xi , β, H(i) xi , ŵ(i) , H(i) xi . 10

These random variables are simple geometric descriptors that reflect how the deleted sample xi aligns within the local geometry of the leave-i−out problem (4), around its minimizer ŵ(i) . This relationship between the Gaussian components of the asymptotic influence distribution φIF ♯N (04 , Q) (9) and simple geometric descriptors opens a valuable gateway to a finer analysis ofD the spatial dependencies of the influence. For instance, the conditional distribution of E IFi | ŵ(i) , xi can be qualitatively assessed by the pushforward through φIF of the Gaussian N (04 , Q) conditioned on its first entry. These ideas are explored in further detail in Section 3, in the context of the problem of active learning, in which one seeks to develop simple agnostic predictors of the influence (thus informativeness) of a given sample. Theorem 2.1 characterizes the asymptotic limit of the marginal distribution of the leave-oneout influence on the test error IF (5), for the high-dimensional ERMs (2) and (4). A stronger convergence result can be established for the DFBETA metric (6), bearing this time on the empirical distribution of DFBETAi over training samples. Namely, the next Proposition answers the following questions: what is the histogram of DFBETA influences? What fraction of samples within the training set are helpful, hurtful, or have small influence ? Proposition 2.2 (Concentration of the empirical DFBETA distribution). Let D = {xi , yi }i∈JnK be a randomly sampled dataset, and {DFBETAi }i∈JnK be the DFBETA influences (6) associated with the ERM (2). In the asymptotic limit n, d ! ∞ with fixed ratio α := n/d, the empirical distribution 1 X δDFBETAi ν̂D = n i∈JnK

converges in probability to the measure P

ν̂D − ! φD ♯ N (02 , Q(0) ), where the map φD : R2 ! R+ is defined by φD (g) =

proxV (1) ℓ(·,g2 ) (g1 ) − g1 V (1)

!2 V (2) .

More precisely, for any twice-differentiable bounded test function f with bounded derivatives, the concentration polylog(n) Ez∼ν̂D f (z) = Ez∼φD ♯N (02 ,Q(0) ) f (z) + O 1 n4 1

holds, namely empirical averages of functions of the DFBETAs concentrate at a polylog(n)/n 4 rate. In the above displays, the summary statistics V (1) , V (2) , Q(0) admit the characterizations (12) and (13) of Theorem 2.1. In the likeness of Theorem 2.1 for the test error influences, Proposition 2.2 shows that the distribution for the DFBETA influences (6) also admits in the n ≍ d regime a limiting distribution, given by the pushforward φD ♯N (02 , Q(0) ) of a Gaussian distribution in two dimensions through 11

3.0

theory experiments

theory, = 0.35 CT scans

2.5 2.0 IF

3.5 3.0 2.5 2.0 1.5 1.0 0.5 0.0

1.5 1.0 0.5

0.0

Figure 1: Empirical distribution ν̂IF of the leave-one-out test error influences IFi (5) across the training set. (left) Logistic regression ℓ(z, y) = ln 1 + exp(−yz) for binary classification (y = sign(⟨β, x⟩)), α = 2, λ = 0.05. The blue histogram represents numerical experiments on synthetic Gaussian data, in dimension d = 2000. The red solid line indicates the limiting distribution φIF ♯N (04 , Q) (9) characterized in Theorem 2.1. (right) Ridge regression ℓ(z, y) = 1/2(y − z)2 , with λ = 0.1. The blue histogram collects numerical evaluations of sample influences in the UCI dataset of CT slice scans [Graf et al., 2011]. The red line indicates the limiting distribution φIF ♯N (04 , Q) (9) characterized in Conjecture F.1, assuming a linear model y = ⟨β, x⟩ + N (0, δ 2 ), and using the corresponding sample complexity α = 1. The noise standard deviation δ ≈ 0.35 was estimated from the dataset using linear regression residuals [Hastie et al., 2009]. a non-linear map φD (·). The latter map and Gaussian distribution are similarly parametrized by the summary statistics Q(k) , V (k) , characterized in (12) and (13). In contrast to Theorem 2.1 however, Proposition 2.2 establishes the concentration of the empirical distribution of the DFBETAi across the training set D — a stronger result. We conjecture that a similar result also holds for the empirical distribution ν̂IF of test error influences IFi , beyond the weak convergence of marginals proven in Theorem 2.1. Proving this convergence however warrants a much finer concentration study of the complex statistic (5), which fall out of the scope of the present work. Fig. 1 (left) however shows that numerical evaluations of the histogram ν̂IF are tightly captured by the density φIF ♯N (04 , Q) (9) , providing numerical evidence in support of this conjecture. Let us comment that while we chose to state Theorem 2.1 and Proposition 2.2 in the simplest noiseless case, we anticipate that the proof can be straightforwardly extended to encompass sources of stochasticity, for instance label noise. Furthermore, the assumption of Gaussian design can be relaxed to cover a larger class of elliptical distributions with heavier tail, as considered for instance in El Karoui [2018], Adomaityte et al. [2024] in the same context of high-dimensional M-estimation. These extensions are discussed in Appendix F. From a practical standpoint, the equations (14), (15) and (16) characterizing the resolvents Ω(·), V(·) can in general be solved numerically, and the summary statistics Q(k) , V (k) , which intervene in both Theorem 2.1 and Proposition 2.2, thereby evaluated through (12), (13). In 12

simple settings, for instance for the square loss ℓ(z, y) = 1/2(z − y)2 , the functional equations (14), (15) and (16) starkly simplify, yielding closed-form expressions for the resolvents V(·), Ω(·), and ultimately the limiting influence distribution. The following remark shows that for the square loss, the limiting distribution of DFBETAi (6) and Cook (7) influences take particularly compact forms, and converge to rescaled χ2 distributions. Remark 2.3. For the square loss ℓ(z, y) = 1/2(z − y)2 , assuming a linear model yi = ⟨xi , β⟩ + ϵi (1) where ϵi ∼ N (0, δ 2 ) are independent Gaussian additive label noises, Proposition 2.2 implies that the empirical distribution of DFBETAi influences (6) across the training set converges in probability in the n ≍ d regime to a rescaled χ2 distribution with one degree of freedom: P

ν̂D − !

V (2) 1 + V (1)

(0) (0) 2 2 2 Q11 + 1 − 2Q12 + δ χ1 .

Observe that the term in parenthesis corresponds to the mean-squared test error of the model, intuitively suggesting that models achieving smaller test error are also less sensitive to changes in the training data, in the DFBETA metric. By the same token, let ν̂C denote the empirical distribution of Cook’s Ci influences (7) within the train set. We conjecture the concentration h i P ν̂C − ! V (1)2 + V (1) − λV (2) χ21 . It is important to stress that the square loss does not in principle satisfy the assumption of bounded loss A.1 under which Theorem 2.1 is stated. However, we note that it can be approximated arbitrarily tightly by a sequence of losses that do obey the assumptions. We hence expect that such restrictions are purely technical in nature, and are amenable to being relaxed by standard mollification arguments. Moreover, we shall illustrate in the following subsection that the analytical predictions obtained from evaluating Theorem 2.1 for the square loss display good agreement with numerical experiments, see Fig. 2.

2.5

Discussion

Fig. 1 contrasts the influence distribution φIF ♯N (04 , Q), characterized in Theorem 2.1, with numerical experiments in large but finite dimension d = 2000, in the problem of binary classification with logistic loss, displaying overall good agreement. The histogram reveals a narrow peak around IF = 0, suggesting a uniformly sampled training point most likely exhibits small influence on the test error. The distribution also displays a rapidly decaying right tail at positive values of IF (capturing detrimental samples), and a heavier left tail (capturing beneficial samples). While the technical results were derived under the stylized assumption of isotropic Gaussian design, we note that this qualitative shape can also be observed for real data, as illustrated in Fig. 1 (right) for the task of predicting the longitude at which a slice of computer tomography (CT) scan has been performed [Graf et al., 2011]. With a view to consolidating intuition on the behavior of influence distributions in high dimensions, we close this section by very briefly commenting on the dependence of the latter on a few key parameters of the ERM 13

= 0.0 = 0.25 = 0.6 IF

7 6 5 4 3 2 1 0

0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7

= 0.01 = 0.1 = 0.2 = 0.5 = 1.0 0

Figure 2: Empirical distribution ν̂IF of the leave-one-out test error influences IFi (5) across the training set, for ridge regression (ℓ(z, y) = 1/2(y − z)2 ), assuming a linear model y = ⟨β, x⟩ + N (0, δ 2 ) (1). (left) Histograms of ν̂IF obtained from numerical experiments in dimension d = 1000, contrasted with the limiting distribution φIF ♯N (04 , Q) (9) characterized in the extension of Theorem 2.1 stated in Conjecture F.1, for various noise levels δ. (right) Empirical mean influence µ̂IF , at various regularizations λ, as a function of the sample complexity α. The noise level is fixed at δ = 0.1. Dots indicate numerical experiments in dimension d = 1000, while solid lines represent the mean of the theoretical limiting distribution φIF ♯N (04 , Q) (9). Error bars span one standard deviation. problem (2), and take the opportunity to connect the results of Theorem 2.1 with the classical theory of influence functions [Hampel, 1974, Hampel et al., 1986]. Label noise — On an intuitive plane, introducing label noise diminishes the information content of all training points, and is thus expected to uniformly dilute their influence. This intuition is confirmed by Fig. 2 (left), where dialing up the strength of an additive Gaussian label noise in ridge regression can be observed to flatten the empirical distribution ν̂IF of test error influences {IFi }i∈JnK . Sample complexity — One is now in a position to return to the question alluded to in the introduction : how does the influence of a training sample depend on the size of the training set ? Studies set in finite dimensions under the standard n ! ∞ asymptotics do not permit to ascertain this dependency at leading order. In the high-dimensional regime n ≍ d on the other hand, Fig. 2 (right) uncovers a non-trivial relationship between the empirical mean µ̂IF of the influence distribution ν̂IF and the sample complexity α = n/d. While on average all training samples are found to be helpful (µ̂IF ≤ 0), there exists a value for the sample complexity α where the average test error influence is maximal in absolute value. This behavior is naturally mitigated for larger values of regularization λ. The existence of this maximum can be intuitively rationalized as follows : at large α, the effect of an individual training point on the final model is drowned out by the cumulated effect of all other samples, resulting in a small average influence |µ̂IF |. By the same token, at small α, the model exhibits a large test error, and the inclusion of 14

an additional sample is but of limited help, yielding again a small influence. This suggests that the influence of a sample is instead maximal at intermediate sample complexities, where the model is reasonably close to a good solution. Population limit — In the population limit α ! ∞, for the square loss, the limiting influence distribution φIF ♯ N (04 , Q) characterized in Theorem 2.1 takes a particularly simple form, which we highlight in the following remark. Remark 2.4. Consider the population limit α ! ∞, and let the Egen be the mean-squared test error. The asymptotic influence distribution φIF ♯ N (04 , Q) for the square loss ℓ(z, y) = 1/2(z−y)2 can in this limit be heuristically shown to converge to a centered and scaled χ2 distribution with one degree of freedom α!∞

φIF ♯ N (04 , Q) −⇀ −

2λ2 (χ2 − 1). (1 + λ)3 1

(17)

Astute readers will have observed that taking α ! ∞ limit in fact recovers the classical n ! ∞, d = O(1) limit. Indeed, the population influence distribution (17) is equal to the law of the Gateaux derivative of the mean-squared error at the population distribution N (0d , Id ), when evaluated in the direction of a Gaussian vector x, which coincides with the pushforward of the data distribution N (0d , Id ) through the influence function, thus making contact with Hampel [1974], Avella-Medina [2017].

Consequences for active learning

Leave-one-out influences (5), (6) or (7) provide interpretable measures of the importance of a data point for a learning task. This question precisely lies at the heart of the fields of active learning and subsampling : given a pool of available data points, limitations in compute or annotation budget often make it necessary to select/subsample only a fraction γ ∈ (0, 1) of samples to use for training. In such cases, it is hence seminal to identify and select the most important samples. Sample influences can in such contexts serve as natural proxies for the informativeness of a training point. This section explores the consequences of the main technical results exposed in Section 2 for data selection in high-dimensional regimes. In order to set the discussion in context, we begin by providing an overview of related literature.

3.1

Related works on data selection

Data selection in the n ≫ d limit — The first explicit connection between influence functions and data selection can be found, to our awareness, in the work of Ting and Brochu [2018], in the context of subsampling. The authors show that choosing sampling probabilities to be proportional to the norm of (population) DFBETA influence functions, namely retaining the most influential samples, satisfies a notion of A-optimality [Kiefer, 1959]. Adjoining ideas were reprised in a number of subsequent works. Let us mention for instance Wang et al. [2020], who 15

0.1

2 0

1 0

2.0

w(i)

1.5

1.0

2 0.5

0.0

0.5

1.0

2 1

w(i)

0 1 2 3

21 18 15 12 9 6 3 0

0.0

0.3 0.0 0.3 0.6 0.9 1.2 1.5 1.8 2.1 2.4

= 0.0 = 2.0 = 8.1

Figure 3: Logistic regression ℓ(y, z) = ln 1 + exp{−yz} with λ = 0.05, binary classification task. (left) distribution νIF|ω of the test error influence IFi (5) conditional on the D Marginal E

margin xi , ŵ(i) = ω, for α = 2. Lines are obtained from conditioning the limiting density φIF ♯ N (04 , Q | ω) (9) characterized in Theorem 2.1. Inset: mean influence µIF|ω conditional on the margin being ω, as a function ofEω. (middle) Mean test error influence µIF|ω,τ conditioned D

on the margin conditions xi , ŵ(i) = ω and ⟨xi , β⟩ = τ , plotted in the plane spanned by ŵ(i) (orange), D β (red). E (right) Mean DFBETA influence (6) µD|ω,τ conditioned on the margin conditions xi , ŵ(i) = ω and ⟨xi , β⟩ = τ .

propose a subsampling scheme retaining only samples with negative test-error influence IFi < 0. From a formal standpoint, the results of Ting and Brochu [2018] are derived in the standard large-sample, finite-dimensional regime n ≫ d, in which the asymptotic linearity of the M-estimator [Tsiatis, 2006] may be leveraged. The discrepancy between the finite-sample and population estimators can in such regimes be expanded into a sum of population influence functions [Hampel, 1974] over the training samples. The latter are then used to design the selection criterion, with most influential data points, in the sense of the population influence function, being selected with higher probability. However, as we have previously discussed in Section 2, the population influence functions are deterministic functions of the considered sample only. As a consequence, criteria built upon population influences are blind to the particular realization of the training set, and instead measure in isolation the relevance of an individual training point, irrespective of other data points. Whether empirical leave-one-out influences truly decouple in such fashion for real applications remains on the other hand largely unclear [Basu et al., 2020b]. A similary story can be told from an algorithmic viewpoint. Many classical works on subsampling [Ma et al., 2022, Wang et al., 2018] (see also Section 4 of Kolossov et al. [2023]), are set in the regime n ≫ γn ≫ d where the data acquisition budget γn is large compared to the dimension d. Intuitively, it is always possible in such cases to first devote a small fraction of the budget to learn an estimator asymptotically close to the population estimator as γn ! ∞, after what all selection policies essentially reduce to population-level criteria. Besides, since the excess error achieved with γn samples is already vanishingly small, choosing a good selection strategy over a bad one only leads to minor improvements in test error. 16

0.03

0.090

w(i)

0 1 0.0

0.045

2.5

1.00 0.75 0.50 0.25 0.00 0.25 0.50

0.180 0.225

2 3

0.135

0.270 2

w(i)

0 1 2 3

2.55 2.25 1.95 1.65 1.35 1.05 0.75 0.45 0.15

0.02

0.000

= 0.0 = 2.0 = 4.0

Figure 4: Reproducing the plots of Fig. 3, at smaller sample complexity α = 0.05. All other parameters are otherwise left unchanged. Challenges in high dimensions — This picture is dramatically altered when considering the high-dimensional regime d ≍ γn ≍ n. First, the asymptotic linearity of M-estimators [Tsiatis, 2006] generically ceases to hold. Simultaneously, the leave-one-out influence of an individual sample develops non-trivial statistical correlations with all training samples, as we discussed in Section 2. Finally, good and bad selection strategies can differ by Θ(1) in achieved test error. This triple challenge overall paints a richer picture of the problem of data selection in high-dimensional regimes. A stream of recent works [Cui et al., 2021, Kolossov et al., 2023, Sorscher et al., 2022, Dohmatob et al., 2025, Askari-Hemmat et al., 2025, Cui and Lu, 2026] initiated the study of active binary classification in the n ≍ d limit, under Gaussian design, impulsed by the seminal works of Kinzel and Rujan [1990], Seung et al. [1992]. These works however all consider (with the exception of Cui et al. [2021]) a specific margin-based selection heuristic [Tong and Koller, 2001, Roth and Small, 2006, Wang and Shang, 2014], where samples lying closest to the estimated decision boundary are selected. We provide theoretical evidence in the present work that the margin of a sample is, in fact, correlated with its leave-one-out influence, providing further analytical support to this heuristic.

3.2

Conditional influence

Margin and influence — Consider an iterative active learning procedure, where samples are selected one by one. Suppose the availability of an estimator, learned from hitherto selected samples. How then to use its knowledge to choose the next sample to select ? Ideally, one would like to evaluate for every yet unselected samples (xi , yi ) the difference in test error upon adding it to the training set (given precisely by the influence IFi (5)), and retain the sample displaying the most negative IF value. In practice, the implementation of this procedure suffers from several limitations: it requires expensive repeated retrainings, necessitates a held-out validation set, in addition to the knowledge of all labels, often unavailable in active learning tasks. It is therefore instrumental to construct simple, agnostic proxies, correlated with the test error leave-one-out influence IF, yet easier to evaluate. This agenda essentially boils down to answering the question : where in the input space are influential data most likely to be found 17

0.0

1.2

3.6

4.8

6.0

3.2

2.4

4.8

1.6

0.0

1.6

7.2

3.2 4

Figure 5: Test-error influence IF (5) for the odd versus even classification task on MNIST digits [LeCun et al., 1998] (left), and for the pneumonia diagnosis task on chest X-rays images [Kermany et al., 2018] (right). A 3−layer, ReLU-activated neural network feature map was trained on a first held-out dataset, and the population readout β estimated from retraining on another held-out dataset. The weights ŵ are estimated from the training set, and the color map represent the difference in test error following the inclusion of a synthesized data point chosen in the (β, ŵ) plane, in the likeness of Fig. 3. All experimental details are collected in Appendix G. ? A natural heuristic in the context of convex M-estimation with linear models consists in examining the margin of a sample, namely its distance to the current decision boundary [Tong and Koller, 2001, Roth and Small, 2006, Wang and Shang, 2014], with the intuition that the closest sample are the hardest to classify, and thus contain the most information. In the notations of Section 2, evaluating the correlation between the influence and margin criteria is tantamount toDstudying E the law νIF|ω of IFi (5) conditional on the sample xi sitting

at a prescribed margin w(i) , xi = ω. Theorem 2.1 and the discussion below suggest that in the high-dimensional regime n ≍ d, this conditional distribution should be described by the pushforward φIF ♯ N (04 , Q | ω), where the shorthand N (04 , Q | ω) denotes the law of g ∼ N (04 , Q) conditional on g1 = ω. Fig. 3 illustrates the conditional limiting influence density νIF|ω (·) and its mean µIF|ω for binary classification with logistic regression, at sample complexity α = 2. The distribution of samples closer to the decision boundary (small ω) exhibits a heavier left tail, signaling a higher density of influential samples in the region. In contrast, the influence distribution conditioned on large margins (large ω) exhibits a narrow peak around 0, suggesting samples with large margin have overall low influence. The mean conditional test error influence µIF|ω accordingly tends to 0 as the distance to the boundary ω increases (inset). This picture thus lends support to the well-known active learning heuristic that samples with smallest margins are most influential. This conclusion needs on the other hand to be nuanced at small sample complexities, where the conditional influence distribution νIF|ω (·) only weakly depends on the margin ω (Fig. 4), somewhat echoing the observations of Hacohen et al. [2022], Hacohen and Weinshall [2023], Sorscher et al. [2022] that the small-margin selection policy might cease to be appropriate in data-scarce regimes.

Spatial distribution of influential samples — In order to paint a more fine-grained picture of the spatial distribution of influential samples, one may further condition on the ground-truth margin ⟨xi , β⟩, although we note that for practical purposes the latter is generically unavailable to the statistician. Formally, this impliesD examining the law νIF|ω,τ of IFi E

conditional on the sample xi sitting at a relative margins w(i) , xi = ω, ⟨β, xi ⟩ = τ . Again, Theorem 2.1 suggests that νIF|ω,τ should be described by the pushforward φIF ♯ N (04 , Q | ω, τ ), where N (04 , Q | ω, τ ) stands for the law of g ∼ N (04 , Q) conditional on g1 = ω, g2 = τ . The corresponding mean influence µIF|ω,τ is illustrated as a color map in Fig. 3, 4 (middle), in the (ω, τ ) plane. In agreement with intuition, the most influential samples are found in the disagreement region delineated by the estimated and true decision boundaries, namely the region of space misclassified by the current estimate ŵ(i) . Fig. 3, 4 (right) show that these regions are qualitatively the most influential also in the DFBETA metric (6).

Real data — Having charted out the spatial apportionment of influential samples in the Gaussian case, one may naturally wonder whether this picture still holds at least qualitatively for learning tasks on real data. We address this question with the following experiment, described in further detail in Appendix G, the results of which we report in Fig. 5. The MNIST [LeCun et al., 1998] (left) and chest X-ray scans [Kermany et al., 2018] (right) datasets were split into four disjoint sets DNN , Dβ , Dtrain , Dtest . A feature map NN(·) was first obtained from DNN , by training a 3-layer fully-connected neural network with ReLU activation using the Adam optimizer [Kingma and Ba, 2014], respectively on the even/odd digit classification task (for the MNIST dataset) and the pneumonia diagnosis task (for the chest X-rays dataset). The readout weights β were then retrained on a large dataset Dβ , to estimate a good separator β of the NN(·) features, henceforth taken as an approximation of the ground truth vector in (1). A smaller training set Dtrain instead yield a less accurate estimator ŵ. What is then the most influential sample to add to Dtrain , so that the test error on Dtest is most reduced ? For every point z in the plane spanned by (β, ŵ), we synthesize the sample z, assume the oracle label y = sign( β, z) can be queried, and add the sample (z, y) to Dtrain . The difference in accuracy induced by the inclusion of this synthesized data point is then evaluated. The values are plotted in Fig. 5, and reveal a qualitatively similar distribution of influential samples as in the Gaussian case, see Fig. 3.

Conclusion

We study the leave-one-out influence of samples within a dataset in the high-dimensional regime n ≍ d where the input dimension d grows proportionally to the sample size n. For convex M-estimation under Gaussian design, we derive tight asymptotic characterizations of the limiting distribution of influences. Building on these results, we probe the spatial distribution of the most influential samples, and provide evidence that influential samples tend to lie close to the decision boundary, making contact with a standard data-selection heuristic in active learning.

Perspectives — The results reported in the present work exclusively concern convex Mestimation with linear models, namely single-layer neural networks. However, accruing empirical evidence [Basu et al., 2020a, Bae et al., 2022] suggests a much more brittle behavior of leaveone-out influences in non-convex landscapes, e.g. for neural network, which we believe makes the case for future investigations in such settings. Let us also mention the problem of subset influence [Broderick et al., 2020, Hu et al., 2024, Fisher et al., 2022, Konrad and Kuschnig, 2025], which naturally extends the question of leave-one-out influences to settings where groups of samples, rather than individual points, are removed from the training set. We anticipate the analysis of subset influences in high-dimensional regimes to be made particularly challenging by the intricate statistical correlations within the carved-out subset, notably when the cardinal of the former is comparable to the sample size n. We believe this question delineates an interesting avenue for future research.

References Robert J Adler and Jonathan E Taylor. Random fields and geometry. Springer, 2007. Urte Adomaityte, Leonardo Defilippis, Bruno Loureiro, and Gabriele Sicuro. High-dimensional robust regression under heavy-tailed data: asymptotics and universality. Journal of Statistical Mechanics: Theory and Experiment, 2024(11):114002, 2024. 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. Marco Avella-Medina. Influence functions for penalized m-estimators. Bernoulli, 23:3178–3196, 2017. Juhan Bae, Nathan Ng, Alston Lo, Marzyeh Ghassemi, and Roger B Grosse. If influence functions are the answer, then what is the question? Advances in Neural Information Processing Systems, 35:17953–17967, 2022. Elnaz Barshan, Marc-Etienne Brunet, and Gintare Karolina Dziugaite. Relatif: Identifying explanatory training samples via relative influence. In International Conference on Artificial Intelligence and Statistics, pages 1899–1909. PMLR, 2020. Samyadeep Basu, Philip Pope, and Soheil Feizi. Influence functions in deep learning are fragile. arXiv preprint arXiv:2006.14651, 2020a. Samyadeep Basu, Xuchen You, and Soheil Feizi. On second-order group influence functions for black-box predictions. In International Conference on Machine Learning, pages 715–724. PMLR, 2020b. Pierre C Bellec. Observable adjustments in single-index models for regularized m-estimators with bounded p/n. The Annals of Statistics, 53(2):531–560, 2025. David A Belsley, Edwin Kuh, and Roy E Welsch. Regression diagnostics: Identifying influential data and sources of collinearity. Wiley Series in Probability and Mathematical Statistics, 1980. Christer Borell. The brunn-minkowski inequality in gauss space. Inventiones mathematicae, 30 (2):207–216, 1975. Tamara Broderick, Ryan Giordano, and Rachael Meager. An automatic finite-sample robustness metric: when can dropping a little data make a big difference? arXiv preprint arXiv:2011.14999, 2020. Samprit Chatterjee and Ali S Hadi. Influential observations, high leverage points, and outliers in linear regression. Statistical science, pages 379–393, 1986. 21

Boris S Cirel’son, Ildar A Ibragimov, and Vladimir N Sudakov. Norms of gaussian sample functions. In Proceedings of the Third Japan—USSR Symposium on Probability Theory, pages 20–41. Springer, 2006. Elizabeth Collins-Woodfin, Courtney Paquette, Elliot Paquette, and Inbar Seroussi. Hitting the high-dimensional notes: An ode for sgd learning dynamics on glms and multi-index models. Information and Inference: A Journal of the IMA, 13(4):iaae028, 2024. R Dennis Cook. Influential observations in linear regression. Journal of the American Statistical Association, 74(365):169–174, 1979. R Dennis Cook. Assessment of local influence. Journal of the Royal Statistical Society Series B: Statistical Methodology, 48(2):133–155, 1986. R Dennis Cook and Sanford Weisberg. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 22(4):495–508, 1980. R Dennis Cook and Sanford Weisberg. Residuals and influence in regression. 1982. Hugo Cui and Yue M Lu. Asymptotic theory of iterated empirical risk minimization, with applications to active learning. arXiv preprint arXiv:2601.23031, 2026. 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. Edgar Dobriban and Stefan Wager. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247–279, 2018. 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. Richard M Dudley. Sample functions of the gaussian process. In Selected works of RM Dudley, pages 187–224. Springer, 2010. Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, pages 586–596, 1981. Noureddine El Karoui. Asymptotic behavior of unregularized and ridge-regularized highdimensional robust regression estimators: rigorous results. arXiv preprint arXiv:1311.2445, 2013.

Noureddine El Karoui. On the impact of predictor geometry on the performance on highdimensional ridge-regularized generalized robust regression estimators. Probability Theory and Related Fields, 170(1):95–175, 2018. Noureddine El Karoui, Derek Bean, Peter J Bickel, Chinghway Lim, and Bin Yu. On robust regression with high-dimensional predictors. Proceedings of the National Academy of Sciences, 110(36):14557–14562, 2013. Jillian Fisher, Lang Liu, Krishna Pillutla, Yejin Choi, and Zaid Harchaoui. Statistical and computational guarantees for influence diagnostics. arXiv preprint arXiv:2212.04014, 2022. F Graf, H-P Kriegel, M Schubert, S Poelsterl, and A Cavallaro. Relative location of CT slices on axial axis. UCI Machine Learning Repository, 2011. DOI: https://doi.org/10.24432/C5CP6G. 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. Frank Hampel, Elvezio Ronchetti, Peter Rousseeuw, and Werner Stahel. Robust statistics: The approach based on influence functions. John Wiley and Sons, 1986. Frank R Hampel. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346):383–393, 1974. Trevor Hastie, Robert Tibshirani, Jerome Friedman, et al. The elements of statistical learning, 2009. Yuzheng Hu, Pingbang Hu, Han Zhao, et al. Most influential subset selection: Challenges, promises, and beyond. Advances in Neural Information Processing Systems, 37:119778–119810, 2024. Peter J Huber. Robust regression: asymptotics, conjectures and monte carlo. The annals of statistics, pages 799–821, 1973. Wesley Johnson. Influence measures for logistic regression: Another point of view. Biometrika, 72(1):59–65, 1985. Iain M Johnstone and D Michael Titterington. Statistical challenges of high-dimensional data. Philosophical transactions. Series A, Mathematical, physical, and engineering sciences, 367 (1906):4237, 2009. 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. 23

Jack Kiefer. Optimum experimental designs. Journal of the Royal Statistical Society: Series B (Methodological), 21(2):272–304, 1959. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. Wolfgang Kinzel and Pal Rujan. Improving a network generalization ability by selecting examples. EPL (Europhysics Letters), 13(5):473–477, 1990. Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885–1894. PMLR, 2017. Germain Kolossov, Andrea Montanari, and Pulkit Tandon. Towards a statistical theory of data selection under weak supervision. arXiv preprint arXiv:2309.14563, 2023. Lucas D Konrad and Nikolas Kuschnig. arXiv:2510.20372, 2025.

Testing most influential sets.

arXiv preprint

Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. Cosme Louart and Romain Couillet. Concentration of measure and generalized product of random vectors with an application to hanson-wright-like inequalities. arXiv preprint arXiv:2102.08020, 2021a. Cosme Louart and Romain Couillet. Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns. arXiv preprint arXiv:2109.02644, 2021b. 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. Arian Maleki, Subhabrata Sen, Sivaraman Balakrishnan, Verena Zuber, Chao Gao, Rishabh Dudeja, Christos Thrampoulidis, Anru Zhang, Weijie Su, Jason M Klusowski, et al. High-dimensional statistics: Reflections on progress and open problems. arXiv preprint arXiv:2605.05076, 2026. Vladimir A Marčenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik, 1(4):457–483, 1967. Bruno Mlodozeniec, Runa Eschenhagen, Juhan Bae, Alexander Immer, David Krueger, and Richard E Turner. Influence functions for scalable data attribution in diffusion models. In International Conference on Learning Representations, volume 2025, pages 51728–51764, 2025.

Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017. Robert T Powers and Erling Størmer. Free states of the canonical anticommutation relations. Communications in Mathematical Physics, 16(1):1–33, 1970. Daryl Pregibon. Logistic regression diagnostics. The annals of statistics, 9(4):705–724, 1981. Dan Roth and Kevin Small. Margin-based active learning for structured output spaces. In European conference on machine learning, pages 413–424. Springer, 2006. Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence functions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8179–8186, 2022. 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. Jack W Silverstein and Zhi Dong Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices. Journal of Multivariate analysis, 54(2):175–192, 1995. 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. Pragya Sur and Emmanuel J Candès. A modern maximum-likelihood theory for high-dimensional logistic regression. Proceedings of the National Academy of Sciences, 116(29):14516–14525, 2019. William Thomas and R Dennis Cook. Assessing influence on predictions from generalized linear models. Technometrics, 32(1):59–65, 1990. 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. Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. Advances in neural information processing systems, 31, 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. Anastasios A Tsiatis. Semiparametric theory and missing data. Springer, 2006. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices., 2012. Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. 25

Esteban Walker and Jeffrey B Birch. Influence measures in ridge regression. Technometrics, 30 (2):221–227, 1988. 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. Zifeng Wang, Hong Zhu, Zhenhua Dong, Xiuqiang He, and Shao-Lun Huang. Less is better: Unweighted data subsampling via influence function. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6340–6347, 2020.

Assumptions and reminders

A.1

Assumptions

We detail the proof of Theorem 2.1 and Proposition A.6 in Appendices B, C and D. Before proceeding, we list in the next section all technical assumptions bearing on the ERM loss ℓ(·, ·) (2) and the test error metric E(·, ·) (3), of which we only stressed the most salient ones in the main text. Assumption A.1 (Loss function ℓ). Let ℓ : R2 ! R+ denote the loss function (2). We assume the following properties to hold: (A.1) ℓ is everywhere three times differentiable in its first argument. We denote by ∂ the derivative with respect to the latter. (A.2) ℓ is strongly convex in its first argument, namely ∂ 2 ℓ is everywhere positive. (A.3) The first three derivatives are everywhere well defined and bounded by O(polylog(n)). (A.4) The reduced function ℓ̃ : y ! ℓ(0, y) is bounded by a constant λM 2/2. (A.5) ∂∂2 ℓ, ∂ 2 ∂2 ℓ (where ∂2 denotes the derivative with respect to the second variable) are well-defined, and bounded by O(polylog(n)). (A.6) The first derivative ∂ℓ satisfies E ∂ℓ(0, g2 )g2 ̸= 0, when the average bears over g2 ∼ N (0, 1). This implies in particular the existence of c > 0 such that the h assumption i 2 sequence E ∥ŵ∥ is lower-bounded by c, see Lemma E.2. Remark A.2. In words, Assumption A.6 can be interpreted as requiring that after a gradient step on the population loss, starting from a vanishing 0d initialization, the weight iterates develop a non-zero alignment with the ground-truth β. Remark A.3. While Assumption A.5 is not satisfied for a sign link function ϕ = sign in (1), the latter can be approximated arbitrarily tightly as n, d ! ∞ by differentiable functions that do, following standard mollification arguments. We note that this restriction is technical in nature, stemming from the proof technique employed for Lemma B.1, and is not expected to constitute an intrinsic limitation of the problem. Assumption A.4 (Test error metric). Let E : R × R+ ! R+ be the test error metric (3). We assume that ∂1 E, ∂2 E, ∂12 E, ∂12 E, ∂1 ∂2 E are everywhere well-defined and bounded by O(polylog(n)). Remark A.5. Note that we in fact only need Assumption A.4 to hold on a subdomain I × (0) (0) K ⊂ R × R+ such that the sequences (Q11 , Q12 ) are included in I × K. Notably, restricting (0) K = (c, ∞) where c is the lower-bound on Q11 (see Lemma E.2) allows the misclassification error E(m, q) = 1/π arccos m/√q to satisfy Assumption A.4.

A.2

Notations

We employ throughout the proof the following notations. • Given two sequences of random variables an , bn indexed by n, and an integer k ∈ N, we denote an = OLk (bn ) when E akn = O(E bkn ). If left unspecified, the OLk (·) is implicitly understood to hold for all k ∈ N. Similarly, for a sequence of random vectors un , a deterministic scalar sequence vn , and an integer k ∈ N, we denote un = OLk (vn ) when h i k k E ∥un ∥ = O(|vn | ) holds for the Euclidean norm. • Let X be a random variable well-defined on an event A, but not necessarily defined on Ac . We denote the truncated random variable 1A X the random variable taking value (1A X)(ω) = X(ω) for all ω ∈ A, and 0 for ω ∈ Ac . • Given a matrix X ∈ Rn×d and an index i ∈ JnK, X\i ∈ R(n−1)×d denotes the matrix obtained from X after removing its i−th row. A.2.1

Notations : leave-one-out estimators

We now introduce the notations that will be employed in the remainder of the proof. We study the minimizer ŵ of the empirical risk (2) ŵ = argmin R̂(w),

R̂(w) =

1 X λ 2 ℓj ( w, xj ) + ∥w∥2 , n 2

(18)

j∈JnK

using the shorthand ℓj (·) = ℓ(·, yj ). For any sample index i ∈ JnK, we further introduce the leave-one out surrogate ŵ\i = argmin R̂\i (w),

R̂\i (w) =

1X λ 2 ℓj ( w, xj ) + ∥w∥2 , n 2

(19)

j̸=i

namely the minimizer of the empirical risk from which the i−th sample point was removed. We define the full and leave-one-out residuals D E rj = ŵ, xj , rj,\i = ŵ\i , xj . Importantly, remark that the risk R̂\i differs from (4) by its 1/n, instead of 1/n − 1, normalization, and consequently ŵ\i ̸= ŵ(i) . A fine analysis of their discrepancy will be given later, in Lemma 62 in Appendix D. From the leave-on-out estimator ŵ\i , one can construct the surrogate estimator w̃i = ŵ\i −

1 −1 ∂ℓi (r̃i,i )H\i xi , n

(20)

which will prove a close approximation of the full estimator ŵ [El Karoui, 2013, 2018], a statement that will be made precise in Proposition A.6. In the above display, we introduced the leave-i out Hessian H\i as H\i =

1X 2 ∂ ℓj (rj,\i )xj x⊤ j + λId n j̸=i

and denoted r̃i,i = proxγi ℓi (·) (ri,\i ),

γi =

1 ⊤ −1 x H xi . n i \i

H\i naturally yields a leave-i−out approximation of the full Hessian H=

1 X 2 ∂ ℓj (rj )xj x⊤ j + λId . n j∈JnK

Finally, for j ̸= i, we similarly define the surrogate residual r̃j,i = w̃i , xj . For simplicity, we will also adopt the shorthand 1 −1 xi , ηi = − ∂ℓi (r̃i,i )H\i n so that w̃i may be more compactly rewritten as w̃i = ŵ\i +ηi . It will finally also prove convenient to introduce the surrogate Hessian H̃i =

1 X 2 ∂ ℓj (r̃j,i )xj x⊤ j + λId . n j∈JnK\i

A.2.2

Notations : resolvent

The Hessian matrix H plays a central role in describing the local geometry of the empirical risk landscape (2) around its minimizer. The influence measures (5) (6) and (7) will crucially depend on the statistics " # −k −k ŵ, H ŵ ŵ, H β Q(k) = =: Υ⊤ H −k Υ (21) ŵ, H −k β β, H −k β where the bookkeeping tall matrix Υ ∈ Rd×2 denotes the stacked vectors h i Υ = ŵ β . On an intuitive level, as discussed in the main text, the (random) summary statistics Q(k) enter in the characterization of the susceptibility of the estimator ŵ when a data sample is removed from the dataset. As we will subsequently outline, the influence metrics depend in particular on Q(k) for k = 1, 2. A naive computation reveals it is generically challenging to close the equations on these two matrices, suggesting the entire family {Q(k) }k∈N needs to be simultaneously described. This can be carried out similarly to Collins-Woodfin et al. [2024] by introducing functional statistics. Given z ∈ C \ spec [H], we define the resolvent G(z) of H as G(z) = (H − zId )−1 . 29

From the Cauchy integral formula for matrices, one can then deduce the summary statistics Q(k) as I −1 1 (k) W(z)dz, Q = 2πi C z k from the functional statistic W(z) ∈ C2×2 , defined as (22)

W(z) = Υ⊤ G(z)Υ.

In the above display, C designates any contour in {z ∈ C| Re{z} > 0} \ spec [H] enclosing spec [H]. Note that such a contour can always be defined since H ⪰ λId with λ > 0. Finally, we introduce the Stieltjes transform S(z) =

1 tr G(z) , n

(23)

from which one can extract the moments I i 1 −1 1 h S(z)dz. V(k) = tr H −k = n 2πi C z k It will also prove convenient to introduce the auxiliary statistic i 1 h X(z) = tr H −1 G(z) . n

(24)

(25)

We will also make use of the leave-one-out equivalents of the above transforms. We accordingly define for i ∈ JnK G\i (z) = (H\i − zId )−1 , i 1 h S\i (z) = tr G\i (z) , n W\i (z) = Υ⊤ \i G\i (z)Υ\i ,

G̃i (z) = (H̃i − zId )−1 , i 1 h S̃i (z) = tr G̃i (z) , n W̃i (z) = Υ̃⊤ i G̃i (z)Υ̃i ,

naturally defining the approximations h i Υ\i = ŵ\i β ,

h i Υ̃i = w̃i β .

Let us stress the following technical subtlety: the leave-one-out resolvents G\i (·), G̃i (·) are defined on the complex plane relative to the spectra of the Hessians H\i , H̃i respectively, which generically differ from that of H. Thus, they do not exactly share the same domain of definition as G(·). In what follows, it will be established that the summary statistics Q(k) , V(k) in fact concentrate in L2 to their expectation. We will denote the latter by h i h i Q(k) = E Q(k) , V (k) = E V(k) . Particular care in the manipulation of the above resolvent quantities needs to be devoted to the fact that those are only well-defined away from spec [H]. In particular, the use of the Cauchy integration formula implies a contour intersecting the real axis : the crossing point must 30

then be ensured to avoid the spectrum. Thanks to the concentration of the spectral density of H on a compact interval, this is possible with overwhelming probability. Let us accordingly introduce the sequence of events p 2 2 1 /α A = ∥X∥ /n < 2 + , By standard non-asymptotic bounds for Wishart matrices (see e.g. Vershynin [2012]), the probability of the complementary event vanishes exponentially P [Ac ] ≤ 2e− /2 . n

It will also prove instrumental to consider for i ∈ JnK the leave-one-out version of the event A\i , similarly defined as p 2 2 1 A\i = X\i /n < 2 + /α . Note the implication A ⊂ A\i . We finally introduce the interval J = λ, λ + ∂ 2 ℓ

∞

1/α

which encloses spec [H] with overwhelming probability. With J being chosen, we fix in the remainder of the proof a deterministic complex contour Γ ⊂ {z ∈ C : Re{z} > 0}, chosen so as to enclose the interval J at a distance dist (Γ, J) ≥ λ/2, while also satisfying dist (Γ, 0) ≥ λ/2; we also require that there exists a constant P such that supz∈Γ |z| ≤ P . Equipped with these definitions, we can finally introduce the functional statistics V(z) = E 1A S(z) , χ(z) = E 1A X(z) , Ω(z) = E 1A W(z)

(26)

which are well-defined for all z ∈ Γ.

A.3

Leave-one-out approximation results

The analysis of ERMs of the form (18) has constituted the object of a rich body of works [El Karoui, 2013, El Karoui et al., 2013, Donoho and Montanari, 2016, El Karoui, 2018, Thrampoulidis et al., 2018, Sur and Candès, 2019]. In this subsection, we remind key approximation results of El Karoui [2013, 2018] controlling the discrepancy between the ERM estimator ŵ and its leave-one-out surrogates ŵ\i , w̃i . The subsequent Appendices will build on these bounds to reach a precise asymptotic characterization of the limiting distribution of sample influences within the dataset, as stated in Theorem 2.1. 31

Proposition A.6 (El Karoui [2013, 2018]). The discrepancy between the ERM estimator (2) and the surrogate w̃i (20) is controlled as polylog(n) sup ∥ŵ − w̃i ∥ = OLk . n i∈JnK We also have the following bound for the surrogate/leave-i−out (19) estimators: polylog(n) √ sup w̃i − ŵ\i = OLk . n i∈JnK Furthermore, at the level of the residuals, sup sup |rj,\i − rj | = OLk i∈JnK j̸=i

polylog(n) √ n

and sup |ri − r̃i,i | = OLk i∈JnK

polylog(n) √ n

and sup sup |r̃j,i − rj,\i | = OLk i∈JnK j̸=i

polylog(n) √ n

Finally, the cross terms can be controlled as X polylog(n) 2 (rj − r̃j,i ) = OLk . sup n i∈JnK j̸=i

Proposition A.6 thus establishes that the surrogate w̃i (20) provides a close approximation to the full estimator ŵ (2), will presenting the advantage of admitting a simpler representation (20). We will leverage the latter in the remainder of the proof, which we report in Appendices B, C and D.

Concentration of summary statistics

We have introduced in Appendix A the random functional statistics S(·), V(·), W(·), which naturally enter in the Cauchy integral representation of key geometric descriptors of the estimator ŵ (2), such as Q(k) (21). We establish in this subsection the pointwise concentration of the functionals S(·), X(·), W(·) (23)(25)(22), before transferring the concentration to Cauchy integrals of these functionals (21), (24). In the subsequent Appendix C, we will then compute the corresponding deterministic equivalents, thereby completing the characterization of the summary statistics Q(k) , V (k) (12),(13).

B.1

Pointwise concentration of functional statistics

Lemma B.1 (1A S(z) concentrates). For any t > 0, for any z ∈ C\J such that dist (z, J) > λ/2, nt2 P S(z) − E S(z)|A ≥ t A ≤ 2e− 2C 2 , (27) where C = O(polylog(n)) only depends on α, λ, but not on z. Its precise expression is given in equation (31) of the proof. As a consequence, C . 1A S(z) = E 1A S(z) + OLk √ n Proof. The sub-gaussian bound is inherited from the classical concentration of Lipschitz functions of Gaussian covariates [Vershynin, 2018, Cirel’son et al., 2006]. Namely, for φ : Rn×d ! R a Lipschitz function with respect to the Frobenius norm, for any t > 0, t2 − 2∥φ∥2 Lip. P φ(X) − E φ(X) > t ≤ 2e If φ is only locally Lipschitz on a subdomain E ⊂ Rn×d (endowed with the Frobenius norm), Lemma 1.6 of Louart and Couillet [2021b] (see also Remark 1.5 in Louart and Couillet [2021a]) ensures the concentration transfers conditionally on X ∈ E, namely t2 − 2 P φ(X) − E φ(X) > t X ∈ E ≤ 2e 2∥φ∥Lip. This ensures one can establish concentration on the event A, where the Stieltjes transform is well-defined and Lipschitz. We accordingly introduce ϕz : EA ! C with −1 1 ⊤ 1 ϕz (X) = S(z) = tr /nX Λ(X)X + (λ − z)Id , (28) n where Λ(X) = diag ∂ 2 ℓ(⟨ŵ, xi ⟩ , ⟨β, xi ⟩) , i∈JnK

√

denoting EA = {M ∈ Rn×d |∥M ∥ < n(2 + 1/α)}, so that A = {X ∈ EA }. We recall that in (28), the estimator ŵ is also a function of the covariate matrix X through the ERM definition (2). To establish the pointwise sub-Gaussian tail bound (27), it thus suffices to establish that p

√

ϕz is O(1/ n) Lipschitz, for any z ∈ C \ J with dist (z, J) > λ/2. To that end, we bound the derivative dϕz/dX . For any test matrix ∆ ∈ Rn×d ,   ! dΛ(X) dϕz 1  , ∆ = − 2 tr G(z) X ⊤ Λ(X)∆ + ∆⊤ Λ(X)X + X ⊤ , ∆ X G(z) (29) dX n dX where

d/dX Λ(X), ∆

is diagonal with elements X X dΛ(X)kk dΛ(X) = ,∆ ∆ij . dX dXij kk i∈JnK j∈JdK

Note that the existence of this derivative is in particular guaranteed by Lemma E.7, which ensures that the function X ! ŵ is differentiable. We now successively bound the three terms that make up the derivative (29). Control of

1 ⊤ n2 tr G(z)X Λ(X)∆G(z)

The first term can be easily controlled by

—

p i ∂2ℓ ∞ h 1 1 4(2 + 1/α) 2 ⊤ tr G(z)X Λ(X)∆G(z) ≤ G(z) ∥X∥∥∆∥ ≤ √ ∥∆∥F . n2 n λ2 n

Control of

D E ⊤ dΛ(X) G(z)X dX , ∆ XG(z) — We now turn to the third term. Expound-

1 n2 tr

ing the derivative,

   * + X X dŵ dΛ(X)  3 = ,∆ , xk  + ∂ 2 ∂2 ℓk (rk )δki βj  ∆ij . ∂ ℓk (rk ) δik ŵj + dX dXij kk i∈JnK j∈[d]

The derivative of the estimator dŵ/dXij may be expounded starting from the stationarity condition 1 X λŵ + ∂ℓk (rk )xk = 0. n k∈JnK

Taking the derivative with respect to Xij , whose existence is guaranteed under Lemma E.7, * + dŵ 1 X 2 dŵ 1 1 λ + ∂ ℓk (rk )xk xk , + ∂ℓi (ri )ej + xi (∂ 2 ℓi (ri )ŵj + ∂∂2 ℓi (ri )βj ) = 0. dXij n dXij n n k∈JnK

We denoted ej ∈ Rd the j−th canonical basis vector. Thus, * + xk , H −1 ej xk , H −1 xi dŵ , xk = −∂ℓi (ri ) − (∂ 2 ℓi (ri )ŵj + ∂∂2 ℓi (ri )βj ). dXij n n Introducing for compactness of notation the vector h ∈ Rn and matrices E ∈ Rn×d , F ∈ Rn×n , J ∈ Rn×n with entries xk , H −1 ej √ , n xk , H −1 xi Jki = −∂∂2 ℓi (ri )∂ 3 ℓk (rk ) , n

1 hi = √ ∂ℓi (ri ), n Fki = −∂ 2 ℓi (ri )∂ 3 ℓk (rk )

Ekj = −∂ 3 ℓk (rk ) xk , H −1 xi , n 34

one can rewrite the diagonal matrix dΛ(X)/dX , ∆ , viewed as a Rn vector, as " # dΛ(X) vec , ∆ = E∆⊤ h + F ∆ŵ + J∆β + diag((∂ 3 ℓk (rk ))k )∆ŵ + diag((∂ 2 ∂2 ℓk (rk ))k )∆β. dX Thus " vec

# dΛ(X) 2 3 ∥∆∥F(30) . ≤ ∥∂ℓ∥∞ ∥E∥ + ∥F ∥∥ŵ∥ + ∥J∥ + ∂ ℓ ∥ŵ∥ + ∂ ∂2 ℓ ,∆ dX ∞ ∞

∥ŵ∥ is deterministically upper-bounded by a constant M (Assumption A.1) through Lemma E.1 for any X. On the other hand, p 2 + 1/α 3 ∥E∥ ≤ ∂ ℓ , λ ∞ p (2 + 1/α)2 2 3 ∥F ∥ ≤ ∂ ∂2 ℓ ∂ ℓ ∞ ∞ pλ 2 (2 + 1/α) ∥J∥ ≤ ∥∂∂2 ℓ∥∞ ∂ 3 ℓ λ ∞ p since we remind X ∈ EA and thus has (2 + 1/α)−bounded operator norm. Taken together, h i these bounds and (30) yield O(polylog(n))∥∆∥F control over vec dΛ(X)/dX , ∆ . Coming back to the initial objective, one is now in a position to build on this control to bound h i 1/n2 tr G(z)X ⊤ dΛ(X)/dX , ∆ XG(z) as " # * " #+ h i 2 ⊤ 1 dΛ(X) 1 XG(z) X ⊤ tr G(z)X , ∆ XG(z) ≤ vec dΛ(X)/dX , ∆ , vect diag , n2 dX n n where vect diag refers to the diagonal viewed as a Rn vector. The desired bound then follows from a Cauchy-Schwarz inequality, remarking that v " # u 4 p XG(z)2 X ⊤ 4√ 2 u X ∥xi ∥ 1/α)2 . vect diag ≤ G(z) t ≤ n(2 + n n2 λ2 i∈JnK

Lipschitzness of φz — Putting everything together, for any z ∈ C \ J satisfying the requirements of the lemma, and any test matrix ∆, dϕz C , ∆ ≤ √ ∥∆∥F , dX n where C = O(polylog(n)) is independent of z, ∆ and explicitly given by  ! 2 4tα  t t α α (31) + ∂3ℓ (M + 1) + ∂ 3 ℓ M + ∂ 2 ∂2 ℓ C = 2 2 + tα ∥∂ℓ∥∞ ∂ 3 ℓ λ ∞ λ ∞ λ ∞ ∞ p √ where tα = (2 + 1/α). One can thus conclude that ϕz is C/ n− Lipschitz, from which the sub-Gaussian tail (27) follows. 35

Proof of the second claim — Finally, we transfer the A− conditional tail bound (27) onto the truncated random variable 1A S(z). The unconditional moments of the residual 1A S(z) − E 1A S(z)|A are related to the conditional moments as E ≤

k k 1A S(z) − E 1A S(z)|A − E S(z) − E S(z)|A A

k k 1A S(z) − E 1A S(z)|A − E S(z) − E S(z)|A 1A

k k k n 4 e− 2 , S(z) − E S(z)|A A − E S(z) − E S(z)|A 1A ≤ 6 λ

E + E

for any n ≥ 4. Using the tail bound (27) to evaluate the conditional moment, one finally reaches k k E 1A S(z) − E 1A S(z)|A = O(C k n− /2 ). Thus, 1A S(z) = E 1A S(z)|A + OLk

C √ n

n = E 1A S(z) + O(e− 2 ) + OLk

C √ n

concluding the proof. One can establish a similar pointwise concentration result for the statistic X(·) (25), as stated in the following Lemma. Lemma B.2 (1A X(z) concentrates). For any t > 0, for all z ∈ C \ J such that dist (z, J) > λ/2, 2 − nt P X(z) − E X(z)|A ≥ t A ≤ 2e 9/λ2 C 2 , where C = O(polylog(n)) was defined in (31) in Lemma B.1. As a consequence, C 1A X(z) = E 1A X(z) + OLk √ . n Proof. The proof of B.2 borrows the same steps as those of Lemma B.1. We accordingly introduce ψz : EA ! C with −1 −1 1 1/nX ⊤ Λ(X)X + (λ − z)I ψz (X) = tr 1/nX ⊤ Λ(X)X + λId , d n where Λ(X) = diag ∂ 2 ℓ(⟨ŵ, xi ⟩ , ⟨β, xi ⟩) , i∈JnK

p √ denoting once more EA = {M ∈ Rn×d |∥M ∥ < n(2 + 1/α)}, so that A = {X ∈ EA }. In the likeness of Lemma B.1, the proof hinges on ascertaining the Lipschitz norm of ψz . We

accordingly evaluate the derivative along any test matrix ∆ ∈ Rn×d :   ! dψz 1  −1 dΛ(X) , ∆ = − 2 tr H G(z) X ⊤ Λ(X)∆ + ∆⊤ Λ(X)X + X ⊤ , ∆ X G(z) dX n dX   ! dΛ(X) 1  −1 X ⊤ Λ(X)∆ + ∆⊤ Λ(X)X + X ⊤ − 2 tr H , ∆ X H −1 G(z). n dX All the terms in the above display can be bounded following identical steps as in Lemma B.1, leading to dψz 3C , ∆ ≤ √ ∥∆∥F . dX 2λ n The proof of the second claim also proceeds identically to Lemma B.1. We now aim at establishing pointwise concentration for 1A W(·) (22). It is however challenging to exhibit a convex open subset of Rn×d satisfying the double requirement of (a) including X with overwhelming probability and (b) on which the function X ! 1A W(z) is globally Lipschitz. For this reason, we instead take an alternative route, and employ the Efron-Stein lemma [Efron and Stein, 1981] to demonstrate a weaker —yet sufficient for the purpose of the remainder of the proof— L2 concentration. Lemma B.3 (1A W(z) concentrates). For any z ∈ C \ J such that dist (z, J) > λ/2, and any indices a, b ∈ {1, 2} polylog(n) Var 1A W(z)ab = O . n Proof. We employ the Efron-Stein lemma [Efron and Stein, 1981] to bound the variance as Var 1A W(z)ab 2 X ≤ E 1A W(z)ab − 1A\i W\i (z)ab i∈JnK

≤3

1A W(z)ab − 1A W̃i (z)ab

1A W\i (z)ab − 1A W̃i (z)ab

i∈JnK

2 W\i (z)ab (1A − 1A\i ) .

(32)

We successively establish O(polylog(n)/n2 ) control over all three terms in the summand. In the remainder of the proof, we use the shorthands u := Υa , v := Υb , so that W(z)ab = u, G(z)v . Furthermore, the notations β̃i , β\i are understood to designate β. Control of W\i (z)(1A − 1A\i ) —

We start with the last term of (32):

1A\i W\i (z)ab ≤

2 u\i λ

v\i = OLk (polylog(n)), 37

using Proposition A.6 to bound the norm of the leave-one-out vectors u\i , v\i . On the other hand, any moment of 1A − 1A\i is bounded as h i h i n E (1A − 1A\i )k = P A\i ∩ Ac ≤ 2e− /2 . Thus, E

W\i (z)ab (1A − 1A\i )

Control of 1A W(z)ab − 1A W̃i (z)ab —

polylog(n) n2

We decompose the first term of (32) as

1A W(z)ab − 1A W̃i (z)ab D E D E D E = u, 1A (G(z) − G̃i (z))v + u − ũi , 1A G̃i (z)v + ũi , 1A G̃i (z)(v − ṽi ) . From Proposition A.6, the last two terms are OLk (polylog(n)/n). The first term of the above display can be bounded as D E u, 1A (G(z) − G̃i (z))v ≤ 1A XG(z)u ∞ 1A X G̃i (z)v

∞

√1 n

∥∂ 3 ℓ∥∞ ∥X∥∥ŵ−w̃i ∥+ n1 ∥∂ 2 ℓ∥∞ .

We thus need to establish OLk (polylog(n)) control of the infinity norms 1A XG(z)u ∞ and 1A X G̃i (z)v

∞

. First,

D E D E 1A XG(z)u ∞ ≤ sup 1A\i xi , G\i (z)u\i + sup 1A xi , G\i (z)(u − u\i ) i∈JnK

(33)

i∈JnK

D E D E + sup 1A xi , (G̃i (z) − G\i (z))u + sup 1A xi , (G̃i (z) − G(z))u . i∈JnK

i∈JnK

The first term is controlled by Lemma E.6, in conjunction with the bound G\i (z) ≤ 2/λ under the event A\i , and Lemma E.1. Furthermore, it follows from Proposition A.6 that the second term is also OLk (polylog(n)). Moreover, polylog(n) √ 1A (G̃i (z) − G\i (z)) = OLk , (34) n which controls the third term. Finally, D E sup 1A xi , (G̃i (z) − G(z))u

(35)

i∈JnK

D E 1 2 ∂ ℓ sup 1A xi , G(z)xi xi , G̃i (z)u + OLk polylog(n) n ∞ i∈JnK ! p D E 2(2 + 1/α)2 2 ≤ ∂ ℓ sup xi , 1A G\i (z)u\i + OLk polylog(n) λ ∞ i∈JnK = OLk polylog(n) ≤

As a byproduct of the above display, we have also established 1A X G̃i (z)u = OLk polylog(n) . ∞ Assembling all intermediary bounds, one finally reaches the desired control polylog(n) 1A W(z)ab − 1A W̃i (z)ab = OLk . n Control of 1A W\i (z)ab − 1A W̃i (z)ab — We now turn to 1A W\i (z)ab − 1A W̃i (z)ab . Similarly, we start by decomposing it into terms amenable to easier control: 1A W\i (z)ab − 1A W̃i (z)ab D E D E D E = u\i , 1A (G\i (z) − G̃i (z))v\i + (u\i − ũi )1A G̃i (z)v\i + ũi 1A G̃i (z)(v\i − ṽi ) . (36) We start from the middle term. If u = β, then this term vanishes trivially. If on the other hand u = ŵ, then D E D E D E 1 −1 −1 (u\i − ũi )1A G̃i (z)v\i = ∂ℓi (r̃i,i ) xi , H\i 1A (G̃i (z) − G\i (z))v\i + xi , H\i 1A G\i (z)v\i n = OLk

polylog(n) n

√ using Lemma E.6 and the bound 1A (G̃i (z) − G\i (z)) = OLk polylog(n)/ n (34). The term D E ũi 1A G̃i (z)(v\i − ṽi ) in (36) can be similarly controlled, using additionally Proposition A.6 to approximate ũi by u\i . On the other hand, the control of the first term in (36) warrants a finer analysis of the correlations between its constituent terms. Expounding the resolvent difference,

D E 1X ⊤ ∂ 3 ℓj (rj,\i )(r̃j,i − rj,\i )1A u⊤ u\i , 1A (G\i (z) − G̃i (z))v\i = \i G\i (z)xj xj G̃i (z)v\i n j̸=i

1 X 4 ⊤ ∂ ℓj (řj,i )(r̃j,i − rj,\i )2 1A u⊤ (37) , \i G\i (z)xj xj G̃i (z)v\i 2n j̸=i

for some řj,i ∈ (r̃j,i , rj,\i ). The last term is bounded as 1 X 4 ⊤ ∂ ℓj (řj,i )(r̃j,i − rj,\i )2 1A u⊤ \i G\i (z)xj xj G̃i v\i 2n j̸=i

≤ ∂4ℓ

∞

1A\i X\i G̃i (z)v\i

The infinity norm 1A\i X\i G\i (z)u\i

∞

1A\i X\i G\i (z)u\i

sup(r̃j,i − rj,\i )2 .

∞ j̸=i

(38)

has previously been established to be OLk (polylog(n))

earlier in the proof, since the bound on 1A XG(z)u naturally transfers to the leave−i out problem. It follows from the resolvent bound (34) that 1A\i X\i G̃i (z)v\i

∞

admits the same

bound. Proposition A.6 then allows to prove OLk (polylog(n)/n) control over (38). We now address

the first term in (37): 1X 3 ⊤ ∂ ℓj (rj,\i )(r̃j,i − rj,\i )1A u⊤ \i G\i (z)xj xj G̃i (z)v\i n j̸=i

= ∂ℓ(r̃i,i )

1X 3 1 ⊤ ⊤ −1 ∂ ℓj (rj,\i ) 1A\i u⊤ \i G\i (z)xj xj G\i (z)v\i xj H\i xi + OLk n n j̸=i

polylog(n) n

This rewriting completely lifts all xi − dependencies within the summand, allowing for the computation of the squared expectation  2  1X 3 1  ⊤ ⊤ −1   E ∂ℓ(r̃i,i ) ∂ ℓj (rj,\i ) 1A\i u⊤  \i G\i (z)xj xj G\i (z)v\i xj H\i xi n n j̸=i



1  1X 3 2 −1 ⊤ ≤ ∥∂ℓ∥∞ EX\i  ∂ ℓj (rj,\i ) 1A\i u⊤ \i G\i (z)xj xj G\i (z)v\i H\i xj n n

  

j̸=i

p 2 2 2 1 1 2 ∥∂ℓ∥∞ ∂ 3 ℓ 1A\i X\i G\i (z)u\i (2 + 1/α)2 1A\i X\i G\i (z)v\i 2 n ∞ ∞ ∞λ polylog(n) =O . n2 ≤

One therefore finally reaches the control 2 polylog(n) . E 1A W\i (z)ab − 1A W̃i (z)ab =O n2 Returning to the Efron-Stein bound (32), the L2 concentration polylog(n) Var 1A W(z)ab = O n follows.

B.2

Concentration of Cauchy integrals

The pointwise concentration properties established for the functionals 1A S(·), 1A X(·), 1A W(·) proven in Lemmas B.1, B.2 and B.3 will prove valuable when computing the corresponding deterministic equivalents Ω(·), V(·) in Appendix C. As such, they however do not suffice to deduce the concentration of the integrals Q(k) , V(k) (21), (24). Instead, we use once more the Efron-Stein lemma [Efron and Stein, 1981] to directly establish their concentration. This is the object of Lemma B.4 and B.5. Lemma B.4 (V(p) concentrates). Let C ⊂ {z ∈ C : Re{z} > 0} be a random contour enclosing the (random) interval " # 2 ∥X∥ 2 +λ . (39) J = λ, ∂ ℓ ∞ n 40

at a distance d(C, J) = λ/2, and d(C, 0) = λ/2. Then for any p ∈ N, I 1 polylog(n) 1 Var S(z)dz = O . 2πi C z p n The variance also bears over both random variables C, S(z). Proof. The proof will leverage the results of Proposition A.6 in order to approximate the full Stieltjes integral by easier-to-handle integrals hbearing over i h the i surrogate and leave-one-out approximations. First, note that spec [H] , spec H̃ , spec H\i ⊂ J, and thus all the resolvent in the proof are well-defined. The following proof borrows the same steps as Lemma B.3. From the Efron-Stein Lemma, I 1 1 S(z)dz Var 2πi C z p " # I 2 X 1 1 ≤ E (S(z) − S\i (z))dz 2πi C z p i∈JnK # " # " I I 2 2 X 1 1 1 1 + 2E (40) (S(z) − S̃i (z))dz (S\i (z) − S̃i (z))dz ≤ 2E 2πi C z p 2πi C z p i∈JnK

Let us remind that the expectations also bear over the random contour C. We successively control the two terms. First term of (40) — First, I PC 1 1 PC 2 p 1 ≤ (S(z) − S̃ (z))dz sup S(z) − S̃ (z) sup ≤ sup S(z) − S̃i (z) , i i p 2πi C z p 2π z∈C 2πλp z∈C z∈C |z| denoting PC the length of the contour, and using the estimation lemma. Lemmas E.3 and E.4 provide control of the latter PC = O polylog(n) . We now need to control the maximal Stieltjes approximation error S(z) − S̃i (z)) along the integral. But sup S(z) − S̃i (z) z∈C

1 tr G(z) H − H̃i G̃i (z) z∈C n D E D E G(z)x , G̃ (z)x G(z)x , G̃ (z)x X j i j i i i 1 1 = sup ∂ 3 ℓ(řj )(rj − r̃j,i ) + ∂ 2 ℓi (ri ) n n n z∈C n

= sup

j∈JnK\i



  1 ≤ √ n

s X

(rj − r̃j,i

j∈JnK\i

xj 1 2  ∂ ℓ + ∂ ℓ  sup n n ∞ ∞ j∈JnK 3

sup G(z) sup G̃i (z) . z∈C

z∈C

We used the Cauchy-Schwartz inequality in the last line. The first term is control by Proposition A.6. The choice of C furthermore ensures supz∈C G(z) ≤ 2/λ and supz∈C G̃i (z) ≤ 2/λ. Assembling these bounds yields the control I polylog(n) 1 1 (S(z) − S̃i (z))dz = OLk . (41) 2πi C z p n Second term of (40) — We now address the leave-one-out/surrogate discrepancy term of (40). Similarly to the first term, the contour integral can be controlled by the uniform supremum over z ∈ C of the difference |S̃i (z) − S\i (z)|: I PC 2p 1 1 (S̃i (z) − S\i (z))dz ≤ sup S̃i (z) − S\i (z) . p 2πi C z 2πλp z∈C But the latter reads D E G̃ (z)x , G (z)x X i j j \i 1 sup S̃i (z) − S\i (z) ≤ sup ∂ 3 ℓj (rj,\i )(r̃j,i − rj,\i ) n z∈C z∈C n j∈JnK\i

D E G̃ (z)x , G (z)x X i j j \i 1 ∂ 4 ℓj (řj )(r̃j,i − rj,\i )2 + sup n n z∈C

(42)

j∈JnK\i

for some řj in the unordered interval (r̃j,i , rj,\i ). The last term of (42) scales as OLk (polylog(n)/n), using Proposition A.6. The second term of (42) warrants more careful control of the correlations within the sum. A first simplification follows from the identity polylog(n) √ sup G̃i (z) − G\i (z) = OLk , n z∈C which guarantees D E G̃ (z)x , G (z)x X i j j \i 1 sup ∂ 3 ℓj (rj,\i )(r̃j,i − rj,\i ) n z∈C n j∈JnK\i

D E G (z)x , G (z)x X j j \i \i 1 polylog(n) 3 ≤ sup ∂ ℓj (rj,\i )(r̃j,i − rj,\i ) + O Lk . n n z∈C n j∈JnK\i

We can thus limit ourselves to the study of the latter term. Unwrapping the expression of the surrogate residual r̃j,i yields the explicit expression D E G (z)x , G (z)x X j j \i \i 1 ∂ 3 ℓi (rj,\i )(r̃j,i − rj,\i ) n n j∈JnK\i

1 n2

−1 ∂ 3 ℓj (rj,\i )∂ℓi (r̃i,i ) xj , H\i xi

j∈JnK\i

D E E G\i (z)xj , G\i (z)xj n

Thus, 

E 2  G (z)x , G (z)x j j   \i \i  1 X 3 E ∂ ℓi (rj,\i )(r̃j,i − rj,\i )    n  n D

j∈JnK\i

  2 ≤ ∥∂ℓ∥∞ E  

1 X 3 ∂ ℓj (rj,\i ) n2 j∈JnK\i

D E G\i (z)xj , G\i (z)xj n

2 −1 H\i xj

  =O 

polylog(n) n2

Assembling these successive bounds, finally yields the control # " I 2 polylog(n) 1 1 = O ( S̃ (z) − S (z))dz . E i \i 2πi C z p n2 Injecting the bounds (41) and (42) into the Efron-Stein lemma (40) concludes the proof. We have established the concentration of random contour integrals of the Stieltjes S(·) in L2 norm, provided the random contour C (39) encloses the spectrum of the Hessian matrix H (and approximations thereof) from a sufficient distance. We now prove similar results for integrals of the summary statistics Ω(·). Lemma B.5 (Q(p) concentrate). Let C ⊂ {z ∈ C : Re{z} > 0} be the same contour as defined in Lemma B.4, equation (39). Then for any p ∈ N and indices a, b ∈ {1, 2} I 1 1 polylog(n) Var W(z)ab dz = O . 2πi C z p n The variance bears over both random variables C, W(z). Proof. Before examining the variance, it proves convenient to observe that the random contour C may in fact be swapped by the deterministic contour Γ, at the price of a small OLk 1/n correction: I I I 1 1 1 1 1 1 c W(z) dz = 1 W(z) dz + 1 W(z)ab dz ab A ab A 2πi C z p 2πi Γ z p 2πi C z p I 1 1 1 = 1 W(z) dz + O . A ab Lk 2πi Γ z p n Thus, it suffices to establish concentration for the former integral, which bears over the simpler deterministic contour Γ.

We now once more appeal to the Efron-Stein lemma [Efron and Stein, 1981] to bound " 2 # I I X 1 1 1 1 Var 1A W(z)ab dz ≤ 3 E (1A W(z)ab − 1A W̃i (z)ab )dz 2πi Γ z p 2πi Γ z p i∈JnK " 2 # I 1 1 +E (1A W\i (z)ab − 1A W̃i (z)ab )dz 2πi Γ z p " 2 # I 1 1 + 3E . (43) (1A − 1A\i )W\i (z)ab dz 2πi Γ z p As in Lemma B.3, we successively establish O(polylog(n)/n2 ) control over all three terms in the summand. In the remainder of the proof, we use the shorthands u := Υa , v := Υb , so that W(z)ab = u, G(z)v . Furthermore, the notations β̃i , β\i are understood to designate β. First term of (43) — From the estimation Lemma, I PΓ 2p 1 1 ≤ (W(z) − W̃ (z) )dz sup W(z)ab − W̃i (z)ab . ab i ab 2πi C z p 2πλp z∈Γ Borrowing steps from the proof of Lemma B.3, one can further decompose D E sup 1A W\i (z)ab − 1A W̃i (z)ab ≤ sup u\i , 1A (G\i (z) − G̃i (z))v\i z∈Γ

z∈Γ

+ sup

(u\i − ũi )1A G̃i (z)v\i

ũi 1A G̃i (z)(v\i − ṽi )

z∈Γ

≤ sup

+ sup

u\i , 1A (G\i (z) − G̃i (z))v\i

+ O Lk

z∈Γ

polylog(n) (44) , n

appealing to Proposition A.6 to bound the last two terms in the first inequality of (44). Furthermore, the first term admits the upper bound D E sup u, 1A (G(z) − G̃i (z))v z∈Γ 1 2 1 √ ∂ 3 ℓ ∥X∥∥ŵ − w̃i ∥ + ∂ ℓ . ≤ sup 1A XG(z)u ∞ sup 1A X G̃i (z)v n n ∞ ∞ ∞ z∈Γ z∈Γ To control the infinity norms as OLk (polylog(n)), one needs to revisit the bound (33), from which it can be deduced that ! p D E 2(2 + 1/α)2 sup 1A XG(z)u ∞ ≤ 1 + sup sup 1A\i xi , G\i (z)u\i + OLk (polylog(n)). λ z∈Γ z∈Γ i∈JnK (45) Furthermore, from equation (35), sup 1A X G̃i (z)u z∈Γ

∞

≤ 1+

2(2 +

1/α)2

D E sup sup 1A\i xi , G\i (z)u\i z∈Γ i∈JnK

+ sup 1A XG(z)u ∞ + OLk (polylog(n)). z∈Γ

Therefore, in order to establish polylog(n) control over the infinity norms supz∈Γ 1A XG(z)u ∞ and supz∈Γ 1A X G̃i (z)v , it suffices to establish control over the supremum of the Gaussian ∞ process D E sup sup 1A\i xi , G\i (z)u\i , i∈JnK z∈Γ

indexed by z ∈ Γ. D E Control of supi∈JnK supz∈Γ 1A\i xi , G\i (z)u\i — We thus need to control the datasetsupremum of the supremum of a Gaussian process defined on the parameter space Γ. In the following, we first work for a given i ∈ JnK, conditionally on X\i . For convenience, we examine the two real Gaussian processes n o n o fi (z) = xi , Re 1A\i G\i (z) u\i , gi (z) = xi , Im 1A\i G\i (z) u\i . In order to control the supremum over z, we appeal to the Borell-TIS theorem [Borell, 1975, Cirel’son et al., 2006, Adler and Taylor, 2007] in conjunction with the Dudley entropy integral inequality [Dudley, 2010, Vershynin, 2012]. The canonical distance associated with the field fi (·) is, for any z, z ′ ∈ Γ 12 df (z, z ′ ) = E (fi (z) − fi (z ′ ))2 X\i n o = Re 1A\i G\i (z)G\i (z ′ )(z − z ′ ) u\i 4(1 + M ) z − z′ . λ2 Thus, for any ϵ > 0, the covering number Nf (Γ, df , ϵ) is upper-bounded by ≤ (1 + M ) 1A\i G\i (z)G\i (z ′ )

z − z′ ≤

2(1 + M ) PΓ , ϵλ2 where we remind that PΓ is the perimeter of the contour Γ, which is bounded by O(1). It then follows from Dudley’s entropy integral [Dudley, 2010, Adler and Taylor, 2007, Vershynin, 2012] that there exists an universal constant K such that diamdf (Γ) " # Z q E sup fi (z) X\i ≤ K ln Nf (Γ, df , ϵ)dϵ Nf (Γ, df , ϵ) ≤

z∈Γ 0 2(1+M ) PΓ λ2

≤K

r ln

2(1 + M ) PΓ − ln ϵdϵ := NΓ . λ2

Let us stress that NΓ is an absolute constant that only depends on the problem parameters M, λ, α. By the same token, " # E sup gi (z) X\i ≤ NΓ . z∈Γ

Having an upper bound in expectation on the process suprema, one is now in a position to prove tail bounds on the suprema of the absolute values. Let us first introduce the variance 2 2 sup E fi (z) X\i = sup 1A\i G\i (z)G\i (z)† (H\i − Re{z}Id )u\i z∈Γ

z∈Γ

≤

16(1 + M )2 λ4

1 +P λ

:= σ 2 ,

where the P was introduced in Appendix A. Similarly, 2 2 sup E gi (z) X\i = sup 1A\i G\i (z)G\i (z)† Im{z}u\i ≤ σ 2 . z∈Γ

z∈Γ

It then follows from the Borell-TIS theorem [Borell, 1975, Cirel’son et al., 2006, Adler and Taylor, 2007] that, for any u > 0 " # u2

P sup fi (z) ≥ u + NΓ ≤ 2e− 2σ2 , z∈Γ

P sup gi (z) ≥ u + NΓ ≤ 2e− 2σ2 . z∈Γ

Taken together, these tail bounds finally imply for any t ≥ 2NΓ # " E D (t−2NΓ )2 P sup 1A\i xi , G\i (z)u\i > t X\i ≤ 4e− 8σ2 . z∈Γ

By the law of total probabilities, this bound holds unconditionally, and # " D E (t−2NΓ )2 P sup 1A\i xi , G\i (z)u\i > t ≤ 4e− 8σ2 . z∈Γ

Equipped with this tail bound, one is now in a position to control the moments of the supremum over i ∈ JnK. Let k be an integer, and u > 2NΓ ∨ σ 2 k. From an union bound,  !  Z∞ D E k t2  ≤ uk + n ktk−1 4e− 8σ2 dt E  sup sup 1A\i xi , G\i (z)u\i i∈JnK z∈Γ

≤ uk + σ 2

u2 32kn k−2 − 8σ 2 u e . 1 − (uk−1 /σ)2

p For n ≥ exp NΓ2 ∨ k/2 , choosing u = 8σ 2 log(n),  !  D E k k  ≤ 8 log(n) 2 1 + E  sup sup 1A\i xi , G\i (z)u\i i∈JnK z∈Γ

4k . 2 log(n) − k + 1

One can thus conclude that D E sup sup 1A\i xi , G\i (z)u\i = OLk polylog(n) .

i∈JnK z∈Γ

Winding back the argument to (44), it can finally be concluded that I 1 1 polylog(n) (W(z) − W̃ (z) )dz = O . i ab Lk ab 2πi C z p n 46

(46)

Second term of (43) — Now turning to the second term of (43), it follows from the estimation lemma that it suffices to control sup 1A W\i (z)ab − 1A W̃i (z)ab . z∈Γ

To that end, let us reprise the decomposition (36), recalling D E D E 1A W\i (z)ab − 1A W̃i (z)ab = u\i , 1A (G\i (z) − G̃i (z))v\i + (u\i − ũi )1A G̃i (z)v\i D E + ũi 1A G̃i (z)(v\i − ṽi ) . We start with the middle term. Once more, if u = β, then this term vanishes trivially. If on the other hand u = ŵ, then ! D E E D 1 −1 sup (u\i − ũi )1A G̃i (z)v\i ≤ ∂ℓi (r̃i,i ) OLk (polylog(n)) + sup xi , H\i 1A\i G\i (z)v\i n z∈Γ z∈Γ

The Gaussian process supremum can once more be controlled, following identical steps as for (46), as sup z∈Γ

D E −1 xi , H\i 1A\i G\i (z)v\i = OLk (polylog(n)),

D E providing OLk (polylog(n)/n) control over supz∈Γ (u\i − ũi )1A G̃i (z)v\i . The third term in D E the decomposition, supz∈Γ ũi 1A G̃i (z)(v\i − ṽi ) , may similarly be controlled, additionally using Proposition A.6 to approximate ũi . The estimation Lemma then ensures that the contour integral of the corresponding terms is also OLk polylog(n)/n . The first term of (36) warrants a more careful handling. We recall the decomposition D E 1X ⊤ u\i , 1A (G\i (z) − G̃i (z))v\i = ∂ 3 ℓj (rj,\i )(r̃j,i − rj,\i )1A u⊤ \i G\i (z)xj xj G̃i (z)v\i n j̸=i

1 X 4 ⊤ ∂ ℓj (řj,i )(r̃j,i − rj,\i )2 1A u⊤ \i G\i (z)xj xj G̃i (z)v\i , 2n j̸=i

for some řj,i ∈ (r̃j,i , rj,\i ). The last term is bounded uniformly over z ∈ Γ as 1 X 4 ⊤ ∂ ℓj (řj,i )(r̃j,i − rj,\i )2 1A u⊤ \i G\i (z)xj xj G̃i v\i 2n z∈Γ

sup

j̸=i

≤ ∂4ℓ

sup 1A\i X\i G̃i (z)v\i

∞ z∈Γ

sup 1A\i X\i G\i (z)u\i

∞ z∈Γ

Observe that the infinity norm supz∈Γ 1A\i X\i G\i (z)u\i

∞

sup(r̃j,i − rj,\i )2 .

∞ j̸=i

(47)

admits polylog(n) control, from

(45) and the Gaussian process bound (46) applied to the leave−i−out problem. Similarly, 47

supz∈Γ 1A\i X\i G̃i (z)v\i

∞

= supz∈Γ 1A\i X\i G\i (z)v\i

A.6) admits the same control. Thus,

∞

+ OLk (polylog(n)) (Proposition

1 X 4 ⊤ ∂ ℓj (řj,i )(r̃j,i − rj,\i )2 1A u⊤ \i G\i (z)xj xj G̃i v\i = OLk z∈Γ 2n

sup

j̸=i

polylog(n) n

In order to unravel the xi dependencies within the first term of (47) and reach control thereover, the surrogate resolvent G̃i (z) first needs to be approximated by the leave-i-out version G\i (z). The corresponding correction term is 1X 3 ⊤ ∂ ℓj (rj,\i )(r̃j,i − rj,\i )1A u⊤ \i G\i (z)xj xj (G̃i (z) − G\i (z))v\i z∈Γ n

sup

j̸=i

≤ ∂3ℓ

sup r̃j,i − rj,\i (1 + M )2 sup 1A (G̃i (z) − G\i (z))

∞ j̸=i

= OLk

polylog(n) n

z∈Γ

∥X∥ n

Thus, one has (up to O polylog(n)/n2 terms) " 2 # I 1 1 E (1A W\i (z)ab − 1A W̃i (z)ab )dz 2πi Γ z p   2 I D E X 1 1  1  2 −1 ⊤ ≤ 2∥∂ℓ∥∞ E  ∂ 3 ℓj (rj,\i )1A\i u⊤  \i G\i (z)xj xj G\i (z)v\i xj , H\i xi p 2 2πi Γ z n j̸=i





1 1 X 3  1 2 −1 ⊤ ∂ ℓj (rj,\i )1A\i u⊤ = 2∥∂ℓ∥∞ E  \i G\i (z)xj xj G\i (z)v\i H\i xj 2πi Γ z p n2

 

j̸=i

 2   PΓ 1 1 X 3   2 −1 ⊤ ⊤ ∂ ℓ (r )1 ≤ 2∥∂ℓ∥∞ E  u G (z)x x G (z)v H x   j A j j j,\i \i \i \i j \i \i \i  2π sup  p 2 z∈Γ z n j̸=i

It remains to bound sup z∈Γ

1 X 3 −1 ⊤ ∂ ℓj (rj,\i )1A\i u⊤ \i G\i (z)xj xj G\i (z)v\i H\i xj n2 j̸=i

1 3 1 X\i √ ≤ ∂ ℓ sup 1A\i X\i G\i (z)u\i sup 1A\i X\i G\i (z)v\i n n ∞ z∈Γ ∞ z∈Γ ∞λ

= OLk

The estimation Lemma thus allows to conclude " E

1 2πi

1 (1A W\i (z)ab − 1A W̃i (z)ab )dz p z Γ 48

2 #

polylog(n) n2

polylog(n) n

Third term of (43) —

It finally remains to bound the last term of (43).  " !  2 # I 2p (1 + M )2 P 2 1 1 Γ  E (1A − 1A\i )W\i (z)ab dz ≤ E  1A − 1A\i 2πi Γ z p λp+1 π ≤

2p (1 + M )2 PΓ λp+1 π

Injecting this control into the Efron-Stein bound completes the proof.

P [Ac ] = O(e− 2 ).

Deterministic equivalents

We have established in Appendix B the concentration of the different random statistics Q(k) , V(k) (21) that characterize the geometric properties of the ERM estimator ŵ (2). It is hence sufficient to ascertain their expectations. To that end, it remains to first determine the asymptotic distribution of the residuals ri,\i , r̃i,i : this is the object of the present section. More precisely, we establish the convergence of the expectations of test functions of ri,\i , r̃i,i to expectations over Gaussian variables. This property will then be leveraged in the subsequent subsection C.2 to compute the deterministic equivalents of the random statistics Q(k) , V(k) (21),(24), and the random functionals 1A S(·), 1A X(·), 1A W(·) (22)-(24).

C.1

Asymptotic residual distribution

We first define the admissible set of functions for which the aforementioned weak convergence holds. Definition C.1 (Class of admissible pseudo-Lipschitz test functions ). Let us define F the class of sequences of functions from R8 ! R that are pseudo-Lipschitz in all their arguments bar the second. Namely, ϕ ∈ F if and only if there exists a constant Lϕ = O(polylog(n)), such that for any R, R′ ∈ R6 coinciding on their second component (R2 = R2′ ), for n sufficiently large, ϕ(R) − ϕ(R′ ) ≤ Lϕ 1 + R(2)

′ + R(2)

R − R′ ,

′ where R(2) , R(2) ∈ R7 denote the vectors obtained by removing the second entry of R, R′ .

The class F introduced in Definition C.1 captures all the functions for which one needs to compute the average over the surrogate residuals, in order to access the deterministic equivalents of the different summary statistics Q(k) , V(k) , as will be made clear in subsection C.2. Note that we do not require pseudo-Lipschitzness for the second argument of the function. One is now in a position to characterize the asymptotic distribution of the leave-one-out residuals ri,\i . Lemma C.2 (Distribution of leave-one-out residuals). Let z ∈ Γ. Introduce the shorthand   Υ⊤ x i \i     ⊤ −1  n Υ\i H\i xi  o  . (48) Ri =  ⊤  RenΥ\i 1A\i G\i (z)xi o   Im Υ⊤ \i 1A\i G\i (z)xi For any sequence of test functions ϕ ∈ F, E ϕ(Ri ) − EX\i Eg ϕ(g) = O

polylog(n) 1

In the above display, g ∼ N (08 , Qi (z)) conditionally on X\i , where   Q(0) Q(1) Re Ω(z) Im Ω(z)    Q(1)  Q(2) fi (z)⊤     Qi = Re Ω(z) ,     f (z) F (z) i i   Im Ω(z) introducing the shorthands  n o −1 ⊤ Re Υ\i 1A\i G\i (z)H\i Υ\i o fi =  n , −1 Im Υ⊤ \i 1A\i G\i (z)H\i Υ\i  n o n ⊤ o Υ 1 G (z) Re A \i \i \i  o Fi =  n Re Υ⊤ 1A\i G\i (z)  \i Im Υ⊤ \i 1A\i G\i (z)

(49)

n o Im Υ⊤ 1 G (z) . \i A\i \i

Proof. By construction, Υ\i , H\i , 1A\i , G\i (z) are independent from xi . Thus, conditionally on X\i , the vector Ri is distributed as h ∼ N (0, Qi (z)), with  n o n o (1) (0) Q\i Re 1A\i W\i (z) Im 1A\i W\i (z)  Q\i    (1) (2) ⊤   Q\i fi (z)  n Q\i  o   . Qi (z) = Re 1A\i W\i (z) (50)     fi (z) Fi (z)  n  o   Im 1A\i W\i (z) The proof then proceeds by exploiting the Lipschitzness of the test function ϕ to control the difference of expectations by the difference between the covariances Qi (z), Qi (z). Particular care however needs to be devoted to handle the second entry, in which the test function ϕ is not (0) (0) assumed Lipschitz. To that end, first observe that Q22 = Q22 = 1, and g2 , h2 thus share an identical marginal. Conditioning on g2 , h2 , and using the shorthand ϕ̃(R2 , R(2) ) = ϕ(R), "  ! 12 E ϕ(Ri ) − EX\i Eg ϕ(g) = EX\i Eg2 Ef ϕ̃ g2 , qi (z)g2 + Qi (z) − qi (z)qi (z)⊤ f  

− Ef ϕ̃ g2 , qi (z)g2 + Qi (z) − qi (z)qi (z)⊤

! # f  ,

with f ∼ N (0, I7 ), and qi (z), qi (z) ∈ R7 correspond to the second column of Qi (z) and Qi (z) respectively after removal of the second entry, qi (z) = (Qi (z)[2:] )(2) ,

qi (z) = (Qi (z)[2:] )(2) , 51

and Qi (z) (resp. Qi (z)) corresponds to minors of Qi (z) (resp. Qi (z)) when its second line and column are removed. Leveraging the pseudo-Lipschitzness of ϕ, E ϕ(Ri ) − EX\i Eg ϕ(g) 1 ≤ Lϕ EX\i ,g2 ,f 1+ qi (z)g2 +(Qi (z)−qi (z)qi (z)⊤ ) 2 f 

× EX\i ,g2 ,f  qi (z)g2 + Qi (z) − qi (z)qi (z)⊤

+ qi (z)g2 +(Qi (z)−qi (z)qi (z)

⊤

)

!4 12

1 2f 1

f − qi (z)g2 − Qi (z) − qi (z)qi (z)⊤

 12  ,

(51) using a Cauchy-Schwartz inequality. We now sequentially examine the two expectations in the bound (51). Control of the second term of (51)— We start by controlling the last term.   21 21 2 EX\i ,g2 ,f  qi (z)g2 + Qi (z) − qi (z)qi (z)⊤ f − qi (z)g2 − Qi (z) − qi (z)qi (z)⊤ f   ≤ 2E

qi (z) − qi (z)



 + 2E Tr

Qi (z) − qi (z)qi (z)⊤

− Qi (z) − qi (z)qi (z)⊤

 !2   

It follows from an application of the concentration results of Lemma B.5 and B.3 to the leave-i-out problem that h i polylog(n) 2 E qi (z) − qi (z) =O . n Furthermore, from the Powers-Størmer inequality [Powers and Størmer, 1970],    !  21 12 2   E Tr Qi (z) − qi (z)qi (z)⊤ − Qi (z) − qi (z)qi (z)⊤ 

⊤

≤E

⊤

Qi (z) − qi (z)qi (z) − Qi (z) + qi (z)qi (z) ∗ √ ≤ 7E Qi (z) − qi (z)qi (z)⊤ − Qi (z) + qi (z)qi (z)⊤ ≤

√

7 E

Qi (z) − Qi (z)

qi (z)qi (z)⊤ − qi (z)qi (z)⊤

! . F

By construction, Qi (z) (50) and Qi (z) (49) coincide at the locations of fi (z), Fi (z), while the √ remaining entries only differ by OL2 (polylog(n)/ n) from the concentration established in Lemma

B.3 and B.5, applied to the leave-i−out problem. Therefore, polylog(n) √ E Qi (z) − Qi (z) =O . n F Furthermore, E qi (z)qi (z)⊤ − qi (z)qi (z)⊤

≤E

i h i (qi (z) − qi (z))qi (z) F + E qi (z)(qi (z) − qi (z)) F

≤

qi (z)

i 21

qi (z)

i 21

h E

qi (z) − qi (z)

i 21

From Lemma E.1, qi (z) , qi (z) = O(polylog(n)), while Lemma B.3 and B.5 ensure qi (z) − qi (z) = √ OL2 (polylog(n)/ n). Thus, polylog(n) √ =O E qi (z)qi (z)⊤ − qi (z)qi (z)⊤ . n F Therefore, 

EX\i ,g2 ,f  qi (z)g2 + Qi (z) − qi (z)qi (z)⊤ =O

polylog(n) √ n

f − qi (z)g2 − Qi (z) − qi (z)qi (z)⊤

 

Control of the first term of (51)— We now turn to the first term in (51). From Hölder’s inequality,  4  21 21   E 1 + qi (z)g2 + Qi (z) − qi (z)qi (z)⊤ f + qi (z)g2 + Qi (z) − qi (z)qi (z)⊤ f   1

" ≤ 27E 1 + 392

qi (z)

4 4 g2 +

Qi (z) − qi (z)qi (z)⊤

∥f ∥ + qi (z)

4 4 g2

Qi (z) − qi (z)qi (z)⊤

!# 4

∥f ∥

" ≤ 27E 1 + 392 3 qi (z)

+ 63

Qi (z) − qi (z)qi (z)⊤

+ 3 qi (z)

+ 63

Qi (z) − qi (z)qi (z)⊤

!# .

F −1 It follows from the bounds 1A\i G\i (z) , H\i ≤ λ1 for z ∈ Γ and ŵ\i ≤ M (Lemma E.1) that all Frobenius norms in the above display are OLk (polylog(n)), yielding O(polylog(n)) control over the first term of (51).

End of proof — Assembling these upper bounds into (51) finally yields the control polylog(n) E ϕ(Ri ) − EX\i Eg ϕ(g) = O , 1 n4 completing the proof. Remark C.3. It is worth pausing at this point to unravel this convergence result. Lemma C.2 establishes that averages over the residuals Ri may be replaced by Gaussian averages with covariance given by the semi-deterministic summary statistic Qi (z) (49). While the latter is in one-fourth populated by deterministic entries, it still retains random entries collected in fi (z), Fi (z), which seemingly restricts the scope of the results. This is in fact inconsequential, as all subsequent applications of Lemma C.2 in the computation of averages over Ri (subsection C) in fact never involve the corresponding random entries, which either do not appear, or are vanishing, when taking the average. We now state a follow-up results that similarly characterizes expectations over the surrogate residual r̃i,i . Lemma C.4 (Distribution of surrogate residuals). Let z ∈ Γ. Introduce the shorthand   r̃i,i     ⟨β, xi ⟩     −1 Υ⊤ H\i xi \i R̃i =  o  n , Re Υ⊤ 1 G (z)x  i   \i A\i \i o  n ⊤ Im Υ\i 1A\i G\i (z)xi which reprises the vector Ri (48) of Lemma C.2 with the replacement of the leave-one-out residual ri\i by the surrogate residual r̃i,i . For any sequence of test functions ϕ ∈ F (see Definition C.1), h i polylog(n) . E ϕ(R̃i ) − EX\i Eg ϕ ◦ π(g) = O 1 n4 In the above display, g ∼ N (08 , Qi (z)) conditionally on X\i , and π : R8 ! R8 is the map " # proxV (1) ℓ(·,g2 ) (g1 ) π(g) = , g(1) where we remind the notation g(1) ∈ R7 for the vector obtained from g after carving out the first entry. Proof. The proofs builds on Lemma C.2, applied to the function ϕ ◦ π. First observe that ϕ(R̃i ) = ϕ ◦ π̂(Ri ), where π̂ : R8 ! R8 is the map   prox x ,H −1 x (g1 ) i   \i i ℓ(·,g2 ) π̂(g) =  , n g(1) 54

and we remind Ri was introduced in (48). Decomposing the objective as h i E ϕ(R̃i ) − E ϕ ◦ π(g) ≤ E ϕ ◦ π̂(Ri ) − E ϕ ◦ π(Ri ) + E ϕ ◦ π(Ri ) − E ϕ ◦ π(g) , we successively control the two terms. Approximation of π, π̂ —

Since ϕ ∈ F,

2 ϕ ◦ π̂(Ri ) − ϕ ◦ π(Ri ) ≤ 1 + π(Ri ) 1 + π̂(Ri ) 1 r̃i,i − proxV (1) ℓ(·,⟨β,xi ⟩) (ri,\i ) (52) But r̃i,i − proxV (1) ℓi (·) (ri,\i ) D E −1 xi , H\i xi

= V (1) ∂ℓi (proxV (1) ℓi (·) (ri,\i )) − ∂ℓi (r̃i,i ) n   D E −1 x , H x i i \i   (1) 2 = V (1) −  ∂ℓi (r̃i,i ) + V ∂ ℓi (ři )(−r̃i,i + proxV (1) ℓi (·) (ri,\i )), n for some ři ∈ (r̃i,i , proxV (1) ℓi (·) (ri,\i )). Therefore, D

∥∂ℓ∥∞ V r̃i,i − proxV (1) ℓi (·) (ri,\i ) ≤

(1)

−

−1 xi xi ,H\i

= OL2

1 + V (1) ∂ 2 ℓi (ři )

polylog(n) √ n

using Lemma E.5 and Lemma B.4. Turning to the first term in (52), and using the contractivity of the proximal map in conjunction with the bound prox x , H −1 x /nℓ(·,0) (0), proxV (1) ℓ(·,0) (0) ≤ i

∥∂ℓ∥∞ OLk (polylog(n)), one has 4 4 E 1 + π(Ri ) 1 + π̂(Ri ) 1 ≤ E 8 OLk (polylog(n)) + 784∥Ri ∥ 2 ≤ E 8 OLk (polylog(n)) + 49392 Qi (z) F = O(polylog(n)). Returning to (52), ϕ ◦ π̂(Ri ) − ϕ ◦ π(Ri ) = OL1

polylog(n) √ n

ϕ ◦ π belongs to F — The desired claim follows from an application of Lemma C.2, provided one can first establish the compound map ϕ◦π belongs to the pesudo-Lipschitz class F (Definition

C.1). For any R, R′ ∈ R8 , 2 ϕ ◦ π(R) − ϕ ◦ π(R′ ) ≤ 1 + π(R) 1 + π(R′ ) 1 R − R′ 2 R − R′ ≤ 1 + 2 π(0) 1 + ∥R∥1 + R′ 1 2 2 ′ ≤ 1 + ∥∂ℓ∥∞ + ∥R∥1 + R 1 R − R′ , λ using the contractivity of the proximal map. It thus follows that ϕ ◦ π ∈ F. Hence, from Lemma C.2, polylog(n) E ϕ ◦ π(Ri ) − E ϕ ◦ π(g) = O , 1 n4 which completes the proof.

C.2

Computation of the deterministic equivalents

h i We are now in a position to ascertain the deterministic equivalents Q(k) = E Q(k) ,V (k) = h i E V(k) (12), (13) of the random summary statistics Q(k) , V(k) (21), (24), leveraging the concentration properties established in Appendix B. We note that the characterization of the particular parameters Q(0) , V (1) constitutes a now classical result featured in a large body of works, e.g. [El Karoui, 2013, Thrampoulidis et al., 2018, Donoho and Montanari, 2016]. The following extends those characterization to a broader class of statistics, characterized by any integer k ∈ N. In the following, we remind Γ ⊂ {z ∈ C : Re{z} > 0} is a deterministic contour enclosing the interval p 2 2 1 J = λ, λ + ∂ ℓ 2+ /α ∞

at a distance dist (Γ, J) ≥ λ/2, while also satisfying dist (Γ, 0) ≥ λ/2. Lemma C.5 (Characterization of V (k) ). The summary statistics V (k) are characterized by I −1 1 −n/2 V (k) = V(z)dz + O polylog(n)e , 2πi Γ z k where we recall V(z) = E 1A S(z) (26). Proof. We showed in Lemma B.4 the concentration of the random statistic I 1 1 V(k) = S(z)dz, 2πi C z p which involves an integration over the random contour C, defined in (39). With a view to ascertaining its expectation, a first step consists in replacing the random contour C by a deterministic contour Γ, in the likeness of the first step of the proof of Lemma B.5. The main 56

idea is that C needs to enclose the spectrum of the Hessian H. In the proportional asymptotic limit, the support of H is upper bounded with high probability, allowing one to interchange C and Γ. Note that the event A implies spec [H] ⊂ J. Partitioning the expectation, h i h i h i E V(k) = E V(k) 1A + E V(k) 1Ac The second term can be bounded as h i PC 2k+1 c −n/2 . E V(k) 1Ac ≤ P [A ] ≤ O polylog(n)e 2πλk+1 From the Fubini-Tonelli theorem, the expectation on the event A can be expressed as I I h i 1 1 1 1 E V(k) 1A = E 1 S(z) dz = V(z)dz A 2πi Γ z k 2πi Γ z k

Lemma C.6 (Characterization of Q(k) ). The summary statistics Q(k) are characterized by I −1 1 (k) −n/2 Q = Ω(z)dz + O polylog(n)e , 2πi Γ z k where Ω(z) = E 1A W(z) . Proof. The proof is identical to that of Lemma C.5. Lemmas C.5 and C.6 thus express the (deterministic) summary statistics V (k) , Q(k) in terms of the functionals V(·), Ω(·) (26). The following builds characterizations for the latter in terms of the summary statistics, thereby closing the equations. Lemma C.7 (Characterization of V(·)). For any z ∈ Γ with Im{z} ̸= 0, the functional V(·) satisfies asymptotically the equation " # 1 ∂ 2 ℓ (r, g2 ) V(z) polylog(n) − (λ − z)V(z) − E =O . 1 α 1 + ∂ 2 ℓ (r, g2 ) V(z) n4 In the above display, the expectations bear over the joint Gaussian variables g1 , g2 ∼ N 02 , Q(0) , and we employed the shorthand r = proxV (1) ℓ(·,g2 ) (g1 ). Proof. For any z ∈ Γ, we start from the identity 1A Id = (λ − z)1A G(z) +

1 X 2 ∂ ℓi (ri )xi x⊤ i 1A G(z) n i∈JnK

One has, by taking the trace and using the Woodbury inversion lemma, xi , 1A G(z)xi 1 1 X 2 1A − (λ − z)S(z) = ∂ ℓi (ri ) α n n i∈JnK

∂ 2 ℓi (ri )

1 X n

⟨xi ,1A Ĝi (z)xi ⟩ n

i∈JnK 1 + ∂ 2 ℓi (ri )

⟨xi ,1A Ĝi (z)xi ⟩

(53)

Where Ĝi (z) = (Ĥi − zId )−1 is the resolvent of the Hessian variant Ĥi =

1X 2 1 2 ∂ ℓj (rj )xj x⊤ ∂ ℓi (ri )xi x⊤ j + λId = H − i . n n

(54)

j̸=i

We note that Ĝi (z) is indeed well-defined for all z ∈ Γ under the event A, since H ⪰ Ĥi , and h i h i λ thus spec Ĥi ⊂ J under the event A. Notably, dist z, spec Ĥi ≥ /2. Approximating ri — The following step is to approximate the residual ri by the surrogate r̃i,i in (53). Bounding the corresponding correction term yields ⟨xi ,1A Ĝi (z)xi ⟩ ∂ 2 ℓi (r̃i,i ) n n − ⟨xi ,1A Ĝi (z)xi ⟩ i∈JnK 1 + ∂ 2 ℓ (r ) ⟨xi ,1A Ĝi (z)xi ⟩ 2 1 + ∂ ℓi (r̃i,i ) i i n n ∂ 2 ℓi (ri )

sup

⟨xi ,1A Ĝi (z)xi ⟩

≤ sup i∈JnK

1 + ∂ 2 ℓi (ri )

× ∂3ℓ

1 sup ⟨xi ,1A Ĝi (z)xi ⟩ i∈JnK n

D E xi , 1A Ĝi (z)xi

sup ri − r̃i,i sup

∞ i∈JnK

1 ⟨xi ,1A Ĝi (z)xi ⟩ 1 + ∂ 2 ℓi (r̃i,i ) n

i∈JnK

Note that the term supi∈JnK ri − r̃i,i is controlled by Proposition A.6, while for the last term D

xi , 1A Ĝi (z)xi

E ≤

p 2 (2 + 1/α)2 . λ

We now exhibit a lower-bound on 1 + ∂ 2 ℓi (ri ) xi , 1A Ĝi (z)xi /n. From the Woodbury formula, D

1A G(z)xi =

1 1 + ∂ 2 ℓi (ri )1A

⟨xi ,Ĝi (z)xi ⟩

1A Ĝi (z)xi .

Thus, one can lower-bound D E Ĝi (z)xi Ĝi xi xi , Ĝi (z)xi + (1 − 1A ) ≥ 1A 2 1 + ∂ 2 ℓi (ri )1A ≥ 1A + (1 − 1A ). n /λ∥xi ∥ G(z)xi

Since furtheremore ∥xi ∥ ≤ Ĥi − zId

Ĝi xi ≤

λ + ∂2ℓ

∞

(2 +

1/α)2 + |z|

Ĝi xi ,

one finally has 1 + ∂ 2 ℓi (ri )1A

D E xi , Ĝi (z)xi

≥

2/λ

λ + ∥∂ 2 ℓ∥∞ (2 +

1/α)2 + |z|

(55)

∧1

The same reasoning holds to reach a lower bound on 1 + ∂ 2 ℓi (r̃i,i ) xi , 1A Ĝi (z)xi /n, using this time the identity D

1A Ǧ(z)xi =

1 + ∂ 2 ℓi (r̃i,i )1A

⟨xi ,Ĝi (z)xi ⟩

1A Ĝi (z)xi .

introducing for that purpose the modified resolvent  −1 X 2 ⊤  , Ǧ(z) =  ∂ 2 ℓ(rj )xj x⊤ j + ∂ ℓ(r̃i,i )xi xi + (λ − z)Id j̸=i

which also satisfies the operator norm bound Ǧ(z) ≤ 2/λ on the event A. Repeating the above argument, D E xi , Ĝi (z)xi 1 ∧1 (56) 1 + ∂ 2 ℓi (r̃i,i )1A ≥ p n 2 2/λ λ + ∥∂ ℓ∥ (2 + 1/α)2 + |z| ∞ and thus ⟨xi ,1A Ĝi (z)xi ⟩ ∂ 2 ℓi (r̃i,i ) n n − ⟨xi ,1A Ĝi (z)xi ⟩ i∈JnK 1 + ∂ 2 ℓ (r ) ⟨xi ,1A Ĝi (z)xi ⟩ 2 1 + ∂ ℓi (r̃i,i ) i i n n sup

∂ 2 ℓi (ri )

⟨xi ,1A Ĝi (z)xi ⟩

= OLk

The next simplification consists in approximating the quadratic form up to corrections with vanishing moments.

polylog(n) √ n

xi , 1A Ĝi (z)xi

/n by V(z)

/n — This step proceeds through successive approximations n o by xi , 1A G\i (z)xi /n, 1A 1/n tr G\i (z) and 1A S(z). First, note that Approximation of D

xi , 1A Ĝi (z)xi

sup i∈JnK

D E xi , 1A (Ĝi (z) − G\i (z))xi n

≤

p 4 (2 + 1/α)4 ∂ 3 ℓ sup sup rj,\i − rj 2 λ ∞ i∈JnK j̸=i

= OLk using Proposition A.6 in the second equality. 59

polylog(n) √ n

We now approximate the quadratic form by a tracial quantity. Decomposing the resolvent G\i (z) into real and imaginary parts yields D E xi , G\i (z)xi sup

i∈JnK

≤ sup Im{z}

−

i 1 h tr G\i (z) n

D E xi , G\i (z)G\i (z)† xi n

i∈JnK

xi , G\i (z)G\i (z)† xi

+ sup Re{z}

i∈JnK

D E xi , G\i (z)G\i (z)† H\i xi + sup

i∈JnK

−

i 1 h tr G\i (z)G\i (z)† n

−

i 1 h tr G\i (z)G\i (z)† n

i 1 h tr G\i (z)G\i (z)† H\i . n

Since G\i (z)G\i (z)† H\i ⪰ 0 and G\i (z)G\i (z)† ⪰ 0, and †

G\i (z)G\i (z)

≤

1 Im{z}

†

G\i (z)G\i (z) H\i ≤

1 Im{z}

∥X∥ λ+ ∂ ℓ ∞ n 2

! ,

one can apply Lemma G.3 in El Karoui [2018], yielding the concentration D E xi , G\i (z)xi sup 1A i∈JnK

i 1 h polylog(n) √ − tr 1A G\i (z) = OLk . n n

Finally, i 1 h polylog(n) √ sup 1A tr G\i (z) − G(z) = OLk , n n i∈JnK again from Proposition A.6. Finally, remember from Lemma B.1 the concentration polylog(n) √ . 1A S(z) − V(z) = OLk n Chaining all these successive approximations together, we have hence established the pointwise concentration D E 1A xi , Ĝi (z)xi polylog(n) √ sup − V(z) = OLk . (57) n n i∈JnK One would like to transfer this control to the summand in (53). Expounding the corresponding

correction term, ∂ 2 ℓi (r̃i,i )

⟨xi ,1A Ĝi (z)xi ⟩

∂ 2 ℓi (r̃i,i )V(z) n − 1 + ∂ 2 ℓi (r̃i,i )V(z) i∈JnK 1 + ∂ 2 ℓ (r̃ ) ⟨xi ,1A Ĝi (z)xi ⟩ i i,i n sup

1 ∂ ℓi (r̃i,i ) sup sup 2 ℓ (r̃ )V(z) x ,1 Ĝ (z)x 1 + ∂ ⟨ ⟩ i A i i i∈JnK i∈JnK i∈JnK i i,i 1 + ∂ 2 ℓi (r̃i,i ) n

≤ sup

D E 1A xi , Ĝi (z)xi n

− V(z) . (58)

Therefore, it remains to lower-bound the two terms in the denominator. The first term was bounded in (56). ∂ 2 ℓi (r̃i,i ) — We now turn to the second term in (58). On the one |1+∂ 2 ℓi (r̃i,i )V(z)| hand, the modulus of 1 + ∂ 2 ℓi (r̃i,i )V(z) is lower-bounded by the absolute value of its imaginary

Upper bound on part, namely

h i 1 + ∂ 2 ℓi (r̃i,i )V(z) ≥ ∂ 2 ℓi (r̃i,i ) Im{z} E 1A 1/n tr G(z)G(z)† ≥ P [A] ∂ 2 ℓi (r̃i,i ) Im{z} ≥

1 2

1 |z| + (λ + ∥∂ 2 ℓ∥∞ (2 +

Im{z} |z| + (λ + ∥∂ 2 ℓ∥

∞ (2 +

1/α)2 )

2 ∂ ℓi (r̃i,i )

Therefore, if ∂ 2 ℓi (r̃i,i ) ≥

λ2 1 p 8 |z| + λ + ∥∂ 2 ℓ∥∞ (2 + 1/α)2

then 1 ≤ 2 1 + ∂ ℓi (r̃i,i )V(z)

16/λ2

|z| + λ + ∂ 2 ℓ ∞ (2 +

Im{z}

1/α)2

3 .

On the other hand, if ∂ 2 ℓi (r̃i,i ) <

λ2 1 p , 2 8 |z| + λ + ∥∂ ℓ∥∞ (2 + 1/α)2

we bound the modulus of 1 + ∂ 2 ℓi (r̃i,i )V(z) by the absolute value of its real part: h i 2 2 † 1 1 + ∂ ℓi (r̃i,i )V(z) ≥ 1 + ∂ ℓi (r̃i,i )E 1A /n tr G(z)G(z) (H − Re{z}Id ) . Since h i p 4 E 1A 1/n tr G(z)G(z)† (H − Re{z}Id ) ≤ 2 λ + ∂ 2 ℓ (2 + 1/α)2 + |z| , λ ∞ 61

one has in this case 1 + ∂ 2 ℓi (r̃i,i )V(z) ≥

1 . 2

Thus, irrespective of the value of ∂ 2 ℓ(r̃i,i ), one has the bound 3 p 16/λ2 |z| + λ + ∂ 2 ℓ 1/α)2 (2 + 1 ∞ ≤ ∨ 2. 1 + ∂ 2 ℓi (r̃i,i )V(z) Im{z} End of the proof of Lemma C.7 — ∂ 2 ℓi (r̃i,i )

Returning to (58), one thus has pointwise in z that

⟨xi ,1A Ĝi (z)xi ⟩

∂ 2 ℓi (r̃i,i )V(z) n − 1 + ∂ 2 ℓi (r̃i,i )V(z) i∈JnK 1 + ∂ 2 ℓ (r̃ ) ⟨xi ,1A Ĝi (z)xi ⟩ i i,i n sup

(59)

= OLk

polylog(n) √ n

Returning to the identity (53) and taking expectation, " # 1 1 X ∂ 2 ℓi (r̃i,i )V(z) polylog(n) √ − (λ − z)V(z) = E +O α n 1 + ∂ 2 ℓi (r̃i,i )V(z) n i∈JnK # " polylog(n) ∂ 2 ℓ1 (r̃1,1 )V(z) √ + O =E , 1 + ∂ 2 ℓ1 (r̃1,1 )V(z) n where in going to the second line we leveraged the observation that by permutation symmetry of the problem, all expectations are equal. The expectation over the surrogate variable r̃1,1 can further be converted into a Gaussian integral by using the distributional approximation of Lemma C.4, since the function in bracket belongs to the admissible class F, as defined in Definition C.1. More precisely, equipped with the shorthand r = proxV (1) ℓ(·) (g1 ), # " # " ∂ 2 ℓ (r, g2 ) V(z) polylog(n) ∂ 2 ℓ1 (r̃1,1 )V(z) =E +O E 1 1 + ∂ 2 ℓ1 (r̃1,1 )V(z) 1 + ∂ 2 ℓ (r, g2 ) V(z) n4 Hence, finally " # ∂ 2 ℓ (r, g2 ) V(z) polylog(n) 1 − (λ − z)V(z) = E +O , 1 α 1 + ∂ 2 ℓ (r, g2 ) V(z) n4 completing the proof. Lemma C.8 (Characterization of χ(·)). For any z ∈ Γ with Im{z} = ̸ 0, the functional χ(·) satisfies pointwise the convergence V (1) polylog(n) +O χ(z) = 1 2 n4 2) (λ − z) + E 1+V (1) ∂ 2 ℓ(r,g∂ ℓ(r,g 2 ( 2 ))(1+V(z)∂ ℓ(r,g2 )) The expectations bear over the joint Gaussian variables g1 , g2 ∼ N 02 , Q(0) , and we employed the shorthand r = proxV (1) ℓ(·,g2 ) (g1 ). 62

Proof. We start with the identity 1A H −1 = (λ − z)H −1 1A G(z) +

1 X 2 ∂ ℓi (ri )1A H −1 G(z)xi x⊤ i . n i∈JnK

Taking the normalized trace, and applying Woodbury’s inversion lemma 1A V(1) = (λ − z)1A X(z) +

1 X 2 −1 ∂ ℓi (ri )x⊤ G(z)xi i 1A H n2 i∈JnK

= (λ − z)1A X(z) +

1/nx⊤ 1 Ĥ −1 Ĝ (z)x i i i A i . ∂ 2 ℓi (ri ) −1 n x ,1 Ĥ x ⟨ ⟩ ⟨xi ,1A Ĝi (z)xi ⟩ i i A i 2 2 i∈JnK 1 + ∂ ℓi (ri ) 1 + ∂ ℓi (ri ) n n

1 X

We remind that the truncated Hessian Ĥi and its associated resolvent Ĝi were defined in (54). Approximation of xi , 1A Ĝi (z)xi /n — As a first step, we approximate V(z). We recall the bound (57) D

D E xi , Ĝi (z)xi sup i∈JnK

− V(z) = OLk

polylog(n) √ n

xi , 1A Ĝi (z)xi

from which it follows that the associated correction term is controlled as 1/nx⊤ 1 Ĥ −1 Ĝ (z)x i i i A i sup −1 x x ,1 Ĥ ⟩ ⟨ ⟨xi ,1A Ĝi (z)xi ⟩ i i A i∈JnK i 2 2 1 + ∂ ℓi (ri ) 1 + ∂ ℓi (ri ) n n 1/nx⊤ 1 Ĥ −1 Ĝ (z)x i i A i i − −1 Ĥ x x ,1 ⟩ ⟨ i i A i 1 + ∂ 2 ℓi (ri ) 1 + ∂ 2 ℓi (ri )V(z) n polylog(n) √ = OLk . n

To bound the denominators, we have used (55) and 1 ≤ 2 1 + ∂ ℓi (ri )V(z)

32/λ2

|z| + λ + ∂ 2 ℓ ∞ (2 + Im{z}

which follows from an identical derivation as (59), and 1 1 + ∂ 2 ℓi (ri )1A Approximation of

xi , 1A Ĥi−1 (z)xi

/n —

⟨xi ,Ĥi (z)xi ⟩ n

Similarly,

≤ 1.

1/α)2

2 ∨ 2,

/n by

D E xi , Ĥi xi sup

−V

i∈JnK

(1)

= OLk

polylog(n) √ n

using Lemma B.4, from which it follows that 1/nx⊤ 1 Ĥ −1 Ĝ (z)x i i i A i

sup

i∈JnK

1 + ∂ 2 ℓi (ri )

= OLk

xi ,1A Ĥi−1 xi

⟨

polylog(n) √ n

⟩

−

1 + ∂ 2 ℓi (ri )V(z)

1/nx⊤ 1 Ĥ −1 Ĝ (z)x i i i Ai 1 + ∂ 2 ℓi (ri )V (1) 1 + ∂ 2 ℓi (ri )V(z)

−1 Approximation of x⊤ Finally, we now turn to approximating the numerator. i 1A Ĥi Ĝi (z)xi/n— Approximating the truncated matrices Ĥi , Ĝi by their leave-i-out equivalents, −1 x⊤ Ĥi−1 Ĝi (z) − H\i G\i (z) xi i polylog(n) √ sup = OLk . n n i∈JnK

We now approximate the quadratic form by a tracial quantity. Decomposing the resolvent G\i (z) into real and imaginary parts yields D E −1 i xi , H\i G\i (z)xi 1 h −1 sup − tr H\i G\i (z) n n i∈JnK

≤ sup Im{z}

D E −1 xi , H\i G\i (z)G\i (z)† xi n

i∈JnK

+ sup Re{z}

D E −1 xi , H\i G\i (z)G\i (z)† xi n

i∈JnK

+ sup i∈JnK

D E −1 xi , H\i G\i (z)G\i (z)† H\i xi n

−

i 1 h −1 tr H\i G\i (z)G\i (z)† n

−

i 1 h −1 tr H\i G\i (z)G\i (z)† n

i 1 h −1 tr H\i G\i (z)G\i (z)† H\i . n

−1 −1 Since H\i G\i (z)G\i (z)† H\i , H\i G\i (z)G\i (z)† ⪰ 0, and exhibit OLk (polylog(n))−bounded operator norms, Lemma E.5 ensures the control D E −1 i xi , H\i G\i (z)xi 1 h −1 polylog(n) √ sup − tr H\i G\i (z) = OLk . n n n i∈JnK

Finally, leveraging Proposition A.6, i 1 h −1 polylog(n) √ sup tr H\i G\i (z) − X(z) = OLk . n i∈JnK n Finally, using the pointwise concentration of X(·) established in Lemma B.2, −1 x⊤ i 1A Ĥi Ĝi (z)xi − 1A χ(z) = OLk n

polylog(n) √ n

We have thus so far established that ∂ 2 ℓi (ri )χ(z) polylog(n) + O Lk √ (60) . n 1 + ∂ 2 ℓi (ri )V (1) 1 + ∂ 2 ℓi (ri )V(z)

End of the proof of Lemma C.8 — 1A V(1) = (λ − z)X(z) +

1 X n

i∈JnK

It now remains to replace the full residual ri by the surrogate r̃i,i , which in turn enables the application of Lemma C.4. From Proposition A.6, and appealing once more to the bound (59), ∂ 2 ℓi (ri )χ(z) ∂ 2 ℓi (r̃i,i )χ(z) − 1 + ∂ 2 ℓi (ri )V (1) 1 + ∂ 2 ℓi (ri )V(z) 1 + ∂ 2 ℓi (r̃i,i )V (1) 1 + ∂ 2 ℓi (r̃i,i )V(z) i∈JnK polylog(n) √ . = OLk n sup

Thus, taking expectation in (60), " # 2 X polylog(n) 1 ∂ ℓ (r̃ )χ(z) i i,i (1) √ V = (λ − z)χ(z) + E +O n n 1 + ∂ 2 ℓi (r̃i,i )V (1) 1 + ∂ 2 ℓi (r̃i,i )V(z) i∈JnK

" = (λ − z)χ(z) + E

# polylog(n) ∂ 2 ℓ1 (r̃1,1 )χ(z) +O √ , n 1 + ∂ 2 ℓ1 (r̃1,1 )V (1) 1 + ∂ 2 ℓ1 (r̃1,1 )V(z)

where we used the observation that by permutation symmetry of the problem, all expectations are equal. Finally, from Lemma C.4, " # ∂ 2 ℓ1 (r̃1,1 )χ(z) E 1 + ∂ 2 ℓ1 (r̃1,1 )V (1) 1 + ∂ 2 ℓ1 (r̃1,1 )V(z) " # ∂ 2 ℓ(r, g2 )χ(z) polylog(n) +O =E . 1 1 + ∂ 2 ℓ(r, g2 )V (1) 1 + ∂ 2 ℓ(r, g2 )V(z) n4 Thus  χ(z) λ − z + E

# ∂ 2 ℓ(r, g2 ) polylog(n)  = V (1) + O (61) . 1 1 + ∂ 2 ℓ(r, g2 )V (1) 1 + ∂ 2 ℓ(r, g2 )V(z) n4

In order to complete the proof, it remains to show that the modulus of the term in bracket admits a strictly positive lower-bound for n sufficiently large. Reasoning by the absurd, let 65

us conversely suppose that for any ϵ > 0 and n0 , there exist an n ≥ n0 such that the term in bracket has modulus inferior to ϵ. The left hand side is then upper bounded by ϵ1/λ Im{z} . On the other hand, when n ≥ 4, h i n V (1) = E 1A H −1 + O e− /2 ≥

1 2(λ + ∥∂ 2 ℓ∥∞ (2 +

1/α)2 )

n + O e− /2 ,

which admits a strictly positive lower-bound for n sufficiently large. Then, (61) cannot hold for all ϵ, thus yielding a contradiction. Thus, one can conclude that the bracketed term admits a positive lower bound in modulus for n sufficiently large, and V (1) polylog(n) χ(z) = +O , 1 2 n4 2) λ − z + E 1+∂ 2 ℓ(r,g )V∂(1)ℓ(r,g ( )(1+∂ 2 ℓ(r,g2 )V(z)) 2 completing the proof. Lemma C.9 (Characterization of Ω(·)). For any z ∈ Γ with Im{z} = ̸ 0 Ω(·) satisfies pointwise the convergence    " # h i g   ∂ 2 ℓ(r, g2 )(Q(0) )+ 1 r g2     g2     Ω(z) (λ − z)I2 + E   2 ℓ(r, g )V(z)   1 + ∂ 2      

r g2  ∂ 2 ℓ(r, g2 )∂ℓ(r, g2 )  0 0  = Q(0) + χ(z)E  2  1 + ∂ ℓ(r, g2 )V(z) 

#   polylog(n)  . +O 1  n4 

The + superscript denotes the Moore-Penrose pseudo-inverse. Proof. The proof proceeds in close likeness to those of Lemma C.7 and C.8. We take again as a starting point the definition of the resolvent G(z), from which one deduces the identity 1A Q(0) = (λ − z)1A W(z) +

1 X 2 ∂ ℓi (ri )Υ⊤ 1A G(z)xi x⊤ i Υ n i∈JnK

1A Ĝi (z)xi x⊤ Υ ⟨xi ,1A Ĝi (z)xi ⟩ i 2 1 + ∂ ℓi (ri ) i∈JnK n ⊤ ⊤ X 1 Υ 1A Ĝi (z)xi xi Υ polylog(n) √ = (λ − z)1A W(z) + ∂ 2 ℓi (ri ) + O Lk n 1 + ∂ 2 ℓi (ri )V(z) n i∈JnK Υ⊤ 1A G\i (z)xi x⊤ 1 X 2 polylog(n) i Υ √ = (λ − z)1A W(z) + ∂ ℓi (ri ) + O Lk n 1 + ∂ 2 ℓi (ri )V(z) n = (λ − z)1A W(z) +

1 X 2 ∂ ℓi (ri )Υ⊤ n

i∈JnK

In the penultimate line, we used the bounds X1A Ĝi (z)Υ

∞

, ∥XΥ∥∞ = OLk (polylog(n)),

which may be derived using identical steps to those used to reach (33) of Lemma B.1. In the √ last line, we used the resolvent bound supi∈JnK 1A (Ĝi (z) − G\i (z)) = OLk polylog(n)/ n . We now turn to approximating the numerator Υ⊤ 1A G\i (z)xi x⊤ i Υ. Developing Υ in terms of its leave-i-out approximation h i 1 −1 xi 0d , Υ = Υ\i − ∂ℓi (r̃i,i ) H\i n one can expound h

⊤ Υ⊤ G\i (z)xi x⊤ i Υ = Υ\i G\i (z)xi ri

D E −1 xi ,H\i G\i (z)xi h i  ri n ⟨β, xi ⟩ − ∂ℓi (r̃i,i )  0

i ⟨β, xi ⟩ .

It then follows from Lemma E.5 and Lemma B.2 that sup Υ

⊤

i∈[n]

admits OLk

⊤ 1A G\i (z)xi x⊤ i Υ − Υ\i 1A G\i (z)xi

polylog(n)/√n

" # i χ(z) h ⟨β, xi ⟩ + ∂ℓi (r̃i,i ) ri 0

control. Thus, (up to OLk 

1A Q(0) = (λ − z)1A W(z) +

1 X 2 ∂ ℓi (ri ) n

polylog(n)/√n

⟨β, xi ⟩

corrections) " # h Υ⊤ 1A G\i (z)xi − ∂ℓi (r̃i,i ) χ(z)  ri \i 0

⟨β, xi ⟩

1 + ∂ 2 ℓi (ri )V(z)

i∈JnK



= (λ − z)1A W(z) +

1 X 2 ∂ ℓi (r̃i,i ) n

" # h χ(z) Υ⊤ 1A\i G\i (z)xi − ∂ℓi (r̃i,i )  r̃i,i \i 0

i ⟨β, xi ⟩

1 + ∂ 2 ℓi (r̃i,i )V(z)

i∈JnK

using Proposition A.6. We omitted the intermediary steps, which are identical to those leveraged in Lemma C.7. Taking expectation, and using the permutation symmetry of all indices i ∈ JnK,    " # h i χ(z)  Υ⊤ 1A\1 G\1 (z)x1 − ∂ℓ1 (r̃1,1 )  r̃1,1 ⟨β, x1 ⟩    \1 0    2  (0) Q = (λ − z)Ω(z) + E ∂ ℓ1 (r̃1,1 )    1 + ∂ 2 ℓi (r̃1,1 )V(z)    

polylog(n) √ n

It can be verified that the function within the bracket belongs to the class F of pseudo-Lipschitz functions defined in Definition C.1. Therefore, applying Lemma C.2, the expectation can be 67

replaced by one bearing over the Gaussian vector g ∼ N (08 , Qi (z)), where Qi (z) is defined in (49):   " # " # " # h i   g5 +i g7 − ∂ℓ(r, g2 ) χ(z)  r g2    g6 g8 0   polylog(n)   2 (0) +O Q = (λ − z)Ω(z)+E ∂ ℓ(r, g2 )  1   1 + ∂ 2 ℓ(r, g2 )V(z) n4    

again with the shorthand r = proxV (1) ℓ(·,g2 ) (g1 ). Note that the component of g5 , ..., g8 uncorrelated with g1 , g2 vanishes, yielding    " # " # h i  Ω(z)(Q(0) )+ g1 − ∂ℓ(r, g2 ) χ(z)  r g2    g2 0    2  (0) Q = (λ − z)Ω(z) + E ∂ ℓ(r, g2 )    1 + ∂ 2 ℓ(r, g2 )V(z)     +O

polylog(n) 1

where the + superscript denotes the Moore-Penrose pseudo-inverse. After a minor rewriting, finally,     " # " # h i r g g 2   ∂ 2 ℓ(r, g2 )∂ℓ(r, g2 )   ∂ 2 ℓ(r, g2 )(Q(0) )+ 1 r g2       0 0 g   2     (0)  =Q +χ(z)E Ω(z)(λ − z)I2 +E         1 + ∂ 2 ℓ(r, g2 )V(z) 1 + ∂ 2 ℓ(r, g2 )V(z)        

+O which concludes the proof.

polylog(n) 1

Convergence of influence distributions

Appendices B and C provides a characterization in the high-dimensional limit n ≍ d of a set of summary statistics Q(k) , V (k) (12), (13), which subsume key statistical and geometric properties of the ERM minimizer ŵ (2), and its interaction with the local risk landscape captured by the Hessian H. Equipped with those descriptors, the present Appendix builds upon this characterizations to deduce the asymptotic distribution of sample influences (5), (6).

D.1

Comments on the risk normalization

Before proceeding, it is crucial to make the observation that in the definition of ŵ\i (19), leveraged repeatedly throughout the leave-one-out analysis presented in Appendices B and C, the sum of losses retains a 1/n normalization, as opposed to the more natural 1/n − 1 scaling in the definition of ŵ(i) (4). This slight difference ripples into subtle effects, and yields a non-negligible contribution when studying influence metrics. We thus first establish approximation results related to this difference in rescaling, and comment that it can be seen as approximation results in the change in estimator when the ridge regularization is perturbed by O(1/n). Let us recall the definitions 1 X λ 2 ŵ = arg min ℓ( xj , w , yj ) + ∥w∥ , n 2 d w∈R j∈JnK

1 X λ 2 ŵ\i = arg min ℓ( xj , w , yj ) + ∥w∥ , 2 w∈Rd n j∈JnK\i

ŵ(i) = arg min w∈Rd

X λ 1 2 ℓ( xj , w , yj ) + ∥w∥ . n−1 2 j∈JnK\i

We also introduce ŵ(·) = arg min w∈Rd

X 1 λ 2 ℓ( xj , w , yj ) + ∥w∥ . n−1 2 j∈JnK

Retracing all steps in the proofs of Appendix B and C reveal that the change of normalization is inconsequential, and all the results above, in particular Propostion A.6 and Lemmas C.7, C.9, apply equally to the pairs (ŵ, ŵ\i ) and (ŵ(·) , ŵ(i) ) respectively. However, because the influence metrics IFi (5) and DFBETAi (6) compare estimators with different normalizations, a finer control of the discrepancies between these pairs of estimators is called for. This is the object of the following Lemmas. Lemma D.1 (Approximation after rescaling). One has 1 ŵ − ŵ(·) = OLk . n D E As a consequence, denoting rj,(·) = xj , ŵ(·) , polylog(n) √ sup rj,(·) − rj = OLk . n j∈JnK 69

Proof. Observe that one can rewrite the empirical risk minimized by ŵ(·) as 1 X λ 1 2 ŵ(·) = arg min ℓ( xj , w , yj ) + 1− ∥w∥ , 2 n w∈Rd n j∈JnK

absorbing the difference in normalization into the ridge regularization. From the optimality conditions, it follows that λ 1 X 2 λ(ŵ − ŵ(·) ) + ŵ(·) + ∂ ℓj (řj )xj x⊤ j (ŵ − ŵ(·) ) = 0, n n j∈JnK

for some řj ∈ (rj,(·) , rj ). Thus  −1 λ 1 X 2  ŵ(·) . ŵ − ŵ(·) = − ∂ ℓj (řj )xj x⊤ j + λId n n

(62)

j∈JnK

A straightforward adaptation of Lemma E.1 shows that ŵ(·) ≤ 2M, from which it follows that ŵ − ŵ(·) ≤

2M . n

Remark D.2. An identical result naturally follows for all i ∈ JnK at the level of the leave-i−out estimators, namely 1 ŵ(i) − ŵ\i = O . n Lemma D.1 thus ensures the full-dataset estimates ŵ, ŵ(·) are close. This claim is refined in the following Lemmas, which establish the concentration of a number of scalar products of the difference ŵ − ŵ(·) . These descriptors will be subsequently used in subsection D.2 to build a characterization for the test error influence distribution. D E Lemma D.3. The inner product β, ŵ − ŵ(·) concentrates as D E polylog(n) (1) √ n β, ŵ − ŵ(·) = −λQ12 + OL2 . n Proof. Once more taking the difference in optimality conditions, λ 1 X 2 1 X 3 λ(ŵ − ŵ(·) ) + ŵ(·) + ∂ ℓj (rj )xj x⊤ ∂ ℓj (řj )(rj,(·) − rj )2 xj = 0, j (ŵ − ŵ(·) ) + n n n j∈JnK

j∈JnK

for some řj ∈ (rj,(·) , rj ). Thus, D E D E X n β, ŵ − ŵ(·) = −λ β, H −1 ŵ(·) − ∂ 3 ℓj (řj )(rj,(·) − rj )2 β, xj . j∈JnK

(63)

On the one hand, D E D E 1 1 1 (1) (1) −1 −1 β, H ŵ(·) = β, H ŵ + OLk , = Q12 + OLk = Q12 + OL2 √ n n n using Lemma B.5. Turning to the remaining term in (63), E λD −1 xi , H ŵ(·) n E λD polylog(n) −1 =− xi , H ŵ\i + OLk , n n

ri,(·) − ri = −

using Lemma D.1 and Proposition A.6, reprising equation (62). We denoted H=

1 X 2 ∂ ℓj (řj )xj x⊤ j + λId . n j∈JnK

To disentangle xi dependencies, we seek to approximate H by H\i . The corresponding correction term reads E D 1 −1 −1 −1 −1 ŵ\i = − ∂ 2 ℓj (ři ) xi , H xi x⊤ H ŵ xi , H − H\i \i i \i n E D 1 −1 ⊤ −1 + xi , H X\i ΛX\i H\i ŵ\i , n where Λ is a diagonal matrix with entries Λjj = ∂ 3 ℓj (rj )(rj\i − řj ), for some rj ∈ (rj\i , řj ). It thus follows that ! Λ

∞

≤ ∂ ℓ

∞

rj − rj,(·) + sup

sup

rj − rj,\i

sup

= OLk

i∈JnK j∈JnK\i

j∈JnK

It follows from an application of Lemma E.6 that sup i∈JnK

D E −1 −1 xi , (H − H\i )ŵ\i = OLk polylog(n) .

As a consequence, applying again Lemma E.6, sup rj,(·) − rj = OLk j∈JnK

polylog(n) n

Finally, returning to (63), X

∂ ℓj (řj )(rj,(·) − rj )

β, xj

j∈JnK

concluding the proof. 71

= OLk

polylog(n) n

polylog(n) √ n

An identical proof furthermore allows to establish the following result, this time on the inner D E product n ŵ, ŵ − ŵ(·) . E D Lemma D.4. The inner product ŵ, ŵ − ŵ(·) concentrates as D E polylog(n) (1) √ n ŵ, ŵ − ŵ(·) = −λQ11 + OL2 . n Proof. The proof of Lemma D.4 follows identically that of Lemma D.3, using in addition ∥X ŵ∥∞ = OLk (polylog(n)).

D.2

Proof of Theorem 2.1

One is now in a position to ascertain the asymptotic distribution of the leave-one-out influences IFi (5) and DFBETAi (6) in the high-dimensional limit n, d ! ∞, while α = n/d = Θ(1), completing the proof of the main theoretical results collected within Theorem 2.1 and Proposition 2.2. Before doing so, it proves useful to unravel the statistical correlations built in the difference in the definition of IFi , so as to reach an expression amenable to easier analysis through the convergence Lemma C.4. This is the object of the following Lemma. Lemma D.5. Define the surrogate influence D E D E (0) (0) (0) (0) −1 −1 (2) 2 ψi =∂2 E(Q12 , Q11 ) −2∂ℓi (ri ) ŵ\i , H\i xi + V ∂ℓi (ri ) − ∂1 E(Q12 , Q11 )∂ℓi (ri ) β, H\i xi (0)

(0)

(1)

(0)

(1)

− 2λ∂2 E(Q12 , Q11 )Q11 − λ∂1 E(Q12 , Q11 )Q12 Then the following approximation result holds:

sup |IFi − ψi | = OL2 i∈JnK

polylog(n) √ n

Proof. We first decompose IFi = n Egen [ŵ] − Egen [ŵ(·) ] + n Egen [ŵ(·) ] − Egen [ŵ(i) ] .

(64)

From a second-order Taylor expansion, n Egen [ŵ(·) ] − Egen [ŵ(i) ] D E D E 2 (0) (0) (0) (0) = n∂2 E Q12 , Q11 ŵ(·) − ŵ(i) + 2 ŵ(i) , ŵ(·) − ŵ(i) + n∂1 E Q12 , Q11 β, ŵ(·) − ŵ(i) D E2 1 D E2 2 1 + n∂22 E(q̌) ŵ(·) − ŵ(i) + 2 ŵ(i) , ŵ(·) − ŵ(i) + n∂12 E(q̌) β, ŵ(·) − ŵ(i) 2 2 D E D E 2 1 + n∂2 ∂1 E(q̌) ŵ(·) − ŵ(i) + 2 ŵ(i) , ŵ(·) − ŵ(i) β, ŵ(·) − ŵ(i) , 2 72

(0) (0) (0) (0) for some q̌ on the line connecting Q12 , Q11 and (Q(i) )12 , (Q(i) )11 . We first show that the second order terms are small. From Lemma E.6, D E2 D E2 1 polylog(n) 2 −1 sup n β, ŵ(·) − ŵ(i) ≤ ∥∂ℓ∥∞ sup β, H(i) xi = OLk . n−1 n i∈JnK i∈JnK We defined H(i) =

X 1 ∂ 2 ℓj (rj,(i) ) + λId . n−1 j∈JnK\i

Similarly, using Proposition A.6 and Lemma E.6, sup

D E polylog(n) 1 −1 xi + O L k ∥∂ℓ∥∞ sup ŵ(i) , H(i) n−1 n i∈JnK polylog(n) = OLk . n

D E ŵ(i) , ŵ(·) − ŵ(i) ≤

i∈JnK

Thus, one concludes (with all correction terms below holding uniformly over all i ∈ JnK) ! n Egen [ŵ(·) ]−Egen [ŵ(i) ] E D 2 (0) (0) = n∂2 E Q12 , Q11 ŵ(·) − ŵ(i) + 2 ŵ(i) , ŵ(·) − ŵ(i) D E polylog(n) (0) (0) + n∂1 E Q12 , Q11 β, ŵ(·) − ŵ(i) + OLk n D E 2 (0) (0) = n∂2 E Q12 , Q11 ŵ(·) − ŵ(i) + 2 ŵ(·) , ŵ(·) − ŵ(i) E D polylog(n) (0) (0) √ + n∂1 E Q12 , Q11 β, ŵ(·) − ŵ(i) + OL2 n D E 2 1 (0) (0) −1 −1 = ∂2 E Q12 , Q11 xi − 2∂ℓi (r̃(·),i,i ) ŵ(i) , H(i) xi ∂ℓi (r̃(·),i,i )2 H\i n D E polylog(n) (0) (0) −1 √ − ∂1 E Q12 , Q11 ∂ℓi (r̃(·),i,i ) β, H(i) xi + OL2 n D E (0) (0) −1 xi + V (2) ∂ℓi (ri )2 = ∂2 E(Q12 , Q11 ) −2∂ℓi (ri ) ŵ\i , H\i D E polylog(n) (0) (0) −1 √ xi + O L 2 − ∂1 E(Q12 , Q11 )∂ℓi (ri ) β, H\i n In the last line, we used Lemma E.5 and Lemma B.4 to approximate the quadratic forms (2) 1/n H −1 x and V (2) successively. We also employed Proposition A.6 to approximate \i i by V the surrogate residuals r̃(·),i,i by the more transparent full residuals r(·),i , then used Lemma 62 to connect with the residuals ri . We now turn to the second term in the decomposition (64) n Egen [ŵ] − Egen [ŵ(·) ] . From a

Taylor expansion, and leveraging the approximation Lemma D.1, n Egen [ŵ] − Egen [ŵ(·) ] D E D E 1 (0) (0) (0) (0) = n∂2 E Q12 , Q11 2 ŵ, ŵ − ŵ(·) + n∂1 E Q12 , Q11 β, ŵ − ŵ(·) + OLk n polylog(n) (0) (0) (1) (0) (0) (1) √ = −2λ∂2 E(Q12 , Q11 )Q11 − λ∂1 E(Q12 , Q11 )Q12 + OL2 , n using the concentration Lemmas D.3 and D.4 in the last line. One is now in a position to establish the weak convergence of the marginals of the influence distribution. Theorem D.6. For any Lipschitz function f and any sequence of indices in ∈ JnK, E f (IFin )  " ! proxV (1) ℓ(·,g2 ) (g1 )−g1 proxV ℓ(·,g2 ) (g1 )−g1 (2) (0) (0) (0) (0) ∂1 E(Q12 , Q11 )g4 +∂2 E(Q12 , Q11 ) 2g3 +  =E f V V (1) V (1)

!# (0) (0) (1) (0) (0) (1) − 2λ∂2 E(Q12 , Q11 )Q11 − λ∂1 E(Q12 , Q11 )Q12

polylog(n)

In the above display, g1 , g2 , g3 , g4 are the components of the Gaussian vector g ∈ R4 with law  " # (0) (1) Q Q . g ∼ N 04 , Q(1) Q(2) Proof. The Theorem follows from Lemma C.4 and Lemma D.5. In the sense of Theorem 2.1, we have thus established the weak convergence of the marginal distribution νIF to φIF ♯N (04 , Q) (where the map φIF (·) is defined in the main text) in the high-dimensional limit n, d ! ∞, namely νIFin ⇀ φIF ♯ N (04 , Q), which finally concludes the proof of Theorem 2.1.

D.3

Proof of Proposition 2.2

A stronger convergence result can be established for the DFBETA metric (6), which measures the change in estimator, in terms of Euclidean norm, when a sample is removed from the dataset. More precisely, for any index i ∈ JnK, we remind the definition 2

DFBETAi = n ŵ − ŵ(i) 74

The following Proposition establishes that the empirical distribution over the training set concentrates to a limiting distribution, shaped by the summary statistics V (2) , Q(0) characterized in Appendix C. Proposition D.7. For any bounded and twice-differentiable test function f with bounded derivatives, the empirical average of DFBETAs processed by f over the train set concentrates as    !2 X polylog(n) 1   proxV (1) ℓ(·,g2 ) (g1 ) − g1 (2)  . f (DFBETAi ) = E f V  + O L2 1 n V (1) n4 i∈JnK Proof. The proof proceeds in two steps. First observe from Lemma D.1 that 2 1 DFBETAi = n ŵ(·) − ŵ(i) + OLk . n We then establish that 2

sup n ŵ(·) − ŵ(i)

− ∂ℓi (r(·),i ) V

i∈JnK

(2)

= OL2

polylog(n) √ n

This follows from Lemma E.5, and the concentration result B.4. Thus, 1 X 1 X polylog(n) 2 (2) √ f DFBETA(·),i = f ∂ℓi (r(·),i ) V + OL2 n n n i∈JnK i∈JnK polylog(n) √ , = E f ∂ℓ1 (r(·),1 )2 V (2) + OL2 n using the concentration Lemma F.1 in Cui and Lu [2026]. The expectation can finally be computed using Proposition A.6 in conjunction with Lemma C.4, proving the claim.

Auxiliary lemmas

For completeness and self-containedness, we reproduce below classical auxiliary lemmas that are repeatedly leverage throughout the main body of the proof. A proof of these standard results can be collected from e.g. El Karoui [2018, 2013], Cui and Lu [2026], Vershynin [2018]. Lemma E.1 (Norm of the estimator). For any k ∈ N, the norm of the estimators ŵ is bounded almost surely as ∥ŵ∥ ≤ M Proof. From the definition of ŵ, 1 X λ 1 X 2 ℓj (rj ) ≤ R̂(0d ) = ℓj (0). ∥ŵ∥ + 2 n n j∈JnK

j∈JnK

Thus 2

∥ŵ∥ ≤

2 ℓ̃ = M 2. λ ∞

2 2 Lemma E.2 (E ∥ŵ∥ is lower bounded). There exists a constant c > 0 such that E ∥ŵ∥ > c, namely the norm of the ERM minimizer is lower-bounded, in expectation. Proof. Let us reason by the absurd, and suppose the existence of a subsequence such that 2 2 E ∥ŵ∥ ! 0, where we remind E ∥ŵ∥ is implicitly a sequence indexed by n. But from the optimality condition, 1 X 1 X 2 ∂ℓ(0, ⟨β, xi ⟩) ⟨β, xi ⟩ = −λ ⟨ŵ, β⟩ − ∂ ℓ(ři , ⟨β, xi ⟩) ⟨β, xi ⟩ ⟨ŵ, xi ⟩ , (65) n n i∈JnK

i∈JnK

for some ři ∈ (0, ⟨ŵ, xi ⟩). But E ⟨ŵ, β⟩ ! 0 on the considered subsequence. Furthermore, 2

1 X 2 ∥X∥ ∂ ℓ(ři , ⟨β, xi ⟩) ⟨β, xi ⟩ ⟨ŵ, xi ⟩ ≤ ∂ 2 ℓ ∥ŵ∥, n ∞ n i∈JnK

which converges to 0 in expectation on the considered subsequence. Thus, taking an expectation in (65) and then the limit on the subsequence, we reach E ∂ℓ(0, g2 )g2 = 0, which contradicts A.1. We thus conclude that there exists a c > 0 that lower-bounds i h Assumption 2 the sequence E ∥ŵ∥ . ⊤

Lemma E.3 (Operator norm of the empirical covariance). Let Σ̂ = X n X be the empirical covariance matrix. Then Σ̂ = OLk polylog(n) . 76

and ∥X∥ √ = OLk polylog(n) . n The same bounds hold for the leave-one-row-out matrix X\i . Lemma E.4 (Norm of the samples). One can control the sample norms as ∥xi ∥ sup √ = OLk (polylog(n)). n i∈JnK Furthermore, sup i∈JnK

X\i √ n

= OLk (polylog(n))

Lemma E.5. (Quadratic forms) Let M\i ∈ Rd×d be a matrix which does not depend on xi , but generically depends on all other samples. Then for any k ∈ [⌈4 log(n)⌉],   D E polylog(n) sup M \i i∈JnK 1   √ sup sup xj , M\i xi = OLk  . n n i∈JnK j̸=i Furthermore [El Karoui, 2018], i E 1 h 1D sup xi , M\i xi − tr M\i = OLk n i∈JnK n

sup M\i i∈JnK

polylog(n) √ n

Lemma E.6 (Sup of one-dimensional projections). Le v\i be vectors that do not depend on xi , but can generically depend on all other samples. Then for any k ∈ [⌈2 log(n)⌉], ! D E p sup v\i , xi = OLk sup v\i polylog(n) . i∈JnK

i∈JnK

Let {{uj,\i }j̸=i }i∈JnK be a family of n(n − 1) vectors such that uj,\i does not depend on xi , but can generically depend on the other samples. Then for any k ∈ [⌈4 log(n)⌉] ! D E p sup sup uj,\i , xi = OLk sup sup uj,\i polylog(n) . i∈JnK j̸=i

i∈JnK j̸=i

Lemma E.7 (X ! ŵ(X) is differentiable). The function f : Rn×d ! Rd with f (X) = ŵ is differentiable. Proof. Let us introduce the function F : Rn×d × Rd ! Rd defined as X F (X, w) = λw + ∂ℓ(⟨w, xi ⟩ , ⟨β, xi ⟩)xi . i∈JnK

For any X, F (X, ŵ(X)) = 0 by definition of the ERM minimizer. Moreover, the Jacobian is ∇w F |X,ŵ(X) = H ≻ 0. Thus, by the implicit function theorem, the function f : Z ! ŵ(Z) is differentiable.

Extensions

Theorem 2.1 and Proposition 2.2 were reported in the main text in the simple setting of a noiseless label generation process (1) and Gaussian data. We discuss in this Appendix how these results may be extended to a larger class of elliptical distribution, and stochastic settings. While we anticipate that the proof should proceed in very close alignment with the one presented in Appendices B and C, we leave a rigorous proof of this extension to future work, and simply conjecture here the end results.

Elliptical design — We now consider the family of elliptical distribution studied in e.g. El Karoui [2018], Adomaityte et al. [2024], which can be defined in superstatistical fashion as an infinite Gaussian mixture of centered clusters of random variance: xi | σi ∼ N (0, σi2 Id ),

(66)

with the scale factors σi being sampled i.i.d from a distribution ρ, which we assumes admits a second moment. We note that the Gaussian case considered in the main text may be retrieved in the special case ρ(·) = δ(· − 1). The class (66) spans a broader class of data distributions, comprising in particular inverse-Gamma distributions. Stochasticity— We also assume there is another source of stochasticity ϵi , sampled i.i.d. from a density µ with all moments being bounded. This stochasticity can intervene for instance as label noise, in which case (1) becomes yi = ϕ(⟨xi , β⟩ , ϵi ). To keep the problem as general as possible, we simply consider the ERM ŵ = arg min w∈Rd

1 X λ 2 ℓ(⟨xi , w⟩ , yi , ϵi ) + ∥w∥ , n 2

(67)

i∈JnK

with an extended loss function ℓ : R3 × R ! R+ taking the noise ϵi as a last argument. We extend in the same fashion the leave-i−out ERM (4). We assume all Assumptions A.1 hold uniformly over the last argument of ℓ. One is now in a position to revisit Theorem 2.1. We form the following conjecture: Conjecture F.1 (Elliptical data, stochastic ERM). Let {xi , yi }i∈JnK be the dataset, and {IFi }i∈JnK be sample influences on the test error (5) for the noisy ERM (67), for elliptical data 66. For any sequence of indices in ∈ JnK, in the asymptotic limit n, d ! ∞ with fixed ratio α := n/d, the marginal distribution of IFin converges weakly to νIFin ⇀ φIF ♯ N (04 , Q) × ρ × µ , 78

in the sense of Theorem 2.1. In the above displays, the map φIF : R6 ! R is defined as φIF (g, σ, ϵ) = proxσ2 V (1) ℓ(·,σg2 ,ϵ) (σg1 ) − σg1 σ 2 V (1) (0)

(0)

Q(1) Q(2)

∂1 E(Q12 ,Q11 )σg4 +∂ 2 E(Q12 ,Q11 ) 2σg3 +

(1)

(0)

prox 2 (1) (σg1 )−σg1 σ V ℓ(·,σg2 ,ϵ) V (2) V (1)

(1)

− 2λ∂2 E(Q12 , Q11 )Q11 − λ∂1 E(Q12 , Q11 )Q12 The covariance Q ∈ R4 is the matrix " Q=

Q(0) Q(1)

The matrices Q(k) and scalars V (k) for k = 0, 1, 2 are related through I −1 1 n Q(k) = Ω(z)dz + O polylog(n)e− /2 , k 2πi Γ z I 1 −1 −n/2 V(z)dz + O polylog(n)e V (k) = 2πi Γ z k The contour Γ is any contour in {z ∈ C : Re{z} > 0} with finite perimeter enclosing the p 2 interval J = λ, λ + ∂ 2 ℓ ∞ 2 + 1/α at a distance dist (Γ, J) ≥ λ/2, while also satisfying dist (Γ, 0) ≥ λ/2. The resolvent Ω(z) furthermore converges pointwise for any z ∈ Γ with Im{z} ̸= 0 as    " # h i ′′ σg1 ℓ (r, σg2 , ϵ)   Ω(z) (λ − z)Q(0) + E  r σg2  1 + σ 2 V(z)ℓ′′ (r, σg2 , ϵ) σg2  = Q(0) + χ(z)E 

2 ′′

′

#

σ ℓ (r, σg2 , ϵ)ℓ (r, σg2 , ϵ) r σg2  +O 1 + σ 2 V(z)ℓ′′ (r, σg2 , ϵ) 0 0

polylog(n) 1

In the above display, V (1)

χ(z) =

(λ − z) + E

ℓ′′ (r,σg2 ,ϵ)σ 2 2 V (1) ℓ′′ (r,σg ,ϵ) 1+σ ( )(1+σ2 V(z)ℓ′′ (r,σg2 ,ϵ)) 2

polylog(n)

and the Stieltjes transform V(z) is the solution of " # 1 σ 2 ℓ′′ (r, σg2 , ϵ)V(z) polylog(n) − (λ − z)V(z) − E =O 1 α 1 + σ 2 V(z)ℓ′′ (r, σg2 , ϵ) n4 Above, we used the shorthand r = proxV (1) ℓ(·,g2 ) (g1 ). The expectations in the above displays are understood to bear over σ ∼ ρ, ϵ ∼ µ, g ∼ N (0, Q).

Details on numerical experiments

In this Appendix, we provide further details on the real data experiments reported in Fig. 5. The code is provided on this online repository.

MNIST [LeCun et al., 1998] 3000 50000 500 9500 10 1000

Chest X-rays [Kermany et al., 2018] 1000 3000 500 1340 50 2000

Table 1: Dataset sizes and training hyparameters used in the experiments reported in Fig. 5. We consider two learning tasks on real datasets: • Even/odd classification of MNIST [LeCun et al., 1998] digits. Images in dimension d = 784 representing handwritten even (resp. odd) digits were labeled +1 (resp −1). • Pneumonia diagnosis from chest X-rays [Kermany et al., 2018]. X-ray scan images (cropped to dimension d = 1600) corresponding to positive (resp. negative) patients receive label +1 (resp. −1). Each dataset was partitioned into four subsets DNN , Dβ , Dtrain , Dtest . Details on their respective cardinals are summarized in Table 1. The following procedure was then carried out: 1. A 3-layer neural network with ReLu activation and batch normalization is trained using the Adam optimizer [Kingma and Ba, 2014] with default Pytorch [Paszke et al., 2017] parameters, for a number of epochs specified in Table 1, on the dataset DNN . The binary cross-entropy loss is employed. The width p of the network was chosen for all hidden layer as p = 1000 for the MNIST dataset and p = 2000 for the chest X-ray dataset. The resulting neural network feature map NN : Rd ! Rp (with the readout removed) will be used in subsequent steps as a feature extractor to process the datapoints. 2. A logistic regression with regularization λ = 0.01 is then used to re-train the readout only, on the processed dataset {(NN(x), y)}(x,y)∈Dβ . The cardinal of Dβ is chosen large on purpose, so that the resulting regression weights β are close to the best separator of the data in the feature space induced by NN(·). β will henceforth be thought of as the "ground truth" vector, in analogy to (1). 3. Similarly, the estimator ŵ learned from a smaller dataset Dtrain is obtained using logistic regression with regularization λ = 0.1. 4. Given the running estimator ŵ and (an approximation of) the ground-truth β, we now ask the question : which sample has the largest influence on the test accuracy (as measured 80

using the test set Dtest ) when added to Dtrain ? We allow ourselves to synthesize (query) any sample z ∈ span(ŵ, β), and assume oracle access to its label, taken to be y = sign(⟨β, z⟩). The influence IF(z) is computed as the difference in the test errors achieved by logistic regression on Dtrain ∪ {x, y}, and that trained only on Dtrain .

Record · ID 361472 · SHA-256 a6b35618ba9c3188
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.