Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions

Introduction

Many classification and prediction problems are solved in practice by regularized empirical risk minimizers (RERM). The risk is measured by a loss function and the quadratic loss function is the most popular function for regression. It has been extensively studied (cf. among others). Still many other loss functions are popular among practitioners and are indeed extremely useful in specific situations.

First, let us mention the quantile loss in regression problems. The $0.5$-quantile loss (also known as absolute or $L_{1}$ loss) is known to provide an indicator of conditional central tendency more robust to outliers than the quadratic loss. An alternative to the absolute loss for robustification is provided by the Huber loss. On the other hand, general quantile losses are used to estimate conditional quantile functions and are extremely useful to build confidence intervals and measures of risk, like Values at Risk (VaR) in finance.

Let us now turn to classification problems. The natural loss in this context, the so called $0/1$ loss, leads very often to computationally intractable estimators. Thus, it is usually replaced by a convex loss function, such as the hinge loss or the logistic loss. A thorough study of convex loss functions in classification can be found in .

All the aforementioned loss functions (quantile, Huber, hinge and logistic) share a common property: they are Lipschitz functions. This motivates a general study of RERM with any Lipschitz loss. Note that some examples were already studied in the literature: the $\left\|\cdot\right\|_{1}$-penalty with a quantile loss was studied in under the name “quantile LASSO” while the same penalty with the logistic loss was studied in under the name “logistic LASSO” (cf. ). The ERM strategy with Lipschitz proxys of the $0/1$ loss are studied in . The loss functions we will consider in the examples of this paper are reminded below:

The two main theoretical results of the paper, stated in Section 2, are general in the sense that they do not rely on a specific loss function or a specific regularization norm. We develop two different settings that handle different assumptions on the design. In the first one, we assume that the family of predictors is subgaussian; in the second setting we assume that the predictors are uniformly bounded, this setting is well suited for classification tasks, including the 1-bit matrix completion problem. The rates of convergence rely on quantities that measure the complexity of the model and the size of the subdifferential of the norm.

We study many applications that give new insights on diverse problems: the first one is a classification problem with logistic loss and LASSO or SLOPE regularizations. We prove that the rate of the SLOPE estimator is minimax in this framework. The second one is about matrix completion. We derive new excess risk bounds for the 1-bit matrix completion issue with both logistic and hinge loss. We also study the quantile loss for matrix completion and prove it reaches sharp bounds. We show several examples in order to assess the general methods as well as simulation studies. The last example involves the SVM and proves that “classic” regularization method with no special sparsity inducing power can be analyzed in the same way as sparsity inducing regularization methods.

A remarkable fact is that no assumption on the output $Y$ is needed (while most results for the quadratic loss rely on an assumption of the tails of the distribution of $Y$). Neither do we assume any statistical model relating the “output variable” $Y$ to the “input variable” $X$.

Note that we chose a Lipschitz constant equal to one in Assumption 1.1. This can always be achieved by a proper normalization of the loss function. We define the oracle predictor as

and $(X,Y)$ is distributed like the $(X_{i},Y_{i})$’s. The objective of machine learning is to provide an estimator $\hat{f}$ that predicts almost as well as $f^{*}$. We usually formalize this notion by introducing the excess risk ${\cal E}(f)$ of $f\in F$ by

Thus we consider the estimator of the form

For the rest of the paper, we will use the following notations: let $rB$ and $rS$ denote the radius $r$ ball and sphere for the norm $\left\|\cdot\right\|$, i.e. $rB=\{f\in E:\left\|f\right\|\leq r\}$ and $rS=\{f\in E:\left\|f\right\|=r\}$. For the $L_{2}$-norm, we write $rB_{L_{2}}=\{f\in L_{2}:\left\|f\right\|_{L_{2}}\leq r\}$ and $rS_{L_{2}}=\{f\in L_{2}:\left\|f\right\|_{L_{2}}=r\}$ and so on for the other norms.

The notation ${\bf C}$ will be used to denote positive constants, that might change from one instance to the other. For any real numbers $a,b$, we write $a\lesssim b$ when there exists a positive constant ${\bf C}$ such that $a\leq{\bf C}b$. When $a\lesssim b$ and $b\lesssim a$, we write $a\sim b$.

We now present briefly one of the outputs of our global approach: an oracle inequality for the $1$-bit matrix completion problem with hinge loss (we refer the reader to Section 4 for a detailed exposition of this example). While the general matrix completion problem has been extensively studied in the case of a quadratic loss, see and the references therein, we believe that there is no satisfying solution to the so-called $1$-bit matrix completion problem, that is for binary observations ${\cal Y}=\{-1,+1\}$. Indeed, the attempts in to use the hinge loss did not lead to rank dependent learning rates. On the other hand, studied RERM procedure using a statistical modeling approach and the logistic loss. While these authors prove optimal rates of convergence of their estimator with respect to the Frobenius norm, the excess classification risk, is not studied in their paper. However we believe that the essence of machine learning is to focus on this quantity – it is directly related to the average number of errors in prediction.

where $\lambda>0$ is some parameter to be chosen. We prove in Section 4 the following result.

Assume that Assumption 1.2 holds and there is $\tau>0$ such that, for any $(p,q)\in\{1,\dots,m\}\times\{1,\dots,T\}$,

There is a $c_{0}(\underline{c},\bar{c})>0$, that depends only on $\underline{c}$ and $\bar{c}$, and that is formally introduced in Section 4 below, such that if one chooses the regularization parameter

the RERM estimator $\widehat{M}$ defined in (2) satisfies for every $1\leq p\leq 2$,

where the notation ${\bf C}$ is used for constants that might change from one instance to the other but depend only on $\underline{c}$, $\bar{c}$ and $\tau$.

Therefore, the RERM from (2) for the choice of regularization parameter $\lambda$ as in Theorem 1.1 satisfies with probability larger than in (4),

where ${\bf C}$ depends on $c$, $\underline{c}$, $\bar{c}$ and $\tau$. This yields a bound on the average of excess number of mistakes of $\widehat{M}$. To our knowledge such a prediction bound was not available in the literature on the $1$-bit matrix completion problem. Let us compare Theorem 1.1 to the main result in . In , the authors focus on the estimation error $\|\widehat{M}-M^{*}\|_{S_{2}}$, which seems less relevant for practical applications. In order to connect such a result to the excess classification risk, one can use the results in and in this case, the best bound that can be derived is of the order of $\sqrt{\rank(M^{*})\max(m,T)/N}$. Note that other authors focused on the classification error: proved an excess error bound, but the bound does not depend on the rank of the oracle. The rate $\rank(M^{*})\max(m,T)/N$ derived from Theorem 1.1 for the $0/1$-classification excess risk was only reached in , but in the very restrictive noiseless setting, which is equivalent to $\inf_{M}R_{0/1}(M)=0$.

We hope that this example convinced the reader of the practical interest of the general study of $\hat{f}$ in (1). The rest of the paper is organized as follows. In Section 2 we introduce the concepts necessary to the general study of (1): namely, a complexity parameter, and a sparsity parameter. Thanks to these parameters, we define the assumptions necessary to our general results: the Bernstein condition, which is classic in learning theory to obtain fast rates , and a stochastic assumption on $F$ (subgaussian, or bounded). The general results themselves are eventually presented. The remaining sections are devoted to applications of our results to different estimation methods: the logistic LASSO and logistic SLOPE in Section 3, matrix completion in Section 4 and Support Vector Machines (SVM) in Section 5. For matrix completion, the optimality of the rates for the logistic and the hinge loss, that were not known, is also derived. In Section 6 we discuss the Bernstein condition for the three main loss functions of interest: hinge, logistic and quantile.

Theoretical Results

The two main theorems in Sections 2.5 and 2.6 below are general in the sense that they allow the user to deal with any (nonnegative) Lipschitz loss function and any norm for regularization, but they involve quantities that depend on the loss and the norm. The aim of this Section is first to provide the definition of these objects and some hints on their interpretation, through examples. The theorems are then stated in both settings. Basically, the assumptions for the theorems are of three types:

a stochastic assumption on the distribution of the $f(X)$’s for $f\in F$. In this work, we consider both a subgaussian assumption and a uniform boundedness assumption. Analysis of the two setups differ only on the way the “statistical complexity of $F$” is measured (cf. below the functions $r(\cdot)$ in Definition 8.1 and Definition 8.2).

finally, we introduce a sparsity parameter as in . It reflects how the norm $\|\cdot\|$ used as a regularizer can induce sparsity - for example, think of the “sparsity inducing power” of the $l_{1}$-norm used to construct the LASSO estimator.

Application of the main results 1. find the Bernstein parameter $\kappa\geq 1$ and $A>0$ associated to the loss and the class $F$; 2. compute the Complexity function $r(\rho)=\left[\frac{A\rho{\rm comp}(B)}{\sqrt{N}}\right]^{1/2\kappa}$ where ${\rm comp}(B)$ is defined either through the Gaussian mean width $w(B)$, in the subgaussian case, or the Rademacher complexity ${\rm Rad}(B)$, in the bounded case; 3. Compute the sub-differential $\partial\left\|\cdot\right\|(f^{*})$ of $\left\|\cdot\right\|$ at the oracle $f^{*}$ (or in the neighborhood $f^{*}+(\rho/20)B$ for approximately sparse oracles) and solve the sparsity equation “find $\rho^{*}$ such that $\Delta(\rho^{*})\geq 4\rho^{*}/5$”. 4. Apply Theorem 2.1 in the subgaussian framework and Theorem 2.2 in the bounded framework. In each case, with large probability, $\left\|\hat{f}-f^{*}\right\|\leq\rho^{*}\text{, }\left\|\hat{f}-f^{*}\right\|_{L_{2}}\leq r(2\rho^{*})\text{ and }\mathcal{E}(\hat{f})\leq{\bf C}\left[r(2\rho^{*})\right]^{2\kappa}.$ For the sake of simplicity, we present the two settings in different subsections with both the exact definition of the complexity function and the theorem. As the sparsity equation is the same in both settings, we define it before even though it involves the complexity function.

2 The Bernstein condition

The first assumption needed is called Bernstein assumption and is very classic in order to deal with Lipschitz loss.

There exists $\kappa\geq 1$ and $A>0$ such that for every $f\in F$, $\left\|f-f^{*}\right\|_{L_{2}}^{2\kappa}\leq AP{\cal L}_{f}$.

The most important parameter is $\kappa$ and will be involved in the rate of convergence. As usual fast rates will be derived when $\kappa=1$. In many situations, this assumption is satisfied and we present various cases in Section 6. In particular, we prove that it is satisfied with $\kappa=1$ for the logistic loss in both bounded and Gaussian framework, and we exhibit explicit conditions to ensure that Assumption 2.1 holds for the hinge and the quantile loss functions.

The careful reader will actually realize that the proof of Theorem 2.1 and Theorem 2.2 requires only a weaker version of this assumption, that is: there exists $\kappa\geq 1$ and $A>0$ such that for every $f\in\mathcal{C}$, $\left\|f-f^{*}\right\|_{L_{2}}^{2\kappa}\leq AP{\cal L}_{f}$, where $\mathcal{C}$ is defined in terms of the complexity function $r(\cdot)$ and the sparsity parameter $\rho^{*}$ to be defined in the next subsections,

Note that the set ${\cal C}$ appears to play a central role in the analysis of regularization methods, cf. . However, in all the examples presented in this paper, we prove that the Bernstein condition holds on the entire set $F$.

3 The complexity function r⁡(⋅)r(\cdot)

The complexity function $r(\cdot)$ is defined by

where $A$ is the constant in Assumption 2.1 and where ${\rm comp}(B)$ is a measure of the complexity of the unit ball $B$ associated to the regularization norm. Note that this complexity measure will depend on the stochastic assumption of $F$. In the bounded setting, ${\rm comp}(B)=C{\rm Rad}(B)$ where $C$ is an absolute constant and ${\rm Rad}(B)$ is the Rademacher complexity of $B$ (whose definition will be reminded in Subsection 2.6). In the subgaussian setting, ${\rm comp}(B)=CLw(B)$ where $C$ is an absolute constant, $L$ is the subgaussian parameter of the class $F-F$ and $w(B)$ is the Gaussian mean-width of $B$ (here again, exact definitions of $L$ and $w(B)$ will be reminded in Subsection 2.5).

Note that sharper (localized) versions of $r(\cdot)$ are provided in Section 8. However, as it is the simplest version that is used in most examples, we only introduce this version for now.

4 The sparsity parameter ρ∗\rho^{*}

The size of the sub-differential of the regularization function $\left\|\cdot\right\|$ in a neighborhood of the oracle $f^{*}$ will play as well a central role in our analysis. We recall now its definition: for every $f\in F$

It is well-known that $\partial\left\|\cdot\right\|(f)$ is a subset of the unit sphere of the dual norm of $\left\|\cdot\right\|$ when $f\neq 0$. Note also that when $f=0$, $\partial\left\|\cdot\right\|(f)$ is the entire unit dual ball, a fact we will also use in two situations, either when the regularization norm has no “sparsity inducing power” – in particular, when it is a smooth function as in the RKHS case treated in Section 5; or when one wants extra norm dependent upper bounds (cf. for more details where these bounds are called complexity dependent) in addition to sparsity dependent upper bounds. In the latter, the statistical bounds that we get are the minimum between an error rate that depends on the notion of sparsity naturally associated to the regularization norm (when it exists) and an error rate that depends on $\left\|f^{*}\right\|$.

The sparsity parameter is the function $\Delta(\cdot)$ defined by

where $\Gamma_{f^{*}}(\rho)=\bigcup_{f\in f^{*}+(\rho/20)B}\partial\left\|\cdot\right\|(f)$.

Note that there is a slight difference with the definition of the sparsity parameter from where there $\Delta(\rho)$ is defined taking the infimum over the sphere $\rho S$ intersected with a $L_{2}$-ball of radius $r(\rho)$ whereas in Definition 2.1, $\rho S$ is intersected with a $L_{2}$-ball of radius $r(2\rho)$. Up to absolute constants this has no effect on the behavior of $\Delta(\rho)$ and the difference comes from technical detains in our analysis (a peeling argument that we use below whereas a direct homogeneity argument was enough in ).

In the following, estimation rates with respect to the regularization norm $\left\|\cdot\right\|$, the norm $\left\|\cdot\right\|_{L_{2}}$ as well as sharp oracle inequalities are given. All the convergence rates depend on a single radius $\rho^{*}$ that satisfies the sparsity equation as introduced in .

The radius $\rho^{*}$ is any solution of the sparsity equation:

Since $\rho^{*}$ is central in the results and drives the convergence rates, finding a solution to the sparsity equation will play an important role in all the examples that we worked out in the following. Roughly speaking, if the regularization norm induces sparsity, a sparse element in $f^{*}+(\rho/20)B$ (that is an element $f$ for which $\partial\left\|\cdot\right\|(f)$ is almost extremal – that is almost as large as the dual sphere) yields the existence of a small $\rho^{*}$. In this case, $\rho^{*}$ satisfies the sparsity equation.

In addition, if one takes $\rho=20\left\|f^{*}\right\|$ then $0\in\Gamma_{f^{*}}(\rho)$ and since $\partial\left\|\cdot\right\|(0)$ is the entire dual ball associate to $\left\|\cdot\right\|$, one has directly that $\Delta(\rho)=\rho$ and so $\rho$ satisfies the sparsity Equation (8). We will use this observation to obtain norm dependent upper bounds, i.e. rates of convergence depending on $\left\|f^{*}\right\|$ and that do not depend on any sparsity parameter. Such a bound holds for any norm; in particular, for norms with no sparsity inducing power as in Section 5.

5 Theorem in the subgaussian setting

First, we introduce the subgaussian framework (then we will turn to the bounded case in the next section).

We say that a class of functions $\mathcal{F}$ is $L$-subgaussian (w.r.t. $X$) for some constant $L\geq 1$ when for all $f\in\mathcal{F}$ and all $\lambda\geq 1$,

We will use the following operations on sets: for any $F^{\prime}\subset E$ and $f\in E$,

Note that there are many equivalent formulations of the subgaussian property of a random variable based on $\psi_{2}$-Orlicz norms, deviations inequalities, exponential moments, moments growth characterization, etc. (cf., for instance Theorem 1.1.5 in ). The one we should use later is as follows: there exists some absolute constant ${\bf C}$ such that $F-F$ is $L$-subgaussian if and only if for all $f,g\in F$ and $t\geq 1$,

for $2\leq q<\infty$, $X$ is uniformly distributed over $p^{1/q}B_{l_{q}}$ (cf. ),

In the subgaussian framework, a natural way to measure the statistical complexity of the problem is via Gaussian mean-width that we introduce now.

We refer the reader to Section 12 in for the construction of Gaussian processes in $L_{2}$. There are many natural situations where Gaussian mean-widths can be computed. To familiarize with this quantity let us consider an example in the matrix framework. Let $H=\{\bigl<M,\cdot\bigr>:\left\|M\right\|_{S_{1}}\leq 1\}$ be the class of linear functionals indexed by the unit ball of the $S_{1}$-norm and $d$ be the distance associated with the Frobenius norm (i.e. $d(\bigl<\cdot,M_{1}\bigr>,\bigl<\cdot,M_{2}\bigr>)=d(M_{1},M_{2})=\left\|M_{1}-M_{2}\right\|_{S_{2}}$) then

We are now in position to define the complexity parameter as announced previously.

The complexity parameter is the non-decreasing function $r(\cdot)$ defined for every $\rho\geq 0$,

where $\kappa,A$ are the Bernstein parameters from Assumption 2.1, $L$ is the subgaussian parameter from Assumption 2.2 and $C>0$ is an absolute constant (the exact value of $C$ can be deduced from the proof of Proposition 8.2). The Gaussian mean-width $w(B)$ of $B$ is computed with respect to the the metric associated with the covariance structure of $X$, i.e. $d(f_{1},f_{2})=\left\|f_{1}-f_{2}\right\|_{L_{2}}$ for every $f_{1},f_{2}\in F$.

After the computation of the Bernstein parameter $\kappa$, the complexity function $r(\cdot)$ and the radius $\rho^{*}$, it is now possible to explicit our main result in the sub-Gaussian framework.

Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.2 hold and let $C>0$ from the definition of $r(\cdot)$ in Definition 2.5. Let the regularization parameter $\lambda$ be

and $\rho^{*}$ satisfying (8). Then, with probability larger than

where ${\bf C}$ denotes positive constants that might change from one instance to the other and depend only on $A$, $\kappa$, $L$ and $C$.

Replacing $w(B)$ by any upper bound does not affect the validity of the result. As a special case, it is possible to increase the confidence level of the bound by replacing $w(B)$ by $w(B)+x$: then, with probability at least

Theorem 2.1 holds for any radius $\rho^{*}$ satisfying the sparsity equation (8). We have noticed in Section 2.4 that $\rho^{*}=20\left\|f^{*}\right\|$ satisfies the sparsity equation since in that case $0\in\Gamma_{f^{*}}(\rho^{*})$ and so $\Delta(\rho^{*})=\rho^{*}$. Therefore, one can apply Theorem 2.1 to both $\rho^{*}=20\left\|f^{*}\right\|$ (this leads to norm dependent upper bounds) and to the smallest $\rho^{*}$ satisfying the sparsity equation (8) (this leads to sparsity dependent upper bounds) at the same time. Both will lead to meaningful results (a typical example of such a combined result is Theorem 9.2 from or Theorem 3.1 below).

6 Theorem in the bounded setting

We now turn to the bounded framework; that is we assume that all the functions in $F$ are uniformly bounded in $L_{\infty}$. This assumption is very different in nature than the subgaussian assumption which is in fact a norm equivalence assumption (i.e. Definition 2.3 is equivalent to $\left\|f\right\|_{L_{2}}\leq\left\|f\right\|_{\psi_{2}}\leq L\left\|f\right\|_{L_{2}}$ for all $f\in{\cal F}$ where $\left\|\cdot\right\|_{\psi_{2}}$ is the $\psi_{2}$ Orlicz norm, cf. ).

There exist a constant $b>0$ such that for all $f\in F$, $\left\|f\right\|_{L_{\infty}}\leq b$.

Under the boundedness assumption, the natural way to measure the ”statistical complexity” cannot be anymore characterized by Gaussian mean width. We therefore introduce another complexity parameter known as Rademacher complexities. This complexity measure has been extensively studied in the learning theory literature (cf., for instance, ).

Note that when $(f(X))_{f\in H}$ is a version of the isonormal process over $L_{2}$ (cf. Chapter 12 in ) restricted to $H$ then the Gaussian mean-width and the Rademacher complexity coincide: $w(H)={\rm Rad}(H)$. But, in that case, $H$ is not bounded in $L_{\infty}$ and, in general, the two complexity measures are different.

There are many examples where Rademacher complexities have been computed (cf. ). Like in the previous subgaussian setting the statistical complexity is given by a function $r(\cdot)$ (we use the same name in the two bounded and subgaussian setups because this $r(\cdot)$ function plays exactly the same role in both scenarii even though it uses different notion of complexity).

The complexity parameter is the non-decreasing function $r(\cdot)$ defined for every $\rho\geq 0$ by

Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.3 hold. Let the regularization parameter $\lambda$ be chosen as $\lambda=720{\rm Rad}(B)/7\sqrt{N}$. Then, with probability larger than

where ${\bf C}$ denotes positive constants that might change from one instance to the other and depend only on $A$, $b$, $\kappa$ and $r(\cdot)$ is the function introduced in Definition 2.7.

In the next Sections 3, 4 and 5 we compute $r(\rho)$ either in the subgaussian setup or in the bounded setup and solve the sparsity equation in various examples, showing the versatility of the main strategy.

Application to logistic LASSO and logistic SLOPE

The first example of application of the main results in Section 2 involves one very popular method developed during the last two decades in binary classification which is the Logistic LASSO procedure (cf. ).

In this section, we consider the class of linear functional indexed by $RB_{l_{2}}$ for some radius $R\geq 1$ and the logistic loss:

where $\lambda$ is a regularization parameter to be chosen according to Theorem 2.1.

The two final ingredients needed to apply Theorem 2.1 are 1) the computation of the Gaussian mean width of the unit ball $B_{l_{1}}$ of the regularization function $\left\|\cdot\right\|_{l_{1}}$ 2) find a solution $\rho^{*}$ to the sparsity equation (8).

for the complexity parameter of the problem (from now and until the end of Section 3, the constants ${\bf C}$ depends only on $L$, $C$, $c_{0}$ and $c_{1}$).

Now let us turn to a solution $\rho^{*}$ of the sparsity equation (8). First note that when the design is isotropic the sparsity parameter is the function

where $\Gamma_{t^{*}}(\rho)=t^{*}+(\rho/20)B_{l_{1}}$.

A first solution to the sparsity equation is $\rho^{*}=20\left\|t^{*}\right\|_{l_{1}}$ because it leads to $0\in\Gamma_{t^{*}}(\rho^{*})$. This solution is called norm dependent.

If there exists some $v\in t^{*}+(\rho/20)B_{l_{1}}$ such that $\left\|v\right\|_{0}\leq c_{0}(\rho/r(\rho))^{2}$ then $\Delta(\rho)\geq 4\rho/5$ where $c_{0}$ is an absolute constant.

In particular, we get that $\rho^{*}\sim s\sqrt{(\log p)/N}$ is a solution to the sparsity equation if there is a $s$-sparse vector which is $(\rho^{*}/20)$-close to $t^{*}$ in $l_{1}$. This radius leads to the so-called sparsity dependent bounds.

After the derivation of the Bernstein parameter $\kappa=1$, the complexity $w(B)$ and a solution $\rho^{*}$ to the sparsity equation, we are now in a position to apply Theorem 2.1 to get statistical bounds for the Logistic LASSO.

and the excess logistic risk of $\widehat{t_{L}}$ is such that

Note that an estimation result for any $l_{q}$-norm for $1\leq q\leq 2$ follows from results in $l_{1}$ and $l_{2}$ and the interpolation inequality $\left\|v\right\|_{l_{q}}\leq\left\|v\right\|_{l_{1}}^{-1+2/q}\left\|v\right\|_{l_{2}}^{2-2/q}$.

Note that Theorem 3.1 recovers the classic rates of convergence for the logistic LASSO estimator that have been obtained in the literature so far. This rates is the minimax rate as long as $\log(p/s)$ behaves like $\log p$. This is indeed the case when $s\ll p$ which is the classic setup in high-dimensional statistics. But when $s$ is proportional to $p$ this rate is not minimax since there is a logarithmic loss. To overcome this issue we introduce a new estimator: the logistic SLOPE.

2 Logistic Slope

where $t_{1}^{\sharp}\geq t_{2}^{\sharp}\geq\cdots\geq 0$ is the non-increasing rearrangement of the absolute values of the coordinates of $t$ and $e$ is the base of the natural logarithm. Using this estimator with a regularization parameter $\lambda\sim 1/\sqrt{N}$ we recover the same result as for the Logistic LASSO case except that one can get, in that case, the optimal minimax rate for any $s\in\{1,\ldots,p\}$:

Indeed, it follows from Lemma 5.3 in that the Gaussian mean width of the unit ball $B_{SLOPE}$ associated with the SLOPE norm is of the order of a constant. The sparsity dependent radius satisfies

as long as there is a $s$-sparse vector in $t^{*}+(\rho^{*}/20)B_{SLOPE}$. The norm dependent radius is as usual of order $\left\|t^{*}\right\|_{SLOPE}$. Then, the next result follows from Theorem 2.1. It improves the best known bounds on the logistic LASSO.

and the excess logistic risk of $\widehat{t_{S}}$ is such that

Application to matrix completion via S1S_{1}-regularization

The second example involves matrix completion and uses the bounded setting from Section 2.6. The goal is to derive new results on two ways: the 1-bit matrix completion problem where entries are binary, and the quantile completion problem. The main theorems in this section yield upper bounds on completion in $S_{p}$ norms ($1\leq p\leq 2$) and on various excess risks. We also propose algorithms in order to compute efficiently the RERM in the matrix completion issue but with non differentiable loss and provide a simulation study. We first present a general theorem and then turn to specific loss functions because they induce a discussion about the Bernstein assumption and the $\kappa$ parameter and lead to more particular theorems.

where $\left\|\cdot\right\|_{S_{\infty}}$ is the operator norm (i.e. the largest singular value), the last inequality follows from Lemma 1 in and $c_{0}(\underline{c},\bar{c})>0$ is some constant that depends only on $\underline{c}$ and $\bar{c}$.

The complexity parameter $r(\cdot)$ is derived from Definition 2.7: for any $\rho\geq 0$,

where from now the constants ${\bf C}$ depend only on $\underline{c}$, $\bar{c}$, $b$, $A$ and $\kappa$.

The next important quantity is the sparsity parameter. Its expression in this particular case is, for any $\rho>0$,

There exists an absolute constant $c_{1}>0$ for which the following holds. If there exists $V\in M^{*}+(\rho/20)B_{S_{1}}$ such that ${\rm rank}(V)\leq\left(c_{1}\rho/(\sqrt{mT}r(\rho))\right)^{2}$ then $\Delta(\rho)\geq 4\rho/5$.

It follows from Lemma 4.1 that the sparsity equation (8) is satisfied by $\rho^{*}$ when it exists $V\in M^{*}+(\rho^{*}/20)B_{S_{1}}$ such that $\rank(V)=c_{1}\left(\rho^{*}/(\sqrt{mT}r(\rho^{*}))\right)^{2}$. Note obviously that $V$ can be $M^{*}$ itself, in this case, $\rho^{*}$ can be taken such that $\rank(M^{*})=c_{1}\left(\rho^{*}/(\sqrt{mT}r(\rho^{*}))\right)^{2}$. However, when $M^{*}$ is not low-rank, it might still be that a low-rank approximation $V$ of $M^{*}$ is close enough to $M^{*}$ w.r.t. the $S_{1}$-norm. As a consequence, if for some $s\in\{1,\ldots,\min(m,T)\}$ there exists a matrix $V$ with rank at most $s$ in $M^{*}+(\rho_{s}^{*}/20)B_{S_{1}}$ where

then $\rho_{s}^{*}$ satisfies the sparsity equation.

Following the remark at the end of Subsection 2.4, another possible choice is $\rho^{*}=20\|M^{*}\|_{S_{1}}$ in order to get norm dependent rates. In the end, we choose $\rho^{*}={\bf C}\min\left[\rho_{s}^{*},\|M^{*}\|_{S_{1}}\right]$. We are now in a position to apply Theorem 2.2 to derive statistical properties for the RERM $\widehat{M}$ defined in (16).

Assume that Assumption 1.1, 1.2 and 2.1 hold. Consider the estimator in (16) with regularization parameter

where $c_{0}(\underline{c},\bar{c})$ are the constants in Assumption 1.2. Let $s\in\{1,\ldots,\min(m,T)\}$ and assume that there exists a matrix with rank at most $s$ in $M^{*}+(\rho^{*}_{s}/20)B_{S_{1}}$. Then, with probability at least

Note that the interpolation inequality also allows to get a bound for the $S_{p}$ norm, when $1\leq p\leq 2$:

Theorem 4.1 shows that the sparsity dependent error rate in the excess risk bound is (for $s={\rm rank}(M^{*})$)

which is the classic excess risk bound under the margin assumption up to a log factor (cf. ). As for the $S_{2}$-estimation error, when $\kappa=1$, we recover the classic $S_{2}$-estimation rate

which is minimax in general (up to log terms, e.g. take the quadratic loss when $Y$ is bounded and compare to ).

2 Algorithm and Simulation Outlines

Since this part provides new methods and results on matrix completion, we propose an algorithm in order to compute efficiently the RERM using the hinge loss and the quantile loss. This section explains the structure of the algorithm that is used with specific loss functions in next sections. Although many algorithms exist for the least squares matrix completion, at our knowledge many of them treat only the exact recovery such as in and , or at least they all deal with differentiable loss functions, see . On the other hand, the two losses that we mainly consider here are non differentiable because they are piecewise linear (in the case of hinge and $0,5$-quantile loss functions): new algorithms are hence needed. It has been often noted that the RERM with respect to the hinge loss or $0.5$-quantile loss can been solved by a semidefinite programming but the cost is prohibitive for large matrices, say dimensions larger than $100$. It actually works for small matrices as we ran SDP solver in Python in very small examples.

We propose here an alternating direction method of multiplier (ADMM) algorithm. For a clear and self-contained introduction to this class of algorithms, the reader is referred to and we do not explain all the details here and we keep the same vocabulary. When the optimization problem is a sum of two parts, the core idea is to split the problem by introducing an extra variable. In our case, the two following problems are equivalent:

Below, we use the scaled form and the $m\times T$ matrix $U$ is then called the scaled dual variable. Note that the $S_{2}$ norm is also the Froebenius norm and is thus elementwise. We can now exhibit the augmented Lagrangian:

where $\alpha$ is a positive constant, called the augmented Lagrange parameter. The ADMM algorithm is then:

The starting point $(M^{0},L^{0},U^{0})$ uses one random matrix with independent Gaussian entries for $M^{0}$ and two zero matrices for $L^{0}$ and $U^{0}$. Another choice of starting point is to use a previous estimator with a larger $\lambda$. The stopping criterion is, as explained in , $\left\|M^{k+1}-M^{k}\right\|_{S_{2}}^{2}+\left\|U^{k+1}-U^{k}\right\|_{S_{2}}^{2}\leq\varepsilon$ for a fixed threshold $\varepsilon$. It means that it stops when both $(U_{k})$ and $(M_{k})$ start converging.

The second step (22) is independent of the loss function. It is well-known that the solution of this problem is $S_{\lambda/\alpha}(M^{k+1}+U^{k})$ when $S_{a}(M)$ is the soft-thresholding operator with magnitude $a$ applied to the singular values of the matrix $M$. It is defined for a rank $r$ matrix M with SVD $M=U\Sigma V^{\top}$ where $\Sigma=\textrm{diag}\left(\left(d_{i}\right)_{1\leq i\leq r}\right)$ by $S_{a}(M)=US_{a}(\Sigma)V^{\top}$ where $S_{a}(\Sigma)=\textrm{diag}\left(\left(\max(0,d_{i}-a)\right)_{1\leq i\leq r}\right)$.

Moreover, the first step (21) (which may be performed elementwise) has a closed form solution for hinge and quantile loss: it is a soft-thresholding applied to a specified quantity.

Simulated observations as well as real-world data (cf. the MovieLens dataset available in http://grouplens.org/datasets/movielens/) are considered in the examples below. Finally note that parameter $\lambda$ is tuned by cross-validation.

3 11-bit matrix completion

Assume that Assumption 1.2 holds. Let $s\in\{1,\ldots,\min(m,T)\}$ and assume that there exists a matrix with rank at most $s$ in $M^{*}+(\rho^{*}_{s}/20)B_{S_{1}}$ where $\rho^{*}_{s}$ is defined in (19). With probability at least

with $\lambda$ as in Equation (20) satisfies

Using an interpolation inequality, it is easy to derive estimation bound in $S_{p}$ for all $1\leq p\leq 2$ as in Theorem 4.1 so we do not reproduce it here. Also, note that our bound on $\left\|\widehat{M}-M^{*}\right\|_{S_{2}}$ is of the same order as the one in . We actually now prove that this rate is minimax-optimal (up to log terms).

for some universal constants $\beta,c>0$.

But this rate on the excess $0/1$-risk may be much better under the margin assumption (cf. Equation (36) below). This motivates the use of the hinge loss instead of the logistic loss, for which the results in do not lead to a loss of a square root in the rate.

As explained above, the choice $b=1$ ensures $\overline{M}=M^{*}$ without additional assumption. Thanks to Proposition 6.3 we know that as soon as $\inf_{p,q}|\overline{M}_{p,q}-1/2|\geq\tau$ for some $\tau>0$, the Bernstein assumption is satisfied by the hinge loss with $\kappa=1$ and $A=1/(2\tau)$. This assumption seems very mild in many situations and we derive the results with it.

Assume that Assumption 1.2 holds. Assume that $\inf_{p,q}|P(Y=1|X=E_{p,q})-1/2|\geq\tau$ for some $\tau>0$. Let $s\in\{1,\ldots,\min(m,T)\}$ and assume that there exists a matrix with rank at most $s$ in $\overline{M}+(\rho^{*}_{s}/20)B_{S_{1}}$ where $\rho^{*}_{s}$ is defined in (19). With probability at least

with $\lambda$ as in Equation (20) satisfies

In this case, implies that the excess risk bound for the classification error (using the $0/1$-loss) is the same as the one for the hinge loss: it is therefore of the order of $\rank(\overline{M})\max(m,T)/N$.

Note that the rate $\rank(\overline{M})\max(m,T)/N$ for the classification excess error was only reached in up to our knowledge (using the PAC-Bayesian technique from ), in the very restrictive noiseless setting - that is, $P(Y=1|X=E_{p,q})\in\{0,1\}$ which is equivalent to $P(Y={\rm sign}(\bigl<\overline{M},X\bigr>)=1$. Here this rate is proved to hold in the general case. Other works, including , obtained only rates in $1/\sqrt{N}$. Finally, we prove that this rate is the minimax rate in the next result.

Theorem 4.5 provides a minimax lower bound in expectation whereas Theorem 4.4 provides an excess risk bound with large deviation. The two residual terms of the excess hinge risk from Theorem 4.5 and Theorem 4.4 match up to the $\log(m+T)$ factor.

As the hinge loss has not been often studied in the matrix context, we provide many simulations in order to show the robustness of our method and the opportunity of using the hinge loss rather than the logistic loss. We follow the simulations ran in and compare several methods. An estimator based on the logistic model, studied in , is also challenged In the followings, the four estimators will be referred to Hinge for estimator given in (24), Hinge Bayes and Logit Bayes for the two Bayesian estimators from with respectively hinge and logistic loss functions, and Logit for the estimator from . The Bayesian estimators use the Gammma prior distribution..

Two different scenarios are tested: the first one (called A), involves a matrix $M^{\star}$ with only entries in $\{-1,+1\}$ so the Bayes classifier is low rank and favors the hinge loss. The second test (called B) involves a matrix $M^{\star}=LR^{\top}$ where $L,R$ have i.i.d. Gaussian entries and the rank is the number of columns. In this case, the Bayes matrix contains the signs of a low-rank matrix, but it is not itself low rank in general. We also test the impact of the noise structure on the results:

(noiseless) $Y_{i}={\rm sign}(\bigl<M^{\star},X_{i}\bigr>)$

(logistic) $Y_{i}={\rm sign}(\bigl<M^{\star},X_{i}\bigr>+Z_{i})$, where $Z_{i}$ follows a logistic distribution

(switch) $Y_{i}=\epsilon_{i}{\rm sign}(\bigl<M^{\star},X_{i}\bigr>)$ where $\epsilon_{i}=(1-p)\delta_{1}+p\delta_{-1}$

Finally, we run all the simulations on rank $3$ and rank $5$ matrices. $\lambda$ is tuned by cross validation. All the simulations are run one time.

The results are very similar among the methods, see Table 2. The logistic loss performs better for matrices of type B and especially for high level of noise in the logistic data generation as expected. For type A matrices, the hinge loss performs slightly better. The Bayesian models performs as good as the frequentist estimators even though the program solved is not convex.

The second experiment is a focus on the switch noise and matrices that are well separated (as A2 in the previous example). The noise lies between $p=0$ and almost full noise ($p=.4$). The performance of the RERM with the hinge loss is slightly worse than the Bayesian estimator with hinge loss but always better than the RERM with the logistic loss, see Figure 2.

We finally run the hinge loss estimator on the MovieLens dataset. The ratings, that lie in $\{1,2,3,4,5\}$, are split between good ratings ($4,5$) and bad ratings (others). The goal is therefore to predict whether the user will like a movie or not. On a test set that contains $20\%$ of the data, the misclassification rate in prediction are almost the same for all the methods (Table 3).

4 Quantile loss and median matrix completion

The following result studies a particular case in which the Bernstein Assumption is proved in Proposition 6.4. Following , it assumes that the conditional distribution of $Y$ given $X$ is continuous and that the density is not too small on the domain of interest – this ensures that Bernstein’s condition is satisfied with $\kappa=1$ and $A$ depending on the lower bound on the density, see Section 6 for more details. It can easily be derived for a specific distribution such as Gaussian, Student and even Cauchy. But we also have to assume that $\overline{M}\in bB_{\infty}$, or in other words $\overline{M}=M^{*}$, which is a more stringent assumption: in practice, it meands that we should know a priori an upper bound $b$ on the quantiles to be estimated.

Assume that Assumption 1.2 holds. Let $b>0$ and assume that $\overline{M}\in bB_{\infty}$. Assume that for any $(p,q)$, $Y|X=E_{p,q}$ has a density with respect to the Lebesgue measure, $g$, and that $g(u)>1/c$ for some constant $c>0$ for any $u$ such that $|u-\overline{M}_{i,j}|\leq 2b$. Let $s\in\{1,\ldots,\min(m,T)\}$ and assume that there exists a matrix with rank at most $s$ in $\overline{M}+(\rho^{*}_{s}/20)B_{S_{1}}$ where $\rho^{*}_{s}$ is defined in (19). Then, with probability at least

with $\lambda=c_{0}(\underline{c},\bar{c})\sqrt{\log(m+T)/(N\min(m,T))}$ satisfies

We obtain the same rate as for the penalized least squares estimator that is $\sqrt{s(m+T)\log(m+T)/N}$ (cf. ).

The goal of this part is to challenge the regularized least squares estimator by the RERM with quantile loss. The quantile used here is therefore the median. The main conclusion of our study is that median based estimators are more robust to outliers and noise than mean based estimators. We first test them on simulated datasets and then turn to use a real dataset.

The observations come from a base matrix $M^{\star}$ which is a $200\times 200$ low rank matrix. It is built by $M^{\star}=LR^{\top}$ where the entries of $L,R$ are i.i.d. gaussian and $L,R$ have $3$ columns (and therefore, the rank of $M^{\star}$ is $3$). The $X_{i}$’s correspond to $20\%$ randomly picked entries. The criterion that we retain is the $l_{1}$ reconstruction of $M^{\star}$ that is: $1/mT\sum_{p,q}|M^{\star}_{p,q}-M_{p,q}|$.

The observations are made according to this flexible model:

$z_{i}$ is the noise, $o$ is the magnitude of outliers and $\zeta_{i}$ is the outlier indicator parametrized by the share $p$ such that $\zeta_{i}=p/2\delta_{-1}+(1-p)\delta_{0}+p/2\delta_{1}$. The different parameters for the different scenarios are summarized in Table 4.

On the first experiment, $p$ is fixed to $10\%$ and the magnitude $o$ increases. As expected for least squares, the results are better for low magnitude of outliers (it corresponds to the penalized maximum likelihood estimator), see Figure 5. Quickly, the performance of the least squares estimator is getting worse and when the outliers are large enough, the best least squares predictor is a matrix with null entries. In opposite to this estimator, the median of the distribution is almost not affected by outliers and it is completely in line with the results: the performances are strictly the same for mid-range to high-range magnitude of outliers. The robustness of the quantile reconstruction is totally independent to the magnitude of the outliers.

A second experiment involves fixed magnitude of outliers but the share of them increases, see Figure 5. The median completion is, as expected, more robust and the results deteriorate less than the ones from least squares. When the outliers ratio is greater than $20\%$, the least squares estimator completely fails while the median completion still works.

The third simulation involves non gaussian noise without outliers: we use the t-distribution, that has heavy tails. In this challenge, a lower degree of freedom involves heavier tails and the worst case is for Student distribution with degree $1$. We can see that the least squares is inadequate for small degrees of freedom ($1$ to $2$) and behaves better than the median completion for larger degrees of freedom, see Figure 5.

The last experiment involves the MovieLens dataset. We keep one fifth of the sample for test set to check the prediction accuracy. Even though the least squares estimator remains very efficient in the standard case, see Table 5, the results are quite similar for the MAE criterion. In a second step, we add artificial outliers. In order to do that, we change $20\%$ of $5$ ratings to $1$ ratings. It can be seen as malicious users that change ratings in order to distort the perception of some movies. As expected, it depreciates the least squares estimator performance but the median estimator returns almost as good performances as in the standard case.

Kernel methods via the hinge loss and a RKHS-norm regularization

In this section, we consider regularization methods in some general Reproducing Kernel Hilbert Space (RKHS) (cf. , Chapter 4 in or Chapter 3 of for general references on RKHS).

Unlike the previous examples, the regularization norm here, which is the norm $\left\|\cdot\right\|_{{\cal H}_{K}}$ of a RKHS ${\cal H}_{K}$, is not associated with some ”hidden” concept of sparsity. In particular, RKHS norms have no singularity since they are differentiable at any point except in $0$. As a consequence the sparsity parameter $\Delta(\rho)$ cannot be larger than $4\rho/5$, i.e. $\rho$ does not satisfy the sparsity equation, unless the set $\Gamma_{f^{*}}(\rho)$ contains $0$ that is for $\rho\geq 20\left\|f^{*}\right\|_{{\cal H}_{K}}$. Indeed, one key observation is that any norm is non differentiable at $0$ and that its subdifferential at $0$ is somehow extremal:

where $\left\|\cdot\right\|_{*}$ is the dual norm.

As a consequence, the rates obtained in this section do not depend on some hidden sparsity parameter associated with the oracle $f^{*}$ but on the RKHS norm at $f^{*}$, that is $\left\|f^{*}\right\|_{{\cal H}_{K}}$. The aim of this section is therefore to show that our main results apply beyond “sparsity inducing regularization methods” by showing that “classic” regularization method, inducing smoothness for instance, may also be analyzed the same way and fall into the scope of Theorem 2.1 and Theorem 2.2. This section also shows an explicit expression for the Gaussian mean-width with localization as used in Definition 8.1 (a sharper way to measure statistical complexity via a local $r(\cdot)$ function provided below).

The core idea behind kernel methods is to transport the design data $X_{i}$’s from ${\cal X}$ to a Hilbert space via the application $x\to K(x,\cdot)$ and then construct statistical procedures based on the ”transported” dataset $(K(X_{i},\cdot),Y_{i})_{i=1}^{N}$. The advantage of doing so is that the space where the $K(X_{i},\cdot)$’s belong have much structure than the initial set ${\cal X}$ which may have no algebraic structure at all. The first thing to set is to define somehow the ”smallest” Hilbert space containing all the functions $x\to K(x,\cdot)$. We recall now one classic way of doing so that will be used later to define the objects that need to be considered in order to construct RERM in this setup and to obtain estimation rates for them via Theorem 2.1 and Theorem 2.2.

The reproducing kernel Hilbert space ${\cal H}_{K}$ is the set of all function series $\sum_{i=1}^{\infty}a_{i}K(x_{i},\cdot)$ converging in $L_{2}$ endowed with the inner product

where $a_{i},b_{j}$’s are any real numbers and the $x_{i}$’s and $x^{\prime}_{j}$’s are any points in ${\cal X}$.

and it is believed that $\left\|f^{*}\right\|_{{\cal H}_{K}}$ is small which justified the use of the RERM with regularization function given by the RKHS norm $\left\|\cdot\right\|_{{\cal H}_{K}}$:

Statistical properties of this RERM may be obtained from Theorem 2.1 in the subgaussian case and from Theorem 2.2 in the bounded case. To that end, we only have to compute the Gaussian mean width and/or the Rademacher complexities of $B_{{\cal H}_{K}}$. In this example, we rather compute the localized version of those quantities because it is possible to derive explicit formula. They are obtained by intersecting the ball with $r{\cal E}$. In order not to induce any confusion, we still use the global ones in estimation bounds.

One can use the feature map $\Phi$ to show that there is an isometry between the two Hilbert spaces ${\cal H}_{K}$ and $l_{2}$ endowed with the norm $\left\|\beta\right\|_{K}=\left(\sum\beta_{i}^{2}/\lambda_{i}\right)^{1/2}$. The unit ball of $l_{2}$ endowed with the norm $\left\|\cdot\right\|_{K}$ is an ellipsoid denoted by ${\cal E}_{K}$.

where the last inequality follows from Proposition 2.2.1 in (note that we defined the Gaussian mean widths in Definition (2.4) depending on the covariance of $X$). We also get from Theorem 2.1 in that

Note that unlike the previous examples, we do not have to assume isotropicity of the design. Indeed, in the RKHS case, the unit ball of the regularization function is isomorphic to the ellipsoid ${\cal E}_{K}$. Since ${\cal E}$ is also an ellipsoid having the same coordinates structure as ${\cal E}_{K}$ (cf. paragraph above), for all $\rho,r>0$, the intersection $\rho B_{{\cal H}_{K}}\cap r{\cal E}$ is equivalent to an ellipsoid, meaning that, it contains an ellipsoid and is contained in a multiple of this ellipsoid. Therefore, the Gaussian mean width and the Rademacher complexity of $\rho B_{{\cal H}_{K}}\cap r{\cal E}$ has been computed without assuming isotropicity (thanks to general results on the complexity of Ellipsoids from Proposition 2.2.1 in and Theorem 2.1 in ).

It follows from (27) and (28) that the Gaussian mean width and the Rademacher complexities are equal. Therefore, up to constant ($L$ in the subgaussian case and $b$ in the bounded case), the two subgaussian and bounded setups may be analyzed at the same time. Nevertheless, since we will only consider in this setting the hinge loss and that the Bernstein condition (cf. Assumption 2.1) with respect to the hinge loss has been studied in Proposition 6.3 only in the bounded case. We therefore continue the analysis only for the bounded framework.

We are now able to identify the complexity parameter of the problem. We actually do not use the localization in this and rather use only the global complexity parameter as defined in Definition 2.7: for all $\rho>0$:

where $\kappa\geq 1$ is the Bernstein parameter.

Finally, let us discuss about the boundedness assumption. It is known (cf., for instance, Lemma 4.23 in ) that if the kernel $K$ is bounded then the functions in the RKHS ${\cal H}_{K}$ are bounded: for any $f\in{\cal H}_{K}$, $\left\|f\right\|_{L_{\infty}}\leq\left\|K\right\|_{\infty}\left\|f\right\|_{{\cal H}_{K}}$ where $\left\|K\right\|_{\infty}:=\sup_{x\in{\cal X}}\sqrt{K(x,x)}$. As a consequence, if one restricts the search space of the RERM to a RKHS ball of radius $R$, one has $F:=RB_{{\cal H}_{K}}\subset\left\|K\right\|_{\infty}B_{L_{\infty}}$ and therefore the boundedness assumption is satisfied by $F$. However, note that a refinement of the proof of Theorem 8.2 using a boundedness parameter $b$ depending on the radius of the RKHS balls used while performing the peeling device yields statistical properties for the RERM with no search space constraint. For the sake of shortness, we do not provide this analysis here.

We are now in a position to provide estimation and prediction results for the RERM

where the choice of the regularization parameter $\lambda$ follows from Theorem (2.2) and (28) (for $r=+\infty$). Note that unlike the examples in the previous sections, we do not have to find some radius $\rho^{*}$ satisfying the sparsity equation (8) to apply Theorem 2.2 since we simply take $\rho^{*}=20\left\|f^{*}\right\|_{{\cal H}_{K}}$ to insure that $0\in\Gamma_{f^{*}}(\rho^{*})$.

Then the RERM defined in (30) satisfies with probability larger than

where ${\cal E}(\hat{f})$ is the excess hinge risk of $\hat{f}$.

satisfies with large probability an oracle inequality like

In particular, an error bound (up to log factors) follows from this result: with high probability,

which is almost the same as the one obtained in (33) when $\kappa=1$ and $p$ is close to $1$. But our result is worse when $\kappa>1$ and $p$ is far from $1$. This is the price that we pay by using the hinge loss – note that the quadratic loss satisfies the Bernstein condition with $\kappa=1$ – and by fixing a regularization function which is the norm $\left\|\cdot\right\|_{{\cal H}_{K}}$ instead of fitting the regularization function in a “complexity dependent way” as in (32). In the last case, our procedure $\hat{f}$ does not benefit from the “real complexity” of the problem which is localized Rademacher complexities – note that we used global Rademacher complexities to fit $\lambda$ and construct the complexity function $r(\cdot)$.

A review of the Bernstein and margin conditions

In the bounded scenario, proved that the logistic loss function satisfies the Bernstein condition for $\kappa=1$. One may therefore use that result to apply Theorem 2.2. The analysis is pretty straightforward in the bounded case. It becomes more delicate in the subgaussian scenario as considered in Theorem 2.1.

This result solves the problem of the Bernstein condition with respect to the logistic loss function over a convex class $F$ of functions as long as all functions in $F$ are uniformly bounded by some constant $b$. We will therefore use this result only in the bounded framework, for instance, when $F$ is a class of linear functional indexed by a bounded set of vectors and when the design takes its values in the canonical basis.

In the subgaussian framework, one may proceed as in and assume that a statistical model holds. In that case, the Bernstein condition is reduced to the study of the Margin assumption since, in that case, the “Bayes rule” $\overline{f}$ (which is called the log-odds ratio in the case of the logistic loss function) is assumed to belong to the class $F$ and so $f^{*}=\overline{f}$. The margin assumption with respect to the logistic loss function has been studied in Example 1 from but for a slightly different definition of the Margin assumption. Indeed, in only functions $f$ in a $L_{\infty}$ neighborhood of $\overline{f}$ needs to satisfy the Margin assumption whereas in Assumption 2.1 it has to be satisfied in the non-bounded set ${\cal C}$.

From our perspective, we do not want to make no “statistical modeling assumption”. In particular, we do not want to assume that $\overline{f}$ belongs to $F$. We therefore have to prove the Bernstein condition when $\bar{f}$ may not belong to $F$. We used this result in Section 3 in order to obtain statistical bounds for the Logistic LASSO and Logistic Slope procedures. In those cases, $F$ is a class of linear functionals. We now state that the Bernstein condition is satisfied for a class of linear functional when $X$ is a standard Gaussian vector.

2 Hinge loss

Unlike the logistic loss function, both the hinge loss and the quantile losses does not enjoy a strong convexity property. Therefore, one has to turn to a different approach as the one used in the previous section to check the Bernstein condition for those two loss functions.

Let $F$ be a class of functions from ${\cal X}$ to $$. Assume that$\overline{f}\in F$so that$\overline{f}$is an oracle in$F$and thus (using the notations from Section 2)$f^{*}=\overline{f}$. In this situation, Margin assumption with respect to the hinge loss (cf. ) restricted to the class$F$and Bernstein condition (cf. Assumption 2.1) coincide. Therefore, Assumption 2.1 holds when the Margin assumption w.r.t. the hinge loss holds. According to Proposition 1 in , the Margin assumption with respect to the hinge loss is equivalent the Margin assumption with respect to the$0-1$loss for a class$F$of functions with values in$$. Then, according to Proposition 1 in and the margin assumption with respect to the$0-1$loss with parameter$\kappa$ is equivalent to

As a consequence, one can state the following result on the Bernstein condition for the hinge loss in the bounded case scenario.

Note that up to a modification of the constant $A$, the same result holds for functions with values in $[-b,b]$ for $b>0$, a fact we used in Section 5.

3 Quantile loss

In this section, we study the Bernstein parameter of the quantile loss in the bounded regression model, that is when for all $f\in F,\|f\|_{L_{\infty}}\leq b$ a.s.. Let $\tau\in(0,1)$ and, for all $x\in{\cal X}$, define $\overline{f}(x)$ as the quantile of order $\tau$ of $Y|X=x$ and assume that $\bar{f}$ belongs to $F$, in that case, $\overline{f}=f^{*}$ and Bernstein condition and margin assumption are the same. Therefore one may follow the study of the margin assumption for the quantile loss in to obtain the following result.

Discussion

This paper covers many aspects of the regularized empirical risk estimator (RERM) with Lipschitz loss. This property is commonly shared by many loss functions used in practice such as the hinge loss, the logistic loss or the quantile regression loss. This work offers a general method to derive estimation bounds as well as excess risk upper bounds. Two main settings are covered: the subgaussian framework and the bounded framework. The first one is illustrated by the classification problem with logistic loss. In particular, minimax rates are achieved when using the SLOPE regularization norm. The second framework is used to derive new results on matrix completion and in kernel methods.

A possible extension of this work is to study other regularization norms. In order to do that, one has to compute the complexity parameter in one of the settings and a solution of the sparsity equation. The latter usually involves to understand the sub-differential of the regularization norm and in particular its singularity points which are related to the sparsity equation.

Proof of Theorem 2.1 and Theorem 2.2

First, we state two theorems: Theorem 8.1 in the subgaussian setting, and Theorem 8.2 in the bounded setting. These two theorems rely on localized versions of the complexity function $r(\cdot)$ that will be defined first. Note that the localized version of $r(\cdot)$ can always be upper bounded by the simpler version used in the core of the paper. Thus, Theorem 2.1 is a direct corollary of Theorem 8.1, and Theorem 2.2 is a direct corollary of Theorem 8.2.

So let us start with a localized complexity parameters. The ”statistical size” of the family of ”sub-models” $(\rho B)_{\rho>0}$ is now measured by local Gaussian mean-widths in the subgaussian framework.

Let $\theta>0$. The complexity parameter is a non-decreasing function $r(\cdot)$ such that for every $\rho\geq 0$,

In the boundedness case, it is written as follows.

Let $\theta>0$. The complexity parameter is a non-decreasing function $r(\cdot)$ such that for every $\rho\geq 0$,

where $\kappa$ is the Bernstein parameter from Assumption 2.1.

To obtain the complexity functions from Definition 2.5 and 2.7, we use the fact that $w\left(\rho B\cap r(\rho)B_{L_{2}}\right)\leq w(\rho B)$ and ${\rm Rad}(\rho B\cap r(\rho)B_{L_{2}})\leq{\rm Rad}(\rho B)$: it indeed does not use the localization. We also set $\theta=7/40A$ in those definitions because it is the largest value allowed in the following theorems.

Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.2 hold where $r(\cdot)$ is a function as in Definition 8.1 for some $\theta$ such that $40A\theta\leq 7$ and assume that $\rho\to r(2\rho)/\rho$ is non-increasing. Let the regularization parameter $\lambda$ be chosen such that

where $\rho^{*}$ satisfies (8). Then, with probability larger than

Proof of Theorem 2.1: Let $r(\cdot)$ be chosen as in (2.5). For this choice, one can check that the regularization parameter used for the construction of the RERM satisfies (37) with an adequate constant choice. Moreover, for this choice of function $r(\cdot)$ it is straightforward to lower bound the sum in the probability estimate in (38). The parameter $\lambda$ is chosen in the middle of the range.

Assume that Assumption 1.1, Assumption 2.1 and Assumption 2.3 hold where $r(\cdot)$ is a function as in Definition 8.2 for some $\theta$ such that $40A\theta\leq 7$ and assume that $\rho\to r(2\rho)/\rho$ is non-increasing. Let the regularization parameter $\lambda$ be chosen such that

where $\rho^{*}$ satisfies (8). Then, with probability larger than

The proof of Theorem 2.2 is identical to the one of Theorem 2.1 and we do not reproduce it here.

2 Proofs of Theorems 8.2 and 8.1

Proof of Theorem 8.1 and and Theorem 8.2 follow the same strategy. They are split into two parts. First, we identify an event onto which the statistical behavior of the regularized estimator $\hat{f}$ can be controlled using only deterministic arguments. Then, we prove that this event holds with a probability at least as large as the one in (38) in the case of Theorem 8.1 and as in (40) in the case of Theorem 8.2. We first introduce this event which is common to the subgaussian and the bounded setups:

where $\theta$ is a parameter appearing in the definition of $r(\cdot)$ in Definition 8.1 and Definition 8.2, $\kappa\geq 1$ is the Bernstein parameter from Definition 2.1 and $\rho^{*}$ is a radius satisfying the sparsity Equation (8).

Let $\lambda$ be as in (37) (or equivalently as in (39)) and let $\rho^{*}$ satisfy (8), on the event $\Omega_{0}$, one has

Proof. Denote $\hat{\rho}=\left\|\hat{f}-f^{*}\right\|$. We first prove that $\hat{\rho}<\rho^{*}$. To that end, we assume that the reverse inequality holds and show some contradiction. Assume that $\hat{\rho}\geq\rho^{*}$. Since $\rho\to r(2\rho)/\rho$ is non-increasing then by Lemma A.1, $\rho\to\Delta(\rho)/\rho$ is non-decreasing and so we have

Now, we consider two cases: either $\left\|\hat{f}-f^{*}\right\|_{L_{2}}\leq r(2\hat{\rho})$ or $\left\|\hat{f}-f^{*}\right\|_{L_{2}}>r(2\hat{\rho})$.