Beyond Tikhonov: faster learning with self-concordant losses, via iterative regularization
Authors: Gaspard Beugnot
Julien Mairal
Alessandro Rudi
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Kernel methods
learning theory
self concordance
iterated tikhonov
proximal point

Abstract: The theory of spectral filtering is a remarkable tool to understand the statistical properties of learning with kernels. For least squares, it allows to derive various regularization schemes that yield faster convergence rates of the excess risk than with Tikhonov regularization. This is typically achieved by leveraging classical assumptions called source and capacity conditions, which characterize the difficulty of the learning task. In order to understand estimators derived from other loss functions, Marteau-Ferey et al. have extended the theory of Tikhonov regularization to generalized self concordant loss functions (GSC), which contain, e.g., the logistic loss. In this paper, we go a step further and show that fast and optimal rates can be achieved for GSC by using the iterated Tikhonov regularization scheme, which is intrinsically related to the proximal point method in optimization, and overcomes the limitation of the classical Tikhonov regularization.

Beyond Tikhonov: Faster Learning with
Self-Coneordant Losses via Iterative Regularization
Gaspard Beugnot Inria*
Julien Mairal Inriat
Alessandro Rudi Inria
gaspard. beugnot@inria.frr
julien. maaialliiiii....
Mudsanddro.ruiiiimmee
Abstract
The theory of spectral filtering remarkable tool to understand the statistical properties of learning with kernels. For least squares, it allows derive various regularization schemes that yield faster convergence rates of the excess risk than with Tikhonov regularization. This is typically achieved by leveraging classical assumptions called source and capacity conditions, which characterize the diffi- culty of the learning task. In order understand estimators derived from other loss functions, Martcau-Ferey et al. [1] have extended the theory of Tikhonov reg- ularization generalized self concordant loss functions (GSC), which contain, e.g., the logistic loss. In this paper, we go step further and show that fast and op- timal rates can be achieved for GSC by using the iterated Tikhonov regularization scheme, which is intrinsically related to the proximal point method in optimiza- tion, and overcomes the limitation of the classical Tikhonov regularization.
Introduction
We consider the problem of supervised learning where we want to find prediction function mapping an input point x living set to a label y in V. In this paper, we assume that lives in separable Hilbert space H and is learned from set of observations (æ;, 1i.i,,...,, that are i.i.d. samples drawn from an unknown probability distribution p on X' minimizes the expected risk L, which is defined below along with the empirical risk L:
The goal is find that
L(0)= = - Cly (z)d(x)) v), I())
Σ Cyv, ((z)),
where l is a suitable loss function comparing true labels with predictions. This paper aims for upper bounds on the excess risk for specific estimator 0. That is, we assume that the minimum of the expected risk is attained for some 0* in H. and we want to derive probabilistic upper bounds on the excess risk:
[())) - T((0)) > Cin log
5
(2)
given some value in (0, 1), where C1 is a positive constant, and is an estimator built from the n observations. The quantity O(n-?) denotes the rate of convergence of the estimator Ô. A classical "slow" rate with 7 = 1/2 typically achieved by many estimators and fact optimal only mild assumptions are made about the data distribution p. Even though optimal, this rate is nevertheless a worst case and faster rates with 7 1/2 can be achieved both in theory and in practice, by making additional assumptions about the difficulty of the learning task. Originally introduced in the
Iniia, École normale supérieure, CNRS, PSI. Research University, 75005 Paris, France Inria, Univ. Grenoble Alpes, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

literature of inverse problems, the so-called source and capacity conditions have been shown to be appropriate for this purpose, leading to statistical analysis with fast rates of convergence [ 2 3. The optimality of results of the form (2 is characterized by comparing them with lower bounds that are available for various sets of data distributions p A Matching upper bounds with lower bounds ensures that the estimator 8 is optimal, in the sense that no information is lost in the process of exploiting the data samples to compute 0, for the given set of distributions.
In this search for optimal estimators, most of the attention has been devoted to minimizers of some function of the empirical risk L, which is defined in (Eq. ( Then, the key challenge is regularize L in order to achieve better generalization properties. The most widely used scheme is probably Tikhonov regularization; other examples when H is RKHS include truncated regression A or early stopping in gradient descent algorithms [ 6] When the loss E is set to least squares, it can be shown that minimizing the excess risk amounts to solving
ill-posed inverse problem [7]. which led to the remarkable theory of spectral filtering. A large class of regularization schemes can indeed be seen filtering process applied to the training labels yi after regularizing the spectrum of the kernel matrix 22 g Interestingly, this theory has highlighted the fact that not all regularization schemes equal: some of them obtain fast learning rates in on "easy" problem thorough definition is given in Section 2 while others cannot leverage this additional regularity to improve the learning rate.
Such a general analysis for least squares is made possible by the fact that a closed-fome expression of the estimator is available. When considering different loss function e, the estimator 0 is unfortunately only implicitly available as the solution of an optimization problem involving L. A step to extend least squares results more general loss functions has been achieved by Marteau-Ferey et al. M. who provide bounds the form (2) for Tikhonov estimator on generalized self concordant (GSC) functions. GSC functions are three-times-difeeeentabl functions whose third derivative bounded by the second-derivative. In practice, they were introduced to conduct general analysis of the Newton method in optimization 19 [0), and adapted in [ to encompass a larger class of loss function. It includes notably the logistic regression loss, which is widely used for classification.
While Tikhonov yields fast rates of convergence in several data regimes, it is known be unable to adapt to the whole range of learning task difficulties. More precisely, it suffers from a "saturation" effect (2). meaning that when the learning task becomes simpler, the learning rate stops improving and is suboptimal. Our paper addresses this limitation for GSC functions by considering instead the iterated Tikhonov regularization (IT) scheme. the context of least squares, this approach consists of successively fitting the residuals. For more general loss functions, it is equivalent to performing few steps of the proximal point method in optimization 112. Our main result a probabilistic upper bound on the excess risk, which is optimal given usual source and capacity conditions assumptions on the learning task, thus addressing the limitations of the classical Tikhonov regularization.
2 Background and Preliminaries
2.1 Definitions: Estimator and Loss Function
Let X' be a Borel input space, y be vector-valued output spaces, and p a probability distribution on X' x y) We consider H to be separable Hilbert space of functions from X' to ). Given a loss function f: y x y + R, we aim at minimizing the expected loss, while we only have access to the empirical loss both are defined in Eq. (I. Our work provides an upper bound on the excess risk of the iterated Tikhonov estimator. For the basic case of least squares with y = R. it is usually defined
as a procedure that refits the residuals, see, e.g.. $5.4 in 22). Starting with 0 = O, it consists of the sequence
12 1
03 = 01-1 + arg min
ΣΣ4 n
y: - - 0(x))) -(:)))))) 2
+ 1101
(3)
BEH
To extend this regularization to other loss function, we make the change of variable H' = -0-1 + in the equation above, which yields the proximal point algorithm [12].

---

Definition (Iterated Tikhonov estimator a.k.a. proximal point algorithm). We define the iter- ated Tikhonov estimator with the following sequence. Given À > 0 and 03 = 0.
0 -prox T.A (0%)
def. arg min + 1 03
BER
where prox denotes the proximal operator of the empirical risk L rescaled by 1/x.
Remark In practice, the proximal operator is only computed approximately by using an optimiza- tion algorithm. Nevertheless, the benefits in terms of statistical accuracy of the iterated Tikhonov scheme are robust to inexact solutions, as long as the accuracy for solving the sub-problems (Eq. is high enough. We discuss this point in Section 3.2]
Remark 2. It is easy to show that the sequence of the proximal point algorithm always converges to minimizer of the unregularized empirical risk, which is of course not what we are interested in. Instead, we consider and analyze the procedure with fixed small number of steps and show later that optimal learning rates can be obtained by choosing an appropriate parameter A.
Remark 3. When the loss is a function of a residual y ((x) assuming y to be a vector space as in the least square case, recover the classical definition consisting of refitting the residual, and with = 1, we recover Tikhonov.
Interestingly, our definition makes the estimator compatible with other loss functions, such as the logistic loss. More precisely, the main assumption we make on the loss is to be generalized self concordant. We follow the definition of I1 which a special case of 2-self concordance introduced in 13:
Definition (Generalized self-concordance), For any z x,y X xy, the function Eg : RR defined as (0) Ely, ((x)) is convex and three times differentiable. Besides, there exists a set <(=) C s.t: h0
< sup |K (0) gEe(=)
(5)
The brackets indicate that the vectors h and k are applied to the 3-dimensional tensor ( The definition seems technical at first sight, but intuitively, this assumption allows to upper bound the deviation between the objective function and its local quadratic approximation. This enables simple analysis of the Newton method for optimization, making it easy to quantify the basin of quadratic convergence [14]. On top of this, it has the benefit of encompassing a large class of loss functions, such the logistic loss: Example in 1 for values of ((2) with usual losses. We provide some intuition on GSC loss functions in Remark Gi Appendix C.I
In order to ensure the existence of the loss and its derivatives everywhere, we also need the following technical assumptions also introduced in [1, which are reasonable in practice. This ensures that both
and T. are generalized self concordant too.
Assumption (Technical assumptions). There exists R s.t supge |e9e| s R almost surely for Tr (0) are almost surely bounded.
drawn from the distribution and [C)(
The following assumption is usual excess risk analysis 15 In our proof strategy, all the quan- tities vectors and operators in H. which makes the analysis simpler. Weakening this assumption (e.g. assuming that 8 E (2())) would require finding an equivalent of the covariance operator for GSC loss function, which constitute interesting future direction.
Assumption (Existence of a minimizer). There exists 6* in H s.I I.(0*) = inføeH L(O).
Finally, following
① we also define the expected Hessian and the regularized expected Hessian as ( = EE-p ( ()) = H())+ AI,
v0 E 0,
and we introduce the degrees of freedom, also known as the effective dimension of the problem: Definition 3 (Degrees of freedom). The degrees of freedom is defined as:
AX, df = Ex~p [ (1,,0)
where we denote by ||0||A- ||At/20||, with 0 E H. the norm induced by a positive definite operator A on H.
3

---

Remark 4. The intuition about this definition is not straightforward. To better understand why this quantity is a key to characterize the amount of regularization
learning problem, it is useful to consider the specific case of the square loss with kernels. In such case, H. is reproducing kernel
Hilbert space (RKHS) and ((r) A (x)), where + X - H the kernel mapping. Then, the Hessian is constant everywhere and equal to the covariance operator T Egwp, (+))) @ (xx) where Ps is the marginal of p. Consequently, the degrees of freedom (also known as effective dimension) a spectral function of T which may be written as y Tr TTx' This is the classical quantity which appears on the bias/variance decomposition of the excess risk, with a variance part decaying in Tr 7 /n, see
2.2 Source and Capacity Conditions
We now introduce the hypotheses we make on the learning task, which will allow us to derive fast rates of convergence. They measure the difficulty of the problem and are classical in the context of learning with kernels, see e.g. g 17.. It is indeed established that given an algorithm which outputs an estimator 8, one can find a probability measure s.t the learning rate of the estimator is arbitrarily low, result known as the "no-free lunch theorem" [88] Inspired by the literature of inverse problems, two assumptions were introduced to restrict the space of considered distributions.
Assumption (Source condition). There exists r > and v H. s. t: 6 = =H"(0")
A A" is the usual power for positive definite operators. The source condition should be seen as a smoothness assumption on 0", and for least square, we recover the usual definition of the source condition, that 6* T" u, with the covariance operator we previously defined. Bigger implies that the optimum can be well approximated by few cigenvectors. Assuming r = 0 simplifies to 0" H.
The second assumption characterizes the iol-posedsess of the problem:
Assumption 4 (Capacity condition). There exists a > s, > O...t SA-1/o I dfx S SA-1/a,
Again, for the square loss, it turns to a bound on the eigenvalue decay of the covariance operator. oj: Cj is eigenbasis of T, then o; O(j=a), Said differently, the bigger a, the fewer directions are needed to approximate well a sample x ~ Pr: in expectation, and the easier is the learning task. This is assumption on the input space X' and does not imply anything on the labels V.
2.3 Previous Results
Our main result considers iterated Tikhonov with GSC loss functions. While iterated Tikhonov has been previously analyzed for squared loss by leveraging the theory of spectral filtering (see below), extensions to other loss functions raise several difficulties, which will be detailed in Section 3
Spectral filters and least squares. As we mentioned earlier, the key insight on regularization with the square loss is that closed-form expression of the estimator is available. By using the same notation as Remark the kernel ridge regression estimator can be for instance written
K n
0x = Σ 3 (Zx) with ,
9A n
y.
(6)
where K is the n x n kernel matrix, y = (3s Usssn is the vector of training labels and gx (K/n) = (K/n + AI)-1. Note that 9x is function acting the spectrum of K, which makes it special case of regularization by spectral filtering, which may be analyzed for more general functions 9x- In particular, key quantity for understanding the regularization effect of filter gx is the so-called qualification. Following 22 g) this quantity is defined below.
Definition 4 (Qualification of a spectral filter). For any X > O, define ga : [0, 1] + R a filter function. Its qualification is the highest such that
Yv S
sup -ogx(ogxaoooo 0" S Sud"
with Wy a constant independant of X.

---

Under the source and capacity conditions, it is possible to show that the resulting estimator would 1(1)
enjoy an optimal rate in n. IT if r + 1/2 I (where r comes from the source condition). 121)
When r + 1/2 > q. the rate is instead of order n IT which is suboptimal, see e.g. Thm. 3.4 17 (set the parameter schemes. For example, Tikhonov regularization amounts to filtering with 9x a + (a + X) and has qualification 1, so the parameter r saturates at r = 1/2. Thus, even if r 1/2. the excess risk of fg will decay in n rīu, which is suboptimal. Designing estimators with high qualification is key obtaining fast rates that can adapt to both hard and easy learning tasks.
1/2). This illustrates the saturation effect of some regularization
Iterated Tikhonov with the Square Loss. sponding to & iterations IT, which yields
We can compute the spectral filter function o corre-
(-1 Σ ==
o )+ ) = =0- (1-(
x aa-
(8)
Choosing fixed and computing the supremum of a + |1 agx(a)l o", we find that IT estimator has qualification which is thus better than Tikhonov. IT has been thoroughly studied in the com- munity of inverse problems, dating back to the work of [19]. It was naturally transferred to learning with kernels thanks the aforementioned connection with inverse problems.
The link we make with the proximal point algorithm has never been studied from a statistical per- spective, the best of our knowledge, even though it has attracted lot of attention in the optimiza- tion literature, notably with accelerated algorithms (20 21], or variants of the proximal operator on class of self-concordant loss functions [22]. More attention was devoted to boosting, where the penalty À is fixed but the number of iterations t may to infinity, necessitating an appropriate stopping rule (23]. Nevertheless, such work focuses on the least square loss, where the theory of spectral filter can be applied. Finally, the proximal sequence in Eq. (4) can be cast as a constrained
optimization problem related to sequential greedy approximation [44
Tikhonov and Generalized Self Concordant losses. Extending the results obtained with the square loss to more general losses is challenging since there is no closed form available for the resulting estimator, and the theory of spectral filtering does not apply. Nevertheless, the case of Tikhonov regularization for GSC loss functions was treated []. It is shown that the resulting esti- mator enjoys optimal rate as long as 1/2, meaning that the saturation of Tikhonov regularization recovered in those settings. We will extend these results to the IT regularization, showing that an improved qualification be achieved, leading to fast rates for larger class of learning tasks.
3
Main Result
Our main result establishes optimal non-asymptotic bias variance decomposition of the excess risk. It is optimal in the sense that choosing an appropriate regularization parameter À enables to achieve the optimal lower rates of convergence established for least squares.
Theorem 1 (Optimal rates of IT estimator). Let ô E (0, 1]. and set X E (0, Lo), 2 N. The following bound on the excess risk holds with probability greater than 28:
dfx with s min fr + 1/2.t}.
L - ((0) S 2 + C
(9)
n
If we further assume that the capacity condition holds and that the estimator does not saturate, that is t 2 + 1/2, then setting
Crisk n F1
(10)
makes the following holds with probability greater than 28:
1(0%) L(0*) < 2Crisk n 14a(2r117
(1I)
The constants Lo, N, Chius, Cvar; Crisk are detailed in Theorem the appendix; they are explicit and depend only a, S, R, t, 8 and the distribution p.
5

---

Optimal rates. First, we note that the decay rate of the excess risk is optimal provided t 2 r+ It means that, up to constant factors, no estimators trained on n observations can benefit from better learning rate (in the worse case sense) with the prior considered on p, that is source and capacity conditions of parameters r, a. This leads to the second point: we see that IT has qualification g = When = 1, this is Tikhonov estimator and we recover the result of [. This qualification shows in the bound on the bias: if < t 1/2, the bias is optimal in > otherwise, it suboptimal and decays only in X which leads to higher excess risk, hence generalization error.
Influence of The leading multiplicative constant of the rate Cvar in Eq. (9) depends linearly on the number of steps i, as shown in Eq. (55) in Appendix B.5 Thus, the rate in Eq. (IT) is optimal in n when (r)) Letting go to infinity amounts to minimizing the empirical risk, which yield the unregularized estimator: this agrees with our bound on the excess risk, as the constant Cvar would go to infinity in that case.
Source and capacity condition. The source and capacity conditions enable precise bounds on the bias and the variance, respectively. If they do not hold, the bias can only be bounded by O()), while we can upper bound the degrees of freedom with O(1/A), leading to slow learning rates. If the source condition holds but the capacity condition does not, we then obtain learning rates in 22//(2++1) 8 min {r 1/2, which are also optimal in these settings.
Example: a very easy learning task. Suppose the source condition satisfies r 10 and that the capacity condition does not hold. Then, using Tikhonov estimator []] amounts to setting t = 1. The generalization error would then decay as n 2/33, On the other hand, using Iterated Tikhonov estimator with /. = 10 would make the generalization error decay in n -20/21 which is much better.
3.1 Sketch of the proof The proof, which is fully detailed in the appendix, has the following outline:
First, we give technical results generalized self concordant functions;
Then, we define the intermediate quantity in our bias-variance decomposition;
Finally, we proceed bounding the bias and the variance separately, which plugged to- gether give our bound on the excess risk.
To prove the theorem above we build upon the tools from [1] generalized self concordant func- tions. The resulting proof covers and simplifies the case of Tikhonov regularization (one step of iterated Tikhonov) and generalizes the rates to > 1/2. We provide also fine control of the constants, that takes into account the sequential nature of the IT estimator.
Properties of generalized self concordant loss functions Here, we report key properties of GSC loss functions, which are covered in depth in Appendix [ GSC loss functions are convenient to study as they come with a set of bounds on the Hessian, the gradients and the function values. Intuitively, by integrating multiple times the relation between the third and second derivative in the definition from Eq. (5), one can obtain bounds on function values. To introduce them, we first define the following function:
4O E H, t(0) = sup sup Ig 0).
(12)
=ESupp gEd(s)
By integrating three times the bound of the definition, one can show that:
T,(0)) T.(0)) S v (1(0 (-)) I 0+ 001 H(O))
V: W:try (1 13/12.
(13)
This type of bound first appeared in [1] and was given in this form in [. We report it in Proposi- tion 3 in the appendix. For instance, when E is the square loss, = 0 everywhere and the r.h.s turns
to 1/2 11, see 17 (25). On top of this, we generalize a lower bound on the gradient:
Lemma 1 (Stacking operator on gradient bounds). Let 0, E H. A 0. If A H commutes with HE),, the following holds:
H
1(0 5) (t(v 0)) |[ (), S [|A(V
VL,
(14)
where o: t e1- /t.

---

Together with Eq. (3)). this result is the workhorse of our proof for the upper bound on the excess risk. It detailed and proven in Appendix
relate the excess risk with the distance between estimates. This is why bounding the excess risk amounts to finding a good bias-variance decomposition. Most of the proof find for the square loss rely the quantity
Bias-variance decomposition. Thanks Eq. [3).
J = 9 (TYTT0
(15)
with / - 1/n ((x)) @ ((;)) ) the empirical covariance operator, obtained by replacing P with the empirical distribution in Remark 4 This is basically the estimator trained on noiseless empirical data (i.e. using 8* (x²) instead of y1) 17 26 23 Unfortunately, working with GSC function makes the spectral filtering point of view inapplicable. We need to translate closed-fon expression of the intermediate quantity with filters into the solution of an optimization problem. In our case, we can achieve the optimal bias bias-variance decomposition with the following quantity:
8 = 0",
(16)
gh+1 = L 1/(
k20 0.
Consequently, we write
|0
0 (H())))) S 100 -XXl |105 1H
(17)
We recover Eq. (15) with the square loss. In different differeent decomposition is used; found Eq. (T6)
to greatly simplify the proof.
Bounding the bias and the variance. The first term in Eq. 17 is the bias of the estimator, as it goes to when the regularization À goes to O. By applying the lower bound on gradient values Eq.
14 with the definition of the proximal operator, one can express |10% * || function of -1 Unfolding the recursion, we obtain Theorem 2 in the appendix. It shows that the bias decreases in O (X*+1/2) if the qualification is sufficient, i.e. 2 r + 1/2. Otherwise, we recover the saturation experienced with least squares; the bias only decreases in O (X*). Specific attention devoted bounding the prefactor, which is otherwise difficult manage.
10x
The second term in Eq. 17 is the variance, as it goes to O when the number of samples n increases. Theorem shows that decays in dfx/n.). It follows closely the work of [7]. However, we cannot the convenient fact that df, Tr H(0)) ( " which is valid for least squares but not in general. Thus, we took specific care in adapting our bounds to the different regimes so as not to impact the learning rate.
Plugging these results together, we obtain the upper bound on the excess risk.
3.2 Optimization
The aim of this section is to extend the result of Theorem to a practical case, where we only have access to an inexact solver for computing the proximal operator. Specifically, let e > 0 be the error (to be defined precisely in Proposition Il made when approximating 05 with 8", the quantity we compute numerically. We aim for a bound of the type:
L(O%)) - L(0") < Criste n T +
2f (1)
The first term in the right hand side is the statistical error, and optimal following the discussion of Theorem [ The second term is the optimization error, which is the price to pay for approximating 0% by &x with tolerance e. The goal to give simple optimization rule on the sub-problems to ensure that is of the same order as the upper-bound for the noiseless case.
Assuming that cannot compute the proximal operator in Eq. (4) exactly, we need evaluate how the error approximating 0 propagates to the evaluation of 02 and so on. As generalized self-concordant functions are well suited to (approximate) second-order optimization scheme,
7

---

assume we use a solver with guarantees on quantity called Newton decrement, such as the one
developed in [4. Starting from 0 0² 0, define the following for l >
0 arg min (0) def. [(0) + X | 0
(0) def.
Vī (0)
(18)
SEH
0x s arg min x (0) T.(0) + 2 0
A
1|
D (0)
def. VT - (0)
(19)
SEH
(0)
8x approximates the proximal operator evaluated 0x and T is the function manipulate
at step t. If the optimization was carried without error in Eq. 19), we would have I'-L = -'-1, The quality of the approximation is measured with the Newton decrement of Eq. (19). see e.g. Lemma of [14]. We need to enforce a bound on the true Newton decrement in Eq. (18) when we only have
access I The next proposition gives a simple rule to achieve this.
Proposition (Error propagation with proximal sequence). Let E > the target precision. Assume that can solve each sub- sub-problem with precision EK:
1.4
Wk (I.
(0%
SE, En
and that S VX/(2R). This suffice to achieve an error the target function:
1/-1 (02) Se.
This is a specialized version of Proposition whose proof is detailed in the appendix. Intuitively, this means that enforcing geometrically higher precision the first steps is sufficient to obtain high precision on the final estimate. To compute IT's estimator in practice, one would need to solve É optimization problem with decreasing precision. As second order schemes have double logarithmic complexity w.r.t the precision c, the complexity of computing the proximal sequence of IT with tolerance would be only (up logarithm term) times bigger than estimating Tikhonov estimator with tolerance e. In practice when learning with kernels, one would use the representer theorem and aim estimating / in Ih" in Eq. 6 (7). This results in an optimization problem with n observations in dimension use Nyström projection avoid this cubic computational burden in the number of samples. The statistical effects of such projection are well studied with Tikhonov regularization 14. [5]; their effect on other regularization scheme is an interesting future research direction.
with complexity ((n"). A practical implementation could
This proposition can be used directly to bound the excess risk with inexact solvers.
Proposition 2 (Upper bound on the exeess risk with inexact solvers). Lei ô E (0, and assume that the statistical assumptions of Theorem 7 hold as well as the optimization assumptions of Propo- sition] Then, the following bound on the excess risk holds with probability greater than 1 28:
L(B')) - I(00) S 2Crish n HaaBri E1/22,
((2r+1)
min fr + 1/2,t)
(20)
with Crisk as in Theorem 7 and E1/2 S
This is specialized version of Proposition g proved in the appendix. The first term is the statistical excess risk, whereas the second term is the price we pay for inexact approximation. For the
sake of clarity, crude upper bounds were used (notably H, 1/2 (-) < / at the expanse of big constants. They can be expected to be an order of magnitude lower in practice.
Setting in real application. In classical machine learning settings, we do not have access to the source condition parameter r. The number of proximal steps / can seen as an hyperparameter, which is chosen by cross-validation. One would run the algorithm and test the resulting error on a validation set for each iteration, and keep doing proximal steps as long as the validation loss improves.
8

---

Experiments
The purpose of the experiments is illustrate the saturation effect of the Tikhonov estimator when r >> 1/2, and see how the saturation is overcome by iterated Tikhonov IT. We also show that the statistical rates we derive achieved both in theory and in practice synthetic data with well-controlled source and capacity conditions.
Settings. To that end, we use synthetic binary classification data set for which we know the source and capacity condition parameters and a by design. Then, we study the performance of IT(t), t , 8), trained with the logistic loss, which satisfies Definition 2 about generalized self-concordant functions. Related experiments were conducted in the context of kernel ridge re- gression with synthetic data in [16], which we follow here. Specifically, we use splines of order to define a kernel matrix:
2irk(a-=) |K|
(xx,2) Ao 22,
KEZ
is positive even integer (see for instance Eq (2.1.7) in (28). We then use X [0, 1]. Ps is the uniform distribution, and (*) = A(r+1/2)a+1/200 (0,-). -), which may be shown to live in the RKHS H of K. Then, it is possible to show that the source and capacity assumption are satisfied with value r, at see [16]
for which closed form expression is available soon
Finally, we design the distribution Pujar of the labels such that 0" is indeed the minimizer of the risk over H. This may be ensured 0* coincides with the minimizer of the risk over the set of measurable functions, which has the following form under mild assumptions (see Eq. (3) in (66)):
0* (x) arg min Enja [e(y,2))
(21)
The previous relation can satisfied by choosing Pule accordingly. More precisely, we need
- P(y 1 1 1
(1+e))))) (x))
Ply = -1 |2)
(1 + -1
details in Appendix E To knowledge, this is the first synthetic dataset with given source and capacity condition for classification tasks. For each X, t, we sample n points uniformly on [0, 1], evaluate 0", the observed labels ys, and 03. We evaluate the excess risk (0)) L(0*) with Monte Carlo sampling. We then report the lowest excess risk achieved across the regularization A, and the optimal regularization used to achieve this loss. We plot lines of slope 2sa/1+2so and a21+ respectively, with s (r + 1/2) A in order to compare the statistical rates achieved in practice and in theory.
which ensures that Eq. 21 holds
Results. Results for the logistic loss are available in Fig. and we also present results with least squares where the noise is Gaussian in Appendix E.2 We set a = 2, r E (1/4, 41/4], and we study corresponds to Tikhonov estimator and saturates at = 1/2. IT(3) and (8) saturates at r = 5/2 and r = 15/2 respectively. 1/4; however, only IT exploits the additional regularity of the easy task, with r = 41/4. This experimentally shows that better sample complexity can be achieved when the learning task is easier and is high, matching the rates predicted in Theorem 4 which are -<(++2)/ with min {r, t - 1/2]. Learning rates were estimated with an ordinary least square regression in log-log scale, and are given in Table D where they are compared with the theoretical values. To conclude, improvement in absolute value of the excess risk in the range r < f, suggesting that IT is useful when the learning task is hard. This could be because of lower constants for high t: e.g. show that Chias decays in 1/1" when /. 2 r + 1/2,, see Theorem in the appendix. We report in the appendix additional experimental results such as plots with the chosen regularization of n, and plots on the ratio between the excess risk of (T and Tikhonov, to show that the former consistently better than the latter on easy tasks.
the performance of Iterated Tikhonov estimators with t E (1.3, 8). t
Consequently, all estimators have optimal rates the difficult task with
observe slight
function
5 Conclusion
This paper studies a well-known regularization scheme for least square, and extend it for the first time to other loss functions, which notably contain the logistic loss used for classification. We prove

---

110% (08)) - L(07
1(05) 1(0)
10-3
10
10
10a
10a
10a
10a
n
Figure 1: Excess risk for various Iterated Tikhonov estimators function of n. Colors: i = 1 (Tikhonov) estimator is shown in blue; t 3, green, orange. Left: from a difficult problem, 1/4, a 2. Right: easy problem,
41/44, a 2. Plain lines are predicted by theory, with min {r, w-,t-0 1/2] (see main text). All plots are averaged over 100
slope (0(1+22/1++0112))) runs of the optimization procedure with different initialization.
Table 1: Learning rate coefficients for capacity condition a and various source condition as- sumption r. We estimate y with ordinary least square with the model L(Ø)) - L(0*) x n We display the coefficient expect in theory, and the one estimate.
0.25
3.25
10.25
Theory
0.75
0.80
0.80
Estimation
0.71
0.73
0.72
Theory
0.75
0.92
0.92
Estimation
0.75
0.83
0.87
Theory 0.75
0.94
0.97
8
Estimation
0.79
0.95
0.98
that Iterated Tikhonov, corresponding to proximal point iterations, has optimal learning rates and higher qualification than Tikhonov, and as such could outperform it on easy tasks. We extend the scope of the theory of learning with generalized self concordant loss functions beyond standard Tikhonov regularization, which fills a gap in the previous theory, showing that it is possible to be fully adaptive to the regularity of the learning problem, without saturation effects. On top of this, gave sufficient conditions to compute the estimator in practice, which is nontrivial by its sequential nature. Interesting research directions include related regularization schemes, such boosting, but also implementations of the iterated Tikhonov procedure with sketching techniques as Nyström projections. The goal is to derive algorithms that are both optimal, in terms of statistical guarantees, and with reduced computational complexity, which is an aspect we will address in future work.
Acknowledgments
A.R. acknowleges support of the French government under management of Agence Nationale de Recherche as part of the "Investissements d' d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute). A.R. acknowledges support of the European Research Council (grant REAL 947908). J. Mairal was supported by the ERC grant number 714381 (SOLARIS project) and by ANR 31A MIAI @ Grenoble Alpes, LANR19-P3LA-000
10

---

References
[1] U. Marteau-Ferey, D. Ostrovskii, Bach, and A. Rudi. Beyond least-squares: Fast rates for regularized empirical risk minimization through seff-concordance. In Conference Learning Theory (COLT), 2019.
[2] I.. Lo Gerfo, L.. Rosasco, F. Odone, E. De Vito, and A. Verri. Spectral algorithms for supervised learning. Neural Computation, 2077):183311977, 2008.
[3] A. Caponnetto and E. De Vito. Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics, 7:331-368, 2007.
[4] B. Schölkopf and A. Smola. Support vector machines and kernel algorithms. Encyclopedia of Biostatistics, 04 2002.
[5] Y. Yao, L. Rosasco, and Caponnetto. On early stopping in gradient descent learning. Con- structive Approximation, 26(2):289-3155 2007.
[6] Y. Averyanov and A. Celisse. Early stopping and polynomial smoothing in regression with reproducing kernels. arXiv preprint arXiv:2007.0668 2020.
[7] E. De Vito, L. Rosasco, A. Caponnetto, U. De Giovannini. and F. Odone. Learning from examples as an inverse problem. Journal of Machine Learning Research (JMLR), 6(30):883- 904, 2005.
[8] Bauer, S. Pereverzev, and L. Rosasco. On regularization algorithms in learning theory. Journal of complexity, 23(1):52-72) 2007.
[9] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[10] Y. Nesterov and A. Nemirovskii. Interior-point polynomial algorithms in convex programming. SIAM, 1994.
[11] Bach. Self-concordant analysis for logistic regression. Electronic Journal of Statistics, 4:384 -414, 2010.
[12] R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14(5):877-898, 1976.
[13] Tianxiao Sun and Quoc Tran-Dinh Generalized celf-concordant functions: A recipe for newton-type methods, 2018.
[14] U. Marteau- Ferey, Bach, and A. Rudi. Globally convergent newton methods for ill- conditioned generalized self-concordant losses. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[15] A. Rudi, R. Camoriano, and L. Rosasco. Less is more: Nyström computational regularization. Advances in Neural Information Processing Systems (NeurIPS), 2015.
[16] A. Rudi and L. Rosasco, Generalization properties of learning with random features. In Ad- vances in Neural Information Processing Systems (NIPS), 2017.
[17] G. Blanchard and N. Mücke. Optimal rates for regularization of statistical inverse learning problems. Foundations of Computational Mathematics, 18, 2016.
[18] L. Györfi, M. Kohler, A. Krzyzak, and H. Walk. A distribution-free theory of nonparametric regression. Springer, 2006.
[19] J. Thomas King and Chillingworth D. Approximation of generalized inverses by iterated reg-
ularization. Numerical Functional Analysis and Optimization, 1 1(5):499-513, 1979.
[20] H. Lin, J. Mairal, and Z. Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research (JMLR), 18(1):7554-9077, 2018.

---

[21] A. Kulunchakov and J. Mairal. Estimate sequences for stochastic composite optimization: Variance reduction, acceleration, and robustness noise. Journal of Machine Learning Re- search (JMLR), 21 2020.
[22] Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, and Kevin Tian. Acceleration with ball optimization oracle. In Advances in Neural Information Pro- cessing Systems (NeurIPS), 2020.
[23] Lin, Y. Lei, and D. Zhou. Boosted kernel ridge regression: Optimal learning rates and early stopping, Journal of Machine Learning Research (JMLR), 20(46):1-36, 2019.
[24] Tong Zhang. Sequential greedy approximation for certain convex optimization problems. IEEE Transactions on Information Theory, 49(3):682-691, 2003.
[25] A. Dieuleveut, Flammarion, and F. Bach. Harder, better, faster, stronger convergence rates for least-squares regression. Journal of Machine Learning Research (JMLR), 18(101):1-51, 2017.
[26] C. Ciliberto, L. Rosasco, and A. Rudi. general framework for consistent structured prediction with implicit loss embeddings. Journal of Machine Learning Research (JMLR), 21(98):1-67, 2020.
[27] B. Schölkopf, R. Herbrich, and A. Smola. A generalized representer theorem. In International conference on computational learning theory, pages 416-426, 2001.
[28] G. Wahba. Spline Models for Observational Data. Society for Industrial and Applied Mathe- matics, 1990.
[29] R. Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
[30] J. Fujii, M. Fujii, T. Furuta, and R. Nakamoto. Norm inequalities equivalent to heinz incquality. In Proceedings of the American Mathematical Society. 1993.
[31] J. Mairal. Cyanure: An open-source toolbox for empirical risk minimization for Python, C++, and soon more, 2019.
12


Reviews:
[{"review_id": "gbG2v1cC_C", "reviewer": "Reviewer_CRtT", "summary": "In this paper, the authors study a supervised learning method called iterative Tikhonov (IT) regularization where the loss function is a generalized self-concordant function. The method is a proximal point algorithm: \n- minimize (empirical loss) + (squared Euclidean distance from the previous iterate), \n\nrun for t iterations. The authors show that their method (IT) achieves optimal excess risk in interesting regimes of signal smoothness (r) and difficulty of the loss function (\\alpha).\n\nThey show the benefit of running multiple iterations of the proximal point algorithm when the signal is smooth. They also analyze their method when the proximal step has some optimization error.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The authors discuss relevant works appropriately. They explain their definitions and assumptions. The manuscript is well-structured. \n\nI have a few questions and comments.\n\n1. What does Theorem 1 yield as t goes to \\infty? As t goes to Infinity we should get the unregularized estimator, but the theorem gives good rates. In the statement of Theorem 1, please explicitly point to the assumptions you are making.\n\n2. Line 235, why is the first term called bias? \n\n3. In Assumption 9 in the supplement, there is a lower bound on df_\\lambda, but it is not present in the main paper. Can you please address the discrepancy, for my understanding?\n\nMinor:\n- Line 122: \\theta* is the true signal, but here it is called the estimator\n- Explain the [h,h] and [k,h,h] notation in the self-concordance condition\n- Regarding Definition 4, for Tikhonov regularization, isn't q=1, not just ½? What are $\\omega_\\nu$ and $\\kappa$?\n- In Assumption 2, in the end, it should be $\\theta,$ not $\\theta^*$\n- Line 226: should there be a 1/n in front of the summation?\n- Line 282: self-reference to Prop. 2\n- After line 299: y should be z\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "NSVQIhd0Yc", "reviewer": "Reviewer_xAhK", "summary": "The authors consider supervised learning problems based on generalized self-concordant (GSC) loss functions and iterated Tikhonov regularization scheme. Unlike the least-squares loss, there is no closed-form expression of the estimator induced by the GSC loss, which makes the generalization error analysis much more complicated. This paper shows that the proposed algorithm can overcome the limitation for GSC functions and achieve optimal learning rates.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The iterative regularization has a higher qualification compared to the conventional Tikhonov regularization scheme, which can overcome the so-called saturation effect. An important and interesting question is to investigate supervised learning problems associated with iterated Tikhonov regularization and generalized self-concordant (GSC) loss functions which are three times differentiable with their third derivative being bounded by the second derivative (e.g. logistic loss). In this paper, the authors investigate the benefit of iterated Tikhonov regularization in learning algorithms associated with GSC loss and show that the proposed method can still achieve optimal learning rates even when the index of the source condition is large. Sufficient conditions are also given for the computation of the proposed estimator in practice. Overall, the paper is well-written and technically sound, which provides new insights for the error analysis of estimators without closed-form expression. I was wondering if the boundedness of $\\theta^*$ is required in the proof. In binary classification, the minimizer of the expected risk associated with logistic loss is usually unbounded (that is, $\\theta^*=\\ln\\frac{\\eta}{1-\\eta}$ with $\\eta(x)=P(Y=1|X=x$)).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "DV6qaYpZvvjS", "reviewer": "Reviewer_Kz6Q", "summary": "The paper derives a probabilistic convergence rate of the estimator obtained by the iterative Tikhonov regularization scheme when the hypothesis space is a Hilbert space within which lies the target function.\nThe analysis relies on the specific type of generalized self concordant losses, as well as some source and capacity conditions.\nThrough links with the theory of spectral filtering, optimal rates are given when the estimator does not saturate, showing that the iterative regularization scheme provides benefits for a certain class of problems.\nDue to the iterative nature of the regularization scheme, an analysis of the error propagation at each iteration is also included, allowing to solve each problem with less and less precision while keeping statistical guarantees.\nNumerical experiments on a toy dataset complete this study, showing the accurateness of the predictions.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "-Originality:\nThe contribution is original, as it extends previous results for Tikhonov regularization and GSC losses to iterative Tikhonov.\nRelated work is appropriately cited, and the contributions are clearly stated.\n\n-Quality:\nThe submission is of high quality. It is technically sound, claims are supported by appropriate mathematical proofs as well as an illustrative numerical study.\n\nQ1: The assumption on the label space Y is very weak (Borel), how could the dimensionality of Y affect the convergence rate of the learning process ?\n\nQ2: The assumption of the target function belonging to the Hilbert space is crucial for the proof as it relies on the geometry of that space, could it be weakened (similarly to the kernel ridge regression case where the target function can be anywhere from the RKHS to L2) to only keep a modified source condition that would characterize alone the smoothness of the target function ?\n\nQ3: In practice, the number of iterations to perform is unknown as we do not have access to the true source condition, how could one set it given a specific dataset ?\n\n-Clarity:\nThe submission is very well written. A special effort has been made to make the bounds understandable and relatable to previous works, which makes the reading enjoyable.\n\n-Significance\nIterative regularization is an active topic in statistical learning, and the paper offers novel theoretical insights associated to this scheme, representing a significant contribution for the area.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "AvkWkWBxvEu", "reviewer": "Reviewer_rN14", "summary": "In this paper the authors study methods for minimizing excess expected risk. More specifically, they show how to use an iterated Tikhonov regularization scheme, which is well-known for least squares, for losses which are generalized self concordant (GSC). By doing so, they go beyond some of the limitations of the standard Tikhonov regularization.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the authors present an interesting method for minimizing expected error for generalized self concordant losses. My main concern is regarding differentiating this work from Marteau-Ferey et al. [1]. This deserves an extended discussion to make more apparent the novelty of the current works' contributions, including a more in-depth overview of the difference between the previously-used Tikhonov regularization, and the newly introduced iterated Tikhonov regularization scheme, as the improvements seem to be somewhat incremental. For example, it would help to include an overview of the specific results achieved by Marteau-Ferey et al. to more directly contrast with the new guarantees in this paper.\n\n======Comments======\n\nGeneralized self concordance is defined differently in [2] (there, the generalization comes from varying the exponent on the second-derivative term). It would therefore be helpful to provide a comment distinguishing between the two notions of generalized self concordance.\n\nThe authors should be made aware of, and include a reference to, Carmon et al. [3], which uses a ball oracle (related to the prox method) for optimizing quasi self concordant losses (a special case of generalized self concordance losses).\n\n\"various set of\" -> \"various sets of\"\n\n\"other examples when\" -> \"other examples include when\"\n\n\"obtain fast learning rate\" -> \"obtain fast learning rates\"\n\n\"While Thikonov\" -> \"While Tikhonov\"\n\n\n[1] U. Marteau-Ferey, D. Ostrovskii, F. Bach, and A. Rudi. Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance. In Conference on Learning Theory (COLT), 2019.\n\n[2] T. Sun and Q. Tran-Dinh. \"Generalized self-concordant functions: a recipe for Newton-type methods.\" Mathematical Programming 178, no. 1 (2019): 145-213.\n\n[3] Y. Carmon, A. Jambulapati, Q. Jiang, Y. Jin, Y.T. Lee, A. Sidford, and K. Tian. \"Acceleration with a Ball Optimization Oracle.\" Advances in Neural Information Processing Systems 33 (2020).\n\n=======================================\n\nAfter reading the authors' response, I appreciate the added clarity in differentiating from Marteau-Ferey et al. [1], and so I have adjusted my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, they state that the contribution is purely theoretical.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes an iterative L2/Tikhonov regularization scheme for statistical learning with general self-concordant losses. All reviewers agree that the paper is technically quite interesting and well-executed, and I believe it will make a nice contribution to the conference program. 

Please add the discussion comparing to Marteau-Ferey et al., to the final version, as this was quite helpful for clearing up some confusions in the discussion phase. 
Decision: Accept (Spotlight)