Robust high dimensional learning for Lipschitz and convex losses

We establish risk bounds for Regularized Empirical Risk Minimizers (RERM) when the loss is Lipschitz and convex and the regularization function is a norm. We obtain these results in the i.i.d. setup under subgaussian assumptions on the design. In a second part, a more general framework where the design might have heavier tails and data may be corrupted by outliers both in the design and the response variables is considered. In this situation, RERM performs poorly in general. We analyse an alternative procedure based on median-of-means principles and called"minmax MOM". We show optimal subgaussian deviation rates for these estimators in the relaxed setting. The main results are meta-theorems allowing a wide-range of applications to various problems in learning theory. To show a non-exhaustive sample of these potential applications, it is applied to classification problems with logistic loss functions regularized by LASSO and SLOPE, to regression problems with Huber loss regularized by Group LASSO, Total Variation and Fused LASSO and to matrix completion problems with quantile loss regularized by the nuclear norm. A short simulation study concludes the paper, illustrating in particular robustness properties of regularized minmax MOM procedures.


Introduction
Regularized empirical risk minimizers (RERM) are standard estimators for high dimensional classification and regression where the estimator is a minimizer of a regularized empirical mean of loss functions. In regression, the quadratic loss of linear functionals regularized by the 1 -norm (LASSO) Tibshirani (1996) is probably the most famous example of RERM, see for example Koltchinskii (2011); Bühlmann and van de Geer (2011) for overviews. Recent results and references, including more general regularization functions can be found, for example in Lecué and Mendelson (2018); . RERM based on quadratic loss are highly unstable when data have heavy-tails or when the dataset has been corrupted by even a few outliers. These problems have attracted a lot of attention in robust statistics, see for example Huber and Ronchetti (2011) for an overview. By considering alternative losses, one can efficiently solve these problems when heavy-tails or corruption happen in the output variable Y . There is a growing literature analyzing performance of some of these alternatives in learning theory. In regression problems, among others, one can mention the L 1 absolute loss Shalev-Shwartz and Tewari (2011), the Huber loss Zhou et al. (2018); Elsener and van de Geer (2018) and the quantile loss that is popular in finance and econometrics. In classification, besides the 0/1 loss function which is known to lead to computationally untractable RERM, the logistic loss and the hinge loss are among the most popular convex surrogates. Quantile, L 1 , Huber loss functions for regression and Logistic, Hinge loss functions for classification are all Lipschitz and convex loss functions (in their first variable, see Assumption 2 for a formal definition). This remark motivated Alquier et al. (2017) to study systematically RERM based on Lipschitz loss functions. A remarkable feature of Lipschitz losses proved in Alquier et al. (2017) is that optimal results can be proved with almost no assumption on the response variable Y .
This paper is built on the approach initiated in Chinot et al. (2018). Compared with Alquier et al. (2017), the approach of Chinot et al. (2018) improves the results by deriving risk bounds depending on a localized complexity parameters rather than global ones and by considering a more flexible setting where a global Bernstein condition is relaxed into a local one, see Assumption 5 and the following discussion for details. The paper Chinot et al. (2018) only considers estimators that are not regularized and that can therefore only be efficient in small dimensional settings. The first main result of this paper is a high dimensional extension of these results that is achieved by analysing estimators regularized by sparsity inducing norms Bach et al. (2012). The main result is a meta-theorem allowing to study simultaneously a broad range of applications including in particular LASSO, SLOPE, group LASSO, total variation, fused LASSO or Shatten S 1 norm. Section 6 provides applications of the main results to some examples among these.
While RERM is studied without assumption on the output variables, somehow strong, albeit classical, hypotheses are granted on the design X in our first main result. We assume actually in this analysis subgaussian assumptions on the input variables as in Alquier et al. (2017). The necessity of this assumption to derive optimal exponential deviation bounds for RERM is not surprising as RERM have downgraded performance when the design is heavy tailed (see Mendelson (2014) for instance).
In a second part of this paper, we study an alternative to RERM in a framework with less stringent assumptions on the design. These estimators, based on Median-Of-Means (MOM) Nemirovsky and Yudin (1983); Birgé (1984); Jerrum et al. (1986); Alon et al. (1999) and minmax principles Audibert and Catoni (2011); Baraud et al. (2017) are called minmax MOM estimators as in Lecué and Lerasle (2019). A non-regularized version of these estimators was analysed in Chinot et al. (2018). The second main and most important result of the paper shows that minmax MOM estimators achieve optimal subgaussian deviation bounds in the relaxed setting where RERM perform poorly. This result is obtained under a local Bernstein condition as for the RERM. It allows to derive fast rates of convergence in a large set of applications where typically, subgaussian assumptions on the design X are replaced by moment assumptions. Minmax MOM estimators are then analysed without the local Bernstein condition. Oracle inequalities holding with exponentially large probability are proved in this case. Compared with results under Bernstein's assumption, an extra variance term appears in the convergence rate. This extra term typically would yield to slow rates of convergence in the applications, which are known to be minimax in this case. However, the variance term disappears under the Bernstein's condition, which shows that fast rates can be recovered from the general results. In addition, all results on minmax MOM estimators, both with or without Bernstein condition, are shown in the "O ∪ I" framework -where O stands for "outliers" and I for "informative"-see Section 4.1 or Lerasle (2017, 2019) for details. In this framework, all assumptions (such as the Bernstein's condition) are granted on "inliers" (X i , Y i ) i∈I . These inliers may have different distributions but the oracles of these distributions should match. On the other hand, no assumption are granted on outliers (X i , Y i ) i∈O , which is to the best of our knowledge the strongest form of aggressive outliers. The minmax MOM estimators perform well in this setting, it means that the accuracy of their predictions is not downgraded by the presence of a few outliers in the dataset. Mathematically, this robustness is not surprising as it is a byproduct of the median step. However, in practice, it is an important advantage of MOM estimators compared to RERM.
The main results on minmax MOM estimators are also meta-theorems that can be applied to the same examples as RERM. Each of these examples provide a new (to the best of our knowledge) estimator that reach performance that RERM could not typically. For example, when the class of classifiers/regressors is the class of linear functions on R p , minmax MOM estimators have a risk bounded by the minimax rate with optimal exponential probability of deviation even if the inputs X only satisfy weak moment assumptions and/or have been corrupted by outliers. These applications are also discussed in Section 6. Finally Section 7 shows heuristics to implement minmax MOM estimators and presents some modifications of these estimators that seem to perform much better in practice. Take-home messages from these simulations are 1) there exist algorithms approximating minmax MOM estimators and so they should not be considered as pure mathematical constructions 2) robustness properties of minmax-MOM estimators are confirmed on practical examples 3) almost any classical algorithm used in high-dimensional statistics can be easily turned into a robust one using a MOM approach.
The remaining of paper is decomposed as follows. Section 2 presents the formal setting. Section 3 presents results for RERM and Section 4 those for minmax MOM estimators with a local Bernstein condition and in Section 5 without this condition. Section 6 details several examples of applications of the main results. A short simulation study illustrating our theoretical findings is presented in Section 7. The proofs are postponed to Sections 9-11.

Mathematical background and notations
Let (Z, A, P ) denote a probability space, where Z = X × Y is a product space such that X denotes a measurable space of inputs and Y ⊂ R is the subset of outputs. Let Z = (X, Y ) denote a random variable taking values in Z with distribution P and let µ denote the marginal distribution of the design X.
Let Y ⊂ R denote a convex set and let F denote a class of functions f : X → Y. The set Y typically contains all possible values of the predictions f (x) of y, for f ∈ F and x ∈ X . As such, it will always contain Y. Let : Y × Y → R denote a loss function such that (f (x), y) measures the error made when predicting y by f (x). For any distribution Q on Z and any function g : Z → R for which it makes sense, let Qg = E Z∼Q [g(Z)] denote the expectation of the function g under the distribution Q and, for any p 1, let g Lp(Q) := (Q[|g| p ]) 1/p , g Lp := g Lp(P ) . The risk of any f ∈ F is given by P f , where f (x, y) := (f (x), y). The prediction of Y with minimal risk is given by f * (X), where f * , called oracle, is defined as any function such that Hereafter, for simplicity, it is assumed that f * exists and is uniquely defined. The oracle is unknown to the statistician that has only access to a dataset (X i , Y i ) i∈{1,...,N } of random variables taking values in X × Y. The goal is to build a data-driven estimatorf of f * that predicts almost as well as f * . The quality of an estimatorf is measured by the error rate f − f * 2 L 2 and the excess risk P Lf , where, respectively, Let P N denote the empirical measure i.e P N (A) = (1/N ) N i=1 I(X i ∈ A). A natural candidate for the estimation of f * is the Empirical Risk Minimizer (ERM) of Vapnik andČervonenkis (1971), see also Vapnik (1998) for an overview, which is defined bŷ The choice of F is a central issue: enlarging the space F deteriorates the quality of the oracle estimation but improves the prediction of this oracle. It is possible to use large classes F without significantly altering the quality estimation if certain structural properties are granted on the oracle and known to the statistician. In that case, a widely spread approach is to add to the empirical loss a regularization term promoting this structural property. In this paper, we consider this problem when the regularization term is a norm. Formally, let E be a linear space such that F ⊂ E ⊂ L 2 (µ) and let · : E → R + denote a norm on E. For any λ ≥ 0, the regularized ERM (RERM) is defined byf In regression, one can mention Thikonov regularization which promotes smoothness Golub et al. (1999) and 1 regularization which promotes sparsity Tibshirani (1996). Likewise, for matrix reconstruction, the 1-Schatten norm S 1 promotes low rank solutions (see Cai et al. (2016)).
In the remaining of the paper, the following notations will be used repeatedly: for any r > 0, let be the canonical basis of R p . Let c denote an absolute constant whose value might change from line to line and let c(A) denote a function depending on the parameters A whose value may also change from line to line.

Regularized ERM with Lipschitz and convex loss functions
This section presents and improves results from Alquier et al. (2017). A local Bernstein assumption, holding in a neighborhood of the oracle f * is introduced in the spirit of Chinot et al. (2018). This assumption does not imply boundedness of F in L 2 -norm unlike the global Bernstein condition considered in Alquier et al. (2017). New rates of convergence are obtained, depending on localized complexity parameters improving the global ones from Alquier et al. (2017).

Main assumptions
We start with a set of assumptions sufficient to prove exponential deviation bounds for the error rate and excess risk of RERM for general convex and Lipschitz loss functions and for any regularization norm. In this section, we consider the classical i.i.d. assumption.
are independent and identically distributed with distribution P . All along the paper, we consider Lipschitz and convex loss functions.
Assumption 2 There exists L > 0 such that, for any y ∈ Y, (·, y) is L-Lipschitz i.e for every f and g in F , x ∈ X and y ∈ Y, There are many examples of loss functions satisfying Assumption 2. The three examples studied in this work (see Section 6) are • the logistic loss function defined for any u ∈ R and y ∈ Y = {−1, 1}, by (u, y) = log(1 + exp(−yu)). It satisfies Assumption 2 for L = 1.
• Tte Huber loss function with parameter δ > 0 is defined for all u, y ∈ R, by It satisfies Assumption 2 for L = δ.
Assumption 3 The class F is convex.
In particular, Assumption 3 holds in the important case considered in high-dimensional statistics when F is the class of all linear functions indexed by R p , F = { t, · : t ∈ R p }. This example is studied in great details in Section 6 as well as the case of linear functions indexed by the set of matrices R m×T to handle problems such as matrix completion.
RERM performs well when the empirical excess risk f ∈ F → P N L f is uniformly concentrated around the excess risk f ∈ F → P L f . This requires strong concentration properties of the class of random variables {L f (X) : f ∈ F }, which is implied by concentration properties of {(f −f * )(X) : f ∈ F } under the Lipschitz assumption. Here, we study RERM under a subgaussian assumption on the design. We first recall the definition of a subgaussian class of functions.

Assumption 4
The class F − f * is L 0 -subgaussian with respect to X.
Assumptions 1-4 are also granted in Alquier et al. (2017). In this setup, a natural way to measure the statistical complexity of the problem is via Gaussian mean widths. We recall the definition of this measure of complexity.
Definition 2 Let H ⊂ L 2 (µ) and (G h ) h∈H be the canonical centered Gaussian process indexed by H, with covariance structure given by Gaussian mean widths of various sets have been computed in Amelunxen et al. (2014), , Chatterjee and Goswami (2019) or Gordon et al. (2007) for example. Risk bounds for f RERM λ are driven by fixed point solutions of a Gaussian mean width of regularization balls (F − f * ) ∩ ρB, which measure the local complexity of F around f * .
Definition 3 For all A > 0, the complexity function is a non-decreasing function r(A, ·), such that for every ρ ≥ 0, Here, L is the Lipschitz constant of Assumption 2 and L 0 is the subgaussian constant from Assumption 4.
The last tool and assumption comes from Lecué and Mendelson (2018). A key observation is that the regularization norm · promoting some sparsity structure has large subdifferentials at sparse functions (see, for instance, atomic norms in Bhaskar et al. (2013)). The subdifferential of · in f is defined as where E * is the dual space of the normed space (E, · ). Let is the union of all subdifferentials of the regularization norm · of functions f close to the oracle f * .
Any constant in (0, 1) could replace 4/5 in Definition 4 as can be seen from a close inspection of the proof of Theorem 1. If the norm · is "smooth" in f , the subdifferential of · in f is just the gradient of · in f . In that case, (∂ · ) f is not rich and the regularization norm has only a low "sparsity inducing power" unless the variety of gradients of · at f in the neighborhood f * + (ρ/20)B is rich enough (the latter case can be seen as · being "almost not differentiable" in f * ). However, any norm has a subdifferential in 0 equal to the entire unit dual ball. Therefore, when 0 belongs to f * + (ρ/20)B, for example when ρ ≥ 20 f * , the sparsity equation is satisfied since, in that case, ∆(ρ) = ρ. We can use this fact to obtain "complexity dependent" rates of convergence -i.e. rates depending on f * . In high-dimensional setups, we also look for statistical bounds depending on the sparsity of f * enforced by · (see Chinot (2019); Mendelson (2017, 2018) for details regarding the difference between "complexity and sparsity" dependent bounds). Hereafter, we focus on norms · promoting some sparsity structure and we establish sparsity dependent rates of convergence and sparse oracle inequalities in Section 6 (except for matrix completion, see Section 6).
Margin assumptions Mammen and Tsybakov (1999); Tsybakov (2004); van de Geer (2016) such as the Bernstein conditions from Bartlett and Mendelson (2006) have been widely used in statistics and learning theory to prove fast convergence rates of RERM. Here, we use a local Bernstein condition in the spirit of Chinot et al. (2018).
Assumption 5 There exist constants A > 0 and ρ * such that ρ * satisfies the A-sparsity equation Hereafter, whenever Assumption 5 is granted, we assume that the constant A is fixed satisfying this assumption and write r(ρ) instead of r(A, ρ). As explained in Chinot et al. (2018) AP L f for all f ∈ F -does not hold.

Main theorem for the RERM
The following theorem gives the main result on the statistical performance of RERM.
Theorem 1 Grant Assumptions 1, 2, 3, 4. Suppose that Assumption 5 holds with ρ = ρ * satisfying the A-sparsity equation from Definition 4. With this value of A, let r(·) := r(A, ·) denote the complexity function from Definition 3. Assume that 10 21A Then, with probability larger than the following bounds hold Remark 1 A remarkable feature of Theorem 1 is that it holds without assumption on Y . This is an important consequence of the Lipschitz property which has been widely used in robust statistics, see for example Huber and Ronchetti (2011) for an overview.
Remark 2 Theorem 1 holds for subgaussian classes of functions F . As in Alquier et al. (2017), it is possible to extend this result under boundedness assumptions.
Theorem 1 improves (Alquier et al., 2017, Theorem 2.1) in two directions: First, the complexity function r(·) measures the (Gaussian mean width) complexity of the local set (F −f * )∩ρB ∩rB L 2 and not the global gaussian mean width of (F − f * ) ∩ ρB such as in Alquier et al. (2017). Second, Theorem 1 holds in a setting where F can be unbounded in L 2 -norm. The proof of Theorem 1 is postponed to Section 9. The proof relies on the convexity of the loss function (and F ) which allows to use an homogeneity argument as in Chinot et al. (2018) for Lipshitz and convex loss functions and in Lecué and Mendelson (2013) for the quadratic loss function, simplifying the peeling step of Alquier et al. (2017). Theorem 1 is a general result which is applied in various applications in Section 6.

Minmax MOM estimators
Even if the results of Section 3 are interesting on their own because the i.i.d. sub-gaussian framework is one of the most considered setup in Statistics and Learning theory, the setup considered in Section 3 can be restrictive in some applications. It does not cover more realistic situations where data are heavy-tailed and/or corrupted. In this section, we consider a more general setup covering these situations. The results of Section 3 are used as benchmarks: we show that similar bounds can be achieved in a more realistic framework by alternative estimators. These use median-of-means principles instead of empirical means.

Definition
Recall the definition of MOM estimators of univariate means from Alon et al. (1999);Jerrum et al. (1986); Nemirovsky and Yudin (1983). Let (B k ) k=1,...,K denote a partition of {1, . . . , N } into blocks B k of equal size N/K (it is implicitly assumed that K divides N . An extension to blocks with almost equal size is possible. It is not considered here to simplify the presentation of the results, the extension is thus left to the interested reader). For any function f : X × Y → R and k ∈ {1, . . . , K}, let The MOM estimator based on this partition is the empirical median of the latter empirical means: The Devroye et al. (2016). The number of blocks K is a tuning parameter of the procedure. The larger K, the more outliers are allowed. When K = 1, MOM K [f ] is the empirical mean, when K = N , it is the empirical median.
Building on ideas introduced in Audibert and Catoni (2011); Baraud et al. (2017), Lecué and Lerasle (2019) proposed the following strategy to use MOM estimators in learning problems. Since the oracle f * is also solution of the following minmax problem minmax MOM estimators are obtained by plugging MOM estimators of the unknown expectations P ( f − g ) in this minmax formulation. Applying this principle to regularized procedures yields the following "minmax MOM version" of RERM that we study in this paper: The linearity of the empirical process P N is important to use localization techniques in the analysis of RERM to derive fast rates of convergence for these estimators improving upon the slow rates of Vapnik (1998), see Tsybakov (2004); Koltchinskii (2011) for example. The minmax reformulation comes from Audibert and Catoni (2011), it allows to overcome the lack of linearity of robust mean estimators and obtain fast rates of convergence for robust estimators based on nonlinear estimators of univariate expectations.

Assumptions and main results
To highlight robustness properties of minmax MOM estimators with respect to outliers in the dataset, their analysis is performed in the following framework. Let I ∪ O denote a partition of {1, · · · N } that is unknown to the statistician. Data (X i , Y i ) i∈O are considered as outliers. No assumption on the distribution of these data is made, they can be dependent or adversarial. Data (X i , Y i ) i∈I bring information on f * and are called informative or inliers. All assumptions are made on these data. They have to induce the same L 2 geometries on F and the same excess risks.
Assumption 6 (X i , Y i ) i∈I are independent and for all i ∈ I : Assumption 6 holds in the i.i.d case, it also covers situations where informative data (X i , Y i ) i∈I may have different distributions. It implies in particular that f * is also the oracle in F w.r.t. all the distributions P i for i ∈ I. Several quantities introduced to study RERM have to be modified to state the results for minmax MOM estimators. First, the complexity function is no longer based on Gaussian mean width, it is now defined as a fixed point of local Rademacher complexities. Let (σ i ) i∈I denote i.i.d. Rademacher random variables (i.e. uniformly distributed on {−1, 1}), independent from (X i , Y i ) i∈I . The complexity function ρ → r 2 (γ, ρ) is defined for all ρ > 0 as the smallest r > 0 such that, for any J ⊂ I satisfying |J| N/2, As in Theorem 1, this parameter measures the complexity of (F − f * ) ∩ ρB locally in a L 2neighborhood of 0. It only involves the distribution of informative data and does not depend on the distribution of the outputs (Y i ) i∈I . The local Bernstein condition, Assumption 5, as well as the sparsity equation have now to be extended to this new definition of complexity. Start with the sparsity equation.
The value of c(A, L) in Definition 5 is made explicit in Section 10. To simplify the presentation we write c(A, L) as it is an absolute constant depending only on A and L. With this definition in mind, one can extend the local Bernstein assumption.
Assumption 7 There exist a constant A > 0 and ρ * such that ρ * satisfies the A-sparsity equation from Definition 5 and, for all f ∈ F such that f − f * 2 As in Assumption 5, the link between f − f * L 2 and the excess risk P L f in Assumption 7 is only granted in a L 2 (µ)-neighborhood of the oracle f * whose radius is proportional to the rate of convergence of the estimators (see Theorems 1 and 2). The local Bernstein assumption is somehow "minimal" since it is only granted on the smallest set of the form F ∩ρ(B +f * )∩r 2 (γ, ρ)(B L 2 +f * ) centered in f * that can be proved to containf K,λ .
We are now in position to state our main result on the statistical performances of the regularized minmax MOM estimator.
Theorem 2 Grant Assumptions 2, 3, 6 and 7 for ρ * satisfying the A-sparsity equation from Definition 5. Let K ≥ 7|O|/3, γ = 1/(6528L), and define λ = 5 17A Then, with probability larger than 1 − 2 exp(−cK), the minmax MOM estimatorf K,λ defined in (9) satisfies Suppose that K = c(A, L)r 2 2 (γ, 2ρ * )N , which is possible as long as |O| ≤ c(A, L)N r 2 2 (γ, 2ρ * ). The L 2 -estimation bound is then r 2 2 (γ, 2ρ * ) and the probability that this bound the L 2 risk is 1 − exp(−c(A, L)N r 2 2 (γ, 2ρ * )). Up to absolute constants, regularized minmax MOM estimators achieve the same bounds as RERM with the same probability as in the i.i.d. subgaussian framework from Theorem 1. Indeed, in that case, a straighforward chaining argument shows that the Rademacher complexity from (10) is upper bounded by the Gaussian mean width. The difference with Theorem 1 is that the estimator depends on K. On the other hand, the results hold in a setting where the subgaussian assumption on F is relaxed into moment assumptions and the data may not be identically distributed and may have been corrupted by some outliers. Section 6.2 will show an example where rate optimal bounds can be derived from this general result. It is also possible to adapt in a data-driven way to the best K and λ by using a Lepski's adaptation method such as in Devroye et al. (2016); Lerasle (2017, 2019); Chinot et al. (2018); Chinot (2019). This step is now well understood, it is not reproduced here. Theorem 2 is "universal" in the sense that it allows to handle many applications, some of these are presented in Section 6

Relaxing the Bernstein condition
In this section, we study minmax MOM estimators when the Bernstein assumption 7 is relaxed. The price to pay for the relaxation is that, on one hand, the L 2 -risk is not controlled and on the other hand an extra variance term appears in the excess risk P Lf λ K . Nevertheless, under a slightly stronger local Bernstein's condition, the extra variance term can be controled and the bounds from Theorem 2 is recovered .
Assumption 8 (X i , Y i ) i∈I are independent and for all i ∈ I, (X i , Y i ) has distribution P i , X i has distribution µ i . We assume that, for any i ∈ I, F ⊂ L 1 (µ i ) and Since the local Bernstein Assumption 7 does not hold, the localization argument has to be modified. Instead of using the L 2 -norm to define neighborhoods of f * , we use the excess loss f ∈ F → P L f . The new fixed point is defined for all γ, ρ > 0 and K ∈ {1, · · · , N }: The value of c in Equation (13) can be found in Section 11. The main differences between r 2 (γ, ρ) in (13) and r(γ, ρ) in (10) are the extra variance V K term and the L 2 localization which is replaced by an "excess of risk" localization. Under the local Bernstein Assumption 9, this extra term disappears and this complexity matches the one of Theorem 2. As in Section 4, the sparsity equation has to be extended.
We are now in position to state the main result of this section.
Theorem 3 Grant Assumptions 2, 3, 8 and assume that |O| ≤ 3N/7. Let ρ * satisfying the sparsity equation from Definition 6. Let γ = 1/(3840L) and K ∈ 7|O|/3, N . Define The minmax MOM estimatorf λ K defined in (9) satisfies, with probability at least 1 − 2 exp(−cK), In Theorem 3, the only stochastic assumption is Assumption 8 which says that the inliers data are independent and define the same excess risk as (X, Y ) over F . In particular, Theorem 3 does not assume anything on the outliers (X i , Y i ) i∈O nor on the outputs of the inliers (Y i ) i∈I . The difficulty of the problem is contained in the computation of the local Rademacher complexities E(r, ρ) that are computed in examples using stronger stochastic assumptions.
To conclude the section, let us show that Theorem 2 can be recovered from Theorem 3 under the following slightly stronger local Bernstein assumption.
Assumption 9 There exist a constantĀ > 0 and ρ * satisfying the sparsity equation from Defini- Up to constants,C K,r is equivalent to C K,r given in Definition 5. Assumption 9 holds for any function f ∈ F such that P L f ≤C K,r (ρ * ,Ā) which is slightly stronger than the L 2 -norm localization used in Assumption 7.
Remark 3 Under Assumption 9 and a slight modification in the constants, ρ * satisfies the sparsity equation of Definition 6 if it verifies the sparsity equation of Definition 5.

Applications
This section presents some applications of Theorem 2. To check the assumptions of the Theorem 2, the following routine is applied: 1. Check Assumptions 2, 3, 6.

Check the local Bernstein condition from Assumption 7.
In this section, we focus on high dimensional statistical problems with sparsity inducing regularization norms Bach et al. (2012) given by the 1 norm Tibshirani (1996), the SLOPE norm Bogdan et al. (2015), the group LASSO norm Simon et al. (2013), the Total Variation norm Osher et al. (2005), the Fused Lasso norm Tibshirani et al. (2005) and the nuclear norm . In the vector case, we consider the class of linear functions F = { t, · : t ∈ R p } indexed by R p . We denote by t * ∈ R p the vector such that f * (·) = t * , · . We consider the logistic loss function for the LASSO and the SLOPE, with data ( 1} and the Huber loss function for the Group LASSO, the Total Variation and Fused Lasso, with data In particular, the results of this section extend results on the logistic LASSO and logistic SLOPE from Alquier et al. (2017) and present new results for the Group Lasso, the Total Variation and the Fused Lasso. Similar notation are used in the matrix case for the quantile loss and the trace-norm regularization in Section 6.7.

Preliminary results
In this section, we recall some tools to check the Local Bernstein condition, compute the local Rademacher complexity and verify the sparsity equation.

LOCAL BERNSTEIN CONDITIONS FOR THE LOGISTIC, HUBER AND QUANTILE LOSSES
In this section, we recall results from Chinot et al. (2018) on the local Bernstein condition for the logistic, Huber and quantile loss functions. For the logistic loss function (i.e. f : (x, y) ∈ R p × {±1} → log(1 + exp(−yf (x)))), we first introduce the following assumption.
There are constants C and c 0 > 0 such that Assumption b) is equivalent to say that the log-odds ratio f * * (X) is bounded by c 0 with large probability. It excludes trivial cases where deterministic predictors equal to 1 or −1 would be optimal.
b) F contains the Bayes rule, the minimizer of the risk over all measurable functions f : X → R.
c) Let C be the constant defined in a). There exists α > 0 such that, for all x ∈ X and all z ∈ R Proposition 2 (Chinot et al. (2018), Theorem 7) Grant Assumption 11. The Huber loss function with parameter δ > 0 satisfies the Bernstein condition: Finally, we recall a third and last result on the local Bernstein for the quantile loss from Chinot et al. (2018). The quantile loss function with parameter τ ∈ The local Bernstein inequality holds for the quantile loss function under the following assumption.
c) Let C be the constant defined in a). There exists α > 0 such that, for all x ∈ X and all z ∈ R satisfying Under Assumption 12, the quantile loss function satisfies a local Bernstein inequality as proved in Theorem 6 in Chinot et al. (2018). We recall this result here because we will use it for the problem of robust quantile matrix completion.
Proposition 3 (Chinot et al. (2018), Theorem 6) The quantile loss function with parameter τ satisfies the following local Bernstein condition under Assumption 12: Note that in Assumptions 10, 11 and 12, C can depend on the dimensionprovided that (C ) 2 r = O(1). For instance, we study in Section 6.7 the problem of quantile matrix completion where C depends on the dimension. Other examples of loss functions satisfying a local Bernstein condition can be found in Chinot et al. (2018).

LOCAL RADEMACHER COMPLEXITIES AND GAUSSIAN MEAN WIDTHS
The computation of r 2 (γ, ρ) may be involved, but can sometimes be reduced to the computation of Gaussian mean widths, thanks to Mendelson (2017). The results of Mendelson (2017) are based on the concepts of unconditional norm and isotropic random vectors.

Definition 1 For a given vector
if, for every x in R p and every permutation π of {1, · · · , p}, and, for any y ∈ R p such that, for all Recall the main result of Mendelson (2017).
Let X 1 , . . . , X N denote independent copies of X, then there exists a constant c 2 depending only on C 0 and M such that Recall that a real valued random variable Z is L 0 -subgaussian if and only if for all q ≥ 1, Z Lq ≤ c 0 L 0 √ q, for some absolute constant c 0 , see Theorem 1.1.5 in Chafaï et al. (2012). Hence, Theorem 5 assumes that the coordinates of the design X have at least C 0 log(p) "subgaussian" moments.

SUB-DIFFERENTIAL OF A NORM
To solve the sparsity equation -find ρ * such that∆(ρ * , A) ≥ 4ρ * /5 -we use the following classical result on the sub-differential of a norm: if · is a norm on R p , then, for all t ∈ R p , we have Here, B * is the unit ball of the dual norm associated with · , i.e. t ∈ R p → t * = sup v ≤1 v, t and S * is its unit sphere. In other words, when t = 0, the sub-differential of · in t is the set of all vectors z * in the unit dual sphere S * which are norming for t.
In the following, understanding the sub-differentials of the regularization norm is a key point for solving the sparsity equation. If one is only interested in proving "complexity" dependent bounds -which are bounds depending on t * and not the sparsity of t * -then one can simply take ρ * = 20 t * . Actually, in this case, 0 ∈ Γ t * (ρ), so∆(ρ * , A) = ρ * ≥ 4ρ * /5 (because B * = (∂ · ) 0 = Γ t * (ρ) according to (18)). Therefore, understanding the sub-differential of the regularization norm matters when one wants to derive statistical bounds depending on the dimension of the low-dimensional structure that contains t * . This is something expected since a norm has sparsity inducing power if its sub-differential is a big part of the dual sphere at vectors having the sparse structure (see, for instance, the construction of atomic norms in Bhaskar et al. (2013)).
We now have all the necessary tools to derive statistical bounds for many procedures by applying Theorem 2. In each example (given by a convex and Lipschitz loss function and a regularization norm), we just have to compute the complexity function r 2 , solve a sparsity equation and check the local Bernstein condition.

The minmax MOM logistic LASSO procedure
When the dimension p of the problem is large and t * 0 = |{i ∈ {1, · · · , p} : t * i = 0}| is small, it is possible to derive error rate depending on the size of the support of t * instead of the dimension p by using a 1 regularization norm. It leads to the well-known LASSO estimators, see Tibshirani (1996). For the logistic loss function, its minmax MOM formulation is the following. For a given K ∈ {1, . . . , N } and λ > 0, the minmax MOM logistic LASSO procedure is defined bŷ with the logistic loss function defined as t (x, y) = log(1 + exp(−y x, t )) for all t, x ∈ R p and y ∈ {±1}, and with the 1 regularization norm defined for all t ∈ R p by t 1 = p i=1 |t i |. We first compute the complexity function r 2 . Theorem 5 can be applied to upper bound the Rademacher complexities from (10) in that case because the dual norm of 1 (i.e the ∞ -norm) is 1-unconditional with respect to (e i ) p i=1 . Then, if X is an isotropic random vector satisfying (17), Theorem 5 holds and where B p 1 denote the unit ball of the 1 norm. From (Lecué and Mendelson, 2018, Lemma 5.3), we have Therefore, one can take .
(20) Let us turn to the local Bersntein assumption. We need to verify Assumption 10. If X is an isotropic random vector satisfying (17) and C 0 log(p) ≥ 4, where C 0 is the constant appearing in Equation (17), then the point a) of Assumption 10 is verified with C = c(M, C 0 ). For point c), let us assume that the Bayes rule (the function minimizing the logistic risk over all measurable functions from R p to R) is a linear function and is therefore equal to t * , · , where t * ∈ R p denotes the oracle. In other words, let us assume that the Bayes rule and the oracle coincide. In that case, point c) of Assumption 10 holds and point b) in Assumption 10 -i.e there exists c 0 > 0 such that Therefore, if the Bayes rule and the oracle coincide and Equation (21) holds, the local Bernstein Assumption is verified for a constant A depending on M, C 0 and c 0 given in Proposition 1 (since the latter formula is rather complicated, we will keep the notation A all along this section).
Finally, let us turn to a solution to the sparsity equation for the p 1 norm . The result can be found in Lecué and Mendelson (2018).
Lemma 3 (Lecué and Mendelson, 2018, Lemma 4.2) . Let us assume that X is isotropic. If the oracle t * can be decomposed as t Assume that t * is a s-sparse vector, so Lemma 3 applies. We consider two cases depending on the values of K and N r 2 For these values, the value of r 2 given in (20) yields Theorem 6 Let (X, Y ) be a random variable taking values in R p × {±1}, where X is an isotropic random vector such that for all 1 ≤ j ≤ p and 1 ≤ q ≤ C 0 log(p), X, e j Lq ≤ M √ q with C 0 log(p) ≥ 4. Assume that the Bayes rule and the oracle coincide for a vector t * in R p that is s-sparse and that there exists For K ≤ c(c 0 , M, C 0 )s log(ep/s), the upper bound on the estimation risk and excess risk matches the minimax rates of convergence for s-sparse vectors in R p . It is also possible to adapt in a datadriven way to the best K and λ by using a Lepski's adaptation method such as in Devroye et al. (2016); Lerasle (2017, 2019); Chinot et al. (2018); Chinot (2019). This step is now well understood, it is not reproduced here.

The minmax MOM logistic SLOPE
In this section, we study the minmax MOM estimator with the logistic loss function and the SLOPE regularization norm. Given β 1 ≥ β 2 ≥ · · · ≥ β p > 0, the SLOPE norm (see Bogdan et al. (2015)) is defined for for all t ∈ R p by The SLOPE norm coincides with the 1 norm when β j = 1 for all j = 1, · · · , p.
Given K ∈ {1, . . . , N } and λ > 0, the minmax MOM logistic SLOPE procedure iŝ Let us first compute the complexity function r 2 . If V ⊂ R p is closed under permutations and reflections (sign-changes)-which is the case for B p SLOP E , the unit ball of the SLOPE norm -then sup v∈V | ·, v | is 1-unconditional. Therefore, the dual norm of · SLOP E is 1-unconditional and Theorem 5 applies provided that X is isotropic and verifies (17). By (Lecué and Mendelson, 2018, Lemma 5 It follows that Let us turn to the local Bernstein Assumption. Since the loss function is the same as the one used in Section 6.2, the Bernstein assumption is verified if the Bayes rule and the oracle coincide and if there exists c 0 > 0 such that where C = c(M, C 0 ) is a function of M and C 0 only. The constant A in the Bernstein condition depends on c 0 , C 0 and M . As for the LASSO, since the formula of A is complicated (given in Proposition 1), we write A all along this section.
A solution to the sparsity equation relative to the SLOPE norm can be found in Lecué and Mendelson (2018). We recall this result here.
Assume that t * is exactly s-sparse, so Lemma 4 applies. We consider two cases depending on K. Consider the case where K ≤ c(c 0 , C 0 , M )N r 2 2 (γ, ρ * ), so C K,r (ρ * , A) = r 2 (γ, ρ * ). For β j = c log(ep/j), one may show that B s = c s log(ep/s) (see Bellec et al. (2018); Lecué and Mendelson (2018)). From (23) and Lemma 4, it follows that we can choose For C K,r (ρ, A) = c(c 0 , M, C 0 )K/N holding when K ≥ c(c 0 , C 0 , M )N r 2 2 (γ, ρ * ), we take ρ * = c(c 0 , C 0 , M ) sK/N satisfying the sparsity equation. We can therefore apply Theorem 2 for Theorem 7 Let (X, Y ) be random variable with values in R p × {±1} such that X is an isotropic random vector such that for all 1 ≤ j ≤ p and 1 ≤ q ≤ C 0 log(p), X, e j Lq ≤ M √ q with C 0 log(p) ≥ 4. Assume that the Bayes rule and the oracle coincide for a vector t * in R p that is s-sparse and that there exists (22) for the choice of weights β j = log(ep/j), j = 1, . . . , p and regularization parameter λ = c(c 0 , M, C 0 ) max(1/ √ N , K/(sN )). With probability larger than 1 − 2 exp(−cK), For K ≤ c(c 0 , M, C 0 )s log(ep/s)/N , the parameter λ is independent from the unknown sparsity s and these bounds match the minimax rates of convergence over the class of s-sparse vectors in R p without any restriction on s Bellec et al. (2018). Ultimately, one can use a Lepski's adaptation method to chose in a data-driven way the number of blocks K as in Lecué and Lerasle (2019) to achieve these optimal rates without prior knowledge on the sparsity s.

The minmax MOM Huber Group-Lasso
In this section, we consider regression problems where Y = R. We consider group sparsity as notion of low-dimensionality for t * . This setup is particularly useful when features (i.e. coordinates of X) are organized by blocks, as when one constructs dummy variables from a categorical variable. The regularization norm used to induce this type of "structured sparsity" is called the Group LASSO (see, for example Yang and Zou (2015) and Meier et al. (2008)). It is built as follows: let G 1 , · · · , G M be a partition of {1, · · · , p} and define, for any t ∈ R p Here, for all k = 1, . . . , M , t G k denotes the orthogonal projection of t onto the linear Span(e i , i ∈ G k ) -(e 1 , . . . , e p ) being the canonical basis of R p . The estimator we consider is the minmax MOM Huber Group-LASSO defined, for all K ∈ {1, · · · , N } and λ > 0, bŷ where t ∈ R p → t is the Huber loss function with parameter δ > 0 defined as In particular, it is a Lipschitz loss function with L = δ. Estimation bounds and oracle inequalities satisfied byt λ,K follow from Theorem 2 as long as we can compute the complexity function r 2 , we verify the local Bernstein Assumption and we find a radius ρ * satisfying the sparsity equation. We now handle these problems starting with the computation of the complexity function r 2 . The dual norm of · GL is z ∈ R p → z * GL = max 1≤k≤M z G k 2 , it is not κ-unconditional with respect to the canonical basis (e i ) p i=1 of R p for some absolute constant κ, so Theorem 5 does not apply directly. Therefore, in order to avoid long and technical materials on the rearrangement of empirical means under weak moment assumptions for the computation of the local Rademacher complexity from (10), we simply assume that the design vectors (X i ) i∈I are L 0 -subgaussian and isotropic: for all i ∈ I, all t ∈ R p and all q ≥ 1 In that case, a direct chaining argument allows to bound Rademacher processes by the Gaussian processes (see Talagrand (2014) for chaining methods): Here, B p GL is the unit ball of · GL , w(ρB p GL ∩ rB p 2 ) is the Gaussian mean width of the interpolated body ρB p GL ∩ rB p 2 . It follows from the proof of Proposition 6.7 in  that when the M groups G 1 , . . . , G M are all of same size p/M we have This yields Let us now turn to the local Bernstein Assumption. We need to verify Assumption 11. As we assumed that the design vectors (X i ) i∈I are isotropic and L 0 -subgaussian, it is clear that the point a) in Assumption 11 holds with C = L 0 . For the point b), we assume that the Bayes rule and the oracle coincide. For the point c). we assume that there exists α > 0 such that, for all x ∈ X and all Under these conditons, the local Bernstein Assumption is verified for A = 4/α according to Proposition 2.
Finally, we turn to the sparsity equation. The following lemma is an extension of Lemma 3 to the Group Lasso norm.
Assume that t * is exactly s-group sparse, so Lemma 5 applies. We consider two cases depending on the value of K. When K ≤ c(L 0 , α, δ)N r 2 2 (γ, ρ * ), C K,r (ρ * , 4/α) = r 2 (γ, ρ * ). By Lemma 5 and (27) This result has a similar flavor as the one for the Lasso. The term s = sp/M equals block sparsity × size of each blocks, i.e to the total number of non-zero coordinates in t * : s = t * 0 . Replacing the sparsity s by sp/M in Theorem 6, we would have obtained ρ * = c(L 0 , α, δ)(sp/M ) log(p)/N which is larger than the bound obtained for the Group Lasso in Equation (28). It is therefore better to induce the sparsity by blocks instead of just coordinate-wise when we are aware of such blockstructured sparsity. In the other case, when K ≤ c(L 0 , α, δ)N r 2 2 (γ, ρ * ), we have C K,r (ρ * , 4/α) = c(L 0 , α, δ) K/N and so one can take ρ * = c(L 0 , α, δ) sK/N . We can therefore apply Theorem 2 with Theorem 8 Let (X, Y ) be a random variables with values in R p × R such that Y ∈ L 1 and X is an isotropic and L 0 -subgaussian random vector in Assume that the Bayes rule (the function minimizing the Huber risk over all measurable functions from R p to R) is a linear function t * , · for some t * ∈ R p which is s-group sparse with respect to equal-size groups (G k ) M k=1 . Let K ≥ 7|O|/3. Assume that there exists α > 0 such that, for all x ∈ R p and all z ∈ R satisfying |z − t With probability larger than 1 − 2 exp(−cK), the MOM Huber group-LASSO estimatort λ,K for For K ≤ c(L 0 , α, δ)s(p/M + log M ), the regularization parameter λ is independent from the unknown group sparsity s (the choice of K can be done in data-driven way using either a Lepski method or a MOM cross validation as in Lecué and Lerasle (2019)). In the ideal i.i.d. setup (with no outliers), the same result holds for the RERM as we assumed that the class F −f * is L 0 -subgaussian and for the choice of regularization parameter λ = c(L 0 , α, δ)( p/(N M ) + log(M )/N ). The minmax MOM estimator has the advantage to be robust up to c(L 0 , α, δ)s(p/M + log M ) outliers in the dataset.

Huber regression with total variation penalty
In this section, we investigate another type of structured sparsity with which be induced by the total variation norm. Given t ∈ R p , the Total Variation norm Osher et al. (2005) is defined as The total variation norm favors vectors such that their "discrete gradient Dt is sparse" that is piecewise constant vectors t.
The estimator considered in this section is the minmax MOM Huber TV regularization defined for all λ > 0 and K ∈ {1, · · · , N } aŝ where the loss is the Huber loss. Let δ > 0, Statistical bounds fort λ,K follows from Theorem 2 and the computation of r 2 , ρ * and the study of the local Bernstein assumption. We start with the computation of the complexity function r 2 . Simple computations yield that the dual norm of · T V is z ∈ R p → z * T V = (D −1 ) T z ∞ = max 1≤k≤p | k i=1 z i | which is not κ-unconditional with respect to the canonical basis (e i ) p i=1 of R p for some absolute constant κ. Therefore, Theorem 5 does not apply directly. To upper bound the Rademacher complexity from (10), we assume that the design vectors (X i ) i∈I are L 0 -subgaussian and isotropic (see Equation (26)) as in Section 6.4. A direct chaining argument allows to bound the Rademacher complexity by the Gaussian mean width (see Talagrand (2014) for chaining methods): A recent result from Chatterjee and Goswami (2019) allows to compute the Gaussian Mean-Width of B p T V .
Lemma 1 (Lemma 4.5 Chatterjee and Goswami (2019)) For any p ≥ 2, there exists a universal constant c > 0 such that It follows from Equation (30) that w(ρB p TV ∩rB p 2 ) ≤ min(ρw(B p TV ), rw(B p 2 )) ≤ c min(ρ log 2 (p), r √ p) and so one can take r 2 2 (γ, ρ) = c(δ, L 0 , γ) min Let us now turn to the local Bernstein Assumption. The loss function and the model being the same as the ones in Section 6.4 the Bernstein Assumption is verified with a constant A = 4/α, if the Bayes rule and the oracle coincide and if there exists a constant α > 0 such that for all x ∈ X and all z ∈ R satisfying |z − Let us turn to the sparsity equation. The following Lemma solves the sparsity equation for the TV regularization.
Compared with Lemma 3, sparsity in Lemma 6 is granted on the linear transformation Dt * (also called discrete gradient of t * ) rather than on the oracle t * . Proof Let us denote C K,r (ρ, 4/α) := r(ρ). Let us recall that We want to find a condition on ρ > 0 insuring that∆(ρ, 4/α) ≥ 4ρ/5. Recall that the oracle t * can be decomposed as t * = u + v, where u ∈ (ρ/20)B T V and thus t * − v T V ≤ ρ/20. Let I denote the support of Dv and s its cardinality. Let I C be the comple- We construct z * = D T u * , such for all i in I, u * i = sign (Dv) i and for all i in I C , u * i = sign (Dw) i . Such a choice of z * implies that z * , v = u * , Dv = i∈I sign (Dv) i (Dv) i = v T V i.e z * is norming for v. Moreover, we have z * * T V = (D −1 ) T z * ∞ = u * ∞ = 1 hence z * ∈ S * T V . Then it follows from (18) that z * ∈ (∂ · T V ) v and since u ∈ (ρ/20)B T V we have z * ∈ Γ t * (ρ). Now let us denote by P I w the orthogonal projection of w onto Span(e i , i ∈ I). From the choice of z * we get z * , w = D T u * , w = u * , Dw = u * , P I Dw + u * , P I C Dw ≥ − P I Dw 1 + P I C Dw 1 = Dw 1 − 2 P I Dw 1 Moreover we have P I Dw 1 ≤ √ s P I Dw 2 ≤ √ s Dw 2 and when ρ ≥ 20 √ sr(ρ).
Theorem 9 Let (X, Y ) be a random variables with values in R p × R such that Y ∈ L 1 and X is an isotropic and L 0 -subgaussian random vector in R p . Assume that (X, Y ), (X i , Y i ) i∈I are i.i.d. Assume that the Bayes rule and the oracle coincide and that t * is such that Dt * is s-sparse. Let K ≥ 7|O|/3. Assume that there exists α > 0 such that, for all x ∈ R p and all z ∈ R satisfying |z − t * , x | ≤ 2L 2 0 C K,r (2ρ * , 4/α), F Y |X=x (δ + z) − F Y |X=x (z − δ) ≥ α (where F Y |X=x is the cumulative distribution function of Y given X = x). With probability larger than 1 − 2 exp(−cK), the MOM Huber TV estimatort λ,K for For K ≤ c(L 0 , α, δ)s log 4 (p), the regularization parameter λ is independent from the unknown sparsity s and t λ,K − t * 2 2 ≤ c(L 0 , α, δ)s log 4 (p)/N which is the right order for s-sparse regression problems (up to the log 2 p term). Without any outliers the same conclusion (for K = c(L 0 , α, δ)s log 4 (p)) holds also for the RERM for λ = c(L 0 , α, δ) log 2 (p)/ √ N since the Assumptions on the design X imply that the class F − f * is L 0 -subgaussian. The minmax MOM estimator has the advantage to be robust up to s log 4 (p) outliers.

Huber Fused Lasso
In this section, we investigate the fusion of two sparsity structures which will be induced by a mixture of the Total Variation and 1 norms. The resulting regularization norm is known as the fused Lasso (see Tibshirani et al. (2005)) defined for some mixture parameters β, η > 0 for all t ∈ R p by t F L = η t 1 + β t T V .
This type of norm is expected to promote signals having both a small number of non-zero coefficients (thanks to the p 1 -norm) and a sparse discrete gradient (thanks to the TV norm) i.e. sparse and constant by blocks signals.
The estimator we consider in this section is defined for all λ > 0 and K ∈ {1, · · · , N } aŝ where t ∈ R p → t denotes the Huber loss function with parameter δ > 0. Theorem 2 may be used to derive robust statistical bounds fort λ,K . To do so we first have to compute a complexity function r 2 . The dual norm of · F L denoted by z ∈ R p → z * F L is not K-unconditional with respect to the canonical basis (e i ) p i=1 of R p ; so Theorem 5 does not apply directly. To compute the Rademacher complexity from (10), we assume that the design vectors (X i ) i∈I are subgaussian and isotropic as in Section 6.4 and 6.5. A direct chaining argument allows to bound the Rademacher complexity by the Gaussian mean width (see Talagrand (2014) for chaining methods): where B p F L denote the unit ball for · F L in R p . Since B p F L ⊂ η −1 B p 1 and B p F L ⊂ β −1 B p T V , it follows from Sections 6.2 and 6.5 that (to simplify the presentation of the results, we used the same upper bound on the Gaussian mean widths of both the p 1 and TV unit balls that is w(B p 1 ), w(B p T V ) ≤ c log 2 (p) instead of using the √ log p sharper bound for w(B p 1 )). We can therefore take Let us turn to the local Bernstein Assumption. The loss function and the model being the same as the ones in Section 6.4 the local Bernstein Assumption is verified with a constant A = 4/α, if the Bayes rule and the oracle coincide and if there exists a constant α > 0 such that for all x ∈ X and all z ∈ R satisfying |z − Finally, let us turn to the sparsity equation. To that end, we will use the following result.
Proof Let us denote C K,r (ρ, 4/α) := r(ρ). Let us recall that where S F L is the unit sphere of · F L and Γ t * (ρ) is the union of all sub-differentials (∂ · F L ) v for all v ∈ t * + (ρ/20)B p F L . We want to find a condition on ρ > 0 insuring that∆(ρ, 4/α) ≥ 4ρ/5. For all t ∈ R p , the sub-differential of the fused Lasso norm is given by (see Theorem 23.8 in Rockafellar (1997) Let w ∈ ρS F L ∩ r(ρ)B p 2 and let us denote I = supp(v) and J = supp(Dv). We construct z * = ηu * + βD T q * such that We have u * , v = v 1 and u * ∈ S * 1 . Likewise D T q * , v = Dv 1 and D T q * ∈ S * T V . Therefore, u * ∈ (∂ · 1 ) v and D T q * ∈ (∂ · T V ) v and it follows that z * ∈ (∂ · F L ) v . Since u ∈ (ρ/20)B p F L we have z * ∈ Γ t * (ρ). Let us denote by P I w (resp. P J w) the orthogonal projection of w onto Span(e i , i ∈ I) (resp. Span(e i , i ∈ J)). We have z * , w = η u * , w + β D T q * , w = η u * , P I w + η u * , P I C w + β q * , P J Dw + β q * , P J C Dw ≥ −η P I w 1 + η P I C w 1 − β P J Dw 1 + β P J C Dw 1 = η w 1 − 2η P I w 1 + β Dw 1 − 2β P J Dw 1 = ρ − 2η P I w 1 − 2β P J Dw 1 .
Theorem 10 Let (X, Y ) be a random variables with values in R p × R such that Y ∈ L 1 and X is an isotropic and L 0 -subgaussian random vector in Assume that the Bayes rule and the oracle coincide for t * in R p such that t * is s 1 -sparse and Dt * is s T V -sparse. Let K ≥ 7|O|/3. Assume that there exists α > 0 such that, for all x ∈ R p and all Let us take β = min(1, s 1 /s T V ) and η = min(1, s T V /s 1 ). With probability larger than 1 − 2 exp(−cK), the MOM Huber FL estimatort λ,K for For K ≤ c(L 0 , α, δ) min(s 1 , s T V ) log 4 (p), we obtain a bound depending on min(s 1 , s T V ). As a consequence, we can use Fused Lasso even when only the sparsity to 1 (or TV) holds. However, note that we obtained this result by choosing η and β depending on the unknown sparsity s 1 and s T V since the latter bounds automatically adapt to the sparsity structure. If both type of sparsity holds (short support and constant by blocks) only the best one is kept. This remarkable feature of the Fused Lasso regularization can be achieved only when the mixture parameters η and β are chosen depending on the ratio of the two sparsity numbers. Given that s T V and s 1 are usually unknown, one should again use an adaptation step on the choice of these mixture parameters. Since s T V and s 1 are in the finite set {1, . . . , p}, this can be easily done using the Lepski's method. The resulting estimator will have the same properties ast λ,K but with a data-driven way to chose η and β. We do not perform this extra step here since it is now well understood (see Devroye et al. (2016); Lecué and Lerasle (2019)).

Robust quantile matrix completion via the minmax MOM quantile trace norm procedure
The aim of this section is to provide an example where the L 4 /L 2 assumption from point a) in Assumptions 10, 11 and 12 is satisfied but with a "constant" C depending on the dimension of the problem. Our aim is to show that even in such a situation, Theorem 2 can be efficiently applied without any loss in the rate of convergence; the only price we pay is on the number of observations we need to insure such a result.
The matrix completion problem with continuous entries has been tackled using a square loss in Candès and Plan (2010); Klopp (2014); Lecué and Mendelson (2018); Mai and Alquier (2015) and robust loss functions in Elsener and van de Geer (2018); Alquier et al. (2017) for bounded or subgaussian classes of functions in the ideal i.i.d. setup. Our aim here is to make no assumption on the class F , that is to take F = { ·, M : M ∈ R m×T } the class of all linear functions, and construct robust procedures, that is procedures which can handle any type of outliers in the database.
Let us start with the particular form of design used in matrix completion.
Assumption 13 generalizes the uniform distribution over the canonical basis of R m×T . In the ideal noiseless and i.i.d. setup, we observe Y i = X i , M * , i = 1, . . . , N where X 1 , . . . , X N are distributed like X satisfying Assumption 13. The aim is to reconstruct exactly M * when M * is known to have low rank Candès and Tao (2010). In the noisy setup, quantile matrix completion can be particularly useful for large and small values of τ (for example the 0.05 and 0.95 quantiles). Actually, these allow to build confidence intervals for Y |X = E p,q for all entries (p, q) of the oracle matrix M * that we want to recover. For this type of problem, global Bernstein conditions have been proved under a boundedness assumption on the class F in van de Geer (2016). In particular, this assumption implies that M * has entries uniformly bounded by some known absolute constant b. There are situations where this assumption is naturally satisfied, for instance, when M * is a users/items matrix whose entries are grades such as {0, 1, 2, 3, 4, 5}. In other applications, M * is a large table of similarities measures using an unbounded metric or kernel. In that case, the boundedness assumption is not satisfied and therefore previous results do not apply.
The main difficulty is that the matrix design under Assumption 13 is degenerated in the sense that it is not a typical diagonal random vector (such as a standard Gaussian vector in R m×T ). In this situation, a L 4 /L 2 norm equivalence assumption holds such as in a) but with a dimension dependent constant C : for all M ∈ R m×T , X, M L 4 ≤ (c/c)(mT ) 1/4 X, M L 2 . The constant C is of the order of (mT ) 1/4 which cannot be improved since it is achieved (up to constants) by a result from Alquier et al. (2017) which we will use as a benchmark. It proves estimation bounds and an oracle inequality for a regularized ERM procedure using the S 1 -norm as a low-rank inducing norm. We recall that the S 1 -norm of M ∈ R m×T is the sum of its singular values.
Theorem 11 (Theorem 11 in Alquier et al. (2017)) Assume that Assumption 13 holds and that the data are i.i.d.. Let b > 0 and assume that M * ∈ bB ∞ . Assume that for any (p, q), Y |X = E p,q has a density g with respect to the Lebesgue measure such that g(u) > 1/c 0 for some constant c 0 > 0 for any u such that |u−M * p,q | ≤ 2b. Let s ∈ {1, . . . , min(m, T )} and assume that M * has rank at most s. Then, with probability at least 1 − c(c 0 ,c, c, b) exp (−c(c 0 ,c, c, b)s max(m, T ) log(m + T )), the estimator where E quantile ( M ) is the excess quantile risk of M .
The S 2 estimation rates obtained in Theorem 11 are the same as the one obtained in Rohde and Tsybakov (2011);  for the penalized least squares estimator that is s(m + T ) log(m + T )/N . We now show how the results from Theorem 11 can be extended in several ways using a tracenorm regularized minimax MOM estimator using the quantile loss function: for all λ > 0 We show below that M λ,K satisfies the same results as in Theorem 11 but under weaker assumptions: we don't need M * to have bounded entries and we allow the dataset to be corrupted. To prove this result we apply Theorem 2 and so we need to check its assumptions.
We start with the local Bernstein condition and to that end Proposition 3 will be helpful: we only need to check Assumption 12 that we do now. We have already seen that point a) of Assumption 12 is satisfied for C = (c/c)(mT ) 1/4 . Given that we make no assumption on the class F of linear functions, we see that f * is the Bayes rules, that is for every x ∈ X := {E p,q : T ] . Hence, point b) of Assumption 12 is satisfied. To check point c) we make the same assumption as in Theorem 11: there are constants C 0 > 0 and α > 0 such that for all z ∈ R satisfying |z − M * p,q | ≤ C 0 , f Y |X=Ep,q (z) ≥ α (where f Y |X=Ep,q is a density function w.r.t. the Lebesgue measure of Y given X = E p,q ). Under this assumption, point c) will be satisfied if 2(C ) 2 C K,r (2ρ * , 4/α) ≤ C 0 where C K,r and ρ * are two quantities that we are now computing using their definitions from Definition 5.
We first start with the computation of the fixed point r 2 2 (γ, ρ) for all ρ > 0 and some γ > 0. When the design X is distributed according to the matrix completion design assumption from Assumption 13 it is (up to absolute constants) isotropic: for all M ∈ R m×T , c(mT ) −1 M 2 S 2 ≤ E X, M 2 ≤c(mT ) −1 M 2 S 2 . A rB L 2 localization is therefore equivalent (up to constants) to a √ mT rB S 2 localization (where B S 2 is the unit ball of the S 2 norm which is the Frobenius norm: the 2 norm of the spectrum). In our setup, we therefore have for all J ⊂ I such that |J| ≥ N/2 where we recall that for all p ≥ 1, S p is the Schatten-p norm, i.e. the p norm of the spectrum. A sharp estimate of ( ) requires estimates of the Euclidean norm of the first singular values of i∈J σ i X i when (X i ) i∈J are i.i.d. distributed according to the matrix design assumption. Such a result is not yet available. We will therefore use a loose estimate here which causes extra log factors.
The key argument to compute the statistical complexity of the problem is Corollary 9.1 in Tropp (2012) (which is also used in Proposition 1 from ); it yields and therefore, one can take We now compute a radius ρ * solution of the sparsity equation. It follows from Equation (15) in Alquier et al. (2017) that, if M * has rank s and K = c(c, c, α)N r 2 2 (γ, ρ * ), then one can pick We see that the condition 2(C ) 2 C K,r (2ρ * , 4/α) ≤ C 0 is satisfied when K = c(c, c, α)N r 2 2 (γ, ρ * ) and r 2 (γ, 2ρ * ) ≤ c(c, c, α)(mT ) −1/2 , i.e. N ≥ c(c, c, α, C 0 )s(mT ) 3/2 log(m + T )/ min(m, T ). We now have all the ingredients to apply Theorem 2 to get the following result.
Theorem 12 Assume that (X i , Y i ) i∈I are i.i.d. such that Y i ∈ L 1 and the design matrices X i is distributed according to the matrix completion design from Assumption 13. Assume that there are constants C 0 > 0 and α > 0 such that for any (p, q) ∈ [m] × [T ], Y |X = E p,q has a density g with respect to the Lebesgue measure such that g(u) ≥ α for any u such that |u − M * p,q | ≤ C 0 . Let s ∈ {1, . . . , min(m, T )} and assume that M * has rank at most s. Let K = c(c, c, α) min(s(m + T ) log(m + T ), M * S 1 (N log(m + T )/ min(m, T )) 1/2 . Assume that N ≥ c(c, c, α)s(mT ) 3/2 log(m + T )/ min(m, T ) and that K ≥ 7|O|/3. Then, with probability at least 1−c(c, c, α) exp (−c(c, c, α)s max(m, T ) log(m + T )), the trace-norm regularized minmax MOM estimator M λ,K with λ = c(c, c, α) log(m + T )/(N min(m, T )) satisfies where E quantile ( M λ,K ) is the excess quantile risk of M λ,K .
For simplicity, we did not write the result for all K in Theorem 12 like in the other examples. We chose K = c(c, c, α)N r 2 2 (γ, ρ * ) to recover the same probability estimate and same results as in Theorem 11. However, this choice requires to know the rank (or at least an upper bound on the rank) of M * and M * S 1 which are usually not available in practice. To solve this issue we can either write the result for all K as in the previous examples and construct M λ,K for this choice of K or use a Lepskii's adaptation method as in Lecué and Lerasle (2019).
Theorem 12 extends Theorem 11 in two ways: we drop the boundedness assumption onto the entries of M * and we allow for corrupted databases (in both inputs and outputs). In particular, the rates of convergence and residual terms in the estimation bounds and the oracle inequality are not downgraded even though the L 4 /L 2 assumption holds with a dimension dependent constant C of the order of (mT ) 1/4 . However, the price we pay for this loose L 4 /L 2 norm equivalence is the extra assumption on the number of data N ≥ c(c, c, α)s(mT ) 3/2 log(m + T )/ min(m, T ). This extra assumption is due to the analysis of the local Bernstein condition via Proposition 12 which uses the L 4 /L 2 assumption. We can relax this assumption into a L 2+ /L 2 assumption (for any > 0), if the sample size is large enough. One could also try to prove directly the local Bernstein condition as it has been done under the boundedness assumption (see Elsener and van de Geer (2018)).
A final word about the proof technique: Theorem 11 follows from Talagrand's concentration inequality which applies only for bounded class of functions. Beyond the boundedness assumption, we need to use other type of arguments (see, for instance, the difference of analysis between the subgaussian and the bounded cases in Alquier et al. (2017)). Here the main result Theorem 2 covers almost any situation with a single analysis and, in particular, the L ∞ -bounded case. Indeed, in that case the local Bernstein is satisfied (see Elsener and van de Geer (2018)) and therefore Theorem 2 applies without any restriction on the number of data.

Simulations
This section provides a simulation study to illustrate our theoretical findings. Minmax MOM estimators are approximated using an alternating proximal block gradient descent/ascent with a wisely chosen block of data as in Lecué and Lerasle (2019). At each iteration, the block on which the descent/ascent is performed is chosen according to its "centrality" (see algorithm 1 below). Two examples from high-dimensional statistics are considered 1) Logistic classification with a 1 penalization and 2) Huber regression with a Group-Lasso penalization.

Presentation of the algorithm
Let X = R p and let F = { t, · , t ∈ R p }. The oracle f * = argmin f ∈F P f (X, Y ) is such that f * (·) = t * , · for some t * ∈ R p . The minmax MOM estimator is defined aŝ where is a convex and Lipschitz loss function and · is a norm in R p . Following the idea of Lecué and Lerasle (2019), the minmax problem (35) is approximated by a proximal block gradient ascent-descent algorithm, see Algorithm 1. At each step, one considers the block of data realizing the median and perform an ascent/descent step onto this block. The regularization step is obtained via the proximal operator prox λ · : x ∈ R p → argmin y∈R p 1 2 x − y 2 2 + λ y .

Algorithm 1: Proximal Descent-Ascent gradient method with median blocks
Input: A number of blocks K, initial points t 0 andt 0 in R p , two sequences of step sizes (η t ) t and (η t ) t and T a number of epochs Output: An approximating solution of the minimax problem (35) To make the presentation simple in Algorithm 1, we have not perform any line search or any sophisticated stopping rule (see, Lecué and Lerasle (2019) for more involved line search and stopping rules). To compare the statistical and robustness performances of the minmax MOM and RERM, we perform a proximal gradient descent to approximate the RERM, see Algorithm 2 below.
Algorithm 2: Proximal gradient descent algorithm Input: Initial points t 0 in R p and a sequence of stepsizes (η t ) t Output: RERM estimator.
The number of blocks K is chosen by MOM cross-validation (see Lecué and Lerasle (2019) for more precision on that procedure). The sequences of stepsizes are constant along the algorithm (η t ) t := η and (η t ) t =η and are also chosen by MOM cross-validation.

Organisation of the results
In all simulations, the links between inputs and outputs are given in the regression and classification problems in R p respectively by the following model: where the distribution of X and ζ depend on the considered framework: • First framework: X is a standard Gaussian random vector in R p and ζ is a real-valued standard Gaussian variable independent of X with variance σ 2 .
• Second framework: X is a standard Gaussian random vector in R p and ζ ∼ T (2) (student distribution with 2 degrees of freedom). This framework is used to verify the robustness w.r.t the noise.
∼ T (2) and ζ is a real-valued standard Gaussian variable independent of X with variance σ 2 . Here we want to test the robustness w.r.t heavy-tailed design (X i ) i .
∼ T (2) and ζ ∼ T (2). We also corrupt the database with |O| outliers which are such that for all i ∈ O, X i = (10 5 ) p i=1 and Y = 1. Here we verify the robustness w.r.t possible outliers in the dataset.
In a both first and second frameworks, the RERM and minmax MOM estimators are expected to perform well according to Theorem 1 and Theorem 2 even though the noise ζ can be heavy-tailed. In the third framework, the design vector X is no longer subgaussian, as a consequence Theorem 1 does not apply and we have no guarantee for the RERM. On the contrary, Theorem 2 provides statistical guarantees for the minmax MOM estimators. Nevertheless, it should also be noticed that the study of RERM under moment assumptions on the design can also be performed, see for instance Lecué and Mendelson (2017). In that case, the rates of convergence are still the same but the deviation is only polynomial whereas it is exponential for the minmax MOM estimators. Therefore, in the third example, we may expect similar performance for both estimators but with a larger variance in the results for the RERM. In the fourth framework, the database has been corrupted by outliers (in both outputs Y i and inputs X i ); in that case, only minmax MOM estimators are expected to perform well as long as |O| is not too large compare with K, the number of blocks.

Sparse Logistic regression
Let denote the Logistic loss (i.e. t ∈ R p → t (x, y) = log(1 + exp(−y x, t )), ∀x ∈ R p , y ∈ Y = {±1}), and let the 1 norm in R p be the regularization norm. Figure 1 presents the results of our simulations for N = 1000, p = 400 and s = 30. In subfigures (a), (b) and (c) the error is the L 2 error, which is here t T K,λ − t * 2 , between the outputt T K,λ of the algorithm and the true t * ∈ R p . In subfigure (d), an increasing number of outliers is added. The error rate is the proportion of misclassification on a test dataset. The stepsizes, the number of block and the parameteter of regularization are all chosen by MOM cross-validation (see Lecué and Lerasle (2019) for more details on the MOM cross-validation procedure) Subfigure (a) shows convergence of the error for both algorithms in the first framework. Similar performances are observed for both algorithms but Algorithm 1 converges faster than Algorithm 2. It may be because the computation of the gradient on a smaller batch of data in step 5 and 6 of Algorithm 1 is faster than the one on the entire database in step 2 of Algorithm 2 and that the choice of the median blocks at each descent/ascent step is particularly good in Algorithm 1. Subfigure (b) shows the results in the second framework. The convergence for the alternating gradient-ascent descent algorithm is a bit faster as the one from Algorithm 2, but the performances are the same. Subfigure (c) shows results in the third setup where ζ is Gaussian and the feature vector X = (x 1 , · · · , x p ) is heavy-tailed, i.e. x 1 , . . . , x p are i.i.d. with x 1 ∼ T (2) -a Student with degree 2. Minmax MOM estimators perform better than RERM. It highlights the fact that minmax MOM estimators have optimal subgaussian performance even without the sub-gaussian assumption on the design while RERM are expected to have downgraded statistical properties in heavy-tailed scenariis. Subfigure (d) shows result in the fourth setup where an increasing number of outliers is added in the dataset. Outliers are X = (10 5 ) p 1 and Y i = 1 a.s.. While RERM has deteriorated performance just after one outliers was added to the dataset, minmax MOM estimators maintains good performances up to 10% of outliers.

Huber regression with a Group Lasso penalty
Let denote the Huber loss function t ∈ R d → t (x, y) = (y − x, t ) 2 /2 if |y − x, t | ≤ δ and t (x, y) = δ|y − x, t | − δ 2 /2 other wise for all x ∈ R p and y ∈ Y = R. Let G 1 , · · · , G M be a partition of {1, · · · , p}, t = t GL = M k=1 t G k 2 . Figure 1 presents the results of our simulation for N = 1000, p = 400 for 30 blocks with a block-sparsity parameter s = 5. In subfigures (a), (b) and (c), the error is the L 2 -error between the output of the algorithm and the oracle t * -which corresponds here to a p 2 estimation error, given that the design in all cases is isotropic. In subfigure (d) the prediction error on a (non-corrupted) test set of both the RERM and the minmax MOM estimators are depicted.
The conclusion are the same as for the Lasso Logistic regression: Algorithm 1 (regularized minmax MOM) has better performances than algorithm 2 (RERM) in case of heavy-tailed inliers and when outliers pollute the dataset while both are robust w.r.t heavy-tailed noise.

Conclusion
We obtain estimation and prediction results for RERM and regularized minmax MOM estimators for any Lipschitz and convex loss functions and for any regularization norm. When the norm has some sparsity inducing properties the statistical bounds depend on the dimension of the low-dimensional structure where the oracle belongs. We develop a systematic way to analyze both estimators by identifying three key idea 1) the local complexity function r 2 2) the sparsity equation 3) the local Bernstein condition. All these quantities and condition depend only of the structure and complexity of a local set around the oracle. This local set is ultimately proved to be the smallest set containing our estimators. We show the versatility of our main meta-theorems in an extensive applications section covering three different loss functions and five sparsity inducing regularization norm. Some of them inducing highly structured sparsity concept such as the Fused Lasso norm.
On top of these results, we show that the minmax MOM approach is robust to outliers and to heavy-tailed data and that the computation of the key objects such as the complexity functions r 2 and a radius ρ * satisfying the sparsity equation can be done in this corrupted heavy-tailed scenario. Moreover, we show in a simulation section that they can be computed by a simple modification of (a) Gaussian design and Gaussian noise.
(b) Heavy-tailed noise ζ (Student distribution of order 2) and standard Gaussian design.
(c) Gaussian noise and heavytailed design (Student distribution of order 2).
(d) Student of order 2 design and noise corrupted by outliers. existing proximal gradient descent algorithms by simply adding a selection step of the central block of data in these algorithms. The resulting algorithms is indeed robust to heavy-tailed data and to few outliers (in both input and output variables). All along this section we will write r(ρ) for r(A, ρ). Let θ = 1/(3A). The proof is divided into two parts. First, we identify an event where the RERMf :=f RERM λ is controlled. Then, we prove that this event holds with large probability. Let ρ * satisfying the A-sparsity Equation from Definition 4 and let B = ρ * B ∩ r(ρ * )B L 2 and consider Proposition 4 Let λ be as in (6) and let ρ * satisfy the Asparsity from Definition 4. On Ω, one has Proof Prove first thatf ∈ f * + B. Recall that Sincef satisfies P N L λ f 0, it is sufficient to prove that P N L λ f > 0 for all f ∈ F \(f * + B) to get the result. The proof relies on the following homogeneity argument. If P N L f 0 > 0 on the border of f * + B, then P N L f > 0 for all f ∈ F \ {f * + B}.
For all i ∈ {1, · · · , N }, let ψ i : R → R be the random function defined for all u ∈ R by By construction, for any i, ψ i (0) = 0 and ψ i is convex because is. Hence, αψ i (u) ≤ ψ i (αu) for all u ∈ R and α ≥ 1. In addition, For the regularization term, by the triangular inequality, From the latter inequality, together with (38), it follows that As a consequence, if P N L λ f 0 > 0 for all f 0 ∈ F ∩∂(f * +B) then P N L λ f > 0 for all f ∈ F \(f * +B).
In the remaining of the proof, assume that Ω holds and let f 0 ∈ F ∩ ∂(f * + B). As f 0 ∈ F ∩ (f * + B), on Ω, By definition of B, as f 0 ∈ ∂(f * + B), either: . We treat these cases independently.

Proof Theorem 2
All along the proof, the following notations will be used repeatedly.
Let B κ = C K,r,κ B L 2 ∩ κρ * B. Consider the following event Proof For any f ∈ F , denote by S(f ) = sup g∈F MOM K [ f − g ] + λ f − g . If (44) holds, by homogeneity of MOM K , any f ∈ f * + F \B κ satisfies On the other hand, if (45) holds, Thus, by definition off and (45), It follows that In addition, f − f * ≤ κρ * . Therefore, from the choice of λ, on Ω K , one has Assume that f belongs to F \B κ . By convexity of F , there exists f 0 ∈ f * + F ∩ B κ and α > 1 such that For all i ∈ {1, · · · , N }, let ψ i : R → R be the random function defined for all u ∈ R by The functions ψ i are convex and satisfy ψ i (0) = 0. Thus αψ i (u) ≤ ψ i (αu) for all u ∈ R and α > 1 Hence, for any block B k , By the triangular inequality, Together with (51), this yields, for all block B k As f 0 can be chosen in ∂(f * + B κ ), either: Since the sparsity equation is satisfied for ρ = ρ * , it is also satisfied for κρ * . By (41), Therefore, on Ω K , there are more than K/2 blocks B k where It follows that Assume that f 0 − f * L 2 = C K,r,κ and f 0 − f * ≤ κρ * . By Assumption 7, on Ω K , there exist more than K/2 blocks B k where It follows that From Equations (48), (56) and (57) with κ = 1, it follows that Therefore, (45) holds with η = 11θC K,r,2 . Now, Equations (56) and (57) Therefore, Equation (44) holds with η = 11θC K,r,2 . Overall, Lemma 3 shows thatf ∈ B 2 . On Ω K , this implies that there exist more than K/2 blocks B k where P Lf ≤ P B k Lf + θC K,r,2 . In addition, by definition off and (58), This means that there exist at least K/2 blocks B k where P B k Lf +λ( f − f * ) 11θC K,r,2 . As f − f * − f − f * −2ρ * , on these blocks, P B k Lf ≤ 31θC K,r,2 . Therefore, there exists at least one block B k for which simultaneously P Lf ≤ P B k Lf + θC K,r,2 and P B k Lf ≤ 31θC K,r,2 . This shows that P Lf ≤ 32θC K,r,2 ≤ A −1 C K,r,2 .