Self-concordant analysis for logistic regression

Introduction

The theoretical analysis of statistical methods is usually greatly simplified when the estimators have closed-form expressions. For methods based on the minimization of a certain functional, such as M-estimation methods , this is true when the function to minimize is quadratic, i.e., in the context of regression, for the square loss.

When such loss is used, asymptotic and non-asymptotic results may be derived with classical tools from probability theory (see, e.g., ). When the function which is minimized in M-estimation is not amenable to closed-form solutions, local approximations are then needed for obtaining and analyzing a solution of the optimization problem. In the asymptotic regime, this has led to interesting developments and extensions of results from the quadratic case, e.g., consistency or asymptotic normality (see, e.g., ). However, the situation is different when one wishes to derive non-asymptotic results, i.e., results where all constants of the problem are explicit. Indeed, in order to prove results as sharp as for the square loss, much notation and many assumptions have to be introduced regarding second and third derivatives; this makes the derived results much more complicated than the ones for closed-form estimators .

A similar situation occurs in convex optimization, for the study of Newton’s method for obtaining solutions of unconstrained optimization problems. It is known to be locally quadratically convergent for convex problems. However, its classical analysis requires cumbersome notations and assumptions regarding second and third-order derivatives (see, e.g., ). This situation was greatly enhanced with the introduction of the notion of self-concordant functions, i.e., functions whose third derivatives are controlled by their second derivatives. With this tool, the analysis is much more transparent . While Newton’s method is a commonly used algorithm for logistic regression (see, e.g., ), leading to iterative least-squares algorithms, we don’t focus in the paper on the resolution of the optimization problems, but on the statistical analysis of the associated global minimizers.

In order to consider such extensions and make sure that the new results closely match the corresponding ones for least-squares regression, we derive in Appendix G new Bernstein-like concentration inequalities for quadratic forms of bounded random variables, obtained from general results on U-statistics .

Taylor expansions and Newton’s method

If $\lambda(w)>0$, i.e., the Hessian is invertible at $w$, we can define the Newton step as $\Delta^{N}(w)=-F^{\prime\prime}(w)^{-1}F^{\prime}(w)$, and the Newton decrement $\nu(F,w)$ at $w$, defined through:

The one-step Newton iterate $w+\Delta^{N}(w)$ is the minimizer of the second-order Taylor expansion of $F$ at $w$, i.e., of the function $v\mapsto F(w)+F^{\prime}(w)(v-w)+\frac{1}{2}(v-w)^{\top}F^{\prime\prime}(w)(v-w)$. Newton’s method consists in successively applying the same iteration until convergence. For more background and details about Newton’s method, see, e.g., .

which allows to prove an upper-bound of the error of the one-step iterate, by application of Eq. (1) to $w+\Delta^{N}(w)$. Note that these bounds are not the sharpest, but are sufficient in our context. These are commonly used to show the global convergence of the damped Newton’s method or of Newton’s method with backtracking line search , as well as a precise upper bound on the number of iterations to reach a given precision.

Note that in the context of machine learning and statistics, self-concordant functions have been used for bandit optimization and online learning , but for barrier functions related to constrained optimization problems, and not directly for M-estimation.

2 Modifications of self-concordant functions

The logistic function $u\mapsto\log(1+e^{-u})$ is not self-concordant as the third derivative is bounded by a constant times the second derivative (without the power $3/2$). However, similar bounds can be derived with a different control of the third derivatives. Proposition 1 provides lower and upper Taylor expansions while Proposition 2 considers the behavior of Newton’s method. Proofs may be found in Appendix A and follow closely the ones for regular self-concordant functions found in .

Inequalities in Eq. (3) and Eq. (4) provide upper and lower second-order Taylor expansions of $F$, while Eq. (5) provides a first-order Taylor expansion of $F^{\prime}$ and Eq. (6) can be considered as an upper and lower zero-order Taylor expansion of $F^{\prime\prime}$. Note the difference here between Eqs. (3-4) and regular third-order Taylor expansions of $F$: the remainder term in the Taylor expansion, i.e., $F(w+v)-F(w)-v^{\top}F^{\prime}(w)-\frac{1}{2}v^{\top}F^{\prime\prime}(w)v$ is upper-bounded by $\frac{v^{\top}F^{\prime\prime}(w)v}{R^{2}\|v\|_{2}^{2}}(e^{R\|v\|_{2}}-\frac{1}{2}R^{2}\|v\|_{2}^{2}-R\|v\|_{2}-1)$; for $\|v\|_{2}$ small, we obtain a term proportional to $\|v\|_{2}^{3}$ (like a regular local Taylor expansion), but the bound remains valid for all $v$ and does not grow as fast as a third-order polynomial. Moreover, a regular Taylor expansion with a uniformly bounded third-order derivative would lead to a bound proportional to $\|v\|_{2}^{3}$, which does not take into account the local curvature of $F$ at $w$. Taking into account this local curvature is key to obtaining sharp and simple bounds on the behavior of Newton’s method (see proof in Appendix A):

Eq. (7) extends Eq. (1) while Eq. (8) extends Eq. (2). Note that the notion and the results are not invariant by affine transform (contrary to self-concordant functions) and that we still need a (non-uniformly) lower-bounded Hessian. The last two propositions constitute the main technical contribution of this paper. We now apply these to logistic regression and its regularized versions.

Application to logistic regression

Throughout this paper, we consider a fixed design setting (i.e., $x_{1},\dots,x_{n}$ are consider deterministic) and we make the following assumptions:

Independent outputs: The outputs $y_{i}\in\{-1,1\}$, $i=1,\dots,n$ are independent (but not identically distributed).

Bounded inputs: $\max_{i\in\{1,\dots,n\}}\|x_{i}\|_{2}\leqslant R$.

We denote by $J_{0}$ the expectation of $\hat{J}_{0}$, i.e.:

Note that with our notation, $\hat{J}_{0}(w)=J_{0}(w)-q^{\top}w$. In this paper we consider $J_{0}(\hat{w})$ as the generalization performance of a certain estimator $\hat{w}$. This corresponds to the average Kullback-Leibler divergence to the best model when the model is well-specified, and is common for the study of logistic regression and more generally generalized linear models . Measuring the classification performance through the 0–1 loss is out of the scope of this paper.

with respect to the function $f$ in the RKHS $\mathcal{F}$ (with norm $\|\cdot\|_{\mathcal{F}}$ and kernel $k$), is equivalent to minimizing the cost function

2 Minimal assumptions (misspecified model)

In this section, we do not assume that the model is well-specified. We obtain the following theorem (see proof in Appendix B), which only assumes boundedness of the covariates and independence of the outputs:

This is to be compared with , which uses different proof techniques but obtains similar results for all convex Lipschitz-continuous losses (and not only for the logistic loss). However, the techniques presented in this paper allow the derivation of much more precise statements in terms of bias and variance (and with better rates), that involves some knowledge of the problem. We do not pursue detailed results here, but focus in the next section on well-specified models, where results have a simpler form.

This highlights two opposite strategies for the theoretical analysis of regularized problems: the first one, followed by , is mostly loss-independent and relies on advanced tools from empirical process theory, namely uniform concentration inequalities. Results are widely applicable and make very few assumptions. However, they tend to give performance guarantees which are far below the observed performances of such methods in applications. The second strategy, which we follow in this paper, is to restrict the loss class (to linear or logistic) and derive the limiting convergence rate, which does depend on unknown constants (typically the best linear classifier itself). Once the limit is obtained, we believe it gives a better interpretation of the performance of these methods, and if one really wishes to make no assumption, taking upper bounds on these quantities, we may get back results obtained with the generic strategy, which is exactly what Theorem 1 is achieving.

Thus, a detailed analysis of the convergence rate, as done in Theorem 2 in the next section, serves two purposes: first, it gives a sharp result that depends on unknown constants; second the constants can be maximized out and more general results may be obtained, with fewer assumptions but worse convergence rates.

3 Well-specified models

We now assume that the model is well-specified, i.e., that the probability that $y_{i}=1$ is a sigmoid function of a linear function of $x_{i}$, which is equivalent to:

Moreover, we denote by $\kappa>0$ the following quantity

Such quantity is an extension of the one used by in the context of kernel Fisher discriminant analysis used as a test for homogeneity. In order to obtain asymptotic equivalents, we require $\kappa$ to be small, which, as shown later in this section, occurs in many interesting cases when $n$ is large enough.

In this section, we will apply results from Section 2 to the functions $\hat{J}_{\lambda}$ and $J_{0}$. Essentially, we will consider local quadratic approximations of these functions around the generating loading vector $w_{0}$, leading to replacing the true estimator $\hat{w}_{\lambda}$ by the one-step Newton iterate from $w_{0}$. This is only possible if the Newton decrement $\nu(\hat{J}_{\lambda},w_{0})$ is small enough, which leads to additional constraints (in particular the upper-bound on $\kappa$).

Assume (A1), (A2) and (A3). Assume moreover $\kappa\leqslant 1/16$, where $\kappa$ is defined in Eq. (13). If $v\in[0,1/4]$ satisfies $v^{3}(d_{2}+nb_{2})^{1/2}\leqslant 12$, then, with probability at least $1-\exp(-v^{2}(d_{2}+nb_{2}))$:

When the dimension $p$ of $w_{0}$ is bounded, then under the regular asymptotic regime ($n$ tends to $+\infty$), $J_{0}(\hat{w}_{\lambda})$ has the following expansion J_{0}(w_{0})+\frac{1}{2}\big{(}b_{2}+\frac{d_{2}}{n}\big{)}, a result which has been obtained by several authors in several settings . In this asymptotic regime, the optimal $\lambda$ is known to be of order $O(n^{-1})$ . The main contribution of our analysis is to allow a non asymptotic analysis with explicit constants. Moreover, note that for the square loss, the bound in Eq. (14) holds with $\kappa=0$, which can be linked to the fact that our self-concordant analysis from Propositions 1 and 2 is applicable with $R=0$ for the square loss. Note that the constants in the previous theorem could probably be improved.

Conditions for asymptotic equivalence.

In order to have the remainder term in Eq. (14) negligible with high probability compared to the lowest order term in the expansion of $J_{0}(\hat{w}_{\lambda})$, we need to have $d_{2}+nb_{2}$ large and $\kappa$ small (so that $v$ can be taken taking small while $v^{2}(d_{2}+nb_{2})$ is large, and hence we have a result with high-probability). The assumption that $d_{2}+nb_{2}$ grows unbounded when $n$ tends to infinity is a classical assumption in the study of smoothing splines and RKHSs , and simply states that the convergence rate of the excess risk $J_{0}(\hat{w}_{\lambda})-J_{0}(w_{0})$, i.e., $b_{2}+d_{2}/n$, is slower than for parametric estimation, i.e., slower than $n^{-1}$.

Study of parameter κ𝜅\kappa.

First, we always have \kappa\geqslant\frac{R}{\lambda^{1/2}}\big{(}\frac{d_{1}}{n}+b_{1}\big{)}^{1/2}; thus an upper bound on $\kappa$ implies an upperbound on $\frac{d_{1}}{n}+b_{1}$ which is needed in the proof of Theorem 2 to show that the Newton decrement is small enough. Moreover, $\kappa$ is bounded by the sum of $\kappa_{\rm bias}=\frac{R}{\lambda^{1/2}}b_{1}b_{2}^{-1/2}$ and \kappa_{\rm var}=\frac{R}{\lambda^{1/2}}\big{(}\frac{d_{1}}{n}\big{)}\big{(}\frac{d_{2}}{n}\big{)}^{-1/2}. Under simple assumptions on the eigenvalues of $Q$ or equivalently of $\mathop{\rm Diag}(\sigma_{i})K\mathop{\rm Diag}(\sigma_{i})$, one can show that $\kappa_{\rm var}$ is small. For example, if $d$ of these eigenvalues are equal to one and the remaining ones are zero, then, $\kappa_{\rm var}=\frac{Rd^{1/2}}{\lambda^{1/2}n^{1/2}}$. And thus we simply need $\lambda$ asymptotically greater than $R^{2}d/n$. For additional conditions for $\kappa_{\rm var}$, see . A simple condition for $\kappa_{\rm bias}$ can be obtained if $w_{0}^{\top}Q^{-1}w_{0}$ is assumed bounded (in the context of RKHSs this is a stricter condition that the generating function is inside the RKHS, and is used by in the context of sparsity-inducing norms). In this case, the bias terms are negligible compared to the variance term as soon as $\lambda$ is asymptotically greater than $n^{-1/2}$.

Variance term.

Note that the diagonal matrix $\mathop{\rm Diag}(\sigma_{i}^{2})$ is upperbounded by $\frac{1}{4}I$, i.e., $\mathop{\rm Diag}(\sigma_{i}^{2})\preccurlyeq\frac{1}{4}I$, so that the degrees of freedom for logistic regression are always less than the corresponding ones for least-squares regression (for $\lambda$ multiplied by 4). Indeed, the pairs $(x_{i},y_{i})$ for which the conditional distribution is close to deterministic are such that $\sigma_{i}^{2}$ is close to zero. And thus it should reduce the variance of the estimator, as little noise is associated with these points, and the effect of this reduction is exactly measured by the reduction in the degrees of freedom.

Moreover, the rate of convergence $d_{2}/n$ of the variance term has been studied by many authors (see, e.g., ) and depends on the decay of the eigenvalues of $Q$ (the faster the decay, the smaller $d_{2}$). The degrees of freedom usually grows with $n$, but in many cases is slower than $n^{1/2}$, leading to faster rates in Eq. (14).

4 Smoothing parameter selection

In this section, we obtain a criterion similar to Mallow’s $C_{L}$ to estimate the generalization error and select in a data-driven way the regularization parameter $\lambda$ (referred to as the smoothing parameter when dealing with splines or RKHSs). The following theorem shows that with a data-dependent criterion, we may obtain a good estimate of the generalization performance, up to a constant term $q^{\top}w_{0}$ independent of $\lambda$ (see proof in Appendix D):

The previous theorem, which is essentially a non-asymptotic version of results in can be further extended to obtain oracle inequalities when minimizing the data-driven criterion $\hat{J}_{0}(\hat{w}_{\lambda})+\frac{1}{n}\mathop{\rm tr}\hat{Q}_{\lambda}(\hat{Q}_{\lambda}+\lambda I)^{-1}$, similar to results obtained in for the square loss. Note that contrary to least-squares regression with Gaussian noise, there is no need to estimate the unknown noise variance (of course only when the logistic model is actually well-specified); however, the matrix $Q$ used to define the degrees of freedom does depend on $w_{0}$ and thus requires that $\hat{Q}_{\lambda}$ is used as an estimate. Finally, criteria based on generalized cross-validation could be studied with similar tools.

We denote by $K=\{j\in\{1,\dots,p\},(w_{0})_{j}\neq 0\}$ the set of non-zero components of $w_{0}$ and $s=\mathop{\rm sign}(w_{0})\in\{-1,0,1\}^{p}$ the vector of signs of $w_{0}$. On top of Assumptions (A1), (A2) and (A3), we will make the following assumption regarding normalization for each covariate (which can always be imposed by renormalization), i.e.,

Normalized covariates: for all $j=1,\dots,p$, $\frac{1}{n}\sum_{i=1}^{n}[(x_{i})_{j}]^{2}\leqslant 1$.

The following theorem provides a sufficient condition for model consistency. It is based on the consistency condition $\|Q_{K^{c}K}Q_{KK}^{-1}s_{K}\|_{\infty}<1$, which is exactly the same as the one for the square loss (see proof in Appendix E):

Assume (A1), (A2), (A3) and (A4). Assume that there exists $\eta,\rho,\mu>0$ such that

$\lambda_{\min}(Q_{KK})\geqslant\rho$ and $\min_{j\in K}|(w_{0})_{j}|\geqslant\mu$. Assume $\lambda\leqslant\min\left\{\frac{\rho\mu}{4|K|^{1/2}},\frac{\eta\rho^{3/2}}{64R|K|}\right\}$. Then the probability that the vector of signs of $\hat{w}_{\lambda}$ is different from $s=\mathop{\rm sign}(w_{0})$ is upperbounded by

For the square loss, the previous theorem simplifies : with our notations, the constraint $\lambda\leqslant\frac{\eta\rho^{3/2}}{64R|K|}$ and the last term in Eq. (16), which are the only ones depending on $R$, can be removed (indeed, the square loss allows the application of our adapted self-concordant analysis with the constant $R=0$). On the one hand, the favorable scaling between $p$ and $n$, i.e., $\log p=O(n)$ for a certain well-chosen $\lambda$, is preserved (since the logarithm of the added term is proportional to $-\lambda n$). However, on the other hand, the terms in $R$ may be large as $R$ is the radius of the entire data (i.e., with all $p$ covariates). Bounds with the radius of the data on only the relevant features in $K$ could be derived as well (see details in the proof in Appendix E).

Necessary condition.

In the case of the square loss, a weak form of Eq. (15), i.e., $\|Q_{K^{c}K}Q_{KK}^{-1}s_{K}\|_{\infty}\leqslant 1$ turns out to be necessary and sufficient for asymptotic correct model selection . While the weak form is clearly necessary for model consistency, and the strict form sufficient (as proved in Theorem 4), we are currently investigating whether the weak condition is also sufficient for the logistic loss.

2 Efficiency

Another type of result has been derived, based on different proof techniques and aimed at efficiency (i.e., predictive performance). Here again, we can extend the result in a very simple way. We assume, given $K$ the set of non-zero components of $w_{0}$:

Note that the assumption made in is slightly stronger but only depends on the cardinality of $K$ (by minimizing with respect to all sets of indices with cardinality equal to the one of $K$). The following theorem provides an estimate of the estimation error as well as an oracle inequality for the generalization performance (see proof in Appendix F):

Assume (A1), (A2), (A3), (A4), and (A5). For all $\lambda\leqslant\frac{\rho^{2}}{48R|K|}$, with probability at least $1-2pe^{-\lambda n^{2}/5}$, we have:

We obtain a result which directly mimics the one obtained in for the square loss with the exception of the added bound on $\lambda$. In particular, if we take $\lambda=\sqrt{\frac{10\log(p)}{n}}$, we get with probability at least $1-2/p$, an upper bound on the generalization performance ${J}_{0}(\hat{w}_{\lambda})\leqslant{J}_{0}(w_{0})+120\frac{\log p}{n}|K|\rho^{-2}$. Again, the proof of this result is a direct extension of the corresponding one for the square loss, with few additional assumptions owing to the proper self-concordant analysis.

Conclusion

The present work could be extended in several interesting ways to different settings. First, for logistic regression, other extensions of theoretical results from least-squares regression could be carried out: for example, the analysis of sequential experimental design for logistic regression leads to many assumptions that could be relaxed (see, e.g., ). Also, other regularization frameworks based on sparsity-inducing norms could be applied to logistic regression with similar guarantees than for least-squares regression, such as group Lasso for grouped variables or non-parametric problems , or resampling-based procedures that allow to get rid of sufficient consistency conditions.

Appendix A Proofs of optimization results

We first consider univariate functions and prove the following lemma that gives upper and lower Taylor expansions:

Thus, we need to prove Eq. (18) for $g^{\prime\prime}$ always strictly positive (which is done above) and for $g^{\prime\prime}$ identically equal to zero, which implies that $g$ is linear, which is then equivalent to Eq. (18). Note the difference with a classical uniform bound on the third derivative, which leads to a third-order polynomial lower bound, which tends to $-\infty$ more quickly than Eq. (20). Moreover, Eq. (21) may be interpreted as an upperbound on the remainder in the Taylor expansion of $g$ around :

The right hand-side is equivalent to $\frac{St^{3}}{6}g^{\prime\prime}(0)$ for $t$ close to zero (which should be expected from a three-times differentiable function such that $g^{\prime\prime\prime}(0)\leqslant Sg^{\prime\prime}(0)$), but still provides a good bound for $t$ away from zero (which cannot be obtained from a regular Taylor expansion).

A.2 Proof of Proposition 1

In order to prove Eq. (5), we consider $h(t)=z^{\top}(F^{\prime}(w+tv)-F^{\prime}(w)-F^{\prime\prime}(w)vt)$. We have $h(0)=0$, $h^{\prime}(0)=0$ and $h^{\prime\prime}(t)=F^{\prime\prime\prime}(w+tv)[v,v,z]\leqslant R\|v\|_{2}e^{tR\|v\|_{2}}[z^{\top}F^{\prime\prime}(w)z]^{1/2}[v^{\top}F^{\prime\prime}(w)v]^{1/2}$ using Eq. (6) and Eq. (17). Thus, by integrating between and $t$,

which implies $\textstyle h(1)\leqslant[z^{\top}F^{\prime\prime}(w)z]^{1/2}[v^{\top}F^{\prime\prime}(w)v]^{1/2}\int_{0}^{1}(e^{tR\|v\|_{2}}-1)dt,$ which in turn leads to Eq. (5).

A.3 Proof of Proposition 2

Since we have assumed that $\lambda(w)>0$, then by Eq. (6), the Hessian of $F$ is everywhere invertible, and hence the function $F$ is strictly convex. Therefore, if the minimum is attained, it is unique.

Moreover, a short calculation shows that for all $\kappa\in(0,1]$:

This implies that for $t_{0}=2(R\|v\|_{2})^{-1}\kappa(1-\kappa)^{-1}$, $F(w+t_{0}v)\geqslant F(w)$. Since $t_{0}\leqslant\frac{2}{1-\kappa}|v^{\top}F^{\prime}(w)|\leqslant{2}{\nu(F,w)}\left(1-\frac{\nu(F,w)R}{\lambda(w)^{1/2}}\right)^{-1}\leqslant 4\nu(F,w)$, we have $F(w+tv)\geqslant F(w)$ for $t=4\nu(F,w)$.

Since this is true for all $v$ such that $v^{\top}F^{\prime\prime}(w)v=1$, this shows that the value of the function $F$ on the entire ellipsoid (since $F^{\prime\prime}(w)$ is positive definite) $v^{\top}F^{\prime\prime}(w)v=16\nu(F,w)^{2}$ is greater or equal to the value at $w$; thus, by convexity, there must be a minimizer $w^{\ast}$—which is unique because of Eq. (6)—of $F$ such that

In order to prove Eq. (9), we will simply apply Eq. (7) at $w+v$, which requires to upper-bound $\nu(F,w+v)$. If we denote by $v=-F^{\prime\prime}(w)^{-1}F^{\prime}(w)$ the Newton step, we have:

Therefore, using Eq. (6) again, we obtain:

We have $R\|v\|_{2}\leqslant R\lambda^{-1/2}\nu(F,w)\leqslant 1/2$, and thus, we have

which leads to Eq. (8). Moreover, it shows that we can apply Eq. (7) at $w+v$ and get:

which leads to the desired result, i.e., Eq. (9).

Appendix B Proof of Theorem 1

Following , we denote by $w_{\lambda}$ the unique global minimizer of the expected regularized risk $J_{\lambda}(w)=J_{0}(w)+\frac{\lambda}{2}\|w\|_{2}^{2}$. We simply apply Eq. (7) from Proposition 2 to $\hat{J}_{\lambda}$ and $w_{\lambda}$, to obtain, if the Newton decrement (see Section 2 for its definition) $\nu(\hat{J}_{\lambda},w_{\lambda})^{2}$ is less than $\lambda/4R^{2}$, that $\hat{w}_{\lambda}$ and its population counterpart $w_{\lambda}$ are close, i.e.:

We can then apply the upper Taylor expansion in Eq. (4) from Proposition 1 to $J_{\lambda}$ and $w_{\lambda}$, to obtain, with $v=\hat{w}_{\lambda}-w_{\lambda}$ (which is such that $R\|v\|_{2}\leqslant 4\frac{R\nu(\hat{J}_{\lambda},w_{\lambda})}{\lambda^{1/2}}\leqslant 2$):

We can now apply the concentration inequality from Proposition 4 in Appendix G, i.e., Eq. (42), with $u=\log(8/\delta)$. We use $\lambda={19R^{2}}\sqrt{\frac{\log(8/\delta)}{n}}$. In order to actually have $\nu(\hat{J}_{\lambda},w_{\lambda})\leqslant\lambda^{1/2}/2R$ (so that we can apply our self-concordant analysis), it is sufficient that:

leading to the constraints $u\leqslant n/125$. We then get with probability at least $1-\delta=1-8e^{-u}$ (for $u\leqslant n/125$):

For $u>n/125$, the bound in Eq. (12) is always satisfied. Indeed, this implies with our choice of $\lambda$ that $\lambda\geqslant R^{2}$. Moreover, since $\|\hat{w}_{\lambda}\|_{2}^{2}$ is bounded from above by $\log(2)\lambda^{-1}\leqslant R^{-2}$,

which is smaller than the right hand-side of Eq. (12).

Appendix C Proof of Theorem 2

We denote by $J_{0}^{T}$ the second-order Taylor expansion of $J_{0}$ around $w_{0}$, equal to $J_{0}^{T}(w)=J_{0}(w_{0})+\frac{1}{2}(w-w_{0})^{\top}Q(w-w_{0})$, with $Q=J_{0}^{\prime\prime}(w_{0})$, and $\hat{J}_{0}^{T}$ the expansion of $\hat{J}_{0}$ around $w_{0}$, equal to $J_{0}^{T}(w)-q^{\top}w$. We denote by $\hat{w}_{\lambda}^{N}$ the one-step Newton iterate from $w_{0}$ for the function $\hat{J}_{0}$, defined as the global minimizer of $\hat{J}_{0}^{T}$ and equal to $\hat{w}_{\lambda}^{N}=w_{0}+(Q+\lambda I)^{-1}(q-\lambda w_{0})$.

What the following proposition shows is that we can replace $\hat{J}_{0}$ by $\hat{J}_{0}^{T}$ for obtaining the estimator and that we can replace $J_{0}$ by $J_{0}^{T}$ for measuring its performance, i.e., we may do as if we had a weighted least-squares cost, as long as the Newton decrement is small enough:

Assume $\nu(\hat{J}_{\lambda},w_{0})^{2}=(q-\lambda w_{0})^{\top}(Q+\lambda I)^{-1}(q-\lambda w_{0})\leqslant\frac{\lambda}{4R^{2}}$. We have:

Proof We show that (1) $\hat{w}_{\lambda}^{N}$ is close to $\hat{w}_{\lambda}$ using Proposition 2 on the behavior of Newton’s method, (2) that $\hat{w}_{\lambda}^{N}$ is close to $w_{0}$ by using its closed form $\hat{w}_{\lambda}^{N}=w_{0}+(Q+\lambda I)^{-1}(q-\lambda w_{0})$, and (3) that $J_{0}$ and $J_{0}^{T}$ are close using Proposition 1 on upper and lower Taylor expansions.

We first apply Eq. (9) from Proposition 2 to get

This implies that $\hat{w}_{\lambda}$ and $\hat{w}_{\lambda}^{N}$ are close, i.e.,

Thus, using the closed form expression for $\hat{w}_{\lambda}^{N}=w_{0}+(Q+\lambda I)^{-1}(q-\lambda w_{0})$, we obtain

We can now apply Eq. (3) from Proposition 2 to get for all $v$ such that $R\|v\|_{2}\leqslant 3/2$,

Thus, using Eq. (28) for $v=\hat{w}_{\lambda}-w_{0}$ and $v=\hat{w}_{\lambda}^{N}-w_{0}$ :

From Eq. (27), we have $\|Q^{1/2}(\hat{w}_{\lambda}-\hat{w}_{\lambda}^{N})\|_{2}^{2}\leqslant\frac{16R^{2}}{\lambda}\nu(\hat{J}_{\lambda},w_{0})^{4}$. We thus obtain, using that $\|Q^{1/2}(\hat{w}_{\lambda}^{N}-w_{0})\|_{2}\leqslant\nu(\hat{J}_{0},w_{0})$:

We can now go on with the proof of Theorem 2. From Eq. (26) in Proposition 3 above, we have, if $\nu(\hat{J}_{\lambda},w_{0})^{2}\leqslant\lambda/4R^{2}$,

We can now bound each term separately and check that we indeed have $\nu(\hat{J}_{\lambda},w_{0})^{2}\leqslant\lambda/4R^{2}$ (which allows to apply Proposition 2). First, from Eq. (13), we can derive

We can now apply concentration inequalities from Appendix G, together with the following applications of Bernstein’s inequality. Indeed, we have ${\lambda}{}w_{0}^{\top}(Q+\lambda I)^{-2}Qq=\sum_{i=1}^{n}Z_{i},$ with

Similarly, with probability at least $1-2e^{-u}$, we have:

We thus get, through the union bound, with probability at least $1-20e^{-u}$:

together with $C\leqslant E$. We now take $u=(nb_{2}+d_{2})v^{2}$ and assume $v\leqslant 1/4$, $\kappa\leqslant 1/16$, and $v^{3}(nb_{2}+d_{2})^{1/2}\leqslant 12$, so that, we have

This implies that $\nu(\hat{J}_{\lambda},w_{0})^{2}\leqslant\frac{\lambda}{R^{2}}\frac{20}{256}\leqslant\frac{\lambda}{4R^{2}}$, so that we can apply Proposition 2. Thus, by denoting $e_{2}=b_{2}+\frac{d_{2}}{n}$, $e_{1}=b_{1}+\frac{d_{1}}{n}$, and $\alpha=69v+10\kappa\leqslant 20$, we get a global upper bound:

With $e_{1}+e_{2}\alpha\leqslant e_{2}^{1/2}(\kappa\lambda^{1/2}/R)(1+\alpha)$, we get

which leads to the desired result, i.e., Eq. (14).

Appendix D Proof of Theorem 3

We follow the same proof technique than for Theorem 2 in Appendix C. We have:

where $\hat{w}_{\lambda}^{NN}$ is the two-step Newton iterate from $w_{0}$. We have, from Eq. (24), $\nu(\hat{J}_{\lambda},\hat{w}_{\lambda}^{N})\leqslant\frac{2R}{\lambda^{1/2}}\nu(\hat{J}_{\lambda},w_{0})^{2}$, which then implies (with Eq. (9)):

Moreover, we have from the closed-form expression of $\hat{w}_{\lambda}^{N}$:

Finally, we have, using Eq. (5) from Proposition 1:

where $\Delta=\hat{w}^{N}_{\lambda}-w_{0}$.

What also needs to be shown is that \big{|}\mathop{\rm tr}\hat{Q}_{\lambda}(\hat{Q}_{\lambda}+\lambda I)^{-1}-\mathop{\rm tr}Q(Q+\lambda I)^{-1}\big{|} is small enough; by noting that $Q=J_{0}^{\prime\prime}(w_{0})$, $\hat{Q}_{\lambda}=J_{0}^{\prime\prime}(w_{0}+v)$, and $v=\hat{w}_{\lambda}-w_{0}$, we have, using Eq. (22) from Appendix A.2:

All the terms in Eqs. (30,31,32,33) that need to be added to obtain the required upperbound are essentially the same than the ones proof of Theorem 2 in Appendix C (with smaller constants). Thus the rest of the proof follows.

Appendix E Proof of Theorem 4

We directly use Proposition 2 with the function $w_{K}\mapsto\hat{J}_{0}(w_{K},0)+\lambda s_{K}^{\top}w_{K}$—where $(w_{K},0)$ denotes the $p$-dimensional vector obtained by completing $w_{K}$ by zeros—to obtain from Eq. (7):

as soon as $\nu^{2}=(q_{K}-\lambda s_{K})^{\top}Q_{KK}^{-1}(q_{K}-\lambda s_{K})\leqslant\frac{\rho}{4R^{2}}$, and thus as soon as $q_{K}Q_{KK}^{-1}q_{K}\leqslant\frac{\rho}{8R^{2}}$ and $\lambda^{2}s_{K}^{\top}Q_{KK}^{-1}s_{K}\leqslant\frac{\rho}{8R^{2}}$. We thus have:

Note that $s_{K}^{\top}Q_{KK}^{-1}s_{K}\leqslant|K|\rho^{-1}$, thus it is implied by the following constraint:

In terms of upper bound on $\lambda$ we then get:

which can be reduced $\lambda\leqslant\min\left\{\frac{\rho}{4|K|^{1/2}}\mu,\frac{\eta\rho^{3/2}}{64R|K|}\right\}$. In terms of upper bound on $q_{K}^{\top}Q_{KK}^{-1}q_{K}$ we get:

which can be reduced to $q_{K}^{\top}Q_{KK}^{-1}q_{K}\leqslant\min\left\{\frac{\rho}{16}\mu^{2},\frac{\lambda\eta\rho^{1/2}}{64R}\right\}$, using the constraint on $\lambda$.

We now derive and use concentration inequalities. We first use Bernstein’s inequality (using for all $k$ and $i$, $|(x_{i})_{k}-Q_{kK}Q_{KK}^{-1}(x_{i})_{K}||\varepsilon_{i}|\leqslant R/\rho^{1/2}$ and $Q_{kk}\leqslant 1/4$), and the union bound to get

as soon as $R\lambda\eta\rho^{-1/2}\leqslant 3$, i.e., as soon as, $\lambda\leqslant 3\rho^{1/2}R^{-1}$, which is indeed satisfied because of our assumption on $\lambda$. We also use Bernstein’s inequality to get

The union bound then leads to the desired result.

Appendix F Proof of Theorem 5

We follow the proof technique of . We have $\hat{J}_{0}(\hat{w}_{\lambda})=J_{0}(\hat{w}_{\lambda})-q^{\top}\hat{w}_{\lambda}$. Thus, because $\hat{w}_{\lambda}$ is a minimizer of $\hat{J}_{0}(w)+\lambda\|w\|_{1}$,

which implies, since ${J}_{0}(\hat{w}_{\lambda})\geqslant J_{0}(w_{0})$:

If we denote by $\Delta=\hat{w}_{\lambda}-w_{0}$ the estimation error, we deduce:

If we assume $\|q\|_{\infty}\leqslant\lambda/2$, then, we have $\|\Delta_{K^{c}}\|_{1}\leqslant 3\|\Delta_{K}\|_{1}$, and thus using (A5), we get $\Delta^{\top}Q\Delta\geqslant\rho^{2}\|\Delta_{K}\|_{2}^{2}$. From Eq. (38), we thus get:

Using Eq. (3) in Proposition 1 with $J_{0}$, we obtain:

which implies, using $\Delta^{\top}Q\Delta\geqslant\rho^{2}\|\Delta_{K}\|_{2}^{2}$ and Eq. (39):

We can now use, with $s=|K|$, $\|\Delta\|_{2}\leqslant\|\Delta\|_{1}\leqslant 4\|\Delta_{K}\|_{1}\leqslant 4\sqrt{s}\|\Delta_{K}\|_{2}$ to get:

This implies using Eq. (23), that $R\|\Delta\|_{2}\leqslant\frac{48\lambda Rs/\rho^{2}}{1-24\lambda sR/\rho^{2}}\leqslant 2$ a soon as $R\lambda s\rho^{-2}\leqslant 1/48$, which itself implies that \frac{1}{(R\|\Delta\|_{2})^{2}}\big{(}e^{-R\|\Delta\|_{2}}+R\|\Delta\|_{2}-1\big{)}\geqslant 1/2, and thus, from Eq. (40),

Appendix G Concentration inequalities

In this section, we derive concentration inequalities for quadratic forms of bounded random variables that extend the ones already known for Gaussian random variables . The following proposition is a simple corollary of a general concentration result on U-statistics .

Proof We apply Theorem 3.4 from , with $T_{i}=\varepsilon_{i}$, $g_{i,j}(t_{i},t_{j})=y_{i}^{\top}y_{j}t_{i}t_{j}$ if $|t_{i}|,|t_{j}|\leqslant 1$ and zero otherwise. We then have (following notations from ):

Moreover, we have from Bernstein’s inequality :

leading to the desired result, noting that for $u\leqslant\log(8)$, the bound is trivial.

We can apply to our setting to get, with $y_{i}=\frac{1}{n}(P+\lambda I)^{-1/2}x_{i}$ (with $\|x_{i}\|_{2}\leqslant R$), leading to $b=\frac{1}{2}Rn^{-1}\lambda^{-1/2}$ and $S=\frac{1}{n}\mathop{\rm Diag}(\sigma)X(P+\lambda I)^{-1}X^{\top}\mathop{\rm Diag}(\sigma)$.

If no assumptions are made, we simply have: $\lambda_{\max}(S)\leqslant(\mathop{\rm tr}S^{2})^{1/2}\leqslant\mathop{\rm tr}(S)\leqslant R^{2}/\lambda n$ and we get after bringing terms together:

Well-specified models

In this case, $P=Q$ and $\lambda_{\max}(S)\leqslant 1/n$, $\mathop{\rm tr}S=d_{1}/n$, $\mathop{\rm tr}S^{2}=d_{2}/n^{2}$.

Acknowledgements

I would like to thank Sylvain Arlot, Jean-Yves Audibert and Guillaume Obozinski for fruitful discussions related to this work. This work was supported by a French grant from the Agence Nationale de la Recherche (MGA Project ANR-07-BLAN-0311).

References