Conceptio › Archive › arXiv CS

arXiv CSopen access

Gradient Regularized Newton Boosting Trees with Global Convergence

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Gradient Regularized Newton Boosting Trees with Global Convergence

Nikita Zozoulenko 1 Daniel Falkowski 2 Thomas Cass 1 † Lukas Gonon 1 3 †

arXiv:2605.00581v1 [stat.ML] 1 May 2026

Abstract

baselines (Qin et al., 2021; Grinsztajn et al., 2022; McElfresh et al., 2023; Erickson et al., 2025). Modern implementations such as XGBoost (Chen & Guestrin, 2016), LightGBM (Ke et al., 2017), and CatBoost (Prokhorenkova et al., 2018) are based on the Newton boosting algorithm, which updates a decision tree ensemble by performing a Newton descent step in the space of decision trees, derived via a second order Taylor expansion with respect to the training data (Chen & Guestrin, 2016). However, despite the widespread use of GBDTs, the theoretical mechanisms of Newton boosting remain poorly understood, with most prior work focused on first-order gradient boosting (Mason et al., 1999; Friedman, 2001; Grubb & Bagnell, 2011; Freund et al., 2017; Cortes et al., 2019; Lu & Mazumder, 2020; Lu et al., 2020).

Gradient Boosting Decision Trees (GBDTs) dominate tabular machine learning, with modern implementations like XGBoost, LightGBM, and CatBoost being based on Newton boosting: a second-order descent step in the space of decision trees. Despite its empirical success, the global convergence of Newton boosting is poorly understood compared to first-order boosting. In this paper, we introduce Restricted Newton Descent, which studies convex optimization with Newton’s method on Hilbert spaces with inexact iterates, based on the concepts of cosine angle and weak gradient edge. Within this framework, we recover Newton boosting with GBDTs and classical finitedimensional theory as special cases. We first prove that vanilla Newton boosting achieves a linear rate of convergence for smooth, strongly convex losses that satisfy a Hessian-dominance condition. To handle general convex losses with Lipschitz Hessians, we extend a recent gradient regularized Newton scheme to the restricted weak learner setting. This scheme minimally modifies the classical algorithm by introducing an adaptive ℓ2 -regularization term proportional to the square root of the gradient norm at each iteration. We establish a O( k12 ) rate for this scheme, thereby obtaining a globally convergent second-order GBDT algorithm with a rate matching that of first-order boosting with Nesterov momentum. In numerical experiments, we show that our scheme converges while vanilla Newton boosting may diverge.

While Newton’s method in RN offers fast quadratic local convergence, it lacks global convergence guarantees for general strictly convex losses, even when combined with line search (Jarre & Toint, 2016). Recently, the convex optimization literature has seen a resurgence of interest in regularized Newton schemes that achieve global O( k12 ) convergence rates. This was first established for the Cubic Regularized Newton (CRN) method (Nesterov & Polyak, 2006; Nesterov, 2008); however, CRN requires solving an expensive subproblem at each iteration, making it unfit for GBDTs. More recently, the Gradient Regularized Newton (GRN) method was proposed, achieving the same O( k12 ) rate as CRN (Mishchenko, 2023; Doikov & Nesterov, 2024). GRN uses an adaptive ℓ2 -regularization term proportional to the square root of the gradient norm at each iteration. Crucially, this method avoids expensive subproblems and incurs negligible computational overhead compared to the standard Newton update. This discovery has sparked new research into the global convergence of second-order numerical schemes (Hanzely et al., 2022; Doikov et al., 2024; Doikov, 2025; Hanzely, 2025). A natural question arises: can these convergence guarantees be extended to GBDTs and optimization with weak learners, providing convergence rates for second-order boosting methods used in practice?

1. Introduction Gradient Boosting Decision Trees (GBDTs) are powerful machine learning models, excelling in tabular settings such as regression, classification, and learning to rank over neural †Equal last author 1 Department of Mathematics, Imperial College London, UK 2 Department of Mathematics, Stockholm University, Sweden 3 School of Computer Science, University of St. Gallen, Switzerland. Correspondence to: Nikita Zozoulenko <[email protected]>.

1.1. Contributions In this paper, we formulate Newton boosting as a convex optimization problem on a Hilbert space H, where optimization is performed on a restricted set of permissible weak learners F ⊂ H. Our contributions are: 1

Gradient Regularized Newton Boosting Trees with Global Convergence

et al. (2014) proved a classical O( k1 ) rate. Lu et al. (2020) incorporated Nesterov momentum to achieve an accelerated O( k12 ) rate, similar to our work. Linear rates for strongly convex losses were proven by Grubb & Bagnell (2011) using gradient descent, and by Lu & Mazumder (2020) via randomized coordinate descent. Telgarsky (2012) studied the primal-dual structure of boosting, obtaining a linear rate with non-standard constants.

• We introduce Restricted Newton Descent using weak iterates based on the concepts of cosine angle and weak gradient edge, obtaining both tree boosting and finitedimensional convex optimization as special cases. • For Hessian-dominated smooth strongly convex losses, we prove that vanilla restricted Newton’s method achieves a linear rate of convergence. This includes ℓ2 -regularized binary and categorical cross entropy.

2. Newton Boosting as Hilbert Space Convex Optimization

• For general convex losses with 2M -Lipschitz Hessians, we generalize the gradient regularized Newton scheme of Mishchenko (2023) to the Hilbert space setting with weak learners. We prove a global O( k12 ) convergence rate for all learning rates η ≤ 1, and a local linear rate if the loss additionally is strongly convex.

In this section, we recall Newton’s method in the Hilbert space setting, and introduce the Restricted Newton Descent framework where Newton boosting with GBDTs is recovered as a special case.

• We present numerical results showing that the gradient regularized Newton scheme converges while vanilla Newton boosting may diverge.

2.1. Hilbert Space Newton’s Method Let H be a Hilbert space. In this paper we consider twice Fréchet differentiable convex loss functions L : H → R, defined below. Definition 2.1. A function L : H → R is said to be Fréchet differentiable if there exists a mapping ∇L : H → H such that for all h, f ∈ H

1.2. Related Literature GBDTs: Gradient boosting models have traditionally been viewed as gradient descent in RN on the training data, where N is the dataset size (Mason et al., 1999; Friedman et al., 2000). Later works identified this process with gradient descent in the Hilbert space of square-integrable functions L2 (b νN ), where νbN is the empirical data distribution (Grubb & Bagnell, 2011); see also connections to gradient representation boosting in deep learning (Nitanda & Suzuki, 2018; Suggala et al., 2020; Zozoulenko et al., 2025). Recent theoretical work has shifted from the gradient perspective to studying boosting via coordinate descent in highdimensional spaces, achieved by enumerating all possible decision trees (Cortes et al., 2019; Lu & Mazumder, 2020; Parnell et al., 2020).

L(h + f ) = L(h) + ⟨f, ∇L(h)⟩ + o(∥f ∥). The element ∇L(h) is called the gradient at h. A function L : H → R is said to be twice Fréchet differentiable if L is Fréchet differentiable, and if for all h ∈ H there exists a bounded, self-adjoint linear operator ∇2 L(h) : H → H such that 1 L(h + f ) = L(h) + f, ∇L(h) + ∇2 L(h)[f ] + o(∥f ∥2 ), 2 for all f ∈ H. The map ∇2 L(h) is called the Fréchet Hessian (or second derivative) of L at h.

Newton Boosting: Newton-like updates were first introduced by LogitBoost (Friedman et al., 2000) for logistic loss, and later applied to GBDTs in a general context by XGBoost (Chen & Guestrin, 2016). Empirical differences between first-order and Newton boosting were investigated in (Sigrist, 2021). Theoretical analysis of Newton boosting remains limited compared to first-order methods; Notable work includes the LogitBoost analysis by Sun et al. (2014) using probability clamping, and later the SnapBoost work using coordinate descent (Parnell et al., 2020).

We aim to minimize L with Hilbert space Newton’s method with a fixed learning rate η > 0. At each iteration k, we Pk update an iterate Fk = Fk−1 + ηfk = t=1 ηft by minimizing a second-order Taylor expansion of the loss: 1 2 L(Fk + f ) ≈ L(Fk ) + f, ∇L(Fk ) + ∇ L(Fk )[f ] 2 1 = L(Fk ) + f, gk + Hk [f ] 2 =: L(Fk ) + Qk (f )

Convergence Rates in Boosting: For second order boosting, both Sun et al. (2014) and Parnell et al. (2020) proved a linear rate in the strongly convex setting. In contrast, our work also covers general convex losses with Lipschitz Hessians. As for first order boosting, the earliest explicit convergence rate was proved by Bickel et al. (2006) with 1 a slow O((log k)− 2 ) rate. For smooth convex losses, Sun

where gk = ∇L(Fk ) is the gradient, Hk = ∇2 L(Fk ) is the Hessian operator, and Qk (f ) is the local second-order approximation of L at the point Fk , that is after k iterations of the optimization scheme. Differentiating Qk yields ∇Qk (f ) = gk + Hk [f ]. 2

Gradient Regularized Newton Boosting Trees with Global Convergence

Setting the derivative of Qk to 0 and solving for f gives the Newton update, assuming that Hk is invertible at the point gk : fk+1 := −Hk−1 [gk ] = argmin Qk (f ).

As we show later, different schemes rely on different error metrics. For vanilla Newton’s method, the relevant metric w is the cosine angle between fk+1 and fk+1 in the induced Hessian norm (see Section 3), whereas for the globally convergent gradient regularized scheme, the metric takes the form of a weak learner edge condition between the true gradient and the implied weak gradient (see Section 4).

(1)

f ∈H

2.2. Restricted Newton Descent In the context of gradient boosting, the exact update fk+1 in (1) is generally not attainable since weak learners, as opposed to exact Newton directions, are used to minimize the loss. Consequently, the ensemble Fk instead takes the Pk form Fk := t=1 ηftw for some notion of a weak iterate ftw . To formalize this, we introduce the Restricted Newton Descent framework (not to be confused with constrained optimization). This differs from standard Newton’s method in two ways. Firstly, the gradient gk and Hessian Hk are computed w.r.t. the sum of weak, rather than exact, iterates Fk . Secondly, we do not minimize Qk (f ) over the entire w space f ∈ H, but rather restrict the weak update fk+1 to w belong to some subset fk+1 ∈ F ⊂ H of admissible weak learners. More specifically, given a family F, we define the weak iterates fk+1 as any element w fk+1 ∈ argmin Qk (f ).

2.3. GBDTs as Restricted Convex Optimization In this section, we provide an overview of gradient boosting from a functional L2 (ν) perspective (Grubb & Bagnell, 2011; Suggala et al., 2020), in the context of Restricted Newton Descent. Let (X, Y ) ∼ ν be a random sample with its corresponding probability measure ν. Denote by X ∼ νX the features in Rq , with targets Y ∼ νY in RK , and νY |X=x the conPN ditional law. Let νbN = N1 i=1 δ(xi ,yi ) be the empirical measure of ν with respect to a training dataset {xi , yi }N i=1 of size N . We work in the Hilbert space L2 (νX ) of square integrable functions defined on the feature space, with inner product ⟨f, g⟩ = EνX [⟨f (X), g(X)⟩RK ]. When ν = νbN , N ×K this space can be identified using the inner PN with R 1 product ⟨f, h⟩ = N i=1 ⟨f (xi ), h(xi )⟩RK . Let l be a twice differentiable convex loss function.

(2)

f ∈F

To derive the Newton boosting algorithm used by e.g. XGBoost and LightGBM as a special case of Restricted Newton Descent, we simply let F be the set of weak decision trees up to a fixed depth, let the base space be H = L2 (b νX,N ), PN and the loss function be L(F ) = N1 i=1 l(F (xi ), yi ) = EνN [l(F (X), Y )]. In the space L2 (νX ), the Fréchet gradient and Hessian take the form ∇L(F )(x) = EνY |X=x ∂1 l(F (x), Y ) , (3)

w Note that fk+1 is not necessarily unique (although it will be for decision trees). We consider general families F satisfying the following scalability condition, similar to Lu et al. (2020):

Assumption 2.2. The family F is closed under scalar multiplication. That is, if f ∈ F then af ∈ F for all a ∈ R. Decision trees, commonly used in boosting, satisfy this asw sumption. If F = H, then the weak update fk+1 coincides with the exact update fk+1 , and standard Newton’s method is recovered. The full algorithm is detailed in Algorithm 1, with the exact step in parentheses.

∇2 L(F )[f ](x) = EνY |X=x ∂11 l(F (x), Y )f (x) ,

(4)

and are easily computed for empirical measures νbN as partial derivatives and matrices with respect to F (xi ). Write g(i) = ∂1 l(Fk (xi ), yi ) ∈ RK and h(i) = ∂11 l(Ft (xi ), yi ) ∈ RK×K . Following the XGBoost derivation (Chen & Guestrin, 2016), the objective becomes to minimize

Algorithm 1 Vanilla Restricted Newton 1: Input: Loss L : H → R. Learning rate η. Weak learner

family F. Initial value F0 . 2: for k = 0, 1, 2, . . . do 3: gk , Hk ← ∇L(Fk ), ∇2 L(Fk ) 4: Exact target fk+1 ← −Hk−1 gk w 5: Weak learner fk+1 ← argminf ∈F Qk (f ) w 6: Fk+1 ← Fk + ηfk+1 7: end for

1 X l(Fk (xi ) + f (xi ), yi ) N i=1 N 1 X 1 ≈ L(Fk ) + f (xi ), g(i) + h(i) f (xi ) N i=1 2 RK

L(Fk + f ) =

Theoretical analysis of any optimization scheme now dew pends on the error between the chosen weak iterate fk+1 and the exact iterate fk+1 , as this difference introduces an error component orthogonal to the optimal descent direction.

= L(Fk ) + Qk (f ) which we see coincides with the Hilbert space derivation using Qk . Furthermore, in boosting we minimize over the 3

Gradient Regularized Newton Boosting Trees with Global Convergence

set of weak learners f ∈ F rather than over P all L2 (b νN ). Letting f be a decision tree of the form f (x) = j wj Ij (x) where Ij (x) ∈ {0, 1} is a disjoint partition of the feature space, one finds that the optimal weights wj minimizing Qk (f ) are  −1 X X wj = −  h(i)  g(i) , i∈Ij

The following lemma motivates the use of the Hessianinduced norm and naturally leads to the definition of the cosine angle between weak and exact iterates. Lemma 3.3. Minimizing Qk (f ) is equivalent to finding a closest element f ∈ F to the exact Newton direction fk+1 in the Hessian-induced norm ∥ · ∥Hk . Proof. Using the Hessian-induced norm and the exact Newton update fk+1 , we can write

i∈Ij

coinciding with the classical XGBoost formula. See Section A.2 for more details and full derivation.

∥f − fk+1 ∥2Hk = ∥f ∥2Hk − 2⟨f, fk+1 ⟩Hk + ∥fk+1 ∥2Hk = ⟨f, Hk f ⟩ + 2⟨f, gk ⟩ + ∥fk+1 ∥2Hk = 2Qk (f ) + ∥fk+1 ∥2Hk .

3. Restricted Newton for Hessian-dominated Losses

Definition 3.4. Consider the iterates produced by vanilla Newton’s method. At each iteration k, we define the Hessian-induced cosine angle Θk ∈ [0, 1] between the exact w update fk+1 and the weak learner fk+1 as

Before introducing the globally convergent scheme in Section 4, we first analyze the vanilla Newton update via Restricted Newton Descent. We prove for smooth strongly convex losses satisfying a Hessian-dominance condition, that vanilla Newton’s method with weak learners converges globally with a linear rate. This analysis broadly parallels that of the LogitBoost analysis (Sun et al., 2014), but we analyze it within our Restricted Newton Descent formulation in a more general setting beyond logistic loss. To ensure the Newton update is well-defined on H, we assume the following:

Θk :=

w ⟨fk+1 , fk+1 ⟩Hk , w ∥fk+1 ∥Hk ∥fk+1 ∥Hk

Θ := inf Θk . k

(6)

In contrast to Sun et al. (2014), which uses a weak learnability assumption specific to binary classification, more recent prior work uses definitions similar in spirit to ours, but defines them by taking suprema and infima over much larger spaces of permissible weak learners and targets (Lu & Mazumder, 2020; Lu et al., 2020; Parnell et al., 2020); see also (Grubb & Bagnell, 2011). Our definition is simpler w and more direct, capturing the specific two vectors fk+1 and fk+1 determining the cosine angle. Using this definition, we immediately obtain the following properties connecting the weak and exact Newton iterates with the gradient gk . Lemma 3.5. If F is closed under scalar multiplication, then

Assumption 3.1. We assume that the equation gk = −Hk f admits a unique solution f = fk+1 = −Hk−1 gk . Theorem 3.1 is satisfied, for example, when L is strongly convex, or in many practical settings when H is a finite dimensional space with a strictly convex loss L. Note that this assumption is not required for the gradient regularized scheme in Section 4.

w 1. ∥fk+1 − fk+1 ∥2Hk = (1 − Θ2k )∥fk+1 ∥2Hk ,

3.1. Cosine Angle

w 2. ∥fk+1 ∥Hk = Θk ∥fk+1 ∥Hk ,

Recall that the iterates of Restricted Newton Descent are derived by minimizing Qk (f ) = f, gk + 12 Hk f restricted Pk to f ∈ F at each iteration k, yielding Fk = t=1 ηftw . In order to analyze the restricted Newton scheme, we need a way to measure the error between the exact direction fk+1 w and the weak learner fk+1 . It turns out that the critical quantity determining the performance of this scheme, is w the cosine angle between fk+1 and fk+1 measured in the Newton geometry induced by the Hessian. For this, we use the following norm definition.

w w 3. ∥fk+1 ∥2Hk = −⟨gk , fk+1 ⟩.

Proof. Since F is closed under scalar multiplication, the w objective Qk (αfk+1 ) is minimized at α = 1. Differentiating the equivalent objective (see Theorem 3.3) ϕ(α) := 1 w 2 2 ∥αfk+1 − fk+1 ∥Hk with respect to α gives the derivative ′ w w ϕ (α) = ⟨fk+1 , αfk+1 − fk+1 ⟩Hk . Setting this to zero at w w α = 1 yields ⟨fk+1 , fk+1 ⟩Hk = ∥fk+1 ∥2Hk . Substituting this into the definition of Θk , we obtain

Definition 3.2. Let A : H → H be a self-adjoint positive operator. We define the inner product induced by A as ⟨h, f ⟩A := ⟨h, Af ⟩.

Θk =

w w ∥fk+1 ∥2Hk ∥fk+1 ∥ Hk = , w ∥fk+1 ∥Hk ∥fk+1 ∥Hk ∥fk+1 ∥Hk

(7)

which proves the second identity. The first identity then follows immediately from expanding the norm using inner products. The third identity follows from the fact that w w w −⟨gk , fk+1 ⟩ = ⟨Hk fk+1 , fk+1 ⟩ = ⟨fk+1 , fk+1 ⟩Hk .

(5)

When A = Hk , we call this the Hessian-induced inner product, with induced norm ∥ · ∥Hk . 4

Gradient Regularized Newton Boosting Trees with Global Convergence 2

of 1 − ρsnap = 1 − Θ2snap Sµ2 for a fixed learning rate η = Sµ . While our definitions of Θ are comparable, our result yields a better dependence on the condition number S µ . Furthermore, we obtain essentially the same rate as Sun et al. (2014), where they instead use a change of Hessian lemma, and their probability clamping is replaced by strong convexity in our lemma.

3.2. Decrease in Loss for Vanilla Restricted Newton We now show that the restricted Newton scheme guarantees a strict decrease in loss at each iteration, forming the basis of our convergence analysis. We rely on the following standard result from optimization theory, see Section B for more details. Lemma 3.6. If the loss L is S-smooth, then for all f ∈ H S L(Fk + f ) ≤ L(Fk ) + ⟨gk , f ⟩ + ∥f ∥2 . 2

While cross entropy loss itself is not strongly convex, this issue is typically addressed in two ways. First, for practical applications ℓ2 -regularization is almost always applied to the loss function, yielding a strongly convex loss. Second, probability values can be clipped to [ϵ, 1 − ϵ] for some ϵ > 0 as in (Sun et al., 2014), which implicitly implies strong convexity. An alternative approach to Theorem 3.8 could be to clip the output tree values, in combination with a change of Hessian Lemma, similar to (Sun et al., 2014, Lemma 9) to obtain a linear rate. However, we believe our approach offers a more concise and simpler theoretical treatment.

(8)

Definition 3.7. We say that the loss L is Hessiandominated if there exists a constant c > 0 such that the exact iterates fk+1 satisfy ∥fk+1 ∥2Hk ≥ cL(Fk ). Theorem 3.7 generalizes the condition derived in (Sun et al., 2014, Theorem 4) for LogitBoost, to general losses using the language of Hessian norms and weak iterates. Examples of Hessian-dominated losses include binary and categorical cross entropy, both with constant c = 1 (see Section F for more details).

4. Gradient Regularized Restricted Newton

We are now ready to state and prove our main convergence result for Restricted Newton Descent.

Despite the fast quadratic local convergence of Newton’s method in finite-dimensional convex optimization, the method does not have global convergence guarantees for general smooth√convex functions. A classical example of this is L(x) = 1 + x2 defined for x ∈ R, see Section E. However, cubic regularized Newton (Nesterov & Polyak, 2006) and the more recent gradient regularized Newton (Mishchenko, 2023; Doikov & Nesterov, 2024) achieve a global O( k12 ) convergence rate. In this section, we extend the latter scheme to Newton boosting with weak learners within our framework of Restricted Newton Descent.

Theorem 3.8 (Global Rate I). If L is S-smooth, µ-strongly convex, and F closed under scalar multiplication, then for any learning rate η ∈ (0, 2µ S ) we have ηS Θ2 ∥fk+1 ∥2Hk . (9) L(Fk ) − L(Fk+1 ) ≥ η 1 − 2µ Consequently, if L satisfies Theorem 3.7, then vanilla restricted Newton’s method converges linearly with rate (1 − ρ), where ρ = cΘ2 η(1 − ηS 2µ ): L(Fk+1 ) ≤ (1 − ρ)L(Fk ).

Instead of minimizing the local quadratic approximation Qk (f ) at each iteration k, gradient regularized Newton’s method minimizes the following regularized objective: 1 λk Qreg (f ) = f, g + H [f ] + ∥f ∥2 k k k 2 2 λk = Qk (f ) + ∥f ∥2 , 2

(10)

Proof. Starting with the standard smoothness upper bound L(F + f ) ≤ L(F ) + ⟨g, f ⟩ + S2 ∥f ∥2 from Theorem 3.6, w we substitute the weak update f = ηfk+1 . Using strong 1 2 2 convexity to write ∥u∥ ≤ µ ∥u∥Hk , and the cosine angle properties from Theorem 3.5, we obtain

where λk ∈ (0, ∞) is a scalar regularization parameter. For losses with 2M p -Lipschitz continuous Hessians, we will allow values λk ≥ M ∥gk ∥. Minimizing Qreg k (f ) yields the exact regularized update

Sη 2 w 2 ∥fk+1 ∥ (11) 2 Sη 2 w 2 w ≥ η∥fk+1 ∥2Hk − ∥f ∥ (12) 2µ k+1 Hk Sη 2 = η− Θ2k ∥fk+1 ∥2Hk . (13) 2µ

w L(Fk ) − L(Fk+1 ) ≥ −η⟨gk , fk+1 ⟩−

fk+1 = −(Hk + λk I)−1 [gk ].

(14)

In other words, gradient regularized Newton is simply an ℓ2 -regularized Newton step where the ℓ2 -regularization is adaptive at each iteration,p being proportional to the square root of the gradient norm ∥gk ∥. Similar to Section 3, we consider Restricted Newton Descent using weak learners rather than the exact update. The full gradient regularized

Applying Theorem 3.7, we get L(Fk+1 ) ≤ L(Fk ) − ρL(Fk ), which implies linear convergence. Remark 3.9. Our bound compares favourably to SnapBoost (Parnell et al., 2020), which proved a linear rate 5

Gradient Regularized Newton Boosting Trees with Global Convergence

We impose a standard regularity condition on the loss L in terms of the Lipschitz continuity of its Hessian, as is common for regularized Newton methods (Nesterov & Polyak, 2006; Nesterov, 2008; Mishchenko, 2023; Doikov & Nesterov, 2024).

scheme is detailed below in Algorithm 2 (the implicit exact step is denoted in parentheses): Algorithm 2 Gradient-Regularized Restricted Newton 1: Input: Loss L : H → R with 2M -Lipschitz Hessian.

Assumption 4.3. The Fréchet Hessian ∇2 L : H → L(H) is 2M -Lipschitz continuous for some constant M > 0:

Learning rate η. Weak learner family F. Initial F0 . 2: for k = 0, 1, 2, . . . do 2 3: gk , Hk ← ∇L(F p k ), ∇ L(Fk ) 4: Choose λk ≥ M ∥gk ∥ 5: Exact target fk+1 ← −(Hk + λk I)−1 gk w 6: Weak learner fk+1 ← argminf ∈F Qreg k (f ) w 7: Fk+1 ← Fk + ηfk+1 8: end for

∥∇2 L(f ) − ∇2 L(g)∥ ≤ 2M ∥f − g∥

∀f, g ∈ H.

Before we delve into the convergence rate analysis, we recall the following standard results on Lipschitz Hessians, well known in the finite-dimensional Rd setting. See Section B for proof. Lemma 4.4. If ∇2 L is 2M -Lipschitz, then for all f, g ∈ H

4.1. Properties of Gradient Regularization 1. L(f ) ≤ L(g) + ⟨∇L(g), f − g⟩ + 12 ⟨∇2 L(g)(f − 3 g), f − g⟩ + M 3 ∥f − g∥ ,

We begin by establishing some basic properties the gradient regularized scheme. In the subsequent analysis, define Kk := Hk + λk I.

2. ∥∇L(f ) − ∇L(g) − ∇2 L(g)(f − g)∥ ≤ M ∥g − f ∥2 .

Lemma 4.1. The exact regularized update (14) satisfies λk fk+1 = − (gk + Hk [fk+1 ]) .

The following lemma shows that the weak iterates of Algorithm 2 guarantee a strict decrease in loss. From this point on, we assume that F is closed under scalar multiplication.

(15)

Proof. Multiply the Newton update (14) by (Hk + λk I).

Lemma 4.5. If L is convex with 2M -Lipschitz Hessian, and η ≤ 2, then the iterates of Algorithm 2 satisfy η3 w L(Fk ) − L(Fk+1 ) ≥ η − λk ∥fk+1 ∥2 (16) 3

Lemma 4.2. If L is convex, then for all u ∈ H ∥u∥2Kk := ⟨(Hk + λk I)u, u⟩ = λk ∥u∥2 + ⟨u, Hk u⟩

Proof. Using Theorem 4.4 and Theorem 4.2, we write

≥ λk ∥u∥2 .

L(Fk+1 ) − L(Fk )

Furthermore, if the weak learner family F is closed under scalar multiplication, then the iterates of Algorithm 2 satisfy

η2 M 3 w 3 w w ⟨Hk (fk+1 ), fk+1 ⟩+ η ∥fk+1 ∥ 2 3 M 3 w 3 η2 η2 w 2 w w = −η∥fk+1 ∥2Kk + ∥fk+1 ∥Kk − λk ∥fk+1 ∥2 + η ∥fk+1 ∥ 2 2 3 η2 η2 M 3 w 3 w w =− η− ∥fk+1 ∥2Kk − λk ∥fk+1 ∥2 + η ∥fk+1 ∥ . 2 2 3 p By Theorem 4.2 and λk ≥ M ∥gk ∥ we see that w ≤ η⟨gk , fk+1 ⟩+

w w 1. ∥fk+1 ∥2Kk = −⟨gk , fk+1 ⟩, w 2. λk ∥fk+1 ∥ ≤ ∥gk ∥.

Proof. The first result follows by convexity. For the rest, let w ϕ(t) := Qreg k (tfk+1 ) =

1 2 w 2 w ⟩. t ∥fk+1 ∥Kk + t⟨gk , fk+1 2

w M ∥fk+1 ∥3 ≤

w w Differentiating gives 0 = ϕ′ (t) = t∥fk+1 ∥2Kk + ⟨gk , fk+1 ⟩. Since F was assumed to be scalable, the minimum must be attained at t = 1, and the result follows. As for the last inequality, this follows by the first inequality and CauchySchwartz:

M ∥gk ∥ w 2 w ∥fk+1 ∥ ≤ λk ∥fk+1 ∥2 . λk

Combining the above, and again using Theorem 4.2, gives the result. 4.2. Convergence of Restricted GRN We now require a way to quantify how well the weak upw dates fk+1 approximate the exact updates fk+1 in the gradient regularized scheme. Previously in Theorem 3.8 for vanilla Newton, the decrease in loss was determined by the

w w w w λk ∥fk+1 ∥2 ≤ ∥fk+1 ∥2Kk = −⟨gk , fk+1 ⟩ ≤ ∥gk ∥∥fk+1 ∥.

Gradient Regularized Newton Boosting Trees with Global Convergence

Hessian-induced norm ∥ · ∥Hk . In contrast, for the regularized scheme the decrease in loss is governed by the quantity w λk ∥fk+1 ∥. As such, the cosine angle from Theorem 3.2 is no longer well suited for theoretical analysis of GRN, since the scheme and its convergence proof are fundamentally driven by gradient growth rather than directional alignment. Consequently, motivated by Theorem 4.1, we introduce the notion of an implied weak gradient gkw , together with a corresponding weak gradient edge condition. This condition essentially states that the weak gradient remains within a relative radius of the true gradient, at each iteration k.

Theorem 4.9 (Global Rate II). Assume L is convex with 2M -Lipschitz Hessian, finite sublevel sets with p diameter Λ, and weak gradient edge γ. Let λk = C M ∥gk ∥ for some C ≥ 1. For any learning rate η ∈ (0, 1], the gradient regularized Newton scheme has global convergence rate L(Fk ) − L(F ∗ ) ≤ 2 2 C M Λ3 2 γ , Λ exp −kηγ O max + 2 − 2η /8 . η 2 k 2 γ 12 2 Proof Sketch. We generalize the analysis of Mishchenko (2023) to the Hilbert space setting with inexact weak learners. The proof proceeds by analyzing two regimes based on the fraction of iterates where the gradient fails to contract sufficiently, determined by η and γ. In the first regime, we 3/2 derive a recurrence of the form αk+1 ≤ αk − τ αk for 1 some τ > 0, yielding a O( η2 γ 12 k2 ) rate. In the second regime, the cumulative contraction dominates, resulting in a linear rate. The global rate is governed by the maximum of these two bounds; see Section D for more details. p Theorem 4.10 (Local Rate). Let λk = C M ∥gk ∥ for some C ≥ 1. If L is µ-strongly convex with 2M -Lipschitz Hessian, weak gradient edge γ, and if there exists a k0 ≥ 0 2 √ 2 1− 1−γ 2 √ 2 , then for all k ≥ such that ∥gk0 ∥ ≤ 4Cµ2 M

Definition 4.6. We define the implied weak gradient as w gkw := −(Hk + λk I)fk+1 .

(17)

w We say that the iterates fk+1 have weak gradient edge γ if there exists a real number 0 < γ ≤ 1 satisfying

∥gkw − gk ∥2 ≤ (1 − γ 2 )∥gk ∥2 .

(18)

The following lemma relates the gradient at consecutive iterations and serves as the primary tool for our convergence analysis. Lemma 4.7 (Gradient Growth). If the iterates of Algorithm 2 have weak gradient edge γ, then p ∥gk+1 ∥ ≤ 1 + η 2 + η 1 − γ 2 ∥gk ∥. (19)

k0 we have ∥gk+1 ∥ ≤

(21)

w = (1 − η)gk + η(gk − gkw ) − ηλk fk+1 +E

(22)

(23)

w Proof Sketch. The weak gradient edge implies that ∥gk ∥ ≤ p 1 + 1 − γ 2 ∥gk ∥ := Cγ ∥gk ∥, while the µ-strong convexity implies that 1 Cγ w w ∥g ∥. ∥fk+1 ∥ = ∥(Hk + λI)−1 gkw ∥ ≤ ∥g w ∥ ≤ µ µ

(20)

w = gk + η(−gkw − λk fk+1 )+E

3+ρ ∥gk ∥, 4

p 2 where ρ = 1 − η(1 − 1 − γ 2 ) = O(1 − η γ2 ). Hence the iterates of Algorithm 2 converge linearly locally.

Proof Sketch. Motivated by Theorem 4.4, we use the identity w gk+1 = gk + ηHk fk+1 +E

1−γ

w where ∥E∥ ≤ M η 2 ∥fk+1 ∥2 . Applying the triangle inequality, the weak learner edge, and Theorem 4.2 yields the result. In the upcoming convergence rate proofs, both the final bound (19) and intermediate expressions using (22) play an important role, see Section D for proofs.

Combining these bounds with Theorems 4.2 and 4.7 yields the recurrence s Cγ2 Cγ2 3 ∥gk+1 ∥ ≤ ρ∥gk ∥ + C 2 M η 2 2 ∥gk ∥ 2 + C 2 M η 2 2 ∥gk ∥2 . µ µ The result follows by solving for the region of strict contraction ∥gk+1 ∥ < ∥gk ∥, where the dependence on η cancels out. See Section D for details.

We now present our main result: establishing the global convergence of gradient regularized Newton’s method with weak learners. Despite the inexact updates inherent to boosting and Restricted Newton Descent, Algorithm 2 retains the O( k12 ) rate, matching first-order momentum boosting (Lu et al., 2020) without the requirement of fitting two trees per iteration. We use the following standard definition from the cubic Newton literature.

Remark 4.11. If η = 1 and γ = 1, the coefficient of the linear ∥gk ∥ term vanishes, allowing for a superlinear rate with exponent 32 , recovering the classical result of Mishchenko (2023). However, when η < 1 or γ < 1, this term is non-zero, and we are only able to prove a linear rate. We conjecture that superlinear rates are generally unattainable in Newton schemes involving weak iterates, suggesting an interesting direction for future research.

Definition 4.8. L has finite sublevel sets if a finite optimum F ∗ ∈ argminF ∈H L(F ) exists, and if there exists a constant Λ > 0 such that L(F ) ≤ L(F0 ) =⇒ ∥F − F ∗ ∥ ≤ Λ. 7

Gradient Regularized Newton Boosting Trees with Global Convergence

1/2 PN g(i) as ∥gk ∥H = N1 i=1 ∥g(i) ∥2RK . Because updating this adaptive ℓ2 term only requires a single vector norm calculation and a scalar addition, and the main computational bottleneck for GBDT algorithms is split finding, the computational overhead of GRN is negligible.

5. Practical Considerations In this section, we discuss when the regularity assumptions of Theorems 3.8, 4.9 and 4.10 are satisfied in practice for boosting, and how the GRN scheme can be implemented into existing tree boosting algorithms with negligible computational overhead.

6. Numerical Experiments 5.1. Regularity of the Boosting Objective

In this section, we empirically validate our theoretical findings regarding the convergence of boosting schemes and the behaviour of weak learner conditions. We implement first-order gradient boosting, Newton boosting, and the Gradient Regularized Newton (GRN) boosting scheme in JAX (Bradbury et al., 2018), following the standard depth-wise greedy tree construction strategy used by XGBoost (Chen & Guestrin, 2016). The code is provided in the supplementary material and at github.com/nikitazozoulenko/ global-newton-boosting.

Our convergence analysis relies on standard convex optimization assumptions, such as Lipschitz-continuous Hessians, smoothness, and strong convexity. Using the same notation as Section PN 2.3, because the boosting empirical risk L(F ) = N1 i=1 l(F (xi ), yi ) is constructed from a prespecified element-wise loss l (e.g., MSE, cross entropy, Charbonnier), one can prove that the regularity of l carries over to L in the boosting space H = L2 (b νX,N ). We formalize this result below. Note, however, that one must be careful when dealing with the previously mentioned Lipschitz constants: the regularity conditions of l are defined in the Euclidean geometry, while the Lipschitz constants used by Theorems 3.8, 4.9 and 4.10 are defined in the boosting space with its own intrinsic geometry and inner products.

The proof can be found in Section C. This result ensures that if the base loss l is well-behaved, the boosting objective is as well. Moreover, because l is chosen prior to training, its Lipschitz constant M0 can be computed analytically. This avoids the need for adaptive backtracking line search algorithms to estimate this constant, as is typically required in finite-dimensional convex optimization (Hanzely et al., 2022; Mishchenko, 2023; Kamzolov et al., 2025).

6.1. Charbonnier loss divergence and convergence p The Charbonnier loss, defined as l(b y , y) = 1 + (y − yb)2 −1, is a classical example of a loss function where Newton’s method can diverge (see Section E). We investigate if this also is true for boosting, using the Wine Quality UCI dataset (Cortez et al., 2009) with depth 4 trees. For GRN we set M = 1, and otherwise use a roughly equivalent static ℓ2 -regularization of 1.0 when explicitly stated. Figure 1 compares the training loss of Newton boosting, first-order gradient boosting, and GRN for different learning rates η. For η = 1, vanilla Newton boosting diverges, whereas GRN decreases the fastest. For a smaller η = 0.1, GRN initially tracks the trajectory of fixed ℓ2 -regularized Newton boosting but eventually outperforms it once the gradient norm decreases sufficiently. Vanilla Newton boosting minimizes the loss most rapidly in this scenario, but is limited to smaller learning rates. Notably, ℓ2 -regularized models will converge to a regularized optimum, whereas GRN provably minimizes the original non-regularized loss.

5.2. Implementing GRN for GBDTs

6.2. Weak learner conditions and tree depth

The GRN scheme is very simple to implement in practice and only differs from vanilla Newton boosting by an extra additive ℓ2 -regularization term based on the gradient norm. Both methods use the exact same split finding, gain calculation, and leaf fitting formulas. The only difference lies in the effective ℓ2 -regularization used. Standard tree boosting implementations (e.g., XGBoost, LightGBM, CatBoost) use a static ℓ2 -regularization λbase . GRN, on the other hand, uses an adaptive regularization term λk calculated via p λk = λbase + M ∥gk ∥H . (24)

To better understand the theoretical constants governing convergence, we train models on a subset of the Higgs dataset (Whiteson, 2014) using BCE loss with ℓ2 -regularization. We compute the cosine angle Θk and weak learner edge γk in Figure 2 at every iteration k, via (6) and (18), by instantiw ating fk+1 , fk+1 , gkw , and gk as vectors in RN . As expected, increasing tree depth results in stronger weak learners, reflected in higher values for Θk and γk . We observe that these metrics are high during the initial iterations of boosting and eventually plateau at positive values. The trajectories of the cosine angle Θk and weak gradient edge γk are remarkably similar, which is somewhat unexpected given that they are

Proposition 5.1. If the element-wise loss l(·, yi ) has an M0 Lipschitz Hessian in RK uniformly across √ all fixed targets yi , then the empirical risk L has an M0 N -Lipschitz Hessian in the boosting space L2 (b νX,N ). Additionally, if l is Ssmooth or µ-strongly convex, then L is also S-smooth or µ-strongly convex, respectively.

Using the notation of Section 2.3, the exact gradient norm in the boosting space is computed from the sample gradients 8

Gradient Regularized Newton Boosting Trees with Global Convergence

100

6 × 10 1

GRN Newton Boosting Newton Boosting Gradient Boosting Newton w. 2-reg Gradient w. 2-reg 0

200

400

600

800

4 × 10 1 Depths | Methods

3 × 10 1

d=6 d=4 d=2

2 × 10 1

GRN Newton Gradient

100

200

300

400

500

100

200

300

400

500

100

200

300

400

500

0.4

1000

Cosine Angle

10 3 10 4

Loss, = 0.1

Train Loss

10 2

0.3 0.2 0.1

10 1 0.4

200

400

600

Tree Boosting Iterations

800

Gradient Edge

Loss, = 1.0

10 1

1000

Figure 1. Charbonnier train loss on the Wine Quality UCI dataset, for different gradient boosting schemes and learning rates η. Vanilla Newton boosting diverges for η = 1.

0.3 0.2 0.1

Tree Boosting Iterations

Figure 2. Binary cross entropy, cosine angle Θk , and weak gradient edge γk computed at each boosting iteration k, for varying tree depths d. The exact values are noisy between iterations, but the rolling window average (highlighted in bold) remains stable.

defined in different geometries. Conceptually, γk (Theorem 4.6) can be viewed as an approximate (Hk + λk I)2 w induced cosine angle between fk+1 and fk+1 , in contrast to w the standard Hk -induced cosine angle Θk . If fk+1 and fk+1 2 were orthogonal under the (Hk + λk I) -induced norm, γk would constitute a true cosine angle; however, we cannot theoretically guarantee this at present.

der weak updates, and see if the dependence on Θ2 and γ 12 can be improved. Finally, investigating the possibility of superlinear rates with weak learners and establishing generalization bounds for Newton boosting remain open problems. Future work will also explore other applications of Restricted Newton Descent beyond the gradient boosting setting.

A similar relationship to tree depth holds for dataset size; larger datasets generally imply harder optimization problems, resulting in smaller cosine angles for a fixed tree depth. Furthermore, as optimization progresses, fitting the diminishing residuals becomes increasingly difficult for the weak learners, naturally leading to lower cosine angles.

Acknowledgements 7. Conclusion and Future Work

NZ has been supported by the Roth Scholarship at Imperial College London. DF was supported by the Göran Gustafsson Foundation for Research in Natural Sciences and Medicine via Alexander Berglund’s 2024 Göran Gustafsson Prize. The work of TC was supported in part by UK Research and Innovation (UKRI) through the Engineering and Physical Sciences Research Council (EPSRC) via Programme Grants [Grant No. UKRI1010: High order mathematical and computational infrastructure for streamed data that enhance contemporary generative and large language models]. We acknowledge computational resources and support provided by the Imperial College Research Computing Service (DOI: 10.14469/hpc/2232). For the purpose of open access, the authors have applied a Creative Commons Attribution (CC BY) licence to any Author Accepted Manuscript version arising.

We introduced Restricted Newton Descent to analyze the global convergence of vanilla Newton boosting and a novel gradient regularized Newton boosting scheme, based on the cosine angle Θ and weak gradient edge γ. For vanilla Newton boosting, we proved a linear convergence rate for Hessian-dominated losses. For the gradient regularized scheme, we established a global O(1/k 2 ) rate for general convex losses with Lipschitz Hessians. Our results suggest several promising directions for future research. First, given that finite-dimensional cubic and gradient regularized Newton can be accelerated to O(1/k 3 ), investigating whether such acceleration can be realized in the boosting setting is a natural next step. Second, it would be interesting to study the Restriction operation for other optimization schemes to determine which convergence properties are retained un9

Gradient Regularized Newton Boosting Trees with Global Convergence

References

and a rejoinder by the authors). The Annals of Statistics, 28(2):337 – 407, 2000.

Bickel, P. J., Ritov, Y., and Zakai, A. Some theory for generalized boosting algorithms. Journal of Machine Learning Research, 7(25):705–732, 2006.

Friedman, J. H. Greedy function approximation: A gradient boosting machine. The Annals of Statistics, 29(5):1189– 1232, 2001.

Bradbury, J., Frostig, R., Hawkins, P., Johnson, M. J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., and Zhang, Q. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/jax-ml/jax.

Grinsztajn, L., Oyallon, E., and Varoquaux, G. Why do treebased models still outperform deep learning on typical tabular data? In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088.

Chen, T. and Guestrin, C. Xgboost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16, pp. 785–794, New York, NY, USA, 2016. Association for Computing Machinery. ISBN 9781450342322.

Grubb, A. and Bagnell, J. A. Generalized boosting algorithms for convex optimization. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML’11, pp. 1209–1216, Madison, WI, USA, 2011. Omnipress.

Cortes, C., Mohri, M., and Storcheus, D. Regularized gradient boosting. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

Hanzely, S. Sketch-and-project meets newton method: Global o(1/k 2 ) convergence with low-rank updates. In Li, Y., Mandt, S., Agrawal, S., and Khan, E. (eds.), Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, volume 258 of Proceedings of Machine Learning Research, pp. 3205–3213. PMLR, 03–05 May 2025.

Cortez, P., Cerdeira, A., Almeida, F., Matos, T., and Reis, J. Wine Quality. UCI Machine Learning Repository, 2009. DOI: https://doi.org/10.24432/C56S3T. Doikov, N. Minimizing quasi-self-concordant functions by gradient regularization of newton method. Mathematical Programming, Aug 2025. ISSN 1436-4646. doi: 10. 1007/s10107-025-02270-9.

Hanzely, S., Kamzolov, D., Pasechnyuk, D., Gasnikov, A., Richtarik, P., and Takac, M. A damped newton method achieves global O k12 and local quadratic convergence rate. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems, volume 35, pp. 25320–25334. Curran Associates, Inc., 2022.

Doikov, N. and Nesterov, Y. Gradient regularization of newton method with bregman distances. Mathematical Programming, 204(1):1–25, Mar 2024. ISSN 1436-4646. doi: 10.1007/s10107-023-01943-7.

Jarre, F. and Toint, P. L. Simple examples for the failure of newton’s method with line search for strictly convex minimization. Mathematical Programming, 158 (1):23–34, Jul 2016. ISSN 1436-4646. doi: 10.1007/ s10107-015-0913-2.

Doikov, N., Mishchenko, K., and Nesterov, Y. Superuniversal regularized newton method. SIAM Journal on Optimization, 34(1):27–56, 2024. doi: 10.1137/ 22M1519444.

Kamzolov, D., Agafonov, A., Pasechnyuk, D., Gasnikov, A., and Takáč, M. OPTAMI: Global superlinear convergence of high-order methods. In The Thirteenth International Conference on Learning Representations, 2025.

Erickson, N., Purucker, L., Tschalzev, A., Holzmüller, D., Desai, P. M., Salinas, D., and Hutter, F. Tabarena: A living benchmark for machine learning on tabular data. In The Thirty-ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2025.

Ke, G., Meng, Q., Finley, T., Wang, T., Chen, W., Ma, W., Ye, Q., and Liu, T.-Y. Lightgbm: A highly efficient gradient boosting decision tree. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.

Freund, R. M., Grigas, P., and Mazumder, R. A new perspective on boosting in linear regression via subgradient optimization and relatives. The Annals of Statistics, 45 (6):2328–2364, 2017.

Lu, H. and Mazumder, R. Randomized gradient boosting machine. SIAM Journal on Optimization, 30(4):2780– 2808, 2020. doi: 10.1137/18M1223277.

Friedman, J., Hastie, T., and Tibshirani, R. Additive logistic regression: a statistical view of boosting (With discussion 10

Gradient Regularized Newton Boosting Trees with Global Convergence

Lu, H., Karimireddy, S. P., Ponomareva, N., and Mirrokni, V. Accelerating gradient boosting machines. In Chiappa, S. and Calandra, R. (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 516–526. PMLR, 26–28 Aug 2020.

Qin, Z., Yan, L., Zhuang, H., Tay, Y., Pasumarthi, R. K., Wang, X., Bendersky, M., and Najork, M. Are neural rankers still outperformed by gradient boosted decision trees? In International Conference on Learning Representations, 2021. Sigrist, F. Gradient and newton boosting for classification and regression. Expert Systems with Applications, 167: 114080, 2021. ISSN 0957-4174.

Mason, L., Baxter, J., Bartlett, P., and Frean, M. Boosting algorithms as gradient descent. In Solla, S., Leen, T., and Müller, K. (eds.), Advances in Neural Information Processing Systems, volume 12. MIT Press, 1999.

Suggala, A., Liu, B., and Ravikumar, P. Generalized boosting. In Advances in Neural Information Processing Systems, volume 33, pp. 8787–8797. Curran Associates, Inc., 2020.

McElfresh, D., Khandagale, S., Valverde, J., C., V. P., Ramakrishnan, G., Goldblum, M., and White, C. When do neural nets outperform boosted trees on tabular data? In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA, 2023. Curran Associates Inc.

Sun, P., Zhang, T., and Zhou, J. A convergence rate analysis for logitboost, mart and their variant. In Xing, E. P. and Jebara, T. (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pp. 1251–1259, Bejing, China, 22–24 Jun 2014. PMLR.

Mishchenko, K. Regularized newton method with global ≀(1/k2 ) convergence. SIAM Journal on Optimization, 33(3):1440–1462, 2023. doi: 10.1137/22M1488752.

Telgarsky, M. A primal-dual convergence analysis of boosting. Journal of Machine Learning Research, 13(20): 561–606, 2012.

Nesterov, Y. Accelerating the cubic regularization of newton’s method on convex problems. Mathematical Programming, 112(1):159–181, Mar 2008. ISSN 1436-4646. doi: 10.1007/s10107-006-0089-x.

Whiteson, D. HIGGS. UCI Machine Learning Repository, 2014. DOI: https://doi.org/10.24432/C5V312.

Nesterov, Y. Lectures on Convex Optimization. Springer Publishing Company, Incorporated, 2nd edition, 2018. ISBN 3319915770.

Zozoulenko, N., Cass, T., and Gonon, L. Random feature representation boosting. In Singh, A., Fazel, M., Hsu, D., Lacoste-Julien, S., Berkenkamp, F., Maharaj, T., Wagstaff, K., and Zhu, J. (eds.), Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pp. 80900–80932. PMLR, 13–19 Jul 2025.

Nesterov, Y. and Polyak, B. T. Cubic regularization of newton method and its global performance. Mathematical Programming, 108(1):177–205, Aug 2006. ISSN 14364646. doi: 10.1007/s10107-006-0706-8. Nitanda, A. and Suzuki, T. Functional gradient boosting based on residual network perception. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 3819–3828. PMLR, 10–15 Jul 2018. Parnell, T., Anghel, A., Ł azuka, M. g., Ioannou, N., Kurella, S., Agarwal, P., Papandreou, N., and Pozidis, H. Snapboost: A heterogeneous boosting machine. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 11166–11177. Curran Associates, Inc., 2020. Prokhorenkova, L., Gusev, G., Vorobev, A., Dorogush, A. V., and Gulin, A. Catboost: unbiased boosting with categorical features. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, pp. 6639–6649, Red Hook, NY, USA, 2018. Curran Associates Inc. 11

Gradient Regularized Newton Boosting Trees with Global Convergence

A. Discussions on Losses and Gradient Boosting Trees In this appendix, we provide explicit calculations for the gradients and Hessians of common loss functions used in boosting. We also provide the full derivation of the optimal weight update for decision trees within the Newton boosting framework, recovering the standard XGBoost formula. A.1. Common loss functions used in boosting We denote the prediction for the i-th data point as ui = F (xi ). The gradient and Hessian with respect to the prediction are denoted by g(i) ∈ RK and h(i) ∈ RK×K , respectively. y − y)2 , the gradient and Hessian are given by: Mean Squared Error (MSE): For the quadratic loss l(b y , y) = 21 (b g(i) = ybi − yi , h(i) = 1. Binary Cross Entropy (BCE): For binary classification, let yi ∈ {0, 1} be the label and ui ∈ R be the logit. The loss is defined as l(ui , yi ) = −[yi log σ(ui ) + (1 − yi ) log(1 − σ(ui ))], where σ(z) = (1 + e−z )−1 is the sigmoid function. Using the chain rule, one finds that the derivatives are g(i) = σ(ui ) − yi , h(i) = σ(ui )(1 − σ(ui )). Categorical Cross Entropy (CCE): In the multi-class setting (K > 2), let yi ∈ {0, 1}K be the one-hot encoded label and PK ui ∈ RK be the vector of logits. The loss is l(ui , yi ) = − k=1 (yi )k log(pi )k , where pi = softmax(ui ) is the vector of class probabilities. The gradient and Hessian are g(i) = pi − yi , h(i) = diag(pi ) − pi p⊤ i , where diag(pi ) is the diagonal matrix with elements of pi on the diagonal, and pi p⊤ i denotes the vector outer product. A.2. Newton Tree Boosting Derivation P Let f (x) be a decision tree defined by f (x) = j wj Ij (x), where {Ij }L j=1 is a disjoint partition of the feature space (i.e., K the leaves of the tree) and wj ∈ R are the leaf values. The second-order approximation of the loss, Q(f ), is given by N 1 X 1 f (xi ), g(i) + h(i) f (xi ) Q(f ) = N i=1 2 RK =

N N 1 X 1 X f (xi ), g(i) RK + f (xi ), h(i) f (xi ) RK . N i=1 2N i=1

We analyze the linear and quadratic terms separately. Substituting the definition of the tree f (x), we find that N X

f (xi ), g(i) RK =

i=1

* N X X i=1

wj Ij (xi ), g(i)

* =

wj ,

RK N X

+ Ij (xi )g(i)

i=1

* =

X j

wj ,

+ X i∈Ij

g(i)

. RK

Gradient Regularized Newton Boosting Trees with Global Convergence

For the quadratic term, we use the property that the regions are disjoint, implying Ij (x)Ik (x) = δjk Ij (x), where δjk is the Kronecker delta. * + N N X X X X f (xi ), h(i) f (xi ) RK = wj Ij (xi ), h(i) wk Ik (xi ) i=1

i=1

Ij (xi ) wj , h(i) wj RK wj , h(i) wj RK

i∈Ij



* =

Ij (xi )Ik (xi ) wj , h(i) wk RK

XX j

N X X i=1

N XX X

 X

wj , 

h(i)  wj

i∈Ij

. RK

The total objective decomposes into a sum of independent objectives for each leaf j. Differentiating with respect to a specific weight wj , we obtain the local quadratic  +  * + * X X 1 q(wj ) = wj , g(i) + wj ,  h(i)  wj . 2 i∈Ij

i∈Ij

Taking the gradient with respect to wj yields 

 ∇q(wj ) =

g(i) + 

i∈Ij

h(i)  wj .

i∈Ij

Setting the gradient to zero gives the optimal weight update −1

 wj∗ = − 

h(i) 

Substituting wj∗ back into the objective (and defining Gj = score used in Newton boosting and XGBoost: X j

g(i) .

i∈Ij

Q(f ∗ ) =

q(wj∗ ) = −

i∈Ij g(i) and Hj =

i∈Ij h(i) ), we recover the standard

1X Hj−1 Gj , Gj RK . 2 j

Remark A.1. The ℓ2 -regularization used in standard implementations like XGBoost differs slightly from the one suggested by our theory. XGBoost adds a fixed scalar λ to the aggregated leaf Hessian, yielding the update wj∗ = −(Hj + λ)−1 Gj . By contrast, our framework regularizes the weak learner in the Hilbert space L2 (b νN ). In this space, the regularization modifies the Hessian operator pointwise, which is equivalent to replacing each h(i) with h(i) + λ. Summing these over the partition Ij results in the update wj∗ = −(Hj + |Ij |λ)−1 Gj . Thus, the theoretically consistent regularization scales proportionally with the number of samples routed to the leaf. This is the formulation we use in our JAX implementation for the numerical experiments.

Gradient Regularized Newton Boosting Trees with Global Convergence

B. Some Classical Optimization Results We collect several standard smoothness and Lipschitz-Hessian definitions and results from optimization theory (Nesterov & Polyak, 2006; Nesterov, 2018), and present them in the Hilbert space setting. Definition B.1 (S-smooth loss). Let H be a real Hilbert space. A Fréchet differentiable function L : H → R is called S-smooth if its gradient is Lipschitz continuous with constant S, i.e., ∥∇L(f ) − ∇L(g)∥ ≤ S∥f − g∥

∀f, g ∈ H.

Equivalently, if L is twice Fréchet differentiable, then its Hessian satisfies ∥∇2 L(h)∥op ≤ S

∀h ∈ H,

or equivalently ∇2 L(h) ⪯ SI as an operator inequality. Definition B.2 (µ-strongly convex loss). A function L : H → R is µ-strongly convex for some µ > 0 if one of the following equivalent conditions holds: 1. (Quadratic lower bound): The function h 7→ L(h) − µ2 ∥h∥2 is convex. 2. (First-order condition): For all f, g ∈ H, L(f ) ≥ L(g) + ⟨∇L(g), f − g⟩ +

µ ∥f − g∥2 . 2

3. (Gradient monotonicity): For all f, g ∈ H, ⟨∇L(f ) − ∇L(g), f − g⟩ ≥ µ∥f − g∥2 . 4. (Second-order condition): If L is twice Fréchet differentiable, then ∇2 L(h) ⪰ µI

∀h ∈ H.

Definition B.3. The Fréchet Hessian ∇2 L : H → L(H) is 2M -Lipschitz continuous if there exists a constant M > 0 such that ∥∇2 L(f ) − ∇2 L(g)∥ ≤ 2M ∥f − g∥

∀f, g ∈ H.

Lemma B.4. If the loss L is S-smooth, then L(Fk + f ) ≤ L(Fk ) + ⟨gk , f ⟩ +

S ∥f ∥2 . 2

(25)

Proof. Using Taylor’s theorem with integral remainder, we express the expansion of the loss as Z 1 L(Fk + f ) = L(Fk ) + ⟨gk , f ⟩ +

(1 − t)⟨f, ∇2 L(Fk + tf )f ⟩ dt.

(26)

The definition of S-smoothness implies that the Hessian is bounded in operator norm by S, i.e., ∇2 L(·) ⪯ SI. Consequently, R1 the quadratic form is bounded by ⟨f, ∇2 L(·)f ⟩ ≤ S∥f ∥2 . Substituting this into the integral yields 0 (1 − t)S∥f ∥2 dt = S 2 2 ∥f ∥ , completing the proof. Lemma B.5. If ∇2 L is 2M -Lipschitz, then for all f, g ∈ H 3 1. L(f ) ≤ L(g) + ⟨∇L(g), f − g⟩ + 12 ⟨∇2 L(g)(f − g), f − g⟩ + M 3 ∥f − g∥

2. ∥∇L(f ) − ∇L(g) − ∇2 L(g)(f − g)∥ ≤ M ∥g − f ∥2 . 14

Gradient Regularized Newton Boosting Trees with Global Convergence

Proof. Let h = f − g. We begin with the Fundamental Theorem of Calculus and expand the terms: Z 1 ⟨∇L(g + th) − ∇L(g), h⟩ dt Z 1 Z t ∇2 L(g + sh)[h] ds, h dt =

L(f ) − L(g) − ⟨∇L(g), h⟩ =

Z 1Z t = 0

⟨h, ∇2 L(g + sh)[h]⟩ ds dt

Z 1Z t

⟨h, ∇ L(g)[h]⟩ ds dt +

= 0

1 = ⟨h, ∇2 L(g)[h]⟩ + 2

Z 1Z t

1 ≤ ⟨h, ∇2 L(g)[h]⟩ + 2

Z 1Z t

1 ⟨h, ∇2 L(g)[h]⟩ + 2

Z 1Z t

1 ⟨h, ∇2 L(g)[h]⟩ + 2

Z 1Z t

≤ ≤

⟨h, (∇2 L(g + sh) − ∇2 L(g))[h]⟩ ds dt

∥h∥ · ∥(∇2 L(g + sh) − ∇2 L(g))[h]∥ ds dt

∥∇2 L(g + sh) − ∇2 L(g)∥op ∥h∥2 ds dt

(2M s∥h∥)∥h∥2 ds dt

1 ⟨h, ∇2 L(g)[h]⟩ + 2M ∥h∥3 2 1 M = ⟨h, ∇2 L(g)[h]⟩ + ∥h∥3 . 2 3

Z 1 2 t dt 0 2

Rearranging the terms yields the desired first inequality. For inequality 2, we express the gradient difference as an integral of the Hessian. Z 1 Z 1 2 2 ∥∇L(f ) − ∇L(g) − ∇ L(g)[h]∥ = ∇ L(g + th)[h] dt − ∇2 L(g)[h] dt 0

Z 1 = 0 Z 1

≤

(∇2 L(g + th) − ∇2 L(g))[h] dt

∥(∇2 L(g + th) − ∇2 L(g))[h]∥ dt

Z 1 ≤

∥∇2 L(g + th) − ∇2 L(g)∥op ∥h∥ dt

Z 1 ≤

(2M t∥h∥)∥h∥ dt 0 2

Z 1

= 2M ∥h∥

t dt 0

= M ∥h∥2 . This completes the proof.

Gradient Regularized Newton Boosting Trees with Global Convergence

C. Proof of Regularity Conditions in the Boosting Space Recall from Section 2.3 that we identify the empirical boosting space H = L2 (b νX,N ) with RN K , equipped with the inner 1/2 PN PN 1 . product ⟨f, h⟩ = N i=1 ⟨f (xi ), h(xi )⟩RK . The induced norm is therefore ∥f ∥ = N1 i=1 ∥f (xi )∥2RK Proof of Theorem 5.1. First, we prove the claim regarding the Lipschitz continuity of the Hessian. Suppose the base loss l(u, y) has a M0 -Lipschitz Hessian with respect to the prediction u ∈ RK , meaning ∥∇211 l(u, y) − ∇211 l(v, y)∥op ≤ PN M0 ∥u − v∥RK . In the gradient boosting space, we minimize the empirical risk L(F ) = N1 i=1 l(F (xi ), yi ). Because the Hessian operator ∇2 L(F ) acts pointwise (i.e., it is block-diagonal over the N samples), its operator norm on H is exactly the maximum of the operator norms of the individual K × K blocks. Thus, for any F, G ∈ H, we can bound the difference in Hessians as follows: ∥∇2 L(F ) − ∇2 L(G)∥op,H = max ∥∇211 l(F (xi ), yi ) − ∇211 l(G(xi ), yi )∥op,RK 1≤i≤N

≤ max M0 ∥F (xi ) − G(xi )∥RK 1≤i≤N

N X

≤ M0

!1/2 ∥F (xi ) − G(xi )∥2RK

i=1

√ = M0 N

1 X ∥F (xi ) − G(xi )∥2RK N i=1

!1/2

√ = M0 N ∥F − G∥. √ This proves that L has an M0 N -Lipschitz Hessian in the space H.

Next, we prove that smoothness and strong convexityP are preserved with the same constants. The Hessian quadratic form in N the boosting space is given by ⟨f, ∇2 L(F )[f ]⟩ = N1 i=1 ⟨f (xi ), ∇211 l(F (xi ), yi )f (xi )⟩RK . If the base loss l is µ-strongly convex and S-smooth, its Euclidean quadratic form is bounded pointwise: µ∥f (xi )∥2RK ≤ ⟨f (xi ), ∇211 l(F (xi ), yi )f (xi )⟩RK ≤ S∥f (xi )∥2RK . Summing these bounds over i = 1, . . . , N and dividing by N directly yields µ∥f ∥2 ≤ ⟨f, ∇2 L(F )[f ]⟩ ≤ S∥f ∥2 .

Gradient Regularized Newton Boosting Trees with Global Convergence

D. Convergence Rate Proofs For ease of exposition, we restate the statement and result of the relevant lemmas and theorems from the main part of the paper. Lemma D.1. If the iterates of Algorithm 2 have weak gradient edge γ, then the gradient growth is bounded by p w ∥gk+1 ∥ = 1 − η(1 − 1 − γ 2 ) ∥gk ∥ + (η + η 2 )λk ∥fk+1 ∥ p ≤ 1 + η 2 + η 1 − γ 2 ∥gk ∥.

(27) (28)

Proof. Using Equation (17), and Theorems 4.1 and 4.4, we can write w gk+1 = gk + ηHk fk+1 +E

(29)

w = gk + η(−gkw − λk fk+1 )+E w w = (1 − η)gk + η(gk − gk ) − ηλk fk+1 +E

(30) (31)

w where ∥E∥ ≤ M η 2 ∥fk+1 ∥2 . Hence using the bounds in Theorem 4.2 we obtain that w ∥gk+1 ∥ = ∥(1 − η)gk + η(gk − gkw ) − ηλk fk+1 + E∥

(32)

w w ≤ (1 − η)∥gk ∥ + η∥gk − gkw ∥ + ηλk ∥fk+1 ∥ + M η 2 ∥fk+1 ∥2

w w 1 − γ 2 ∥gk ∥ + ηλk ∥fk+1 ∥ + η 2 λk ∥fk+1 ∥

≤ (1 − η)∥gk ∥ + η p w ∥ = 1 − η(1 − 1 − γ 2 ) ∥gk ∥ + (η + η 2 )λk ∥fk+1 p ≤ 1 + η 2 + η 1 − γ 2 ∥gk ∥.

(33) (34) (35) (36)

The following global convergence proof of the gradient regularized Newton scheme generalizes the proof of Mishchenko (2023) to the setting of Restricted Newton Descent with a constant learning rate η ∈ (0, 1] and weak learners. The primary w challenge lies in handling the additional error terms introduced by the learning rate and the inexact weak iterates fk+1 , which we handled in our previous Lemmas in this paper. Additonally, the original proof which uses a fixed subsequence condition and fraction, we must make this dependent on both the learning rate η and weak gradient edge γ. Theorem D.2. Assume L is convex with 2M -Lipschitz Hessian, finite sublevel sets with diameter Λ, and weak gradient edge p γ. Let the regularization be chosen as λk = C M ∥gk ∥ for some C ≥ 1. For any learning rate η ∈ (0, 1], the gradient regularized Newton scheme has the global convergence rate    p p kη  ∗ 2 2 L(Fk ) − L(F ) ≤ max Λ∥g0 ∥ exp − (1 − 1 − γ )(3 − 1 − γ − 2η) ,  8 | {z } Linear Regime

 1024C 2 M Λ3 (1 + η)4   p . 1 2 2 . 2 2 6 2  (1 − η ) η (1 − 1 − γ ) (2 + k) 3 | {z } O ( k12 ) Regime (37)

Proof. By Theorem 4.5 we have that L(Fk ) ≤ L(Fk−1 ) ≤ ... ≤ L(F0 ), implying that the iterates Fk remain within the sublevel set defined by F0 . Consequently, ∥Fk − F ∗ ∥ ≤ Λ for all T . By convexity we have the bound L(Fk ) − L(F ∗ ) ≤ ⟨gk , Fk − F ∗ ⟩ ≤ ∥gk ∥Λ.

(38)

Let I∞ := {t ∈ N : ∥gt+1 ∥ ≥ (1 − ηa)∥gt ∥} be the set of indices where the gradient does not contract sufficiently, for some 0 < a < 1 to be specified later. Consider first any k ∈ I∞ . It follows from Theorem D.1 that p w (1 − ηa)∥gk ∥ ≤ ∥gk+1 ∥ ≤ 1 − η(1 − 1 − γ 2 ) ∥gk ∥ + (η + η 2 )λk ∥fk+1 ∥ (39) 17



Gradient Regularized Newton Boosting Trees with Global Convergence

Rearranging the terms we obtain that w λk ∥fk+1 ∥≥

1−

1 − γ2 − a ∥gk ∥ 1+η

(40)

For the next argument we require the bound (40) to be positive, hence we choose p 1 − 1 − γ2 a := . 2

(41)

By (40) and Theorem 4.5 we have

1 2 w L(Fk ) − L(Fk+1 ) ≥ 1 − η ηλk ∥fk+1 ∥2 3 ∥gk ∥2 1 η ≥ 1 − η 2 a2 3 (1 + η)2 λk 3 ∥gk ∥ 2 1 η √ = 1 − η 2 a2 3 (1 + η)2 C M 32 a2 η 1 ∗ √ L(F ) − L(F ) ≥ 1 − η2 k 3 C M Λ3 (1 + η)2 3 2 = τ L(Fk ) − L(F ∗ )

(42) (43) (44) (45) (46)

2 η 1 where τ = 1 − 13 η 2 C √aM Λ3 (1+η) 2 . If this recursion held for all k ≥ 1, the O( k 2 ) rate would follow by Theorem D.3. Instead, we consider the subsequence technique as in (Mishchenko, 2023). We start by enumerating I∞ = {t0 , t1 , t2 , ...}. We have that αk+1 := L(Ftk+1 ) − L(F ∗ )

(47)

∗

= L(Ftk ) − L(F ) + L(Ftk +1 ) − L(Ftk ) 23 ∗ ∗ ≤ L(Ftk ) − L(F ) + τ L(Ftk ) − L(F )

(48) (49)

= αk − τ αk2

(50)

4 Theorem D.3 implies that αk ≤ τ 2 (2+k) 2 . Consider now any general k ≥ 1. Define Ik = {t ∈ I∞ : t ≤ k}. We consider two cases based on the cardinality of the index set Ik , that is, |Ik | ≥ pk and |Ik | < pk, for some fraction 0 < p < 1 to be specified later in the proof.

Case |Ik | ≥ pk: Using the fact that both L(Fk ) and αk are decreasing sequences, we obtain that L(Fk ) − L(F ∗ ) ≤ L(F|Ik | ) − L(F ∗ ) = α|Ik | ≤ αpk ≤

4 τ 2 p2 (2 + k)2

4C 2 M Λ3

(1 + η)4

η 2 a4 p2 (2 + k)2 (1 − 13 η 2 )2

(51)

Consequently in this case we have a global O( k12 ) rate. Case |Ik | < pk: For indices t ∈ / Ik , we have thecontraction ∥gt+1 ∥ ≤ (1 − ηa)∥gt ∥. For t ∈ Ik the gradient may grow, p but it is bounded by Theorem D.1 via ∥gt+1 ∥ ≤ 1 + η 2 + η 1 − γ 2 ∥gt ∥. Combining both we obtain that |Ik | p ∥gk ∥ ≤ 1 + η 2 + η 1 − γ 2 (1 − ηa)k−|Ik | ∥g0 ∥ pk p ≤ 1 + η2 + η 1 − γ 2 (1 − ηa)(1−p)k ∥g0 ∥. Using the bound 1 + x ≤ ex and taking logarithms, we see that this scheme produces a contraction if p p η 2 + η 1 − γ 2 − (1 − p)ηa < 0. 18

(52) (53)

(54)

Gradient Regularized Newton Boosting Trees with Global Convergence

Rearranging the above, we find that we require p<

a p . η + a + 1 − γ2

(55)

p p p Substituting our choice a = (1 − 1 − γ 2 )/2, the denominator simplifies to η + (1 + 1 − γ 2 )/2. Since 1 − γ 2 ≤ 1, this denominator is strictly less than η + 1. Therefore, for any η ∈ (0, 1], the choice p = a2 is sufficient. In general, one can show that a and p need to satisfy the inequality p p η + 1 − γ2 p (56) < a < 1 − 1 − γ2. 1−p p for the proof in both cases above to be valid. With the choice 4p = 2a = 1 − 1 − γ 2 , one finds through elementary algebra and the bound 1 + x ≤ ex that the gradient growth can be bounded by p p kη ∥gk ∥ ≤ exp − (1 − 1 − γ 2 )(3 − 1 − γ 2 − 2η) ∥g0 ∥, (57) 8 yielding a linear rate of convergence. Final bound: The final convergence rate is obtained by taking the maximum bound of the two cases above. Note that p 2 1 − 1 − γ 2 = γ2 + o(γ 2 ). Hence the global convergence rate in the first case is O while for the second case this is

C 2 M Λ3 η 2 k 2 γ 12

(58)

2 γ + 2 − 2η /8 . O exp −kηγ 2 2

(59)

This concludes the proof. The following lemma is a standard result in the convex optimization literature, see e.g. (Nesterov & Polyak, 2006). We include the general proof here for completeness 3

Lemma D.3. If αk is a decreasing sequence satisfying 0 ≤ αk+1 ≤ αk − cαk2 for some c > 0, then for all k ≥ 0: αk ≤

1 √1 + c k α0 2

2 ≤

4 . c2 (k + 2)2

(60)

3/2

Proof. Using the hypothesis αk − αk+1 ≥ cαk , consider the increment √

√ αk − αk+1 √ αk αk+1 αk − αk+1 =√ √ √ αk αk+1 ( αk + αk+1 )

1 1 −√ = √ αk+1 αk

(61) (62)

3/2

≥√ Since the sequence is decreasing (αk+1 ≤ αk ), we have

√

cαk . √ √ αk αk+1 ( αk + αk+1 )

αk+1 ≤

√

(63)

αk , hence

3/2

cα 1 1 c −√ ≥p 2 √ k √ = . √ αk+1 αk 2 αk ( αk + αk ) 19

(64)

Gradient Regularized Newton Boosting Trees with Global Convergence

Summing from i = 0 to k − 1 yields a telescoping sum, from which we obtain that 1 1 ck ≥√ + . √ αk α0 2

(65)

Inverting and squaring both sides yields the inequality αk ≤

1 √1 + c k α0 2

2 .

3 √ The final bound follows from the fact that c αk ≤ 1, which follows directly from the hypothesis 0 ≤ αk+1 ≤ αk −cαk2 .

(66)

Gradient Regularized Newton Boosting Trees with Global Convergence

M ∥gk ∥ for some C ≥ 1. If L is µ-strongly convex with 2M -Lipschitz 2 √ 1− 1−γ 2 µ2 √ 2 , then for all k ≥ k0 Hessian and weak gradient edge γ, and if there exists a k0 ≥ 0 such that ∥gk0 ∥ ≤ 4C 2 M Lemma D.4. Let the regularization be λk = C

1−γ

we have that ∥gk+1 ∥ ≤ where ρ = 1 − η(1 −

3+ρ ∥gk ∥ 4

(67)

1 − γ 2 ). Hence the iterates of Algorithm 2 converge linearly locally.

Proof. We have the standard bound ∥gkw ∥ ≤ ∥gk ∥ + ∥gkw − gk ∥ p ≤ 1 + 1 − γ 2 ∥gk ∥ := Cγ ∥gk ∥,

(68) (69) (70)

and since we assumed µ-strong convexity, we have that w ∥fk+1 ∥ = ∥(Hk + λI)−1 g w ∥ 1 ≤ ∥g w ∥ µ Cγ w ∥g ∥. ≤ µ

(71) (72) (73)

We combine the above with Theorems D.1 and 4.2, specifically Equation (33), to obtain that w w ∥gk+1 ∥ ≤ (1 − η)∥gk ∥ + η∥gk − gkw ∥ + ηλk ∥fk+1 ∥ + M η 2 ∥fk+1 ∥2

(74)

w w ≤ (1 − 2η + ηCγ )∥gk ∥ + ηλk ∥fk+1 ∥ + M η 2 ∥fk+1 ∥2

(75)

s ≤ (1 − 2η + ηCγ )∥gk ∥ +

C 2 M η2

Cγ2 Cγ2 3 2 + C 2 M η2 ∥g ∥ ∥gk ∥2 . k µ2 µ2

(76)

Write ρ = (1 − 2η + ηCγ ) and K = C 2 M η 2 µ2γ . We seek the condition for a strict decrease ∥gk+1 ∥ < ∥gk ∥. Substituting the above and dividing by ∥gk ∥ we obtain that p K∥gk ∥ + K∥gk ∥ < 1 − ρ. (77) p p Let ∆ = 1 − ρ = η(1 − 1 − γ 2 ). Since η ≤ 1, we observe that ∆ ≤ 1. Let y = K∥gk ∥. The condition becomes ∆(2+∆) ∆ ∆2 2 y + y 2 < ∆. A sufficient condition for this to hold is y ≤ ∆ . Since 2 , because this implies y + y ≤ 2 + 4 = 4 ∆ 3 ∆ ≤ 1, we have (2 + ∆) ≤ 3, and thus y + y 2 ≤ 4 ∆ < ∆. Expanding the condition y ≤ 2 yields s p M η 2 Cγ2 η(1 − 1 − γ 2 ) ∥gk ∥ ≤ . (78) µ2 2 p Canceling η and rearranging for ∥gk ∥, we obtain p p p µ 1 − 1 − γ2 µ 1 − 1 − γ2 √ √ p ∥gk ∥ ≤ = . (79) Cγ 2 M 2 M 1 + 1 − γ2 Squaring both sides gives the bound in the hypothesis. Under this condition, the sum of the higher order terms is bounded by 34 ∆∥gk ∥ = 34 (1 − ρ)∥gk ∥. Plugging this back into the gradient bound we obtain that 3 3+ρ ∥gk+1 ∥ ≤ ρ∥gk ∥ + (1 − ρ)∥gk ∥ = ∥gk ∥. 4 4 Since ρ < 1, the factor is strictly less than 1, proving linear convergence. 21

(80)

Gradient Regularized Newton Boosting Trees with Global Convergence

E. Divergence of Vanilla Newton on Smooth Convex Losses This appendix records explicit smooth convex objectives for which the classical (unregularized) Newton step may fail to converge globally, even though the loss satisfies the Lipschitz-Hessian assumption used throughout Section 4 and Section D. These examples show that a fixed damping (constant learning rate) does not, by itself, globalize Newton’s method, and motivate the adaptive gradient regularization used in Algorithm 2. E.1. Newton, damped Newton, and gradient regularized Newton Definition E.1 (Newton-type updates in Rd ). Let L : Rd → R be twice continuously differentiable and assume ∇2 L(x) ≻ 0 at the current iterate. • The (classical) Newton update is N (x) := x − (∇2 L(x))−1 ∇L(x). • Given a fixed learning rate η > 0, the damped Newton update is Nη (x) := x − η(∇2 L(x))−1 ∇L(x). Assume moreover that ∇2 L is 2M -Lipschitz in operator norm: ∥∇2 L(u) − ∇2 L(v)∥op ≤ 2M ∥u − v∥

∀u, v ∈ Rd .

Then the (exact) gradient regularized Newton (GRN) update is −1 GRNM,η (x) := x − η ∇2 L(x) + λ(x)I ∇L(x), E.2. A canonical 1D counterexample: L(x) =

√

λ(x) :=

M ∥∇L(x)∥.

1 + x2

√ Proposition E.2 (A smooth convex loss with divergent Newton (1D)). Let L : R → R be given by L(x) := 1 + x2 . Then L is convex and smooth, and L′′ is globally Lipschitz. The classical Newton iteration xk+1 = N (xk ) satisfies the exact recursion xk+1 = −x3k . In particular, |xk+1 | = |xk |3 , yielding cubic local convergence for |x0 | < 1 and divergence for |x0 | > 1. Proof. We compute L′ (x) = √

x , 1 + x2

L′′ (x) =

1 , (1 + x2 )3/2

L(3) (x) = −

3x . (1 + x2 )5/2

In particular L′′ (x) > 0 for all x, hence L is convex. Since L(3) is bounded, L′′ is globally Lipschitz. Moreover, x L′ (x) =√ (1 + x2 )3/2 = x(1 + x2 ). 2 L′′ (x) 1+x Thus the Newton update is xk+1 = xk −

L′ (xk ) = xk − xk (1 + x2k ) = −x3k . L′′ (xk )

Finally, |xk+1 | = |xk |3 implies xk → 0 if |x0 | < 1 and |xk | → ∞ if |x0 | > 1. Proposition√E.3 (Fixed damping does not globalize Newton). Fix any learning rate η > 0 and consider xk+1 = Nη (xk ) for L(x) = 1 + x2 . Define r n 3 o X(η) := max 0, − 1 . η Then every initialization with |x0 | ≥ X(η) diverges and satisfies |xk+1 | ≥ 2|xk | 22

∀k ≥ 0.

Gradient Regularized Newton Boosting Trees with Global Convergence

Proof. From the computations above, L′ (x)/L′′ (x) = x(1 + x2 ), hence xk+1 = xk − ηxk (1 + x2k ) = xk 1 − η(1 + x2k ) . If |xk | ≥ X(η), then by definition η(1 + x2k ) ≥ 3, so |1 − η(1 + x2k )| ≥ 2 and therefore |xk+1 | ≥ 2|xk |. Induction yields divergence. E.3. A drift-based generator for smooth convex Newton counterexamples The previous example is not accidental. We now record a general construction principle: prescribing a one-dimensional ˜ k ), where d˜ is the Newton drift d(x) determines a convex objective L whose Newton iteration is exactly xk+1 = xk − d(x odd extension of d. This yields an infinite family of smooth convex losses on which classical Newton diverges. Theorem E.4 (Lipschitz-Hessian drift-to-loss generator for 1D Newton dynamics). Let d : [0, ∞) → [0, ∞) be continuous and satisfy: (D0) d(0) = 0 and d(x) > 0 for all x > 0; (D1) there exist δ > 0 and C0 < ∞ such that |d(x) − x| ≤ C0 x2

∀x ∈ [0, δ].

Define, for x > 0, Z x Φ(x) := 1

ds , d(s)

L′+ (x) := a eΦ(x) (a > 0),

Z x L+ (x) :=

L′+ (t) dt,

˜ := sign(x) d(|x|) with d(0) ˜ = 0. Then: and extend evenly by L(x) := L+ (|x|). Let d˜ : R → R be the odd extension d(x) (i) L is even, convex, and C 2 (R), with L′′ (x) > 0 for x ̸= 0. Moreover, for x > 0, L′ (x) = L′+ (x),

L′′ (x) =

L′+ (x) . d(x)

In particular, L′ is odd and L′′ is even. (ii) For every x ̸= 0, L′ (x) ˜ = d(x), L′′ (x) and therefore the classical Newton update for L is exactly N (x) = x −

L′ (x) ˜ = x − d(x). L′′ (x)

(iii) If there exist X0 > 0 and β > 1 such that d(x) ≥ (1 + β)x

∀x ≥ X0 ,

then every Newton iterate initialized with |x0 | ≥ X0 diverges and satisfies |xk+1 | ≥ β|xk |

∀k ≥ 0.

(iv) (Globally Lipschitz Hessian.) Assume in addition that d ∈ C 1 ((0, ∞)) and that |d′ (x) − 1| < ∞. d(x) x>0

C1 := sup

(81)

Gradient Regularized Newton Boosting Trees with Global Convergence

Assume moreover that there exist κ > 1 and X1 > 0 such that d(x) ≥ κx

∀x ≥ X1 .

(82)

(For instance, Equation (82) holds whenever the hypothesis in (iii) holds.) Then L′′ is globally Lipschitz on R, i.e. there exists M < ∞ such that |L′′ (u) − L′′ (v)| ≤ 2M |u − v| ∀u, v ∈ R. More precisely, for x > 0 we have L(3) (x) =

L′+ (x) 1 − d′ (x) ′ ′′ 1 − d (x) = L (x) , d(x)2 d(x)

(83)

and hence supx>0 |L(3) (x)| < ∞, so one may take 2M = supx̸=0 |L(3) (x)|. Proof. We split the argument into four parts. Part A: construction and smoothness on (0, ∞). By (D0), the map s 7→ 1/d(s) is continuous on compact subsets of (0, ∞). Hence Φ ∈ C 1 ((0, ∞)) with Φ′ (x) = 1/d(x). Therefore L′+ (x) = aeΦ(x) is C 1 ((0, ∞)) and (L′+ )′ (x) = aeΦ(x) Φ′ (x) =

L′+ (x) . d(x)

Thus L+ ∈ C 2 ((0, ∞)), with L′′+ (x) = (L′+ )′ (x) =

L′+ (x) >0 d(x)

(x > 0),

so L+ is strictly convex on (0, ∞). Part B: behavior at 0 and C 2 even extension. hence ε(x) → 0 as x ↓ 0. Then on (0, δ],

Write d(x) = x(1 + ε(x)) on (0, δ], where by (D1) we have |ε(x)| ≤ C0 x,

1 1 1 1 = · = + g(x), d(x) x 1 + ε(x) x where g is bounded on (0, δ] (since (1 + ε)−1 = 1 + O(ε)). Integrating gives Z x Φ(x) = 1

ds = d(s)

Z x 1

ds + s

Z x g(s) ds = log x + C∗ + o(1)

(x ↓ 0)

for some finite constant C∗ . Exponentiating yields L′+ (x) = aeΦ(x) = aeC∗ x(1 + o(1))

(x ↓ 0),

so L′+ (x) → 0 and L′+ (x)/x → aeC∗ ∈ (0, ∞). Since d(x) = x(1 + o(1)), we obtain L′′+ (x) =

L′+ (x) → aeC∗ ∈ (0, ∞) d(x)

(x ↓ 0).

Define L+ (0) := 0, L′+ (0) := 0, and L′′+ (0) := limx↓0 L′′+ (x); then L+ ∈ C 2 ([0, ∞)). Now define L(x) = L+ (|x|). This L is even and C 2 (R) with L′ (x) odd and L′′ (x) even, and for x > 0 we have L′ (x) = L′+ (x) and L′′ (x) = L′′+ (x) = L′+ (x)/d(x). Since L′′ (x) ≥ 0 everywhere and L′′ (x) > 0 for x ̸= 0, L is convex. This proves (i). 24

Gradient Regularized Newton Boosting Trees with Global Convergence

Part C: drift identity and divergence.

For x > 0, by (i) we have L′ (x) = L′+ (x) and L′′ (x) = L′+ (x)/d(x), hence L′ (x) = d(x). L′′ (x)

By evenness of L′′ and oddness of L′ , the ratio L′ /L′′ is odd, so for x < 0, L′ (x) L′ (|x|) ˜ = − = −d(|x|) = d(x), L′′ (x) L′′ (|x|) proving (ii). The divergence statement (iii) follows exactly as in Theorem E.4: if x ≥ X0 , then N (x) = x − d(x) ≤ −βx, hence |N (x)| ≥ β|x|, and similarly for x ≤ −X0 . Part D: globally Lipschitz Hessian. Assume Equations (81) and (82). For x > 0, differentiating L′′ (x) = L′+ (x)/d(x) and using (L′+ )′ (x) = L′+ (x)/d(x) from Part A gives Equation (83). Hence, for x > 0, |L(3) (x)| ≤

L′+ (x) L′+ (x) ′ |1 − d (x)| ≤ C = C1 L′′ (x). 1 d(x)2 d(x)

It remains to show supx>0 L′′ (x) < ∞. By Part B, L′′ extends continuously to x = 0 with 0 < L′′ (0) < ∞. On [0, X1 ], continuity gives sup[0,X1 ] L′′ < ∞. For x ≥ X1 , using Equation (82), Z x Z x ds 1 x ds ≤ Φ(X1 ) + = Φ(X1 ) + log Φ(x) = Φ(X1 ) + , d(s) κs κ X 1 X1 X1 so L′+ (x) = aeΦ(x) ≤ C x1/κ for some C. Therefore, L′′ (x) =

L′+ (x) Cx1/κ C 1 ≤ = x κ −1 , d(x) κx κ

which is bounded for x ≥ X1 since κ > 1. Thus supx>0 |L(3) (x)| < ∞, and since L′′ is even, L′′ is globally Lipschitz on R. E.4. Explicit Counterexamples Corollary E.5 (Elementary closed-form losses from explicit drifts). Applying Theorem E.4 with the following choices of d (and the corresponding choice of a) yields the stated closed-form losses: 1. If d(x) = x(1 + x) and a = C/2, then L(x) = C |x| − ln(1 + |x|) . √ 2. If d(x) = x(1 + x2 ) and a = C/ 2, then L(x) = C

1 + x2 − 1 .

3. Fix an integer m ≥ 3. If d(x) =

1+x (1 + x)m−1 − 1 m−1

then L(x) = C|x| −

and

a = C 1 − 2−(m−1) ,

C 1 − (1 + |x|)−(m−2) . m−2

4. If d(x) = (1 + x2 ) arctan x and a = C(π/4), then L(x) = C |x| arctan |x| − 12 ln(1 + x2 ) . 25

Gradient Regularized Newton Boosting Trees with Global Convergence

In each case, L is even, convex, C 2 with globally Lipschitz Hessian, and the classical Newton method diverges from sufficiently large initializations. ˜ for x ̸= 0, and that L′ (1) = a matches the Proof. For each item, one checks that the stated L has L′ (x)/L′′ (x) = d(x) + choice of a above; therefore Theorem E.4 constructs exactly the stated L. The regularity and divergence conclusions follow from the theorem. We indicate this in the case of d(x) = x + x3 = x(1 + x2 ). We compute, for x > 0, Z x is=x h ds 2 1 Φ(x) = log(1 + s ) = log x − 21 log(1 + x2 ) + 12 log 2. = log s − 2 2 s=1 1 s(1 + s ) Therefore eΦ(x) =

√

2√

x , 1 + x2

L′+ (x) = aeΦ(x) = √

Integrating from 0 to x and using L(0) = 0 yields L(x) =

√

x 1 + x2

when a = 2−1/2 .

1 + x2 − 1. Finally, by Theorem E.4(ii),

˜ k ) = xk − (xk + x3 ) = −x3 , xk+1 = xk − d(x k k as claimed. E.5. A boosting/Hilbert-space realization Proposition E.6 (A separable empirical-risk objective with divergent Newton updates). Let H = L2 (ν̂N ) ∼ = RN be the space of predictions on the training points, and consider the empirical risk N

L(F ) :=

1 Xp 1 + F (xi )2 . N i=1

Then L is convex and has 2M -Lipschitz Hessian for some M < ∞, and the exact Newton update satisfies, coordinate-wise, Fk+1 (xi ) = −Fk (xi )3 ,

i = 1, . . . , N.

In particular, if |F0 (xi )| > 1 for some i, then ∥Fk ∥ → ∞. N Proof. The √ objective is separable across coordinates in R . The coordinate-wise gradient and Hessian are those of L(x) = 1 + x2 , so Theorem E.2 applies componentwise. Lipschitzness of the Hessian follows because the scalar third derivative is bounded, hence the diagonal Hessian map is Lipschitz in operator norm.

E.6. Why gradient regularization fixes it Proposition E.7 (GRN converges on the same examples). Consider any convex objective L : Rd → R with 2M -Lipschitz Hessian and finite sublevel sets. Then the exact gradient regularized Newton method in Theorem E.1 converges globally √ with function-value rate L(xk ) − minx L(x) = O(1/k 2 ) for any fixed η ∈ (0, 1]. In particular, this applies to L(x) = 1 + x2 and to all losses generated by Theorem E.4. Proof. This is a direct specialization of Theorem 4.9 / Section D, since the weak-step becomes exact and the weak-gradient edge is 1.

Gradient Regularized Newton Boosting Trees with Global Convergence

F. Newton Boosting for Hessian-Dominated Losses This appendix proves the claims stated around Theorem 3.7: binary and categorical cross entropy are Hessian-dominated with constant c = 1, and pointwise Hessian-dominance implies Hessian-dominance of the empirical risk. F.1. A useful log inequality Lemma F.1 (A log inequality). For all p ∈ (0, 1],

Equivalently, for all p ∈ [0, 1),

1−p ≥ − log p. p

(84)

p ≥ − log(1 − p). 1−p

(85)

Proof. Define ϕ(p) = p1 − 1 + log p on (0, 1]. Then 1 p−1 1 ≤ 0, ϕ′ (p) = − 2 + = p p p2 so ϕ is non-increasing. Since ϕ(1) = 0, we have ϕ(p) ≥ 0 for all p ∈ (0, 1], which is (84). Substituting q = 1 − p gives (85). F.2. Binary cross entropy is Hessian-dominated Proposition F.2 (Binary cross entropy is Hessian-dominated with c = 1). Let y ∈ {0, 1} and u ∈ R, and set p = σ(u) = (1 + e−u )−1 . Consider the binary cross entropy l(u, y) = − y log p + (1 − y) log(1 − p) . Let g(u, y) = ∂u l(u, y) and h(u) = ∂uu l(u, y). Then the (scalar) Newton step f (u, y) = −h(u)−1 g(u, y) satisfies ∥f (u, y)∥2h(u) := f (u, y)2 h(u) =

g(u, y)2 ≥ l(u, y). h(u)

(86)

Hence binary cross entropy is pointwise Hessian-dominated with constant c = 1. Proof. A direct computation gives g(u, y) = p − y,

h(u) = p(1 − p) > 0.

Thus ∥f ∥2h = g 2 /h. If y = 1, then g = p − 1 = −(1 − p), so g2 (1 − p)2 1−p = = . h p(1 − p) p Also l(u, 1) = − log p, and Theorem F.1 gives 1−p p ≥ − log p = l(u, 1). If y = 0, then g = p, so g2 p2 p = = . h p(1 − p) 1−p p ≥ − log(1 − p) = l(u, 0). This proves (86). Also l(u, 0) = − log(1 − p), and Theorem F.1 gives 1−p

Lemma F.3 (Softmax Hessian is positive definite on the zero-sum subspace). Let p ∈ RK satisfy pk > 0 and and define H := diag(p) − pp⊤ .

k=1 pk = 1,

Let V := {v ∈ RK : 1⊤ v = 0}. Then H maps V to V and is positive definite on V . In particular, the restriction H : V → V is invertible. 27

Gradient Regularized Newton Boosting Trees with Global Convergence

Proof. First, for any v ∈ RK , 1⊤ Hv = 1⊤ diag(p)v − 1⊤ p(p⊤ v) = p⊤ v − (p⊤ v) = 0, so Hv ∈ V whenever v ∈ V . Next, for any v ∈ RK , v ⊤ Hv =

K X

pk vk2 −

K X

k=1

pk vk

k=1

K X

p k vk −

K X

pj vj

≥ 0.

j=1

k=1

Equality holds iff vk is constant in k, i.e. v ∈ span{1}. Intersecting with V leaves only v = 0, hence v ⊤ Hv > 0 for all nonzero v ∈ V . Therefore H is positive definite on V and invertible as H : V → V . Proposition F.4 (Categorical cross entropy is Hessian-dominated with c = 1). Let u ∈ RK , p = softmax(u), and let y = et be a one-hot label. Consider categorical cross entropy l(u, y) = −

K X

yk log pk = − log pt .

k=1

Let g(u, y) = ∇u l(u, y) = p − y and H(u) = ∇2uu l(u, y) = diag(p) − pp⊤ . Work on the subspace V = {v : 1⊤ v = 0}; then g(u, y) ∈ V and by Theorem F.3 the Newton direction f ∈ V solving H(u)f = y − p

(87)

is unique. Moreover, ∥f ∥2H(u) := f ⊤ H(u)f =

1 − pt ≥ − log pt = l(u, y). pt

(88)

Hence categorical cross entropy is pointwise Hessian-dominated with constant c = 1. Proof. Let H = diag(p) − pp⊤ . Define s := p⊤ f . Expanding (87) yields diag(p)f − p(p⊤ f ) = y − p

⇐⇒

so (since pk > 0) we have fk = s +

pk (fk − s) = yk − pk

∀k,

yk − 1. pk

With y = et , this becomes ft = s +

1 − 1, pt

fk = s − 1

(k ̸= t).

Using symmetry of H and (87), ∥f ∥2H = f ⊤ Hf = f ⊤ (y − p). Compute f ⊤ (y − p) = ft (1 − pt ) +

fk (0 − pk )

k̸=t

= ft (1 − pt ) − (s − 1)

k̸=t

= ft − (s − 1) (1 − pt ) = =

1 − pt . pt

t Finally, Theorem F.1 gives 1−p pt ≥ − log pt = l(u, y), proving (88).

1 − 1 − (s − 1) (1 − pt ) pt

Gradient Regularized Newton Boosting Trees with Global Convergence

Remark F.5 (Relation to Assumption 3.1 (uniqueness of Newton step)). On RK one has H(u)1 = 0 (softmax is shiftinvariant), so the Newton equation is not uniquely solvable without fixing a gauge. Restricting to the zero-sum subspace V = {v : 1⊤ v = 0} (or equivalently fixing one logit coordinate) yields uniqueness and matches Assumption 3.1. The decrement ∥f ∥2H(u) is invariant to the choice of representative. Remark F.6. Binary cross entropy corresponds to the special case K = 2 of categorical cross entropy (after identifying the scalar logit with the difference of the two softmax logits). Thus Theorem F.4 strictly generalizes Theorem F.2; the latter is included separately for clarity and because it avoids the gauge-fixing required in the multiclass setting. F.3. From pointwise to empirical Hessian-dominance Lemma F.7 (Pointwise ⇒ empirical Hessian-dominance). Let {(xi , yi )}N i=1 be a dataset and define the empirical risk N

L(F ) =

1 X l(F (xi ), yi ), N i=1

with F (xi ) ∈ RK (take K = 1 for binary). Work in the empirical Hilbert space H = L2 (ν̂N ) with inner product N

⟨A, B⟩ =

1 X ⟨A(xi ), B(xi )⟩RK . N i=1

Fix F ∈ H and write ui := F (xi ). Let g(i) := ∂1 l(ui , yi ) ∈ RK ,

h(i) := ∂11 l(ui , yi ) ∈ RK×K .

Assume there exists c > 0 such that for all i, ⊤ −1 g(i) h(i) g(i) ≥ c l(ui , yi ),

(89)

where h−1 (i) is taken on the relevant space (for categorical CE one may restrict to V pointwise as in Theorem F.4). Let g = ∇L(F ) and H = ∇2 L(F ), and let f = −H −1 g be the exact Newton direction (Assumption 3.1). Then ∥f ∥2H ≥ c L(F ). In particular, L is Hessian-dominated in the sense of Theorem 3.7 with constant c. Proof. In the empirical setting, the gradient and Hessian act pointwise: g(xi ) = g(i) ,

(H[f ])(xi ) = h(i) f (xi ).

Thus the Newton equation H[f ] = −g decouples over samples: h(i) f (xi ) = −g(i)

⇒

f (xi ) = −h−1 (i) g(i) .

Therefore, using Theorem 3.2, ∥f ∥2H = ⟨f, H[f ]⟩ =

N N 1 X 1 X ⊤ −1 f (xi )⊤ h(i) f (xi ) = g h g(i) . N i=1 N i=1 (i) (i)

Applying (89) term-by-term yields N

∥f ∥2H ≥

c X l(ui , yi ) = c L(F ), N i=1

which is exactly Theorem 3.7. PN Corollary F.8 (Empirical cross entropy risks are Hessian-dominated with c = 1). Let L(F ) = N1 i=1 l(F (xi ), yi ) where l is either binary cross entropy (Theorem F.2) or categorical cross entropy (Theorem F.4). Then L is Hessian-dominated with c = 1 (in the sense of Theorem 3.7, with the gauge-fix of Theorem F.5 in the categorical case). 29

Record · ID 151754 · SHA-256 b9db3b0ed3aae545
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.