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. maaialliiiiia...
Mudsanndro.ruiiiima
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 (æ;, 1=.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))) + 1101
(3)
2
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 (Zz) 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 1)/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 -X |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 ox 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+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% (09)) - 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": "m-tBsonHoUw", "reviewer": "Reviewer_7njB", "summary": "A self-concordant loss is a convex and three times differentiable function with the third derivative bounded by the second one. The focus in this paper is on giving sharp bounds for learning with iterated Tikhonov regularization scheme and self-concordant loss functions. For example, the standard kernel ridge regression involves Tikhonov regularization but not iterative scheme. In the same setting, the iterative scheme builds a sequence of hypotheses by starting with the one fit to given labels and then continues with fitting residuals defined by the current predictor, which is just a sum of all the constructed sequence elements. \n\nThe main technical contribution is a sharp bound for the iterated Tikhonov scheme. In addition to this, the paper also identifies an inefficiency in Tikhonov regularization for some source conditions (see Assumption 3 that covers the smoothness of the target hypothesis). The authors also provide an extension of the iterated Tikhonov regularization to the setting known as $\\epsilon$-greedy sequence of functions, where in individual steps one is not required to find optimal solution to the empirical risk minimization problems. A particularly interesting and I believe useful contribution for future work is the synthetic experiment that was designed for one to have a complete control over the source condition that expresses the smoothness of the target hypothesis as well as the capacity which describes the spectrum of the kernel function used for learning (see Assumptions 3 and 4).", "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": "There are two points which would in my opinion improve the paper: $i$) notation and $ii$) discussion of prior work on sequential greedy approximations.\n\nI have tried to list below some of the parts that were confusing to me when reading for the first time.\n- Assumption 1: The Hessian is only defined in Assumption 2 and yet it is for the first time used in Assumption 1. Given the definition in Assumption 2, I think it should be $Tr\\ H(0)$ instead of the existing expression?\n- Definition 2 (generalized self-concordance): I fail to parse this definition of self-concordance and the reference provided is not helping. It is not clear what the operator $[...]$ does and what the role of h and k is here. When referring to Boyd (Convex optimization), the self-concordant loss is introduced first for 1D functions and then an extension to Euclidean spaces requires that \"... it is self-concordant along every line in its domain...\". Given that the latter deals with vector inputs, there is a reparametrization $\\hat{l}(t)=l(u + tv)$ where $t \\in \\mathbb{R}$ and $u + tv$ are all lines. The definition then reduces to that of the 1D case.  \nThis work is introducing the self-concordance over reproducing kernel Hilbert spaces and it would be good to do this in details and as clearly as possible. Moreover, the right-hand side has a term $\\sup | k\\ \\dot\\   g|$ which requires clarification and motivation (e.g., the explicit impact it will play in the bounds, in my understanding it is fundamental for sharp rates). Along these lines, the map $\\phi$ needs motivation so that one is able to carry this definition with some understanding/motivation to the proofs.\n - Definition 3: The norm has only been defined in the appendix and it would be good to have it as part of this definition. That would also allow for an easy walk through the paragraph that follows.\n - Eq. (12): This is an unfortunate overload of symbols, t denoting the function and iteration number in the iterated Tikhonov scheme.\n - Eq. (33): Which operator takes the precedence, $+$ or $\\wedge$?  \n \n\nThe second comment is regarding prior work on sequential greedy approximations, which is especially related to the second part of the paper and Proposition 1. If my understanding is correct, the iterated Tikhonov scheme has been studied previously under the name of sequential greedy approximations and it would be great if the authors could expand the discussion of related work by comparing their contributions to the two papers below. It would be a great way of bridging the two disparate directions that have significant overlap. Here, I would like to point out that the theoretical contributions of this paper are significant and augment prior understanding of the iterated scheme.\n \n [1] M. Donahue, C. Darken, L. Gurvits, and E. Sontag (Constructive Approximation, 1997). Rates of convex approximation in non-Hilbert spaces.\n \n [2] T. Zhang (IEEE Transaction on Information Theory, 2003). Sequential greedy approximations for certain convex optimization problems.\n ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequately addressed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "fWfIq84vDV", "reviewer": "Reviewer_KRE1", "summary": "This paper aims at optimal learning rates for regression with a generalized self-concordant convex loss function which were achieved by regularized least squares and the induced spectral algorithms overcoming saturation. Such optimal rates are unknown for general convex loss functions. The results in the paper are nice. ", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "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": "This paper gives optimal learning rates for regression with generalized self-concordant convex loss functions and the saturation effect is overcome. The goal is achieved by iterations with proximal operators with the number of iterations depending on the order r of approximation in the source condition as t \\geq r+1/2. The optimal rates stated in Theorem 1 are significant. These rates and the choice of the regularization parameter are stated in terms of the source condition and capacity condition imposed on the underlying probability measure. The authors also present sufficient conditions for the optimal learning rates when implementing the scheme in practical applications. The ideas in the paper are novel and clearly presented. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The optimal learning rates in Theorems 1 and 2 are stated in probability with unknown dependence on the confidence. Even for the regularized least squares, this problem existed in [3] which was only solved by Lin, Guo and Zhou (Distributed learning with regularized least squares, J. Machine Learning Research  18 (92): 1-31, 2017) and extended to spectral algorithms by Guo, Lin and  Zhou (Learning theory of distributed spectral algorithms, Inverse Problems 33 (2017) 074009 (29pp)). The authors might consider to study this problem somewhere else. The authors may also comment on possible results when Assumption 2 does not hold. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ObUPX33MDnM", "reviewer": "Reviewer_v7Aq", "summary": "This paper studies the rates of iterative Tikhonov regularization for self concordant loss functions and under the source and capacity condition. The presented results generalize two lines of works: (1) iterative Tikhonov regularization for least squares and (2) Tikhonov regularization for self concordant loss functions. The main theorems assume an exact solver to find a proximal point (at every iterate), which could be computationally infeasible. To overcome this issue, an additional result is presented to discuss the error propagation when the proximal points are computed inexactly. Finally, numerical simulations are provided as well to justify the theorems.", "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": "# Pros:\n+ The paper is written well.\n+ I think the presented results are solid that extend existing results for both Tikhonov regularization and least squares.\n\n# Cons:\n- Even though the computational issues are discussed a bit in the paper, the results are built upon Newtons' method which poorly scales with the problem dimensionality. Discussions for obtaining the inexact solutions by first-order methods could be interesting, especially observing that the proximal algorithm is closely related to gradient descent.\n- Eq. (19) is hard to interpret. Could you elaborate what is $\\bar{L}$?\n- l.153. Based on my calculation I think the qualification for Tikhonov regularization is $1$ instead of $1/2$. This is also supported by the references provided. Since this property is used for multiple times in the later results, could you please elaborate a bit? I might miss important point here as I have little background on inverse problems.\n\n\n# Overall\nI am temporarily holding a weak reject to respect the potential technical mistake mentioned above & I will be happy to re-evaluate the paper based on the future feedback from the authors.\n\n\n# Typos\n* l.105. The last $\\theta^*$ should be $\\theta$\n* l.115. I am not sure if I missed something, but I feel here it should write $df \\propto Tr TT_{\\lambda}^{-1}$? For example, consider least square with additive Gaussian noise with variance level $\\sigma$?\n* The paragraph title style (capitalization) could be aligned.\n\n----\n\nPost-Rebuttal: after discussion with the authors, it turns out the issue of the qualification of Tikhonov is a typo, but does not affect the final established results. I am therefore happy to vote for acceptance to this work. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6xkJriO1Nb", "reviewer": "Reviewer_r7mh", "summary": "### Update ###\n\nI have the author response. Many thanks for addressing my concerns.\n\nThis is a strong paper and I look forward to seeing it published.\n\n=============\n\nThis submission establishes convergence rates for the excess risk of _iterated Tikhonov regularization_ for generalized self-concordant functions.\nIterated Tikhonov regularization is equivalent to the proximal point algorithm;\nin finite dimensions, it is a procedure which sequentially solves $\\ell_2$-regularized learning problems, where the regularization at time $t + 1$ is centered at $\\theta_t$, the solution to previous iteration.\nThis is an extension of previous work by Marteau-Ferey et al. [1], who considered Tikhonov regularization (which is equivalent to iterated Tikhonov regularization with $t = 1$) for self-concordant functions. \nThe authors show that by taking $t > 1$, limitations on the learning rate imposed by saturation of the spectral filter are alleviated.\nThis leads to optimal (with respect to least-squares regression) convergence rates of the excess and is a strictly stronger result than that obtained by Ferey et al. [1]. \nThe authors also investigate approximate evaluation of the proximal-operator. \nThey show to obtain $O(\\epsilon)$ additive error in the final excess risk, it is sufficient to solve the sub-problems with geometrically increasing error in $\\epsilon$.\nThe submission concludes with an empirical validation of the theoretical results on synthetic datasets. \n", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "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": "## Detailed Comments\n\nThis is a strong submission which continues a sequence of well-known existing works on learning-theoretic bounds for self-concordant functions [1,2].\nThe main convergence rate for iterated Tikhonov regularization is novel and addresses a specific open question from Marteau-Ferey et al., who posited that alternative regularizers could overcome the _saturation effect_ of Tikhonov regularization. \nDespite the mathematical complexity, the result is fairly intuitive: Tikhonov regularization is not flexible enough to handle cases where the bias decays very quickly in the regularization strength (ie, $r$ in the source condition is large), while iterated Tikhonov can exploit this structure in the data.\n\nI particularly enjoyed the results on excess risk from sub-optimality of the optimization procedure.\nBias from optimization is easy to ignore, but a problem of significant concern when composing optimization problems, as in iterated Tikhonov.\nThe requirement that accuracy decay geometrically is a nice result that matches our intuition: early accuracy is critical to avoid propagating errors. \n\nThe main weaknesses of the submission are the following: i) it is an iterative improvement on existing work, and ii) the complexity of the theoretical developments, which often lack suitable intuition.\nAs to the first point, the major assumptions used by the authors --- generalized self-concordance, capacity condition, and source condition --- were previously leveraged by Marteau-Ferey et al. and are not new contributions.\nSimilarly, the approach based on upper and lower second-order Taylor bounds using (generalized) self-concordance is due Bach [2].\nOn the second point, some clearer intuition on the source\\capacity conditions in the main text would be very useful for the reader.\nFor example, Marteau-Ferey [1] provide fairly detailed developments connecting the conditions to spectral properties of the expected Hessian after they are introduced. \nWith that said, these are small issues that can be addressed before the camera-ready deadline. \n\n\n### Writing\n\nThe writing in main paper is polished with only a few typographical issues. See \"Minor Comments\" below.\n\n### Theory\n\nI briefly checked the appendix and did not see any issues. \nHowever, the proofs provided with the paper are 22 pages long and I could not fully examine them during the review period.\n\n### Experiments\n\nThe experiments are toy-sized, but do a fair job illustrating the main theorem.\nThe match between theoretical predictions and estimated learning rates in Table 1 is surprisingly tight.\n\n## Minor Comments\n\n- Line 139: \"As we mentioned earlier, the key hindsight on\" -> \"As we mentioned earlier, the key \\*\\*insight\\*\\* on\"\n- Line 332 \"This paper study a well-known\" -> \"This paper \\*\\*studies\\*\\* a well-known\".\n\n# References\n\n[1] Marteau-Ferey, Ulysse, et al. \"Beyond least-squares: Fast rates for regularized empirical risk minimization through self-concordance.\" Conference on Learning Theory. PMLR, 2019.\n\n[2] Bach, Francis. \"Self-concordant analysis for logistic regression.\" Electronic Journal of Statistics 4 (2010): 384-414. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a purely theoretical paper with no negative societal impacts. The authors take care to contextualize their results and point out limitations.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "11"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The topic of the submission is supervised learning in RKHSs (reproducing kernel Hilbert space) with generalized self-concordant (GSC; such as the logistic one) losses. Particularly, the authors raise the question if spectral filtering techniques can be leveraged to achieve faster/optimal convergence rates under source and capacity conditions in case of GSC losses when the regularization is changed from the classical Tikhonov one (as studied in [1] and suffering from saturation) to the iterative Tikhonov scheme (also known as proximal point algorithm). The authors answer this question affirmatively (Theorem 1) with extension to inexact proximal solvers (Proposition 2). The efficiency of the approach is illustrated on synthetic examples.

Kernel techniques are omnipresent in machine learning with a large number of successful applications. The reviewers agreed that the authors deliver a solid theoretical contribution in this direction in a well-written paper which can be of clear interest to the NeurIPS audience.
Decision: Accept (Spotlight)