A Precise High-Dimensional Asymptotic Theory for Boosting and Minimum-$\ell_1$-Norm Interpolated Classifiers

Introduction

Modern machine learning methods are regularly used for classification tasks. Typically, these algorithms are complex, and often produce solutions with zero training error, even for random labels. Prominent examples include ensemble learning, neural networks, and kernel machines. However, among the many solutions that interpolate the training data, not all exhibit superior generalization. Empirically, it has been commonly observed that practical algorithms—running even on large overparametrized models—favor minimal ways of interpolating the training data, which has been conjectured to be crucial for good generalization. Different problem formulations and optimization algorithms favor distinct notions of minimalism, typically measured by specific norms of the classifier. This paper focuses on the celebrated boosting/AdaBoost algorithm in this minimum-norm interpolation regime, where we conduct a precise analysis of its statistical and computational properties under specific data-generating mechanisms.

Ensemble learning algorithms, recognized as powerful toolkits at the disposal of a data scientist, have found widespread usage across domains. Boosting is arguably one of the most powerful ensemble learning algorithms that combines weak learners using intelligent schemes and exhibits remarkable generalization performance. The groundbreaking AdaBoost paper, Freund and Schapire , is widely regarded as the milestone in the boosting literature, which can be traced back even earlier . AdaBoost is an iterative algorithm that updates the weights on the training examples adaptively based on the errors incurred at prior iterations. AdaBoost demonstrated preferable generalization capabilities over existing algorithms such as bagging , which led to decades of research activities devoted to a better understanding of this algorithm and its variants.

The seminal papers observed that AdaBoost achieves zero error on the training data within a few iterations, whereas the generalization error continues to decrease well beyond this interpolation timepoint. Recently, similar phenomena and puzzles resurfaced in the context of neural networks , and motivated the study of interpolation and implicit regularization . This peculiar and seemingly counter-intuitive phenomenon naturally piqued the interest of a broad community of statisticians and machine learners. Several explanations emerged over the past two decades.

Consistency and early stopping. In conjunction with the generalization error, statisticians and learning theorists deeply care about the consistency of AdaBoost, and in particular, about the precise relationship between the test error and the optimal Bayes error. The problem of consistency was posed by Breiman , who studied convergence properties of the algorithm in the population case. The seminal papers Jiang , Lugosi and Vayatis , Zhang , Koltchinskii and Besnozova considered different function classes and variants of boosting, and furthered this direction of research. established that AdaBoost is process consistent, in the sense that, there exists a stopping time at which the prediction error approximates the optimal Bayes error in the limit of large samples. A parallel understanding emerged from empirical studies conducted in —AdaBoost may overfit, particularly in complex model classes and high noise settings, when left to run for an arbitrary large number of steps. On the one hand, these naturally inspired subsequent work on appropriate regularization strategies for “early stopping" as in Zhang and Yu , Bartlett and Traskin . On the other hand, as the model classes become complex and overparametrized, the test error of boosting algorithms may deviate from the optimal Bayes error. Despite an extensive bulk of work, a precise characterization of the test error and its relation to the Bayes error for the overparametrized case is still missing in the current literature.

Furthermore, boosting has empirically demonstrated exceptional performance with many weak-learners. Therefore, to study properties of boosting on separable data, it is both theoretically necessary and empirically natural to analyze the algorithm in a high-dimensional (overparametrized) setting. This paper studies these crucial questions surrounding boosting, in high dimensions, focusing on the case of binary classifications. Our theoretical contributions apply under specific data generating schemes detailed in Sections 2 and 3.5. Throughout the paper, boosting/Boosting Algorithms loosely refers to the version of AdaBoost described in Section 2.

The aforementioned result holds under certain assumptions on the random feature matrix $F$ and the non-linearity $\sigma(\cdot)$. (see Section 3.5.2 for details). But note that, conditional on $F$, $b_{i}$ is Gaussian whereas $a_{i}$ is not. This universality result suggests that the margin value is asymptotically insensitive, at least under some settings, to nuanced properties of the feature distribution. Thus, results that apply for the Gaussian case might be relevant for certain non-Gaussian feature distributions. We further validate this through empirical observations in Section 3.5.2. On the technical front, our universality result starts with a leave-one-out argument from . However, considered loss functions satisfying certain smoothness and strong-convexity assumptions, which are grossly violated in our setting. This leads to several technical challenges that we handle by establishing new analytic results (Section 3.5.2 and Appendix B.2).

Organization. The rest of the paper is organized as follows. Section 2 introduces some crucial preliminaries that are heavily used through the rest of the paper. Section 3 presents our main results, whereas a proof sketch and description of our technical contributions is presented in Section 5 (details are deferred to the Appendix). Section 4 discusses relevant literature that has been omitted from this introduction. Finally, Section 6 concludes with a discussion on possible directions for future work.

Formal Setup and Preliminaries

Let $\lambda_{i}(n)$ denote the eigenvalues of $\Lambda(n)$. Assume that there exists a positive constant $0<c<1$ such that $c\leq\lambda_{i}(n)\leq 1/c,~{}\forall 1\leq i\leq p(n)$ and for all $n$ and $p$.

Note that Assumption 1 and (2.3) together imply that $\sum_{j=1}^{p}\theta_{\star}(n)_{j}^{2}=O(1)$. If all the entries of $\theta_{\star}$ are of the same order, this yields $\theta_{\star,i}=O(1/\sqrt{p})$. This also justifies why we include $\sqrt{p}$ in the numerator of $\bar{w}_{i}$. The convergence in $W_{2}$ equivalently means weak convergence and convergence of the second moments (see for instance, ). In particular, this implies that $\int w^{2}\mu(d\lambda,dw)=1$.

for all $n$ and $p$, for some constants $C^{\prime},C^{\prime\prime}>0$.

Linear separability. We assume that our sequence of problem instances is (asymptotically) linearly separable in the following sense

Initialize: data weight $\eta_{0}=1/n\cdot\mathbf{1}_{n}\in\Delta_{n}$, parameter $\theta_{0}=0$.

Feature Selection: $v_{t+1}:=\operatornamewithlimits{arg\,max}_{v\in\{e_{j}\}_{j\in[p]}}~{}|\eta_{t}^{\top}Zv|\enspace;$

Adaptive Stepsize $\alpha_{t}$: $\alpha_{t}:=\eta_{t}^{\top}Zv_{t+1}\enspace;$

Coordinate Update: $\theta_{t+1}=\theta_{t}+\alpha_{t}\cdot v_{t+1}\enspace;$

Weight Update: $\eta_{t+1}[i]\propto\eta_{t}[i]\exp(-\alpha_{t}y_{i}x_{i}^{\top}v_{t+1}),$ normalized such that $\eta_{t+1}\in\Delta_{n}$.

Terminate after $T$ steps, and output the vector $\theta_{T}$.

Main Results

Above, $c_{1}\equiv c_{1}(\psi,\rho,\mu,\kappa),c_{2}\equiv c_{2}(\psi,\rho,\mu,\kappa),s\equiv s(\psi,\rho,\mu,\kappa)$ form the unique solution to the non-linear system of equations introduced in (1) (Proposition 3.1 establishes uniqueness of the solution). A detailed description of this system is deferred until Section 3.2; the key point is that, the system takes as input the quantities $\psi,\rho,\mu,\kappa$, and solves three equations in three unknowns, producing a triplet $c_{1},c_{2},s$. Throughout, $\mu$ and $\rho$ will be defined via (2.4) and (2.3) respectively, and if these are fixed, $c_{1},c_{2},s$ then simply form functions of $\psi,\kappa$. Note that we drop the dependence on $f$ for simplicity of the exposition; however, it is important to emphasize that $f$ enters the definition of $F_{\kappa}(\cdot,\cdot)$, which in turn affects the equation system.

Some comments regarding the limit $\kappa_{\star}(\psi,\rho,\mu)$ are in order. First, the limit is well-defined, owing to properties of $T(\psi,\kappa)$: Section 3.2 presents an argument towards this claim. Next, (3.3) clearly demonstrates the dependence of $\kappa_{\star}(\psi,\rho,\mu)$ on the overparametrization ratio $\psi$. Its dependence on the signal strength $\rho$ and the distribution $\mu$ is encoded through $F_{\kappa}(\cdot,\cdot)$, and the parameters $c_{1}\equiv c_{1}(\psi,\rho,\mu,\kappa),c_{2}\equiv c_{2}(\psi,\rho,\mu,\kappa),s\equiv s(\psi,\rho,\mu,\kappa)$, which appear in the definition of $T(\psi,\kappa)$ (3.1).

where $c_{i}^{\star}:=c_{i}(\psi,\rho,\mu,\kappa_{\star}(\psi,\rho,\mu)),~{}i=1,2.$ Together with a third parameter $s^{\star}\equiv$ $s(\psi,\rho,\mu,\kappa_{\star}(\psi,\rho,\mu))$, $c_{1}^{\star},c_{2}^{\star},s^{\star}$ form the unique solution to the system of equations (1), when the inputs to the system are $\psi,\rho,\mu$ and $\kappa_{\star}(\psi,\rho,\mu)$, (3.2). Furthermore, $(Y,Z_{1},Z_{2})$ follows the joint distribution specified in (2); note that this depends on the problem parameters through $\rho$.

Finally, recall the Bayes error formula, and contrast it with the test error formula (3.4) proved in Theorem 3.2,

The curious reader may wonder about the accuracy of our asymptotic theory for design matrices excluded from our assumptions. We further investigate this sensitivity along few directions—violation of independence between the features, violation of Gaussianity of the covariates used for boosting, and misspecification in the model due to missing a fraction of the relevant variables. We defer the readers to Section 3.5 for more details on these.

2 The non-linear system of equations

and the expectation is over $(\Lambda,W,G)\sim\mu\otimes\mathcal{N}(0,1)=:\mathcal{Q}$ with $\mu$ and $F_{\kappa}(\cdot,\cdot)$ defined as in (2.4), and (2) respectively.

Note that $\Lambda$ denotes both the random variable in (1) and the covariance matrix in Assumption 1. Such overload of notations will prove useful in the technical derivations.

Uniqueness. Theorems 3.1-3.2 expressed our limiting results in terms of the solution to the system (1). It is, therefore, crucial to establish that the solution will indeed be unique. To this end, introduce the constants $\zeta$ and $\omega$ as follows:

where $\psi^{\star}(\rho,f)$ is given by (2.8).

3 Boosting in high dimensions

Let $S_{0}(p)$ denote the number of features selected the first time $t$ when the Boosting Algorithm achieves zero training error (with an initialization of $\hat{\theta}^{0}=0$), in the sense that,

Under the assumptions of Theorem 3.3, $S_{0}(p)$, scaled appropriately, is asymptotically bounded by

4 A new class of boosting algorithms

Denote $q_{\star}\geq 1$ to be the conjugate index of $q$, with $1/q_{\star}+1/q=1$, and consider the following algorithm.

Initialize: $\eta_{0}=1/n\cdot\mathbf{1}_{n}\in\Delta_{n}$, and parameter $\theta_{0}=0$.

Adaptive Stepsize: $\alpha_{t}(\beta)=\beta\cdot\|Z^{\top}\eta_{t}\|_{q_{\star}}\enspace,$ with $0<\beta<1$ being a shrinkage factor.

Parameter Update: $\theta_{t+1}=\theta_{t}+\alpha_{t}\cdot v_{t+1}\enspace;$

Weight Update: $\eta_{t+1}[i]\propto\eta_{t}[i]\exp(-\alpha_{t}y_{i}x_{i}^{\top}v_{t+1}),$ normalized such that $\eta_{t+1}\in\Delta_{n}$.

Terminate after $T$ steps, and output the vector $\theta_{T}$.

where $\mathcal{Q}_{\infty}=\mu\times\mathcal{N}(0,1)$. It is not hard to see that this system reduces to (1) for $q=1$.

Note that Corollary 3.3 assumes the data is asymptotically linearly separable, that is, $\psi>\psi^{\star}(\rho,f)$. This separability threshold is an inherent property of the sequence of problem instances, and does not depend on the geometry under which the max-margin is considered in (3.28).

5 Robustness to assumptions

As a first step towards understanding dependent covariates, consider a simple Gaussian mixture model:

Similar to Assumption 2, let $p(n)/n=\psi$ and denote

We can further this characterization to analogous settings where the marginal covariance between features contains a finite rank perturbation of a diagonal matrix. To provide a precise description, consider an extension of (3.29)-(3.30), where (3.29) remains the same but (3.30) changes to

5.2 Beyond Gaussian covariates

To formalize this result, we consider a sequence of problem instances $\{y(n),X(n),\theta^{\star}(n)\}_{n\geq 1}$ satisfying the conditions in Section 2, and in addition consider feature matrices $A(n),B(n)$ with the $i$-th row of $A(n)$ (resp. $B(n)$) given by $a_{i}$ (resp. $b_{i}$) described above. The sequence of random feature matrices $F(n)$ in the definition of $A(n)$ are taken to be of the form $F(n)=[f_{1},\ldots,f_{d(n)}]$, where $f_{i}\sim\mathcal{N}(0,\boldsymbol{I}_{p}/p)$, and both $p(n),d(n)$ scale linearly with $n$. In the sequel, we suppress the dependence on $n$, whenever clear from context.

where $A,B$ are the feature matrices defined under the fitting procedures (i) and (ii) respectively. To see this, denote $\lambda_{A}$ to be the solution to the optimization problem

To prove (3.38), we start with a leave-one-out argument adapted from , which in turn builds upon . In , the authors prove that the training and generalization errors are asymptotically equivalent in a random features model and a corresponding linearized model, where the covariates have matching moments and are Gaussian conditional on the random features. However, defined the training error to be based on the objective function of a penalized empirical risk minimization problem, where the loss admits derivatives upto the third order and the regularizer is strongly convex. In our setting, neither of these properties hold, and this leads to several technical challenges. To handle these, we use a specific smoothing argument and develop several new analytic results (Appendix B.2).

5.3 Model Misspecification

Consider that both components of $\theta_{\star}$, (3.40), contribute a non-trivial signal strength, in the sense that

Related Literature

This section discusses prior literature that is relevant to our problem, but were omitted from Section 1.

Proof Sketch for Theorems 3.1 and 3.2

Step 1: A basic reduction. To begin with, define

Now, defining $z_{i}:=\Lambda^{-1/2}x_{i}~{}\forall i\in[n]$, where $\Lambda$ is the covariance matrix, we may express

Step 2: Reduction to Gordon’s problem. Due to the min-max form of (5.1), one can use Gordon’s Gaussian comparison inequality to further simplify the problem. To this end, introduce the following “de-coupled” optimization problem

Marginalizing over $y$ and $z$, this suggests that it suffices to study (5.5).

Step 3: The key step—large $n,p$ limit, new uniform deviation result.

Recall the function $F_{\kappa}(\cdot,\cdot)$ from (2), and define the empirical version

Note that $\hat{\xi}^{(n,p)}_{\psi,\kappa}(\lambda,w,g)$ is a random quantity, here we denote $\lambda,w,g$ as arguments to make explicit the dependence.

We seek to study (5.1) in the large sample and feature limits $n,p\rightarrow\infty$ with $p/n\rightarrow\psi$. On taking limits naively, one can reach the following infinite-dimensional convex problem,

We provide an outline of the proof below, deferring the details to Section A.2.

For $i=1,2$, with probability at least $1-n^{-2}$,

where $C$ is a constant that does not depend on $n$.

Step 4: Fixed point equations and final step.

By standard analysis arguments (see Appendix A.4), the KKT conditions for the optimization problem (5.1) can be expressed as

From properties of the proximal mapping operator, the KKT conditions suggest that the solution must satisfy (see Appendix A.4 for a derivation of this claim, and the proof of uniqueness of the solution)

2 Proofs of Theorems 3.3 and Corollary 3.1

Consider the Boosting Algorithm stated in Section 2. Assume that $|X_{ij}|\leq M$ for $i\in[n],j\in[p]$. Consider the learning rate $\alpha_{t}(\beta)=\beta\cdot\eta_{t}^{\top}Zv_{t+1}$, with $\beta=1/M^{2}$. When

the Boosting Algorithm iterates $\theta_{T}$ will satisfy $\sum_{i\in[n]}1_{x_{i}^{\top}\theta_{T}\leq 0}\leq\epsilon.$

Discussion

References

Appendix A Main Proofs

For the convenience of the readers, we state the convex Gaussian min-max theorem below [101, Theorem 4] (see also )

A.2 Large n,p𝑛𝑝n,p Limit: New Uniform Convergence Results

where $F_{\kappa}(\cdot,\cdot)$ is given by (2).

Then from Proposition 3.1, we immediately obtain the following.

then, $(c_{1},c_{2},s)$ must be $\epsilon$-close to $(c_{1}^{\star},c_{2}^{\star},s^{\star})$,

We next turn to define different empirical versions of (A.2), which will be used later. To this end, recall that (5.8)

Observe $V_{i}^{(\infty,p)}(\cdot,\cdot,\cdot)$ and $V_{i}^{(n,p)}(\cdot,\cdot,\cdot)$ only differs in the following sense: $\widehat{F}_{\kappa}$ is used in place of $F_{\kappa}$.

With the above preparation, we are now in position to establish (5.11). Recall the finite $n,p$ optimization problem

and the corresponding infinite-dimensional optimization problem given by

Under the assumptions of Theorem 3.1, almost surely,

where $(\Lambda,W,G)\sim\mathcal{Q}_{\infty}$.

To begin with, recall the KKT conditions (A.4) and its consequences (A.4)-(A.88), together these establish the following fixed point equations

We postpone the derivation of the KKT conditions later so as to not interrupt the flow.

Note that the objective function in (A.8) is not convex in $\theta$ (due to $\widehat{F}$). Nonetheless, for any $\theta$ that minimizes the objective, the KKT conditions still hold as first-order necessary conditions. Thus, by arguments similar to that in the proof of Proposition 3.1, with $\theta/\sqrt{p},\mathcal{Q}_{p},\widehat{F}_{k}$ replacing $h,\mathcal{Q}_{\infty},F_{k}$, we obtain the finite sample versions

We claim that almost surely, the following uniform convergence result holds, in the region $c_{1}\in[0,M],c_{2}>0,s>0$

In the following, we will prove the above claims.

The first claim in (A.2). By the triangle inequality,

We start with providing a uniform deviation bound in the region $c_{1}\in[0,M],c_{2}>0,s>0$ for

Note here that $c_{2},s$ lie in unbounded regions—such a scenario does not arise in the study of the max-$L_{2}$-margin, for instance. Define

and similarly $C^{\uparrow},C^{\downarrow}$ by replacing $\widehat{F}_{\kappa}$ by $F_{\kappa}$. By the contraction property of the soft-thresholding operator,

As in Lemma 5.1, divide the range of $c_{2}$ into the regions $(0,M]$ and $(M,\infty)$ respectively. For $c_{2}\in(0,M]$, multiply both the denominator and nominator by $c_{2}^{2}$ to obtain

where $L^{1/2}$ is a uniform upper bound on $\|\Lambda^{-1/2}G\|_{L_{2}(\mathcal{Q}_{p})}$, $\|\Lambda^{1/2}W\|_{L_{2}(\mathcal{Q}_{p})}$, $\|W\|_{L_{2}(\mathcal{Q}_{p})}$ for all $p$. By Lemma 5.1, we know that w.p. at least $1-n^{-2}$ for all $|c_{1}|\leq M,0<c_{2}\leq M,s>0$

which ensures that w.p. at least $1-n^{-2}$ for all $|c_{1}|\leq M,0<c_{2}\leq M,s>0$,

and the upper bound is uniform for all $p$.

For the second region, $c_{2}\in(M,\infty)$, we use the following technique as in Lemma 5.1

By Lemma 5.1, we know that w.p. at least $1-n^{-2}$, uniformly for the region $|c_{1}|\leq M,c_{2}>M,s>0$,

Putting things together, we have established that w.p. at least $1-2n^{-2}$,

We remark that the above uniform deviation bound over unbounded region is proved due to a key self-normalization property of the function $\partial_{i}F_{\kappa}(c_{1},c_{2}),i=1,2$, as derived in Lemma 5.1.

We now proceed to bound the second term in (A.13)

Since $\mathcal{Q}_{p}\stackrel{{\scriptstyle W_{2}}}{{\implies}}\mathcal{Q}_{\infty}$, by Theorem 2.7 and Proposition 2.4 in , we know that (1) for any function $g$ that grows at most quadratically,

We first verify that $g_{c_{1},c_{2},s}:=(c_{2}\vee 1)^{-1}f_{c_{1},c_{2},s}$ satisfies the quadratic growth condition uniformly for all $|c_{1}|\leq M,c_{2}>0,s>0$. Observe that

Further, for all $|c_{1}|\leq M,0\leq c_{2}\leq M,s\geq 0$, uniformly for $\Lambda,W,G$ (recall that $\Lambda,W$ has bounded domain)

since $|c_{2}C^{\uparrow}|$ is bounded above and $|c_{2}C^{\downarrow}|=\psi^{-1/2}|\partial_{2}F_{\kappa}|$ is bounded below. For the other part where $|c_{1}|\leq M,c_{2}>M,s\geq 0$, since $|c_{1}c_{2}^{-1}|$ is bounded and, thus, $|C^{\uparrow}|$ is bounded, hence

Therefore uniformly over $|c_{1}|\leq M,c_{2}>0,s>0$, with a universal constant $K$

Note that $g_{c_{1},c_{2},s}(\Lambda,W,G)$ depends on $c_{1},c_{2},s$. We now prove the convergence of $\mathop{\mathbf{E}}_{\mathcal{Q}_{p}}[g_{c_{1},c_{2},s}]$ to $\mathop{\mathbf{E}}_{\mathcal{Q}_{\infty}}[g_{c_{1},c_{2},s}]$ uniformly over $c_{1},c_{2},s$. Recall that $\mathcal{Q}_{p}$ is $2$-uniformly integrable, hence for any fixed $\epsilon>0$, there exists $R_{\epsilon}$ such that (A.29) holds true. Therefore

where the last step uses the quadratic growth condition of $g_{c_{1},c_{2},s}$ in (A.32) uniformly over $|c_{1}|\leq M,c_{2}>0,s>0$, and 2-uniform integrability (A.29), as

Inside a bounded region $B_{R_{\epsilon}}$, it is easy to see that $g_{c_{1},c_{2},s}(\Lambda,W,G)$ is Lipschitz in $(\Lambda,W,G)$ with a uniform Lipschitz constant $L_{R_{\epsilon}}$ regardless of the choice of $|c_{1}|\leq M,c_{2}>0,s>0$. Therefore we have

By the fact that $\epsilon$ can take an arbitrarily small value, we have proved

We combine with the analysis of (A.15) and by Borel-Cantelli Lemma obtain that, almost surely

Thus we have established that uniformly over $|c_{1}|\leq M,c_{2}>0,s>0$,

The second claim in (A.2). This step follows similarly to the aforementioned analysis, here we only highlight the differences. Once again,

Now it suffices to provide a uniform deviation bound for $c_{1}\in[0,M],c_{2}>0,s>0$

Again we divide the range of $c_{2}$ into two parts, $(0,M]$ and $(M,\infty)$. For the first part, uniformly over $(c_{1},c_{2})\in[-M,M]\times(0,M]$, Lemma 5.1 shows that

For the second part, uniformly over $(c_{1},c_{2})\in[-M,M]\times(M,\infty)$, Lemma 5.1 shows that

In either case, one can show that w.p. at least $1-n^{-2}$,

one can verify that uniformly over $|c_{1}|\leq M,c_{2}>0,s>0$ and $\Lambda,W,G$

The uniform convergence can be established repeating the argument in (A.2). Therefore,

The third claim in (A.2). The proof of the following uniform convergence for the term involving $V_{3}$ follows the exact same steps as for $V_{1}$ and, is therefore, omitted.

We next establish that for any solution $\hat{c}_{1},\hat{c}_{2},\hat{s}$ that solves the empirical fixed point equation,

where $(c_{1}^{\star},c_{2}^{\star},s^{\star})$ is the unique solution for the fixed point equation

This follows by standard arguments on combining (A.2) and Lemma A.1. For any $\epsilon>0$, there exist $\delta>0$ small enough, that satisfies Eqn. A.1. By the uniform convergence (A.2), for that particular $\delta$, there exist $n,p$ large enough, such that for $(\hat{c}_{1},\hat{c}_{2},\hat{s})$

Recall that $V_{1}^{(n,p)}(\hat{c}_{1},\hat{c}_{2},\hat{s})=0$, which implies

therefore we know that for all $n,p$ large enough,

Note this holds for arbitrary $\epsilon$. Therefore, we have proved Eqn. (A.53).

We remark that this convergence result implies the following: any optimizer $\hat{\theta}$ of the finite $n,p$ optimization problem $\hat{\xi}^{(n,p)}_{\psi,\kappa}(\lambda,w,g)$ must satisfy the necessary condition

for some absolute constant $R>0$, for sufficiently large $n$ and $p$. This established property will be useful in the next paragraph.

Given Eqn. (A.53), one can verify by the KKT condition that the optimal value of finite $n,p$ optimization problem $\hat{\xi}^{(n,p)}_{\psi,\kappa}(\lambda,w,g)$ can be expressed in the form

where $\hat{c}_{1},\hat{c}_{2},\hat{s}$ are solutions to the empirical fixed point equations $V_{i}^{(n,p)}(\hat{c}_{1},\hat{c}_{2},\hat{s})=0,i=1,2,3$ (that may not be unique for fixed $n,p$). Now recall that we have proved for sufficiently large $n,p$, $\hat{c}_{1},\hat{c}_{2}$ lie in a neighborhood of fixed radius $R$ (does not grow with $n,p$) around $c_{1}^{\star},c_{2}^{\star}$, say denoted by $\mathcal{B}(c_{1}^{\star},R),\mathcal{B}(c_{2}^{\star},R)$. It is easy to show that $\widehat{F}_{\kappa}$ satisfies the uniform convergence bound

By Lemma 5.1, $\partial_{1}\widehat{F}_{\kappa}$ and $\partial_{2}\widehat{F}_{\kappa}$ all satisfy uniform convergence over $|c_{1}|\leq M,c_{2}>0$. Therefore

Below, we introduce a key lemma used in the uniform convergence proof in Proposition A.1. This lemma appears to be new to the literature.

For $i=1,2$, we have with probability at least $1-n^{-2}$,

where $C$ is a constant that does not depend on $n$.

The proof uses a key self-normalization property of the partial derivatives of $F_{\kappa}$, that ensure good concentration behavior even when $c_{2}$ is large. We remark that this structural property makes our uniform convergence result over unbounded region possible in Proposition A.1. Note that

where $\sigma(t):=\max(t,0)$ satisfies the positive homogeneity $\sigma(|c|t)=|c|\sigma(t)$.

We prove the claim by dividing $c_{2}$ into two regions, $(0,M]$ and $(M,\infty)$.

In the first region, where $(c_{1},c_{2})\in[-M,M]\times(0,M]$, it is easy to verify that $R_{1}(c_{1},c_{2}):=YZ_{1}\sigma(\kappa-c_{1}YZ_{1}-c_{2}Z_{2})$, $R_{2}(c_{1},c_{2}):=Z_{2}\sigma(\kappa-c_{1}YZ_{1}-c_{2}Z_{2})$ and $R_{0}(c_{1},c_{2}):=\sigma^{2}(\kappa-c_{1}YZ_{1}-c_{2}Z_{2})$ are all sub-exponential random variables with sub-exponential parameters being at most a constant (depends on $M$), since $\sigma(\kappa-c_{1}YZ_{1}-c_{2}Z_{2}),YZ_{1},Z_{2}$ are all sub-Gaussian random variables. Denote the $\epsilon$-covering net as $\mathcal{N}_{\epsilon}([-M,M]\times(0,M])$, we know that on this bounded region, with probability at least $1-n^{-2}$,

The above bound is derived with $\epsilon\asymp 1/\sqrt{n}$. Recall that $\mathop{\mathbf{E}}[R_{0}(c_{1},c_{2})]=F_{\kappa}(c_{1},c_{2})>0$. Then for $n$ large enough, the claim follows since

w.p. at least $1-n^{-2}$ uniformly for all $|c_{1}|\leq M,0<c_{2}\leq M$.

For the second region (unbounded), where $(c_{1},c_{2})\in[-M,M]\times(M,\infty)$, we use the following self-normalization property of $\partial_{i}\widehat{F}_{\kappa}(c_{1},c_{2})$

Now the regions for the parameters of interest are bounded since

The proof can be completed following standard algebra based on the expression (A.67) and (A.68), since

A.3 Proof Outline for Generalization Error

The proof follows by an adaptation of [76, Section E], on using Theorem 3.1 and Proposition A.1. Here we provide an outline of the argument. Note that since the model (2.1) involves Gaussian covariates, by rotation, we can equivalently express it as a model where all but the first coordinate of the true signal is zero. Thus,

where $c_{1}^{\star}$ is defined following (3.4).

Further, define $\xi_{\psi,\kappa}^{(n,p)}(c)=\min_{\|\theta\|_{1}\leq\sqrt{p},\frac{\langle\theta,\theta_{\star}\rangle_{\Lambda}}{\|\theta\|_{\Lambda}\|\theta_{\star}\|_{\Lambda}}=c}\frac{1}{\sqrt{p}}\|(\kappa\mathbf{1}-(y\odot X)\theta)_{+}\|_{2}$ and note that

To show (A.73), from (A.75)-(A.76), the final step then involves establishing that for any $\epsilon>0$

This can be established by analytic arguments similar to [76, Section E], on using the limiting characterizations of $\hat{\kappa}_{n}$ and $\xi_{\psi,\hat{\kappa}_{n}}^{(n,p)}$ from Theorem 3.1 and Proposition A.1.

A.4 Uniqueness Results

To analyze the equation system (1), we will, in fact, begin by examining the objective function in (A.2) as a function of $h$, that is, define

We claim that any solution of (A.4) and the associated dual variable $s$ satisfy $s>0$ and $\|\Pi_{W^{\perp}}(\Lambda^{1/2}h)\|>0$. The former follows directly from [76, Section B.3.3], but we describe the detail here for the sake of completion. Recall that $(\Lambda,W)\sim\mu$ defined in (2.4). From properties of $\mu$ it follows that $\Lambda>0,\|W\|=1$. Suppose if possible that $s=0$, then (A.4) implies that

Taking inner products with $W$ on both sides, we obtain $\psi^{-1/2}\left[\partial_{1}F_{\kappa}(c_{1},c_{2})\right]=0.$ Using this relation back in (A.80), we obtain that

We next proceed to show that for any solution $h$, $c_{2}=\|\Pi_{W^{\perp}}(\Lambda^{1/2}h)\|>0$. Suppose by contradiction that $c_{2}=0$. By decomposing $h$ in the direction of $W$ and $W^{\perp}$, observe that in this case

where recall the definition of $c_{1}$ from (A.79). Since we established $s>0$, for any solution, $\|h\|_{L_{1}(\mathcal{Q}_{\infty})}=1$. This yields that in this case,

Now divide the problem into two cases: Case (i): $c_{1}>0$ and Case (ii): $c_{1}<0$. Here we only show the argument for Case (i), since the other case follows similarly. From the first equation in (A.4), we have

Since $s>0$, this yields that $\partial_{1}F_{\kappa}(\zeta,0)<0$, which implies that by definition, $\psi$ should be above the threshold $\psi_{+}(\kappa)$ that satisfies

Now plugging (A.4) back in (A.83) and using (A.81), we obtain that

However, this contradicts the range of $\psi$ determined by (A.85). The case of $c_{1}<0$ can be similarly handled on recalling the fact that, by definition, $\psi>\psi_{-}(\kappa)$ introduced in (3.14). Thus, we conclude that $c_{2}>0$.

Now that we have established that $c_{2}$ and $s$ must be strictly positive when $(c_{1},c_{2},s)$ solves our equation system, we can proceed to explicitly identify the formula for the solution $h^{\star}$ to (A.4). The KKT conditions yield that

From [76, Section B.3], $\partial_{2}F_{\kappa}(\zeta,0)>0$, so we may rewrite the above as follows:

Now the above implies that the solution $h^{\star}$ is given by

yields the fixed point equations (1). Since the solution $h^{\star}$ is unique, the values $c_{1}:=\langle\Lambda^{1/2}h^{\star},W\rangle_{L_{2}(\mathcal{Q}_{\infty})}\,\,$, $c_{2}:=\|\Pi_{W^{\perp}}(\Lambda^{1/2}h^{\star})\|_{L_{2}(\mathcal{Q}_{\infty})}$ and the value $s$ satisfying (A.4) are also unique and, furthermore, $c_{2}$ and $s$ are strictly positive. ∎

Under the assumptions of Proposition 3.1, the minimum value of the optimization problem (A.77) is given by

A.5 Optimization Results

We will show the convergence of Boosting Algorithm as a special instantiation of the Mirror Descent proof. We will establish the result for two scenarios: (1) AdaBoost, with $X_{ij}\in\{\pm 1\}$, and (2) Boosting Algorithm from Section 2, with bounded continuous $|X_{ij}|\leq M$ and a shrinkage on the learning rate (the specifics will be made clear in the proof below). Note that in the discrete case (Case (1)), Steps (a) and (b) in the Boosting Algorithmfrom Section 2 could be replaced by

It is easy to verify that the (1) AdaBoost algorithm defined above is equivalent to the following mirror descent algorithm:

Learning rate is $\alpha_{t}=\frac{1}{2}\log\frac{1+\gamma_{t}}{1-\gamma_{t}}$ since

Updates on $\eta_{t}\in\Delta_{n}$ (mirror descent) reduce to

Now we are ready to prove the final statement. Due to the fact that $R^{\star}$ is strongly smooth w.r.t. the $L_{\infty}$ norm

The above derives the reduction in $R^{\star}$ for each step.

For the (2) Boosting Algorithm from Section 2, with $|X_{ij}|\leq M$, define a shrinkage on the learning rate $\alpha_{t}(\beta)$ with a constant factor $\beta>0$,

A good choice of $\beta$ will be clear in a second. Then

where the last step uses the choice of $\beta=1/M^{2}$.

Now telescoping with the terms $R^{\star}(-Z\theta_{t+1})-R^{\star}(-Z\theta_{t})$, we have

The proof follows from Proposition 5.1 and a re-scaling technique in ’s asymptotic analysis. Here instead, we spell out a non-asymptotic result. For any $\kappa>0$

with $R^{\star}$ defined in (A.90). Due to the proof in Proposition 5.1, we know

In addition, due to the coordinate update of $\theta_{t}$, we know

The proof follows by modifying some steps of our proof in the $q=1$ case. Recall the notations in (A.94),

with $\gamma_{t}=\|Z^{\top}\eta_{t}\|_{q_{\star}}$.

Plug in the above to the argument in (A.105), we have

where the last step uses the Sion’s Minimax Theorem,

The following two formulations are equivalent

Suppose that $\theta_{\star}$ solves $II$, then take $\theta=\theta_{\star}/II^{\star}$ satisfy $\|\theta\|=1$, then

Suppose that $I^{\star}$ is the optimal solution for $I$, then there exist a $\theta,\|\theta\|\leq 1$ such that $y_{i}x_{i}^{\top}(\theta/I^{\star})\geq 1$, then

Appendix B Extended Derivations

We collect here the detailed derivations in Section 3.5, where robustness of the assumptions is investigated.

and by an application of CGMT, this is asymptotically equivalent to analyzing the following optimization problem

where $z,g$ are independent vectors with entries i.i.d. $\mathcal{N}(0,1)$. Maximizing over $\lambda$, this further reduces to

Using tricks similar to those in Proposition (A.1), we have that $\xi_{n}$ must converge to the following infinite-dimensional version

where $Z=\Lambda^{1/2}h/\|\Lambda^{1/2}h\|$ if the denominator is strictly positive, and $Z^{\prime}$ with $\|Z^{\prime}\|\leq 1$ when the denominator is zero. Rewriting things, we obtain

Using properties of the proximal mapping operator, this yields

For the formal argument that $\xi_{n}\rightarrow\xi_{\infty}$ as $n,p\rightarrow\infty$, we assume that the aforementioned equation system admits a unique solution. We expect that arguments similar to Proposition (3.1) can be used to prove this in the regime where the data is asymptotically linearly separable.

The aforementioned arguments for the model in (B.1) naturally extend to the following,

B.2 Derivations in Section 3.5.2

To prove (3.38), we define for fixed $\kappa,\lambda>0$, the following perturbed Lagrangian that is strongly convex in $\theta$

By a standard probability argument (see for instance ), it suffices to show that \mathop{\mathbf{E}}\left[\phi\big{(}\tfrac{1}{p}\Phi_{n}^{\kappa,\lambda}(0,0)\big{)}\right]-\mathop{\mathbf{E}}\left[\phi\big{(}\tfrac{1}{p}\Phi_{0}^{\kappa,\lambda}(0,0)\big{)}\right]\rightarrow 0 for any bounded test function $\phi$ that has bounded derivatives up to the third order. To bound this difference, we will approximate the problems at $(0,0)$, that is, $\Phi_{n}^{\kappa,\lambda}(0,0),\Phi_{0}^{\kappa,\lambda}(0,0)$ with the corresponding problems for positive $\epsilon,\delta$. To control this approximation, we further need to control the approximation error of $h(\cdot)$, using $h_{\delta}(\cdot)$, and the derivatives of $h_{\delta}(\cdot)$. This is achieved in Lemma B.2. On working out this argument, we obtain that

Above $C$ involves universal constants and the scaled norms $\|\theta^{\star}_{n}\|^{2}/p,\|\theta^{\star}_{0}\|^{2}/p$, where these denote optimizers of the objective functions in $\Phi_{n}^{\kappa,\lambda}(0,0),\Phi_{0}^{\kappa,\lambda}(0,0)$. Thus, it suffices to control $(i)$, which we achieve by a Lindeberg argument. Denoting $\mathop{\mathbf{E}}_{x}$ to be the expectation with respect to $x$, keeping all other random variables fixed, we note that

With this notation, bounding the RHS of (B.15) breaks down to two tasks—controlling the error of quadratic approximation

where the regularization parameter is defined to be

Thus, it suffices to bound $(ii),(iv)$ and $(v).$ This requires controlling the approximation error of $h(\cdot)$ using $h_{\delta}(\cdot)$, derivatives of $h_{\delta}(\cdot)$ and the Moreau envelope. We achieve these in Lemma B.1-B.2, and using these, we claim the following bounds,

We will prove these invoking Lemma B.2-B.1 and techniques from [55, Lemma1,2,24]. Before we present the proofs, note that, together with (B.2), this implies that with proper choice of $\epsilon,\delta=p^{-c_{1}}$

with some $c_{1},c_{2}>0$. The above is true since it can be shown that the constant $C$ in (B.2) is $O(1)$, by arguments similar to (B.33). The rest of the proof thus focuses on establishing (B.23)–(B.25).

To bound the term (v), it suffices to control \big{|}\mathop{\mathbf{E}}_{x_{k}}[\mathcal{M}_{k}(t,\gamma(x_{k}))-\mathcal{M}_{k}(t,\gamma_{k})]\big{|} with $t=\tfrac{1}{\sqrt{p}}x_{k}^{\top}\theta^{\star}_{\backslash k}$. First, calculate the partial derivative of $\mathcal{M}_{k}(t,\gamma)$ w.r.t. $\gamma$,

and hence it suffices to bound $\|\tfrac{1}{\sqrt{p}}\theta^{\star}_{\backslash k}\|$. Note that, in the definition of $\gamma_{k}$ above, $x$ has the same distribution as $x_{k}$ so that the term $E_{x_{k}}(\frac{1}{p}x_{k}^{\top}(H_{\backslash k}(\epsilon))^{-1}x_{k}-\gamma_{k})^{2}$ can effectively be treated as variance of a chi-square random variable with $p$ degrees of freedom, scaled by $p$. We know

The proof follows directly from Lemma B.1 and [55, Lemma 2] since Lemma B.1 verifies the needed condition needed in [55, Lemma 2]. ∎

To upper bound (ii), we need to control the quadratic approximation

By a Taylor expansion up to the third order and the mean value theorem, the above expression can be bounded by

With this fact in mind, we continue to control each term (a), (b), (c).

The last two steps use the following fact:

as $\tfrac{1}{p}\|\theta_{\backslash\{k,i\}}^{\star}\|^{2}\precsim\epsilon^{-1}$.

Term (c): First, observe that by Lemma B.2, $h^{\prime\prime\prime}_{\delta}\precsim\delta^{-2}$, thus we only need to control

Case 2: $\theta=\theta^{\star}(x_{k})$. Compared to Case 1, here we need an additional fact that controls the deviation

Due to the strong convexity of $\mathcal{L}_{k}^{\kappa,\lambda}(\theta~{};~{}\epsilon,\delta)$, we know

Therefore (B.51) can be bounded as follows

Now we revisit the terms (a), (b), (c) in the case where $\theta=\theta^{\star}(x_{k})$.

Again, putting the upper bounds on (a), (b) and (c) together, we have shown (B.2) with $\theta=\theta^{\star}(x_{k})$ is upper bounded by

B.3 Supporting Lemmas

Throughout the proof of Theorem 3.4, we rely on the following two lemmas, and the proof is complete on proving these.

Assume that $\delta<\tfrac{\kappa}{2}\epsilon$, the following estimates on the Moreau envelope hold,

For the first order estimate, we have by the Envelope Theorem

where $s^{\star}(t)$ is the solution to the equation on $s$, for any fixed $t$ (proximal map)

Due to the non-expansiveness of the proximal map, we have

and if $y_{k}s^{\star}(0)>\kappa$, we will reach a contradiction $2\delta<\kappa\epsilon<\tfrac{\kappa}{\gamma_{k}}\leq 2|h_{\delta}(\kappa-y_{k}s^{\star}(0))h^{\prime}_{\delta}(\kappa-y_{k}s^{\star}(0))|\leq 2\delta$. ∎