Gaspard Beugnot

Julien Mairal
email: julien.mairal@

Alessandro Rudi
email: alessandro.rudi@

Po-Ling Loh

Maxim Raginsky

On the Benefits of Large Learning Rates for Kernel Methods

Keywords: Optimization, Statistical Learning, Kernel methods

This paper studies an intriguing phenomenon related to the good generalization performance of estimators obtained by using large learning rates within gradient descent algorithms. First observed in the deep learning literature, we show that such a phenomenon can be precisely characterized in the context of kernel methods, even though the resulting optimization problem is convex. Specifically, we consider the minimization of a quadratic objective in a separable Hilbert space, and show that with early stopping, the choice of learning rate influences the spectral decomposition of the obtained solution on the Hessian's eigenvectors. This extends an intuition described by Nakkiran (2020) on a two-dimensional toy problem to realistic learning scenarios such as kernel ridge regression. While large learning rates may be proven beneficial as soon as there is a mismatch between the train and test objectives, we further explain why it already occurs in classification tasks without assuming any particular mismatch between train and test data distributions.

Introduction

Gradient descent methods are omnipresent in machine learning, and a lot of effort has been devoted to better understand their theoretical properties. Optimal rates of convergence have been well characterized for minimizing convex functions in various contexts, including, for instance, stochastic optimization [START_REF] Nemirovski | Robust stochastic approximation approach to stochastic programming[END_REF]. For supervised learning, one is however more interested in the statistical optimality of the resulting estimator rather than in the ability to quickly optimize a training objective [START_REF] Bottou | The tradeoffs of large scale learning[END_REF]. When considering both optimization and statistical questions, gradient descent methods were proven to be optimal under many assumptions [START_REF] Yao | On early stopping in gradient descent learning[END_REF]Pillaud-Vivien et al., 2018a).

An important observation for this paper is that gradient descent algorithms typically require to tune some learning rate, or step size, to achieve the best performance. This has been thoroughly investigated in the optimization literature. For convex smooth problems in particular, the influence of step size on convergence rates is well understood [START_REF] Nesterov | Lectures on Convex Optimization[END_REF]. However, recent empirical studies have highlighted a surprising aspect of this parameter: when using gradient descent methods on neural networks, large learning rates were found to be useful for obtaining good generalization properties, or in other words, good statistical performance [START_REF] Jastrzebski | Catastrophic Fisher explosion: Early phase Fisher matrix impacts generalization[END_REF], even though they may be sub-optimal from an optimization point of view.

This paper aims at understanding this phenomenon from a broad but simple perspective, where both the function F we optimize and the function R used to evaluate the statistical performance are quadratic forms of some separable Hilbert space H. Specifically, we assume that ∀θ ∈ H, F (θ) = 1 2 ∥θ -θ ⋆ ∥ 2 T + cst, and

R(θ) = 1 2 ∥θ -ν ⋆ ∥ 2 U , (1)
where ∥•∥ A denotes the norm on H induced by a positive definite operator A, i.e., ∥θ∥ 2 A = ⟨θ, Aθ⟩ for any θ in H. With Eq. ( 1), F and R are characterized by positive definite operators T and U, along with their minimizers denoted by θ ⋆ and ν ⋆ , respectively. The constant value cst does not affect the optimization problem and can be safely ignored in the rest of this presentation. The model from Eq. ( 1) captures a large class of problems such as learning with kernels, detailed in Section 4, but we give here a simple example with ridge regression.

Example 1 (T and U with Ridge Regression.) Let x 1 , . . . , x n be data points in R d , and y 1 , . . . , y n prediction variables, with n ≥ d. Define X ∈ R n×d the data matrix. We consider the ridge regression estimator with regularization λ > 0, which is defined as the minimum of

∀θ ∈ R d , F (θ) = 1 n n i=1 1 2 (θ ⊤ x i -y i ) 2 + λ 2 ∥θ∥ 2 = 1 2n ∥Xθ -y∥ 2 + λ 2 ∥θ∥ 2 .
F is a quadratic function of θ, which can be rewritten as in Eq. (1) with

∀θ ∈ R d , F (θ) = 1 2 ∥θ -ν ⋆ ∥ 2 T + cst, with ν ⋆ = 1 n 1 n X ⊤ X + λI d -1 X ⊤ y T = 1 n (X ⊤ X + λI d ).
Assuming that the output can be written y i = x ⊤ i ν ⋆ + ϵ i with ν ⋆ ∈ R d and ϵ i some independent, zero-mean noise, then the population loss is P(θ) = E 1 /2 θ ⊤ x i -y i 2 , and the excess risk defined by R(θ) = P(θ) -inf ν P(ν) is given with

R(θ) = E 1 2 (θ -ν ⋆ ) ⊤ x 2 = 1 2 ∥θ -ν ⋆ ∥ 2 U , with U = E xx ⊤ .
In this example, a discrepancy between train and test losses (between T and U) may occur in particular situations (e.g., presence of data augmentation during training, or simply mismatch between train and test distributions). The next example shows that such a mismatch may be in fact frequent for classification problems, even when train and test distributions do match.

Example 2 (Discrepancy between train and test losses in classification with separable classes.)

The scenario described in Eq. (1) is particularly evident in the context of binary classification, when the classes are separable by a non-zero margin. This is considered a typical situation in many learning scenarios of interest, as classification over natural images-motivating the wide use of largemargin based classifiers in the field [START_REF] Rawat | Deep convolutional neural networks for image classification: A comprehensive review[END_REF]. We highlight here, that in this context, the loss we are using for training is not the best loss to consider for the test error, as discussed next. More precisely, consider a classification problem with two classes with non-zero margin. Let X ⊆ R d and Y = {-1, 1} be the input and the output space. Denote by ρ(x, y) = ρ X (x)ρ(y|x) the probability distribution describing the classification problem, where ρ X is the marginal probability over X , while ρ(y|x) is the conditional probability of y given x. The error that we would like to minimize is the binary error on the population, i.e. B(θ) = P[Sign[θ(x)] ̸ = y] for a model θ. Let ν ⋆ be a function minimizing the binary error and H be the class of models under consideration. Assume, for simplicity, that H is a RKHS with norm ∥ • ∥ [START_REF] Aronszajn | Theory of reproducing kernels[END_REF], i.e., there exists a map ϕ : X → H such that the function in H are characterized as θ(x) = ⟨ϕ(x), θ⟩, for any θ in H. It has been shown by Pillaud-Vivien et al. (2018a) (in particular, Lemma 1 and Appendix A, Theorem 13), that in the context of two classes separated by a non-zero margin and whose conditional probability is regular enough, then ν ⋆ is in H and moreover B(θ) -B(ν ⋆ ) ≤ e -c/∥θ-ν ⋆ ∥ for some constant c. Therefore, the binary error decreases exponentially in terms of the Hilbert norm ∥ • ∥. On the other hand, the norm minimized at training time is some smooth convex surrogate of the binary loss, as, for example, the quadratic loss.

In this case, the trained vector may be obtained by minimizing the population loss (in fact, a regularized empirical version, but we omit this fact here for simplicity) such that

F (θ) = E(θ(x) -y) 2 . Noting that (θ(x)-θ ⋆ (x)) 2 dρ(x) = ∥T 1/2 (θ -θ ⋆ )∥ 2 = ∥θ -θ ⋆ ∥ T for T = ϕ(x)ϕ(x) ⊤ dρ X (x),
and θ ⋆ = ν ⋆ under the considered conditions (see the same paper), we have

F (θ) -F (θ ⋆ ) = (θ(x) -θ ⋆ (x)) 2 dρ X (x) = ∥θ -θ ⋆ ∥ 2 T .
This is a typical case, where there is a discrepancy between the error of interest

R(θ) -R(ν ⋆ ) = ∥θ -ν ⋆ ∥ 2 ,
which, if optimized, would lead to an exponential decrease of the classification error, and the loss that is instead optimized by the algorithm at training time, i.e. F , for which we have only the slower rate B(θ) -B(ν ⋆ ) ≤ (F (θ) -F (ν ⋆ )) α , with α ∈ (1/2, 1) (see, e.g. [START_REF] Audibert | Classification under polynomial entropy and margin assumptions and randomized estimators[END_REF] or [START_REF] Audibert | Fast learning rates for plug-in classifiers[END_REF] for what concerns the CAR assumption).

In this paper, we are interested in understanding in which regime large learning rates with early stopping could be useful for kernel methods, even if they are suboptimal from an optimization point of view. We consider indeed the optimization of F in Eq. ( 1) with plain gradient descent, starting from a vector θ 0 in H with step-size η, and we distinguish between two cases: having a small learning rate η s or a large learning rate η b , the range of both is to be detailed later. A simple intuition was suggested by Nakkiran (2020) on a two-dimensional toy problem, showing that large learning rates may be beneficial as soon as there is a mismatch between F and R (meaning, what we train on does not correspond to what we test on). We show that such an insight can be extended beyond toy problems to realistic scenarios with traditional kernel methods, and that, perhaps surprisingly, this phenomenon occurs already in simple classification tasks.

Theorem 1 (Informal version of our main result) Under a few assumptions described later in this paper, consider the target accuracy α and large and small step sizes θ b and θ s (these quantities being defined in the aforementioned assumptions). Consider the gradient descent iterations θ t+1 = θ t -ηT(θ t -θ ⋆ ) either with step size η = η b or η = η s , and stop the procedure as soon as

F (θ t+1 ) ≤ α, resulting in two estimators θ b or θ s . Then, R(θ b ) -R(ν ⋆ ) ≤ 34 κ U κ T (R(θ s ) -R(ν ⋆ )), (2)
where κ U and κ T are the condition numbers of the operators U and T, respectively, restricted to H n .

Note that R(ν ⋆ ) = 0 by definition of R; we made this quantity explicit in the bound for clarity purposes. The main conclusion from the theorem is that with early stopping (and with a target accuracy that is reasonable according to statistical learning theory, as discussed later), large learning rates can provide better estimators than small ones, even though the quantity η s may yield much faster convergence for minimizing the objective function F than η b (a fact also discussed later). This phenomenon occurs when the condition number κ T is much larger than κ U , which may already arise in classification tasks, as mentioned earlier in Example 2 where κ U = 1. Note that Eq. ( 2) raises several questions and could be easily misinterpreted, since such a relation may suggest that an arbitrarily small risk R(θ b ) could be obtained by considering minimization problems that are arbitrarily badly conditioned. Unfortunately, but not surprisingly, there is however no free lunch here, as discussed in the next remark.

Remark 2 (The issue of ill-conditioning.) A naive observation is that R(θ b ) could be arbitrarily small by making the problem more ill-conditioned. However, the bound on R(θ b ) in Eq. ( 2) is relative to R(θ s ). Notably, a careful reading of the proof shows that R(θ s ) is an increasing function of the conditioning number, for the chosen level sets α.

Summary of contributions. Our first contribution is the relation described in Eq. ( 2), highlighting potential benefits of large learning rate strategies when the training objective has a worse condition number than the one used to evaluate the quality of the estimator. This is illustrated in Fig. 1, a figure inspired by [START_REF] Nakkiran | Learning rate annealing can provably help generalization, even for convex problems[END_REF]. Our second contribution is to show that such a mismatch systematically occurs in simple classification scenarios with low noise, where the quantity of interest to minimize may not be the population risk, as discussed earlier. Overall, this allows us to show that the previous phenomenon occurs in realistic learning scenarios with kernels, which we also check in practice through numerical experiments. descent, starting from θ 0 until we reach the level sets α (filled line, red). However, we evaluate the quality of the estimator through R (level sets are dashed lines, centered in ν ⋆ ). Doing small step size (blue dots) optimizes the direction e 1 first, and yields an estimate which is far from ν ⋆ in U norm; doing big step size (brown dots) oscillates in the direction e 1 , but ultimately yields an estimator which is close to ν ⋆ in U norm.

Related Work

Our main motivation is to better understand the role of learning rate in obtaining good generalization for supervised learning. Even though empirical benefits of large learning rates were first described for neural networks, a few recent works have studied this phenomenon for convex problems. We review here some relevant work.

Setting the learning rate in neural networks. Stochastic gradient descent has become the standard tool for optimizing neural networks. When the learning rate is very small, the network evolves in a so-called "lazy-regime" where its dynamics are well understood [START_REF] Chizat | On lazy training in differentiable programming[END_REF][START_REF] Jacot | Neural tangent kernel: Convergence and generalization in neural networks[END_REF] but which fails to capture the good generalization performance observed with large learning rate. Specifically, this phenomenon has been empirically observed numerous times (see, for instance [START_REF] Samuel | On the origin of implicit regularization in stochastic gradient descent[END_REF][START_REF] Jastrzebski | Catastrophic Fisher explosion: Early phase Fisher matrix impacts generalization[END_REF][START_REF] Jastrzebski | The break-even point on optimization trajectories of deep neural networks[END_REF]; common strategies consist of using first a large learning rate, before annealing it to a smaller value. As a first step towards proving theoretically the effect of choosing large learning rates for training neural networks, [START_REF] Li | Towards explaining the regularization effect of initial large learning rate in training neural networks[END_REF] devise a twolayer neural network model with different set of features where the order in which they are learnt matters, where the previous annealing strategy could be shown to be useful in theory.

A convex perspective. Recently, different papers tried to reproduce this phenomenon in convex settings. This is probably thanks to the observation made by [START_REF] Nakkiran | Learning rate annealing can provably help generalization, even for convex problems[END_REF], where a toy dataset is exhibited, which was the main motivation for this work. However, it fails to capture realistic scenarios where the data distribution is not isotropic, or with non linear data embeddings. [START_REF] Wu | Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate[END_REF] aimed at filling these gaps but again, relies on the data distribution to be linear, isotropic, with the number of dimension going to infinity in order to have all data points approximately orthogonal; we do not make any of those assumptions. The bound with the condition number we obtain in Theorem 5 is totally new. Finally, we highlight that we use plain gradient descent, and do not need stochasticity to exhibit the big learning rate phenomenon. This is consistent with recent work [START_REF] Geiping | Stochastic training is not necessary for generalization[END_REF] which shows that SGD is not necessary to obtain state of the art performances, and that GD simply needs a better fine tuning of hyper parameters.

Main Result

In this section, we show that by performing standard gradient descent on the empirical loss F , choosing a big learning rate will first optimize the smallest eigencomponent of T. That is, the resulting estimator is mostly located on the biggest eigenvector of T. On the other hand, the smaller the learning rate, the more will the solution be located on the small eigencomponents, with biggest eigenvectors of T being learnt first.

Settings and notations

Gradient descent updates. We perform standard gradient descent on the empirical loss F , starting from some θ 0 ∈ H, with step size η. We obtain

∀t ≥ 0, θ t+1 = θ t -ηT(θ t -θ ⋆ ), thus θ t -θ ⋆ = (I -ηT) t (θ 0 -θ ⋆ ). (3)
This enables a very simple analysis of the training in the eigenbasis of T. We now give a more precise definition of the model in Eq. ( 1).

Assumption 1 (Representer theorem assumption)

There is a n-dimensional subspace H n ⊆ H that is invariant by T -that is, T θ is in H n for all θ in H n and such that ν ⋆ is in H n .
We denote by (σ i , e i ) the eigenbasis of the p.d. operator T restricted to H n , with σ 1 > • • • > σ n > 0, assuming eigenvalues are distinct from each other, and we call κ T = σ 1 /σ n the condition number. Similarly, the restriction of U to H n is a positive definite operator whose spectrum is

ς 1 > • • • > ς n , with condition number κ U = ς 1 /ς n .
Since, rescaling the objectives F and R by constant factors does not change their minimizers, we also safely assume that σ 1 = ς 1 = 1.

The model described by Assumption 1 is quite natural, and ensures that a representer theorem holds when learning on a finite training set of n points. It is notably satisfied in classical learning formulations with kernels.

With the notations of Assumption 1, we can now rewrite the update of Eq. ( 3) along a specific direction e i :

∀t ≥ 0, ⟨θ t -θ ⋆ , e i ⟩ H = (1 -ησ i ) t ⟨θ 0 -θ ⋆ , e i ⟩ H . (4)
Consider the quantity |1 -ησ i |. The closer to 0, the smaller will the i-th component of θ t -θ ⋆ on the eigenbasis be when the number of steps t increases. We plot |1 -ησ i | in Fig. 2. i ≤ n, the attenuation is the quantity by which decays the projection of θ -θ ⋆ on e i at each step. The closer to 0, the faster will the direction e i of T be learnt. In our analysis, the learning rate must satisfy

2/σ 1 2/(σ 1 + σ n ) 1/σ 1 0 0.5 1 η |1 -ησ i | σ1 = 1. σ2 = 0.9 σn-1 = 0.3 σn = 0.2
η s < 2/(σ 1 + σ n ) < η b < 2/σ 1 .
Specifically, two ranges of learning rate naturally appear. With a small learning rate satisfying η s < 2/(σ 1 + σ n ), we see on Fig. 2 that the attenuation |1 -ησ i | is biggest for the smallest eigenvalue. On the other hand, with a big learning rate satisfying η b > 2/(σ 1 + σ n ), we see that the attenuation is biggest for the biggest eigenvalue. This motivates the next assumption.

Assumption 2 (Learning rate) The learning rates satisfy

0 < η s < 2 σ 1 + σ n < η b < 2 σ 1 . ( 5
)
Note that the quantity η = 2 σ 1 +σn which naturally appears in Fig. 2 is a classical upper bound for proving the convergence of σ 1 -smooth and σ n -strongly convex function, of which F belongs to, see e.g. Thm 2.1.15 in [START_REF] Nesterov | Lectures on Convex Optimization[END_REF]. The rate 1/σ 1 is the classical one when we do not have a strong convexity assumption. This means that in our model, the concept of "small" learning rate simply means being of the order of the best possible learning rates available from an optimization point of view, while the concept of "large" means being close to values leading to diverging algorithms.

Remark 3 (Biggest learning rate before divergence.) In a recent work, [START_REF] Cohen | Gradient descent on neural networks typically occurs at the edge of stability[END_REF] observed that neural networks trained with gradient descent and "good" constant step size η were often in a regime where σ 1 -the maximum value of the Hessian of the loss -hovered just around 2/η. It is surprisingly analogous to our model: the range of learning rate we consider for big step sizes in Assumption 2 enforces 2/η b to be close to σ 1 .

Remark 4 (Oscillating weights.) Geometrically, having η > 1/σ 1 means that the estimator will oscillate along the direction e 1 , i.e. ⟨θ t -θ ⋆ , e 1 ⟩ will change sign at each iteration. Such behaviour was observed for neural networks trained with classical learning rate strategies, where the weights' sign change in the early phase of training [START_REF] Xing | A walk with SGD[END_REF].

Then, the following technical assumption is needed to ensure that there is a signal on the lowest and biggest eigendirection. It is satisfied e.g. as soon as the initialization is chosen at random.

Assumption 3 (Initialization) We assume ⟨θ 0 -θ ⋆ , e 1 ⟩ H ̸ = 0, ⟨θ 0 -θ ⋆ , e n ⟩ H ̸ = 0.
Finally, we assume that the target accuracy in terms of optimization is not too small compared to the model error R(ν ⋆ ):

Assumption 4 (Target accuracy and model error) Consider some learning rates η b and η s chosen in the range of Assumption 2. We assume that the target accuracy α satisfies α ≤ α 1 , where α 1 is given in Definition 10 and only depends on the spectrum of T and the learning rates. Furthermore, we assume that

R(θ ⋆ ) α ≤ min 1 4 , κ T 72κ U . ( 6
)
This assumption is twofold, providing on the target accuracy α both an upper bound (with α ≤ α 1 ) and a lower bound (with Eq. ( 6)). The lower bound not being satisfied amounts to F being a poor approximation of R: R(θ ⋆ ) is too big, or the two ellipsoids' centers are far apart in Fig. 1. Usual machine learning settings often involve large amounts of data, where the limiting factor for good generalization is poor optimization rather than lacking information, so we can expect this assumption to often hold in practice. The upper bound stems from the proof technique of our main result in Theorem 5, a brief sketch of which is available in Section 3.4. The proof relies on the fact that sufficiently many steps t s (resp. t b ) are made before the gradient descent is stopped, so that the biggest (resp. the smallest) eigen component is attenuated enough. To ensure this, we can (i) either make the learning rate smaller1 , or (ii) take the target error α sufficiently small. We choose the latter, hence the assumption α ≤ α 1 .

The Main Theorem

We now give our main theorem, whose proof is given in Appendix A.

Theorem 5 (Benefits of large learning rates) Consider the different quantities defined in Assumptions 1, 2, 3 and 4. Then, perform the gradient descent updates of Eq. (3), with either small step size η s or big step size η b , and stop as soon as F (θ t ) ≤ α, assuming that the resulting estimators satisfy

F (θ s ) ≥ α/2 and F (θ b ) ≥ α/2 2 . Then, R(θ b ) -R(ν ⋆ ) ≤ 34 κ U κ T (R(θ s ) -R(ν ⋆ )). (7)
Recall that R has minimum 0, so Eq. ( 7) essentially guarantees better performance of θ b . The estimator obtained with big step size is better that the one obtained with small step size as soon as the operator T is ill-conditioned. This is notably the case when doing classification with kernel methods with the ridge estimator, as we discuss in Section 4.

Discussion

Implications in classification with separable classes. In the context of the example discussed in the introduction, we see clearly that, under the simplifying hypothesis that the population error behaves similarly to the empirical error, the choice of the learning step has the unexpected impact of reducing the Hilbert norm by a multiplicative constant that can be significantly smaller than 1, leading to an exponential improvement in the classification error.

Comparison with analysis techniques based on learning rate annealing. Most recent approaches to explain the role of the learning rate in the generalization [START_REF] Li | Towards explaining the regularization effect of initial large learning rate in training neural networks[END_REF][START_REF] Wu | Direction matters: On the implicit bias of stochastic gradient descent with moderate learning rate[END_REF] rely on annealing the learning rate: the first phase of the training is carried out with a large step size, before it is discounted to a lower value. We do not need such mechanism in our theoretical analysis, which turns to be simpler with a unique value for the step size. With annealing, our analysis could sum up the following way: do t steps with learning rate greater or equal to 2/σ 1 , so that all attenuation coefficient |1 -η b σ i | in Eq. ( 4) are smaller than 1 except for the first (few) eigencomponent. Doing so, all eigendirections would be optimized except for the first (few) ones. Then, anneal the learning rate until the α level set of the loss are reached.

Discussion on the complexity. The fact that the result of Theorem 5 relies on the condition number can be somewhat surprising. Indeed, we may wonder why the other eigenvalues of the spectrum do not play a role in the result. This is in fact due to the proof technique, which relies on comparing the estimator mostly located on e 1 (for big learning rates) and the one mostly on e n (for the small learning rates). Thus, the distance σ n-1 -σ n and σ 1 -σ 2 play a role in the complexity of the gradient descent, which is highlighted by the next lemma, which is a consequence of Lemmas 11 and 12 in Appendix A.

Lemma 6 (Computational complexity) Under the settings of Theorem 5, denote t s (resp. t b ) the number of steps necessary to obtain θ s (resp. θ b ). Then,

t s ≥ O log 1 -η s σ n 1 -η s σ n-1 , t b ≥ O log |η b σ 1 -1| max {η b σ 2 -1, 1 -η b σ n } . (8)
In particular, if s = σ n-1 -σ n , then t s = O(1/s), and the same holds for t b with s = σ 1 -σ 2 . We emphasize that the complexity incurred by using learning rates satisfying Assumption 2 may be very large. However, the motivation of our work is to study an existing practice in deep learning (using large step sizes that are not optimal in terms of optimization of the training loss, but which are better in terms of test loss). We study this phenomenon from a kernel perspective to be able to leverage theoretical tools. Analysing the computational complexity to obtain a given statistical accuracy in convex problems is a separate and well-documented problem, and we do not necessarily advocate the use of very large step sizes for kernel regression.

Nyström projections. In practice projections techniques (known as Nyström projections) are used to reduce the dimension and avoid a cost quadratic in n for gradient descent. Given some m ≪ n, this amounts to choosing m anchor points among the data and approximating the kernel matrix K with a rank-m matrix

K = K nm K -1 m K ⊤ nm .
Fortunately, this is still encompassed in the framework of the model in Eq. ( 1). Indeed, the resulting problem is still a quadratic problem, for which a representer theorem holds -the solution lies on the span of the anchor points.

Beyond the square loss. The result of Theorem 5 relies on using the square loss for obtaining a closed-form expression of the gradient descent update. This is fairly common in learning theory and already provides interesting hindsight. A natural extension to other loss functions would be to consider local quadratic approximations using the Hessian. This is for instance what has been done for kernel ridge regression and self-concordant loss functions by [START_REF] Bach | Self-concordant analysis for logistic regression[END_REF].

Sketch of proof for the main result

The detailed proof is delayed to Appendix A. The idea is the following: by tuning the number of steps, we can have the estimator trained with small (resp. big) step size mostly aligned with the smallest (resp. biggest) eigenvector.

The directional bias induced by the step size. As shown in Fig. 2, having the learning rates satisfying Assumption 2 ensures that the quantities

ϵ 2 b = 2≤i≤n ⟨θ b -θ ⋆ , e i ⟩ 2 ⟨θ b -θ ⋆ , e 1 ⟩ 2 , ϵ 2 s = 1≤i≤n-1 ⟨θ s -θ ⋆ , e i ⟩ 2 ⟨θ s -θ ⋆ , e n ⟩ 2 , (9)
can be made arbitrarily small, while Assumption 3 ensures they are well defined. ϵ b (resp. ϵ s ) quantifies to what extent is θ b -θ ⋆ (resp. θ s -θ ⋆ ) mostly on e 1 (resp. e n ). For instance, in the extreme case where ϵ b = 0 (resp.

ϵ s = 0), then θ b -θ ⋆ = xe 1 , x ∈ R (resp. θ s -θ ⋆ = ye n , y ∈ R).
To see why it can be made small, refer to the closed-form expression of θ (η,t) in Eqs. ( 3) and ( 4), and assume for simplification that ⟨θ 0 -θ ⋆ , e i ⟩ = c 0 for all i, with c 0 some constant factor. This gives

ϵ 2 b = 2≤i≤n (1 -η b σ i ) 2t (1 -η b σ 1 ) 2t , ϵ 2 s = 1≤i≤n-1 (1 -η s σ i ) 2t (1 -η s σ n ) 2t . ( 10
)
Following the discussion of Assumption 2, we have that

|1 -η b σ 1 | > |1 -η b σ i | for all i > 1, and |1 -η s σ n | > |1 -η s σ n |
for all i < n. Thus, we have that for any δ > 0,

t b ≥ 1 2 log 1/δ 2 log η b σ 1 -1 max 2≤i≤n |1-η b σ i | =⇒ ϵ 2 b ≤ δ 2 , t s ≥ 1 2 log 1/δ 2 log 1-ηsσn max 1≤i≤n-1 |1-ηsσ i | =⇒ ϵ 2 s ≤ δ 2 . ( 11
)
Different risk on the α-level sets. In this paragraph, assume (A) θ b = xe 1 , and θ s = ye n , that is

ϵ b = ϵ s = 0, (B) that R(θ ⋆ ) = 0 and (C) that α/2 ≤ F (θ b ) ≤ α, α/2 ≤ F (θ s ) ≤ α. (12)
Then, we have for

θ b that R(θ b ) = 1 2 ∥xe 1 ∥ 2 U ≤ 1 2 ς 1 x 2 ≤ α 2 ς 1 σ 1 , (13)
where we used Eq. ( 12) to bound α ≥ F (θ b ) = 1/2 • σ 1 x 2 . We do the same with θ s , this time using

1/2 • σ n y 2 = F (θ s ) ≤ α to obtain R(θ s ) = 1 2 ∥ye n ∥ 2 U ≥ 1 2 ς n y 2 ≥ α σ n ς n , (14)
Finally, combining Eq. ( 13) with Eq. ( 14), we obtain

R(θ b ) ≤ 2 κ U κ T R(θ s ).
Ensuring both conditions can be met together. We now point out the main differences between this simplified sketch of proof and the rigorous proof in Appendix A. First of all, we do not have (A) but rather an approximation of it, with ϵ s ≤ δ and ϵ b ≤ δ. Second, we do not have (B) and rather take into account the error R(θ ⋆ ) to derive Theorem 5. Finally, and most importantly, we check that we can have low ϵ and F (θ) ≥ α/2 at the same time. Indeed, we need a big number of iterations to achieve low ϵ b or ϵ s . This implies better optimization of the objective function F . To prevent this, we can either tune the learning rate (having η s close to 0 and η b close to 2/σ 1 ) or provide an upper bound on α. We choose the later, hence the hypothesis α ≤ α 1 in Assumption 4.

Comparison with Results in Kernel Regression

To provide some intuition over the result of Theorem 5, we consider its implications in a supervised learning setting, specifically classification on a low-noise dataset.

Background on the kernel ridge regression estimator

We consider standard settings. We denote by X ⊆ R d the input space, and Y = {-1, 1} the output space. We draw n i.i.d samples (x i , y i ) 1≤i≤n from an unknown distribution ρ on X × Y, and we search a prediction function θ ∈ H, where H is a RKHS with feature map ϕ : X → H. We assume the kernel to be bounded by a constant C K . See [START_REF] Aronszajn | Theory of reproducing kernels[END_REF] for a precise account on RKHS.

We use the square loss as loss function. In order to find a function θ which maps elements of X to Y, we optimize the (regularized) empirical risk F , defined for all θ ∈ H and λ ≥ 0 a regularization parameter with

F (θ) = 1 n n i=1 1 2 (θ(x i ) -y i ) 2 + λ 2 ∥θ∥ 2 . ( 15
)
The minimizer θ ⋆ of F is always well defined as soon the training samples x i are distinct (in the case λ = 0), which we assume now. We will be minimizing F with gradient descent when we are in fact interested in minimizing the test error

B(θ) = P[Sign[θ(x) ̸ = y]]. (16)
We will relate the test error and the empirical risk to quadratics forms in H by means of other quantities. To do that, we first define the population loss along with its regularized version with

∀θ, P(θ) = X ×Y 1 2 (θ(x) -y) 2 dρ(x, y), P λ (θ) = P(θ) + λ 2 ∥θ∥ 2 . ( 17
)
The minimizer of P on L 2 (ρ x ) is the regression function g

⋆ (x) = E[y|x]. It is an element of L 2 (ρ x )
but not necessary of H. We denote by ν ⋆ the minimizer of P λ on H. If λ > 0, it is always well defined; otherwise, with I : H → L 2 (ρ x ) the inclusion operator, ν ⋆ exists as soon as the projection of the regression function on the closure of the range of I belongs to the range of I. See Vito et al. ( 2005) for a precise account.

In the following, we assume λ ≥ 0 and that ν ⋆ is well defined, and we consider specific assumptions on ρ, via assumptions on ν ⋆ and g ⋆ .

Relating supervised learning with quadratic forms in H

To relate the problems of Eqs. ( 15) and ( 16) to quadratic forms in the RKHS, we simply need to introduce the empirical covariance operator, with

T = 1 n n i=1 ϕ(x i ) ⊗ ϕ(x i ). (18)
Then, as optimizing the Hilbert norm is a good proxy for optimizing the test error (following Example 2 and Lemma 14 in Appendix B), we define

F (θ) = 1 2 ∥θ -θ ⋆ ∥ 2 T +cst, R(θ) = 1 2 ∥θ -ν ⋆ ∥ 2 H , with cst = 1 2n y ⊤ I n - K n K n + λ -1
y.

(19) K is the kernel matrix (K/n shares the same spectrum than T), and the minimum F (θ ⋆ ) = cst is 0 when λ = 0. We are in the settings of the model of Eq. ( 1), and we can readily apply Theorem 5 with U being the identity operator I H .

Corollary 7 (Benefit of big step size for classification task.) Under the settings of Theorem 5 with the additional assumption that U = I Hn , we have

R(θ b ) -R(ν ⋆ ) ≤ 34 κ T (R(θ s ) -R(ν ⋆ )).

Experiments

We evaluate the claims of Section 4 on CKN-MNIST, a dataset consisting of the MNIST dataset embedded by a convolutional kernel network [START_REF] Mairal | End-to-End Kernel Learning with Supervised Convolutional Kernel Networks[END_REF]. It allows for a realistic use-case, with classification accuracy close to 99%, by necessitating a reasonable number of samples n = 1000.

On CKN-MNIST, we achieve 98.5% test accuracy with the Gaussian kernel with scale parameter 30 and no regularization. Adding regularization only improves the test accuracy by 0.04%.

1 .230751.231001.231251.231501.23175 Learning rate η ×10 -2 0 . 9 5 0 . 9 6 0 . 9 7

Test accuracy 1.230751.231001.231251.231501.23175 Learning rate η ×10 -2 0 . 9 5 0 . 9 6 0 . 9 7

Test accuracy Test accuracy function of the step size. We define some final level set α. We plot three quantities function of the learning rate η. The projection on the first component ⟨θ -θ ⋆ , e 1 ⟩ H must be small for moderate learning rate and big for learning rate close to 2/σ 1 , as the attenuation satisfies |1 -ησ 1 | → 1 when η → 2/σ 1 , see Fig. 2. This makes the Hilbert norm R(θ(η)) decreases as η increases, as predicted by Corollary 7. This results in better test accuracy 1-B for big learning rate, following Lemma 14. This is summed up in Fig. 3, left. Note that the range for big step size is narrow. This is consistent with Assumption 2, which requires a range equal to 2σ n /(σ 1 + σ n ) ≈ 2κ -1 T . This is also in line with practices in deep learning where the best performance in generalization is often obtained by choosing the largest possible learning rate such that the model does not diverge.

Test accuracy function of optimization. Our main bound in Theorem 5 relies on Assumption 4: in learning settings, it means that the optimization error α must be greater than a constant times the statistical error R(θ ⋆ ) in order to observe improvements with big step sizes. This is shown in Fig. 3, right. Additional details on the plot is available in Appendix E.

Scale of the kernel. In Fig. 3, the scale of the Gaussian kernel is set to s = 30, with which we obtained the best results on the test set. It is worth noting though that the scale of the kernel directly impacts the conditioning of the matrix. Notably, when s → 0, the kernel matrix K tends to the identity (hence κ T → 1) while when s → ∞, K tends to a rank-1 operator (hence κ T → ∞). A core result of Theorem 5 is that we have bigger improvement for bigger κ T . We reproduce the experiment on the test accuracy with different scale in Fig. 4, and notice indeed bigger improvements for larger scale s, hence worse conditioning.

Conclusion

A large class of learning problems can be formulated as optimizing a function F with gradient descent while we are interested in optimizing another function R. Using simple quadratic forms to model this mismatch is a natural thing to do, while already providing lots of insight. We indeed show that the choice of large step sizes that may be suboptimal from an optimization point of view may provide better estimators than small/medium step sizes. In particular, we show that this phenomenon occurs in realistic classification tasks with low noise when learning with kernel methods. In future work, we are planning to study other variants of gradient-based algorithms, which may be stochastic, or accelerated, and perhaps exploit the insight developed in our work to design new algorithms, which would focus on statistical efficiency, exploiting prior knowledge on the test loss, rather than on optimization of the training objective.

Definition 9 (Second biggest attenuation coefficient.) We introduce the second biggest attenuation coefficients Āb , Ās with

Āb def. = max A (η b ) 2 , A η b n , Ās def. = A (ηs) n-1 . (23)
Referring to Fig. 2, this implies

• For η b , we have that

A 1 > max {A 2 , A n } def. = Āb ≥ A i , ∀i > 1. (24)
Thus, by tuning the number of steps t, we can make the ratio (A i /A 1 ) t arbitrarily small for any i > 1.

• For η s we have that

A n > A n-1 def. = Ās ≥ A i , ∀i < n. (25)
Again, for a sufficiently large number of steps t, we can make (A i /A n ) t arbitrarily small for any i < n.

Definition 10 (Upper bound on α.) Given some small and big learning rate η s , η b , we introduce α 1 , a technical quantity depending on the spectrum of T and U and the initialization:

α 1 = 1 2 σ n ι 2 n exp   - log ∥θ 0 -θ ⋆ ∥ 2 H max {16nκ U , 4κ T } • max 1 ι 2 1 , 1 ι 2 n + 1 1-ηsσn + 1 η b σ 1 -1 min log 1-ηsσn 1-ηsσ n-1 , log A 1 Āb   (26)
In particular, note that we have

α 1 ≤ 1 2 σ 1 ι 2 1 exp   - log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 1 4nκ U + 1 η b σ 1 -1 log A 1 Āb    , α 1 ≤ 1 2 σ n ι 2 n exp   - log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 n max {16nκ U , 4κ T } + 1 1-ηsσn log 1-ηsσn 1-ηsσ n-1    ,
which will prove useful for the derivation of Lemmas 11 and 12.

A.2. An upper bound for the estimator with big learning rate

In this subsection, we denote µ η b ,t b i with µ i .

Lemma 11 (Estimator with big step size.) Set α > 0 s.t.

α < α 1 , (27)
where α 1 is defined in Def. 10. Define the quantity ϵ b with

ϵ 2 b = i>1 µ 2 i µ 2 1 . (28)
Then, running gradient descent on F with step size η b until the (α/2, α) level sets are reached, i.e.

1 2 α ≤ F (θ b ) ≤ α, ( 29
)
ensures that ϵ 2 b ≤ 1 4nκ U , and
2 5 α ≤ 1 2 σ 1 µ 2 1 ≤ α. ( 30
)
The resulting estimator is obtained with t b steps, with

t b ≥ 1 2 log 1 2 σ 1 ι 2 1 α log 1 η b σ 1 -1 ≥ 1 2 log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 1 4nκ U log A 1 Āb . ( 31
)

Proof

Bound on ϵ b . By using the definition of ϵ b and the expression of the (µ i ) 1≤i≤n given in Def. 8, we have

ϵ 2 b = i>1 µ 2 i µ 2 1 = i>1 ι 2 i A 2t i ι 2 1 A 2t 1 ≤ ∥θ 0 -θ ⋆ ∥ 2 H ι 2 1 Āb A 1 2t . (32)
Thanks to the proper choice of η b given in Asmpt. 2, we have that Āb /A 1 < 1, so that

∀δ > 0, t ≥ t 1 def. = 1 2 log ∥θ 0 -θ ⋆ ∥ 2 H δ 2 ι 2 1 log A 1 Āb =⇒ ϵ 2 b ≤ δ 2 . ( 33
)
Bound on µ 1 . Now, recall that the optimization error reads

F (θ b ) = 1 2 n i=1 σ i µ 2 i = 1 2 σ 1 µ 2 1 1 + i>1 σ i µ 2 i σ 1 µ 2 1
as we assumed that ι 1 ̸ = 0 in Asmpt. 3. Thus, we can bound the loss in two ways. First, by definition

1 2 σ 1 µ 2 1 ≤ F (θ b ) ≤ 1 2 σ 1 µ 2 1 (1 + ϵ 2 b ) (34)
and second, we assumed the estimator to belong to the (α/2, α) level set of F , i.e.

α 2 ≤ F (θ b ) ≤ α. (35)
Combining Eq. ( 34) with Eq. ( 35), we have that

α 2(1 + ϵ 2 b ) ≤ 1 2 σ 1 µ 2 1 ≤ α. ( 36
)
Feasability. Finally, we consider if ϵ 2 b ≤ 1 4nκ U and θ b being in the (α/2, α) level sets can occur at the same time.

First of all, we set the value of δ 2 to 1 4nκ U in Eq. ( 34). We get

t 1 def. = 1 2 log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 1 4nκ U log A 1 Āb . (37)
Then, we derive necessary conditions for having Eq. ( 35). Those conditions are derived through the bounds established in Eq. ( 34). For the lower bound, assuming t ≥ t 1 , so that, in particular, we have

ϵ 2 b ≤ 1/4, α 2 ≤ F (θ b ) =⇒ α 2 ≤ 1 2 σ 1 µ 2 1 (1 + ϵ 2 b ) =⇒ 4α 5σ 1 ≤ µ 2 1 = ι 2 1 (η b σ 1 -1) 2t =⇒ t ≤ t 3 def. = 1 2 log 5 4 σ 1 ι 2 1 α log 1 η b σ 1 -1 .
Likewise, for the upper bound we have,

F (θ b ) ≤ α =⇒ 1 2 σ 1 µ 2 1 ≤ α =⇒ t ≥ t 2 def. = 1 2 log 1 2 σ 1 ι 2 1 α log 1 η b σ 1 -1
.

Summing up, we have

• t ≥ t 1 implies that the bound on ϵ b in Eq. ( 33) holds.

• Ensuring that the level set condition in Eq. ( 35) holds are met implies that t ∈ (t 2 , t 3 ).

Thus, we need to ensure that t 2 > t 1 (and that t 3 -t 2 > 1; we assume this, as we can look at smaller level sets if necessary). To do this, we use that t 2 is an decreasing function of α. Thus, t 2 > t 1 as soon as

α ≤ 1 2 σ 1 ι 2 1 exp   - log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 1 4nκ U + 1 η b σ 1 -1 log A 1 Āb    ,
which is exactly the purpose of the technical assumption α ≤ α 1 , with α 1 defined in Def. 10.

A.3. A lower bound for the estimator with small learning rate

We now derive a similar result for θ s . To lighten the notations, we use µ (ηs,ts) i = µ i .

Lemma 12 (Estimator with small step size.) Set α > 0 s.t.

α < α 1 , (38)
where α 1 is defined in Def. 10. Define the quantity ϵ s with

ϵ 2 s = i<n µ 2 i µ 2 n . (39)
Then, running gradient descent on F with step size η s until the (α/2, α) level sets are reached, i.e.

1 2 α ≤ F (θ b ) ≤ α, (40)
ensures that ϵ 2 s ≤ 1/(16nκ U ), and

2 5 α ≤ 1 2 σ n µ 2 n ≤ α. ( 41
)
The resulting estimator is obtained with t s steps, with

t s ≥ 1 2 log 1 2 σnι 2 n α log 1 1-ηsσn ≥ 1 2 log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 n max {16nκ U , 4κ T } log 1-ηsσn 1-ηsσ n-1 . ( 42
)
Proof The proof is very close to the one of Lemma 11. We only give the main results.

Bound on ϵ s . This quantity can be written

ϵ 2 s = i<n µ 2 i µ 2 n = i<n ι 2 i A 2t i ι 2 n A 2t n ≤ ∥θ 0 -θ ⋆ ∥ 2 H ι 2 n Ās A n 2t , with 1 -η s σ n-1 = Ās > A n = 1 -η s σ n following Asmpt.2. Thus, ∀δ > 0, t ≥ t 1 def. = 1 2 log ∥θ 0 -θ ⋆ ∥ 2 H δ 2 ι 2 n log 1-ηsσn 1-ηsσ n-1 =⇒ ϵ 2 s ≤ δ 2 .
Bound on µ n Again, following the same paragraph in Lemma 11, we have

F (θ s ) = 1 2 n i=1 σ i µ 2 i = 1 2 σ n µ 2 n 1 + i>1 σ i µ 2 i σ n µ 2 n
as we assumed that ι n ̸ = 0 in Asmpt. 3. We bound the loss in two ways. First, by definition

1 2 σ n µ 2 n ≤ F (θ s ) ≤ 1 2 σ n µ 2 n (1 + κ T ϵ 2 s ) (43)
and second, we assumed the estimator to belong to the (α/2, α) level set of F , i.e.

α 2 ≤ F (θ s ) ≤ α. (44)
Combining Eq. ( 43) with Eq. ( 44), we have that

α 2(1 + κ T ϵ 2 s ) ≤ 1 2 σ n µ 2 n ≤ α. (45)
Feasability. The discussion is the same, but with the values

t 1 = 1 2 log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 n max {16nκ U , 4κ T } log 1-ηsσn 1-ηsσ n-1 t 2 = 1 2 log 1 2 σnι 2 n α log 1 1-ηsσn t 3 = 1 2 log 5 4 σnι 2 n α log 1 1-ηsσn .
Note that the addition of κ T in the definition of t 1 is simply to ensure that

∀t ≥ t 1 , ϵ 2 s ≤ 1 4κ T , so that 2 5 α ≤ α 2(1 + κ T ϵ 2 s ) ≤ 1 2 σ n µ 2 n .
To ensure the feasibility of both bounds at the same time, we need to ensure t 2 > t 1 . A sufficient condition for this is having

α ≤ 1 2 σ n ι 2 n exp   - log ∥θ 0 -θ ⋆ ∥ 2 H ι 2 n max {16nκ U , 4κ T } + 1 1-ηsσn log 1-ηsσn 1-ηsσ n-1   
which is, again, covered with the assumption α ≤ α 1 defined in Def. 10.

A.4. Plugging the two together

Theorem 13 Assume that the optimization error satisfy

α ≤ α 1 , (46)
where α 1 is defined in Definition 10. Assume that Assumption 1 on the operators T and U hold, that the condition on the learning rates η b , η s of Assumption 2 hold, as the condition on the initialization in Assumption 3. Assume that gradient descent is performed until the (α/2, α) level sets are reached. Then we have that

R(θ b ) ≤ c α R(θ s ), with c α =      1 + 2 σ 1 ς 1 R(θ ⋆ ) α 1 -18 σn ςn R(θ ⋆ ) α +      . ( 47
)
Further assume that Assumption 4 holds. Then c α ≤ 2 and the bound becomes

R(θ b ) ≤ 34 κ U κ T R(θ s ). (48)

Proof

Upper bound for big learning rate. We first proceed to bounding R(θ b ). In this paragraph, we use µ

i = µ η b ,t b i . We have R(θ b ) = 1 2 ∥θ b -ν ⋆ ∥ 2 U (Definition) ≤ ∥θ b -θ ⋆ ∥ 2 U + ∥θ ⋆ -ν ⋆ ∥ 2 U (Triangular inequality) = ∥θ b -θ ⋆ ∥ 2 U + 2R(θ ⋆ ) ≤ ∥µ 1 e 1 ∥ 2 U 1 + i>1 µ i e i U ∥µ 1 e 1 ∥ U 2 + 2R(θ ⋆ ) (Triangular inequality) ≤ 2 ∥µ 1 e 1 ∥ 2 U 1 + i>1 µ i e i 2 U ∥µ 1 e 1 ∥ 2 U + 2R(θ ⋆ ) ((a + b) 2 ≤ 2(a 2 + b 2 )) ≤ 2 ∥µ 1 e 1 ∥ 2 U 1 + κ U i>1 µ i 2 |µ 1 | 2 + 2R(θ ⋆ ) (Def. of κ U , ∥e i ∥ = 1) ≤ 2 ∥µ 1 e 1 ∥ 2 U 1 + κ U nϵ 2 s + 2R(θ ⋆ ). (Cauchy-Schwartz)
Now, we use the results of Lemma 11. Firstly, we have κ U nϵ 2 b ≤ 1/4. Secondly, we can use ∥e 1 ∥ 2 U ≤ ς 1 . The previous inequality then turns to

R(θ b ) ≤ 5ς 1 2 µ 2 1 + 2R(θ ⋆ ).
Finally, we use the fact that 1 2 σ 1 µ 2 1 ≤ α to conclude with

R(θ b ) ≤ 5α ς 1 σ 1 + 2R(θ ⋆ ). ( 49
)
Early stage of training. The bound in Eq. ( 56) ensures better generalization when taking big step size, if the r.h.s is bigger than 1. However, the pioneering work of [START_REF] Yao | On early stopping in gradient descent learning[END_REF] established that the learning rate had no influence in the generalization capabilities of the estimator. A key difference though is that the results of Theorem 5 only holds in the early stage of training, when the optimization error α is big w.r.t to the statistical error R(θ ⋆ ) : otherwise, Assumption 4 is not satisfied. In contrast, results of the like of [START_REF] Yao | On early stopping in gradient descent learning[END_REF] holds for sufficiently many samples n, and require a number of steps t bounded by below by a power of n -they require an upper-bound on α, while we require a lower-bound in Assumption 4.

Is Eq. ( 56) informative? As mentioned above, Eq. ( 56) ensures better generalization of big step size only if the r.h.s is bigger than 1. However, in the particular scenario of kernel regression, the empirical covariance T is the discretization of the population covariance U. Thus, numerous results bound the discrepancy between the two, notably when the capacity condition holds, see e.g. Proposition 5.3 to 5.5 in [START_REF] Blanchard | Optimal rates for regularization of statistical inverse learning problems[END_REF]. In these settings, we can expect the ratio κ T /κ U to go to 1 for large number of samples n. Thus, we cannot conclude in better excess risk of θ b compared to θ s .

Comparison with spectral filters. Spectral filters are an elegant way to describe a wide family of regularization for kernel regression Gerfo et al. ( 2008); [START_REF] Bauer | On regularization algorithms in learning theory[END_REF]. In a nutshell, it relies on studying the class of estimator characterized by a filter function g λ , where λ is a regularization parameter, equal to 1/t in the case of early stopping in GD. GD with moderate step sizes is a spectral filter; but GD with large step size is not. We now explain this difference, which helps to build an intuition on our result. Consider the estimator θ = g λ (T)S * y, where S is the so-called sampling operator defined in Appendix D.1. The unregularized solution is obtained with λ = 0, for which we must have g λ=0 (σ) = σ -1 . We denote it with θ ⋆ = T -1 S * y, and we can see how does θ approaches the unregularized optimum. We have ⟨θ -θ ⋆ , e i ⟩ = g λ (T)S * y -T -1 S * y, e i = g λ (T)T -1 -I T -1 S * y, e i = ⟨(g λ (T)T -I) θ ⋆ , e i ⟩ = (g λ (σ i )σ i -1) ⟨θ ⋆ , e i ⟩ .

If we start from θ 0 ̸ = 0, this relation turns to |⟨θ -θ ⋆ , e i ⟩| = |1 -g λ (σ i )σ i | |⟨θ 0 -θ ⋆ , e i ⟩| in the case of GD. We denote the residual with r λ (σ) = |1 -σg λ (σ)|. We then compare r λ for various spectral filters in Fig. 5. Note that for gradient descent, we have r 1/t (σ) = |1 -ησ| t and we recover the expression we obtained from Eq. (3). The key hindsight is that spectral filters will learn, i.e optimize, the biggest eigendirection first. For instance, truncated regression uses as estimator the first eigencomponents of the unregularized estimator, leaving the smaller eigencomponents untouched. This is at odds with what we aim at with big learning rate. There is no contradictions though, as we want in the end to minimize the excess risk R -a quadratic with operator U -and we assumed the empirical covariance T to be a discretization of U. Thus, in this settings F is a good proxy for R and minimizing the biggest eigendirection first will make the excess risk R decrease faster. This corresponds to having level sets well aligned in Fig. 1.

Theorem 5 in practice. The limits of this subsection -low optimization regime, low value for κ T /κ U and difference with spectral filters -can be mitigated for multiple reasons. First of all, as we discussed earlier kernel regression can simply be a mean in order to solve a classification task, in which case the statistical results of spectral filters are no longer relevant. Secondly, there can be big discrepancies between the train and test set in practice. Indeed, the risk R with which estimators are compared is often a separate test set, with fixed condition number κ U . Additionally, data augmentation can be used on the train set, which then introduces spurrious directions in the empirical covariance matrix T. Thus, even though spectral filters are optimal in theoretical settings, taking big step size can prove useful in practical scenari, which are covered by our settings with quadratic forms of H.

Figure 1 :

 1 Figure1: We optimize the quadratic F (level sets are filled lines, centered in θ ⋆ ) with gradient descent, starting from θ 0 until we reach the level sets α (filled line, red). However, we evaluate the quality of the estimator through R (level sets are dashed lines, centered in ν ⋆ ). Doing small step size (blue dots) optimizes the direction e 1 first, and yields an estimate which is far from ν ⋆ in U norm; doing big step size (brown dots) oscillates in the direction e 1 , but ultimately yields an estimator which is close to ν ⋆ in U norm.

Figure 2 :

 2 Figure 2: Attenuation coefficient |1 -ησ i | function of the step size η, for 4 eigenvalues. For 1 ≤i ≤ n, the attenuation is the quantity by which decays the projection of θ -θ ⋆ on e i at each step. The closer to 0, the faster will the direction e i of T be learnt. In our analysis, the learning rate must satisfy η s < 2/(σ 1 + σ n ) < η b < 2/σ 1 .

Figure 3 :

 3 Figure 3: (Left) Test accuracy (blue) function of step size η for CKN-MNIST. As the learning rate increases, the projection on the first component (orange) increases, which makes the Hilbert norm (green) decreases. This results in predictions closest in L ∞ norm to the optimum.(Right) Test accuracy function of level set α for CKN-MNIST. As we optimize more, the better performances of big step size (orange) compare to optimal step size (blue) vanish to reach the prediction of the optimum of F (green, dashed). Shaded areas show standard deviation (train set and initialization) over 10 runs.

  s = 120, κ T = 4.0 • 10 7

Figure 4 :

 4 Figure4: Theorem 5 predicts that the improvement in taking big rather than small step size increases with the condition number of T. We test this claim on our dataset: larger kernel scale s makes the condition number of the kernel matrix κ T increases, which results in a larger margin between the test accuracy of θ b and the one of θ s .

Figure 5 :

 5 Figure5: Residual of various spectral filters, with regularization λ = 1/4 or t = 4 for GD. The best filter is spectral cut-off (red). The resulting estimator is purely directed along the smallest eigenvectors of T. Gradient descent with small step sizes (blue) and (iterated) Tikhonov (yellow, brown) mimick this filter. On the other hand, gradient descent with big step sizes (green) is not an admissible filter in the sense of Gerfo et al. (2008), as it attenuates less the biggest component.

Proceedings of Machine Learning Research vol 178:1-29, 2022

© 2022 G. Beugnot, J. Mairal & A. Rudi.

Informally, by making η b → 2/σ1 (resp. ηs → 0) we need bigger t b (resp. ts) to achieve optimization error α. Thus, α < α1 can be replaced with η b > 2/σ1 -ϵ (resp. ηs < ϵ).

This is a mild assumption that could be removed at the price of cumbersome technical details.

Acknowledgments

A.R. acknowleges support of the French government under management of Agence Nationale de la Recherche as part of the "Investissements 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 3IA MIAI@Grenoble Alpes, (ANR19-P3IA-0003).

Overview of the appendix

• In Appendix A, we prove Theorem 5.

• In Appendix B, we give additional technical information on the low-noise classification task.

• We compare the bound in Theorem 5 to existing results in the case of regression task with kernels, in Appendix C. We highlight the difference between gradient descent with big step size and the estimators which write as a spectral filter.

• Appendix D makes a simple remark, highlighting the difference between gradient descent on the train loss and gradient descent on the Hilbert norm in kernel regression.

• Finally, Appendix E gives additional information on the experiments.

Appendix A. Proof of main result

A.1. Definition and assumptions

Recall from the main text Assumptions 1, 2, 3, 4. We can rewrite precisely the gradient descent update in Eq. ( 3) with the following definition.

Definition 8 (Notations for the estimator) For some step size η, a number of steps t and some θ 0 ∈ H n , we denote θ (η,t) the estimator obtained through gradient descent from θ 0 . We denote µ (η,t) i 1≤i≤n

the decomposition of θ (η,t) -θ ⋆ on e i , i.e.

Denoting the initialization with

we have that ∀i ∈ {1, . . . , n} , µ

where A i is the attenuation of the i-th eigencomponent at each step.

To lighten the notations, we denote θ s = θ (ηs,ts) the estimator obtained with t s small step size η s , and θ b = θ (η b ,t b ) the estimator obtained with t b big step size η b . Likewise, we use µ i when it is clear from the context which of θ s or θ b we study.

With these notations and Assumption 2 and 3, note that

Also, we can now introduce the second biggest attenuation coefficients in the following definition.

Lower bound for small learning rate. We now turn to bounding R(θ s ). Here, we use µ i = µ ηs,ts i . We have

We then use Lemma 12. Firstly, we can use ϵ 2 s ≤ 1/(16nκ U ) so that 2 √ κ U nϵ s ≤ 1/4. This gives

Secondly, we have σ n µ 2 n /2 ≥ 2α/5. This give ultimately

Simplifying this expression gives

Combining the two bounds. We now simply combine the upper bound of Eq. ( 49) and the lower bound of Eq. ( 49). We get

We may prefer the other form, introducing the positive part (x) + = max(0, x) and using 50/3 < 17:

Finally, with Assumption 4 we have

Appendix B. Low-noise classification tasks

Taking big step size is particularly critical in classification tasks. In this section, we build on the result of Pillaud-Vivien et al. (2018b) to relate classification performances with Hilbert norm. Recall notably the notations of Section 4.

Assumptions. The following assumption comes from (A1) in Pillaud-Vivien et al. (2018b). It is well characterized in usual image classification settings.

Assumption 5 (Strong margin condition.) We have g ⋆ (x) ≥ δ for some δ ∈ (0, 1).

The second assumption characterizes the statistical optimality of ν ⋆ . It does not assume the regression function to belong to H, but ensures some proximity in L ∞ norm. It is close to (A4) in Pillaud-Vivien et al. (2018b).

Assumption 6 (Statistical optimality of the population loss' optimum.) We have that

This assumption is satisfied as soon as the regression function can be approximated by a function of the RKHS with precision δ/2 in L ∞ norm. For instance, a sufficient condition is the regression function g ⋆ (x) to belong to H. Then g ⋆ = ν ⋆ and the assumption is satisfied. Note that this always imply that θ ⋆ reaches 0 test error for sufficienly many samples, which is the key hindsight of Pillaud-Vivien et al. (2018b). Indeed, for a proper choice of regularization λ one has that

where (r, b) are the parameters of the source and capacity condition, both of which characterizes the difficulty of the learning task, see [START_REF] Blanchard | Optimal rates for regularization of statistical inverse learning problems[END_REF]. This implies that for sufficiently many training samples n, θ ⋆ will be close to ν ⋆ in Hilbert norm, which implies proximity in L ∞ (pointwise) norm.

Hilbert norm proximity implies statistical optimality

The following lemma is very close to Lemma 1 in Pillaud-Vivien et al. (2018b), and is a direct consquence of our assumption. We first introduce

Next lemma basically relies on the decomposition

Lemma 14 (Small Hilbert norm implies statistical optimality) Consider an estimator θ which satisfies

Then, this estimator is statistically optimal, in the sense that it has 0 excess error:

Proof First of all, we leverage the fact that the Hilbert norm upper bounds the L ∞ norm, with

Then, on Ω + , whose definition is given in Eq. ( 54), we have that

so θ will have accurate prediction for all positive labels. The same goes for negative labels. Thus, θ has 0 test error.

Thus, we see that the Hilbert norm is a good proxy for minimizing the test error B.

Appendix C. Regression tasks and comparison with spectral filters

If the downstream task is regression, then we can still apply our result by introducing the population covariance operator,

Then, Theorem 5 holds by considering (recall the definition of the population loss P in Eq. ( 17))

which is nothing but the excess risk of the estimator. Then, under the assumptions of Theorem 5 we have that

Gradient descent for kernel ridge regression has been widely studied in the past, to say the least. Equation (56) appears to be in contradiction with most of them. In this section, we emphasize the limit of our assumptions to point out that there is no conflict with existing theory.

Appendix D. Gradient descent updates in practice D.1. Useful operators

We assume there are n training samples. If considered, the test loss consists of m samples.

We denote Ŝ, Ŝ⋆ the sampling operator and its dual, which are defined as

so that the covariance operator T = Ŝ⋆ Ŝ and the kernel matrix K write

The population version are S, S ⋆ , U. There are written with an expectation, or with the test dataset as a proxy. Note that we have T -1 Ŝ⋆ = Ŝ⋆ (K/n) -1 . We denote σ i , e i the spectrum of T and u i the eigenvectors of K/n (not K), with the same spectrum. The eigenvectors in H and R n are related with ∀i ∈ {1, . . . , n} ,

Finally, an estimator θ ∈ H can be represented with a vector α ∈ R n . Specifically, we have the relation

D.2. Gradient descent on the Hilbert norm is possible

Different spectrum between H and R n . We denote the training loss with F and the Hilbert norm with L H . Given the relation of Eq. ( 59), we have that

where we overloaded F to be a function of H n and R n . Specifically, we used

Recall that K/n and T share the same spectrum. Thus, F is a quadratic whose spectrum is (σ 1 , . . . , σ n ) w.r.t the variable θ, but spectrum nσ 2 1 , . . . , nσ 2 n w.r.t the variable α. Likewise, L H is a quadratic with spectrum (1, . . . , 1) w.r.t the variable θ, but a spectrum (nσ 1 , . . . , nσ n ) w.r.t the variable α.

Do we care about this difference? The global picture behind what follows is that α is isomorphic to T -1/2 H. If we expressed the estimator θ as a combination of eigenbasis vector, that is θ = i β i e i , then β is isormorphic to H and the distinction does not hold. The fact that the estimator writes as a combination of ϕ(x i ) with α adds another level of geometric distortion.

Gradient descent in H. In the Hilbert space H, the updates are easy:

The big learning rate range is then

Gradient descent in R n . In practice, we do not have access to α ⋆ , or only though it's evaluation with K. Yet, we are still able to minimize these quadratic form through the gradient. E.g. when α ⋆ is defined through Kα ⋆ = y in the unregularized settings, or (K + nλ)α ⋆ = y in the Tikhonovregularized case. The gradient descent updates on the train loss read:

Here, the range of learning rate is η s < 2/ n(σ 2 1 + σ 2 n ) < η b < 2/ nσ 2 1 . Interestingly, we can still do gradient descent on the Hilbert norm in closed form!

Here, the optimal learning rate is 1/[nσ 1 ]. Interestingly, choosing a big learning rate in the range

Note that even though we can evaluate the gradient of L H , we cannot evaluate its value. Indeed, the objective function would read

which is not accessible without inverting the (regularized) kernel matrix.

Appendix E. Additional details on the experiment

Setting the learning rate. We give additional details on the plot "test accuracy function of train loss α" in Fig. 3. The plot is averaged over 10 initialization for θ 0 . We used η s = 1/σ 1 and η b = τ • 2/σ 1 , with τ = 1 -10 -5 . We elaborate on these choices:

• The optimal learning rate for upper bounding for σ 1 -smooth, σ n -strongly convex function is η opt = 2/(σ 1 + σ n ), as explained in the discussion of Assumption 2. However, this requires a massive amount of steps to converge. This is due to the terms depending on the initialization in the lower bound for t b , t s in Eqs. ( 31) and ( 42). Thus, we set η s = 1/σ 1 , which is the optimal rate for σ 1 -smooth function, and we do observe fast convergence with this choice.

• Instead of choosing η b ∈ [2/(σ 1 + σ n ), 2/σ 1 ], we use η b = τ • 2/σ 1 , with τ chosen with the experiment on the test accuracy (Fig. 3, left). Indeed, setting τ = 1 can result in situation where there can't be convergence; and choosing η b > η opt , as we describe in the theory, results in very slow convergence.

This discrepancy between theory and practice is due to our proof which is very conservative in the error bound. A more refined analysis would rely on θ b -θ ⋆ (resp. θ s -θ ⋆ ) belonging to the span of the k-th first (resp. last) eigenvectors. Besides, in practical settings the learning rate is an hyperparameter to tune, which is exactly the approach we used to produce Fig. 3.


Chiara Mazzocconi

Caterina Petrone

Maud Champagne-Lavau

Does laughter play a role in irony comprehension?

Keywords: irony, laughter, multi-modal language processing

Laughter performs multiple pragmatic functions in conversation [START_REF] Glenn | Studies of laughter in interaction[END_REF]. It is often used to show enjoyment of pleasant incongruities (c.a. humour), to smooth dialogue acts having a potential negative effect on the ideal flow of a conversation (e.g. disagreement, asking a favour), or to show pleasant appraisals (e.g., accompanying a compliment) [START_REF] Mazzocconi | What's your laughter doing there? A taxonomy of the pragmatic functions of laughter[END_REF]. Furthermore, laughter can be a cue of non-literal intentions [START_REF] Hoicka | Do the wrong thing: How toddlers tell a joke from a mistake[END_REF] signalling incongruities between what is said and what is meant (e.g. irony or scare quoting ;[START_REF] Schaffer | Processing negation without context-why and when we represent the positive argument[END_REF]Haiman, 1998;[START_REF] Ginzburg | Laughter as language[END_REF], marking non-serious or negative speaker's attitudes [START_REF] Attardo | Mul-timodal markers of irony and sarcasm[END_REF][START_REF] Utsumi | Verbal irony as implicit display of ironic environment: Distinguishing ironic utterances from non irony[END_REF]. Bryant (2016) extracted ironic utterances from natural friendly conversations and presented them out of context, with or without the adjacent laughter. The presence of laughter increased listeners' judgements of non-literal speaker's meaning. However, we still don't know whether laughter cues ironic interpretation of sentences when embedded in context. Contextual incongruity in relation to the target sentence has been consistently identified as the most important factor for ironic interpretation [START_REF] Stacey | Context incongruity and irony processing[END_REF][START_REF] Champagne-Lavau | Theory of mind and context processing in schizophrenia: the role of cognitive flexibility[END_REF]Riviere et al. 2018). Burgers et al.'s (2012) results show, in line with [START_REF] Utsumi | Verbal irony as implicit display of ironic environment: Distinguishing ironic utterances from non irony[END_REF] model, that the co-presence of multiple cues reduces the complexity of irony processing. [START_REF] Deliens | Context, facial expression and prosody in irony processing[END_REF] demonstrates that the presence of other multi-modal markers of irony, such as prosody or facial expressions, can outweigh the presence of more reliable contextual cues, in the interest of faster, yet less accurate, responses. We hypothesized that laughter would lead towards ironic responses, especially when contextual cues are not very strong (i.e. weak incongruity with the target sentence). Furthermore, laughter will facilitate processing and induce faster reaction times in the case of strong incongruity, as in this case it will be a redundant cue for irony interpretation.

Methods

Ninety-one French native speakers have participated in the experiment so far, out of 120 estimated (mean age 20.29 sd 3.25; 19 men). All participants gave informed consent and got 10€ compensation.

Our stimuli were constituted by twenty-four stories adapted into French by Champagne-Lavau et al. ( 2012) from [START_REF] Stacey | Context incongruity and irony processing[END_REF]. Each story included a situational context followed by a target sentence. We manipulated the contextual incongruence with respect to the target sentence in strong ("Marine is taking a maths exam. She has revised a lot and she gets 5/20 in the exam. Thomas says:"), weak ("Marine is taking a maths exam. She has revised a lot and she gets 11/20 in the exam. Thomas says:") and no incongruity ("Marine is taking a maths exam. She has revised a lot and she gets 20/20 in the exam. Thomas says:"). A French actress uttered both the contexts and the targets. Targets were preceded by a short laugh ("<laugh>/Marine is a clever student."). Only the targets embedded in the no incongruity context (i.e. sincere prosody) were selected to be played across all contextual conditions. Targets were validated as being reliably interpreted as non ironic in a previous perception study. Each target sentence was presented either with or without the short preceding laugh. Thus, there were 6 versions of each story (24 stories x 3 context conditions x 2 laughs present/absent), for a total of 144 stimuli. The stimuli were divided into 6 groups of 24 stories, in a Latin square design, so that each participant heard each story only once.

Participants listened to each story and judged as quickly as possible whether the final target statement was ironic or not. Response type (ironic/non-ironic) and response times (RTs) were collected for each item.

Results

We performed a Generalised Linear Mixed Model on participants' responses (ironic/nonironic), with subjects and items as random factors. The effect of Context was significant, with ironic responses being more likely in the weak than in the no incongruity condition (E=2.7361, SE= 0.2183, z=12.53, p<.001) and even more so for strong incongruity (E=4.6344, SE= 0.2617, z=17.71 , p<.001). Neither the effect of Laughter nor its interaction with Context were significant (Figure 1). Furthermore, we run a Linear Mixed Effect Model on log-transformed RTs. The model had t he same fixed and random structure as for the GLMM model. We observed a significant effe ct of Context, with slower RTs in the weak incongruity condition compared to the other two contextual conditions (no incongruity: E=73.28; SE=18.96; df=2000.40; t=3.865; p<.001; stro ng incongruity E=123.10; SE=18.91; df=2000.15, t=6.508, p<.001). Neither the effect of Laug hter nor its interaction with Context were significant (Figure 2).

Discussion

Contrarily to our hypotheses, the presence of laughter did not lead to more "ironic" responses and did not affect reaction times. The lack of effects was independent of the degree of incongruity with the preceding context. Our results have implications for irony and multi-modal language processing models. The effect of Context confirmed previous data on the impact of contextual incongruity on irony detection [START_REF] Stacey | Context incongruity and irony processing[END_REF][START_REF] Champagne-Lavau | Theory of mind and context processing in schizophrenia: the role of cognitive flexibility[END_REF] as well as confirming that in the weak incongruity condition participants have slower RTs (Riviere et al. 2018). Despite laughter being a potential salient cue of non-literal intentions, we do not observe laughter to outweigh the situational context in the interest of a faster processing (contra [START_REF] Deliens | Context, facial expression and prosody in irony processing[END_REF], neither to speed up RTs in the strong incongruity condition (contra Burger et al., (2012) and [START_REF] Utsumi | Verbal irony as implicit display of ironic environment: Distinguishing ironic utterances from non irony[END_REF] predictions). Our data are also in contrast with Bryant (2016), who found that laughter leads to more ironic interpretation of utterances presented in isolation. The lack of Laughter effects on ironic responses when targets are embedded in context can be due to two reasons. First, being laughter a highly multifunctional signal, it might be more ambiguous that other ironic multi-modal markers. Second, similarly to indexicals, the interpretation of laughter is closely tied to the context, so much that it cannot outweigh or interact with contextual processing being influenced by it. This resonates with data on speech processing showing the impact of context on semantic and pragmatic incremental interpretations (e.g. [START_REF] Mante | When peanuts fall in love: N400 evidence for the power of discourse[END_REF][START_REF] Daniel J Grodner | some," and possibly all, scalar inferences are not delayed: Evidence for immediate pragmatic enrichment[END_REF][START_REF] Schaffer | Processing negation without context-why and when we represent the positive argument[END_REF].

Figure 1

 1 Figure 1 Mean percentages of ironic responses (I) according to Context (No Incongruity, Weak Incongruity and Strong Incongruity) and Laughter (Present/Absent) conditions.

Figure 2

 2 Figure 2 Mean Reaction Times of Ironic Responses (I) according to Contextual Incongruity and Laughter (Presence/Absence).