PaperlayerView exact revision on arXiv

Source-linked AI summary

Affine-invariant Cubic Newton with Weak Learners

Nikita Zozoulenko, Daniel Falkowski, Thomas Cass, Lukas Gonon

arXiv:2610.33516v1stat.MLcs.LGmath.OC

TL;DR

Newton boosting lacks broad global convergence guarantees, and the weak-GRN analysis has a pessimistic worst-case edge dependence. This paper extends affine-invariant cubic Newton to weak learners, obtaining global bounds based on path-averaged cosine angles and a damped update set by directional improvement.

  • Problem

    Newton boosting has limited global convergence theory, while weak-GRN's guarantee depends heavily on a potentially small worst-case Euclidean weak gradient edge.

    Source: §1 · p. 1

  • Method

    The paper generalizes affine-invariant cubic Newton to weak learners, using local Hessian geometry, path-averaged cosine angles, and a directional-improvement-based damped step.

    Source: §1 · pp. 1–2, §3 · p. 4

  • Results

    Weak-AICN establishes a global O(1/overline{Theta}_k^4 k^2) rate under semi-strong self-concordance, improving on weak-GRN's O(1/γ^12 k^2) bound.

    Source: §1 · p. 2, §3.2 · p. 6, Conclusion · p. 10

  • Takeaways & Limitations

    Newton coordinate descent arises as a special case of optimization with weak learners, extending the framework beyond gradient boosting.

    Source: §4.2 · p. 8

    Weak-AICN can struggle on ill-conditioned problems without static ℓ2 regularization, unlike weak-GRN's adaptive gradient-based penalties.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Modern gradient boosting algorithms are based on Newton's method, which excels empirically but lacks global convergence guarantees. While recent work on Gradient-Regularized Newton (GRN) boosting achieved a global $\mathcal{O}(1/\gamma^{12}k^2)$ rate, its analysis was not able to exploit the natural Hessian geometry and suffers from a heavy $\gamma^{12}$ dependence on a worst-case `weak gradient edge' $\gamma$. In this paper, we tackle these theoretical drawbacks by generalizing the Affine-Invariant Cubic Newton (AICN) scheme to convex optimization with weak learners. Our analysis is based on average cosine values $\overline{\Theta}_k$ along the optimization path and directional improvements $\delta_k$ in the Hessian-induced norm. We show that the weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by $\delta_k$. Under semi-strong self-concordance, we establish a global $\mathcal{O}(1/\overline{\Theta}_k^4 k^2)$ rate, significantly improving upon the weak-GRN bound. We further prove a local linear rate, global linear convergence for Hessian-dominated losses, cosine angle lower bounds, and present weak-AdaAICN, which adaptively tunes the cubic regularization. Finally, we demonstrate the broader applicability of this framework beyond gradient boosting by showing that Newton coordinate descent emerges naturally as a special case of optimization with weak learners.

1 Introduction

Newton boosting is widely used, but its global convergence theory remains limited; the weak-GRN guarantee improves this while retaining a pessimistic worst-case weak-gradient-edge dependence. This paper generalizes affine-invariant cubic Newton to weak learners and replaces that worst-case perspective with path-averaged cosine bounds.

1 Introduction

  • Extending GRN to weak learners via Restricted Newton Descent established Newton boosting’s first global O(1/k^2) rate [42], while weak-GRN’s bound has severe O(1/γ^12 k^2) dependence because γ can be very small.Source: §1 · p. 1
  • Weak-AICN generalizes Affine-Invariant Cubic Newton to weak learners and measures convergence through path-averaged cosine angles rather than worst-case edges.The analysis uses local Hessian norms and is intended to avoid having one poorly fitted weak learner invalidate the whole bound.Source: §1 · pp. 1–2
  • The paper also establishes local linear convergence, global linear convergence for Hessian-dominated losses, and adaptive tuning of cubic regularization.It further gives random lower bounds on decision-tree alignment, including a Beta-distributed stochastic lower bound.Source: §1 · p. 2

1.1 Related Work

  • Newton boosting theory has global guarantees for weak-GRN, while vanilla Newton boosting guarantees have been limited to strongly convex settings with small learning rates.Earlier gradient-boosting rates progressed from O((log k)^−1/2) to O(1/k) under smoothness and O(1/k^2) with Nesterov momentum.Source: §1.1 · p. 2
  • AICN attains a global O(1/k^2) rate with local quadratic convergence as a damped Newton method with an explicit computable stepsize.Unlike cubic regularized Newton, AICN does not require solving a costly subproblem each iteration.Source: §1.1 · p. 2

2 Setup and Optimization with Exact and Weak Learners

The setup treats optimization in a Hilbert space and restricts Newton updates to a scalable family of weak learners. It introduces Hessian-geometric alignment measures and relates weak quadratic minimization to directional improvement.

2 Setup and Optimization with Exact and Weak Learners

  • The optimization objective is a convex, twice-differentiable loss on a real Hilbert space with positive-definite Hessian, and exact Newton steps minimize a second-order Taylor model.The setup defines the gradient and Hessian at each iterate and uses the quadratic model centered there.Source: §2 · pp. 2–3

2.1 Restricted Newton Descent

  • Restricted Newton Descent replaces the unrestricted Newton update with minimization of the quadratic model over a weak-learner family, typically bounded-depth decision trees in boosting.The family is assumed closed under scalar multiplication.Source: §2.1 · p. 3

2.2 Hessian norms, cosine angle, and directional improvement

  • The analysis uses a Hessian-induced norm and dual norm, and defines the cosine angle between exact and weak Newton directions alongside directional improvement in local Hessian geometry.Directional improvement measures alignment with the exact Newton direction in that geometry.Source: §2.2 · p. 3
  • Q-δ duality makes maximizing directional improvement equivalent to minimizing the weak quadratic model under the stated nonzero-direction and nonnegative-improvement condition.The proposition also relates the model value at a weak minimizer to the maximal directional improvement.Source: §2.2 · pp. 3–4

3 AICN with Weak Learners

Weak-AICN converts a weak Newton update into a damped step whose size is determined by directional improvement. Under semi-strong self-concordance, its global guarantees use path-averaged cosine edges, with additional local and Hessian-dominated linear rates.

3 AICN with Weak Learners

  • AICN uses a cubic term in the Hessian-induced norm, yielding a damped Newton step, whereas Euclidean cubic regularization requires an expensive inner subproblem.The section introduces the weak-learner version of this update.Source: §3 · p. 4
  • The weak-AICN update reduces to a damped weak-Newton step with an explicit stepsize determined by directional improvement δ_k.The algebraic update result requires no extra loss-regularity assumptions, and δ_k drives damping rather than the exact method's dual gradient norm.Source: §3 · p. 4

3.1 Semi-strong Self-concordance and Weak Contracting-point Inequality

  • Under semi-strong self-concordance, the cubic model supplies a global bound and the weak update contracts the objective toward any comparison point, with contraction scaled by squared cosine angle and learning rate.The stated contracting-point result requires C_est ≥ C_ssc and 0 < η ≤ 1.Source: §3.1 · p. 5

3.2 Global and Local Convergence of AICN with Weak Learners

  • Weak-AICN has an initial global linear phase followed by a global O(1/k^2) phase, with bounds based on path-averaged cosine edges rather than worst-case edges.The convergence theorem also assumes a bounded local radius; its stated phases depend on the threshold k0.Source: §3.2 · p. 6
  • A local linear rate holds when the dual-Hessian gradient norm satisfies the theorem's local condition, and the analysis obtains gradient contraction rather than the classical quadratic rate.The local rate depends on squared weak-learner cosine angle and learning rate.Source: §3.2 · pp. 6–7

3.3 Global Convergence of weak-AICN for Hessian-dominated Losses

  • For Hessian-dominated losses, weak-AICN has a global linear rate; cross entropy is a canonical example, but the theorem also requires semi-strong self-concordance.Unregularized binary log-loss is not self-concordant, whereas ℓ2-regularized cross entropy satisfies Hessian dominance and self-concordance.Source: §3.3 · p. 7

4 Applications of Weak-AICN

The applications section connects weak-AICN to Newton tree boosting and shows that Newton coordinate descent is a special case of optimization with weak learners. It also reports supplementary experiments on the method and its alignment measures.

4.1 Newton boosting

  • Restricting weak learners to depth-J decision trees recovers classical Newton boosting, and empirical-risk semi-strong self-concordance follows from that of the pointwise loss.The inherited constant is bounded by √n times the pointwise-loss constant; implementing weak-AICN requires computing its stepsize.Source: §4.1 · p. 7
  • For random tree configurations, Theorem 4.2 gives dyadic lower bounds on the expected proxy tree angle, with the proxy equal to 1 almost surely when 2^J ≥ n.The proxy is a tractable no-signal baseline for random tree alignment in a realized Hessian geometry.Source: §4.1 · p. 8

4.2 Newton Coordinate Descent

  • Choosing scaled standard-basis vectors as weak learners recovers Newton coordinate descent, selecting the coordinate that maximizes |(g_k)_i|/√(H_k)_{ii}.The coordinate update is a one-dimensional Newton step; its cosine angle has a deterministic lower bound involving dimension and the Hessian condition number.Source: §4.2 · pp. 8–9

4.3 Supplementary Experiments

  • The supplementary experiments examine adaptive weak-AICN, tree-boosting convergence and weak-learner edges, and random tree-angle proxy bounds.They are intended to validate and supplement the theory, not claim state-of-the-art predictive performance; on HIGGS, weak-AICN's edge is slightly higher at equivalent loss values, while the compared metrics are similar overall.Source: §4.3 · p. 9

Limitations

Weak-AICN improves the stated weak-learner-edge dependence but its local Hessian geometry can pose a challenge on ill-conditioned problems without static ℓ2 regularization.

Limitations

  • Without static ℓ2 regularization, weak-AICN can struggle on ill-conditioned problems, unlike weak-GRN with adaptive gradient-based ℓ2 penalties.The geometric shift improves the stated dependence from γ^12 to Θ_k^4 but comes with this trade-off.Source: Limitations · p. 9
  • With small learning rates, vanilla Newton boosting and globally convergent variants often show little empirical difference, although global schemes remain necessary for theoretical convergence guarantees.The paper says standard Newton boosting is guaranteed to converge when its learning rate η does not exceed the weak-AICN dampening factor α_k.Source: Limitations · p. 10

Conclusion

The paper presents weak-AICN as a globally convergent second-order scheme for weak learners, with an affine-invariant rate under semi-strong self-concordance. It also establishes additional rate results, stochastic tree-alignment bounds, and a connection to Newton coordinate descent.

Conclusion

  • Weak-AICN reduces to a damped weak-Newton step with an explicit stepsize, using directional improvements measured in the local Hessian norm.The update result does not require regularity assumptions on the loss.Source: Conclusion · p. 10
  • Under semi-strong self-concordance, weak-AICN achieves a global O(1/(Θ_k^4 k^2)) rate, improving the weak-GRN edge dependence and replacing a worst-case infimum with an average-performance bound.The paper also establishes a local linear rate for general convex losses and a global linear rate for Hessian-dominated losses.Source: Conclusion · p. 10
  • For decision trees, the paper derives explicit Beta-distributed stochastic alignment lower bounds, including an expectation bound that improves dyadically with tree depth.These bounds address the stated impossibility of deterministic worst-case bounds for decision trees.Source: Conclusion · p. 10
  • Newton coordinate descent emerges as a special case when the weak-learner family is restricted to standard basis vectors.This illustrates the framework's extension beyond gradient boosting to finite-dimensional convex optimization.Source: Conclusion · p. 10

A Proofs for Weak Learner Direction Selection

The appendix develops proof steps for selecting weak-learner directions and establishing the damped weak-Newton update, then supplies inequalities and recurrence arguments used in the convergence analysis.

A Proofs for Weak Learner Direction Selection

  • Because the weak-learner family is closed under scalar multiplication, minimizing the quadratic model over it reduces to minimizing along each generated ray.The ray minimization is a scalar quadratic with a unique minimizer.Source: A Proofs for Weak Learner Direction… · p. 14

B.1 Proof of Weak-AICN is Damped weak-Newton

  • The cubic model proof orients each weak direction toward nonnegative directional improvement, then minimizes over its nonnegative step length.For positive directional improvement, the scalar cubic model has a unique positive minimizer, yielding the explicit damped step.Source: §B.1 · p. 16

B.2 Proof of Weak Improvement Θ2 k Factor

  • The weak-improvement proof uses the damping factor and the directional-improvement identities to compare improvement along weak and exact Newton directions.Source: §B.2 · p. 17

B.3 Proof of Weak Contracting-point Inequality

  • The contracting-point inequality follows by combining upper and lower Taylor bounds, Jensen's inequality, and the condition C_ssc ≤ C_est.Source: §B.3 · pp. 17–18

B.4 Proof of Recurrence Lemmas

  • The recurrence proofs use telescoping sums for the sublinear bound and repeated contraction inequalities for the linear bound.The recurrence terms are non-increasing under the stated nonnegative assumptions.Source: §B.4 · p. 18

B.5 Proof of Global Convergence with Weak Learners

The appendix details the convergence proofs and extensions of weak-AICN, including local and Hessian-dominated linear rates, semi-strong self-concordance in boosting space, coordinate descent, and adaptive regularization.

B.5 Proof of Global Convergence with Weak Learners

  • The global-convergence proof derives a recurrence for the loss gap, with an initial linear regime followed by a global decrease controlled by the weak-learner cosine angle.The proof also notes that when the weak-learner family is the full space and η = 1, the first iteration reduces the gap below the stated threshold.Source: §B.5 · p. 19

B.6 Proof of Local Linear Convergence with Weak Learners

  • The local-rate proof bounds the next gradient using a linear term and an error term, then establishes contraction under the stated bounded-radius assumption.The appendix notes sufficient conditions for that assumption using strong convexity together with smoothness or a Lipschitz Hessian.Source: §B.6 · pp. 20–21

B.7 Proof of Linear Rate for Hessian-dominated Losses

  • For Hessian-dominated losses, the proof applies the affine-invariant cubic bound and the Hessian-dominance condition to obtain the claimed linear rate.The derivation uses the weak-AICN dampening factor αk.Source: §B.7 · p. 22

C Semi-Strong Self-Concordance in the Boosting Space

  • In the empirical boosting space, the appendix derives semi-strong self-concordance of the empirical risk from the one-dimensional condition, with Cssc(L) ≤ √nCl.The proof represents the Hessian and its variation as diagonal operators and bounds their affine-invariant norm using the scalar loss condition.Source: C Semi-Strong Self-Concordance in the… · p. 23

D.1 Proof of Newton Coordinate Descent Cosine Angle Lower Bound

  • For Newton coordinate descent, the proof bounds the weak and exact directional improvements separately before forming their ratio as a cosine-angle lower bound.The coordinate update selects the basis direction maximizing directional improvement; its computation uses the Hessian diagonal and gradient.Source: §D.1 · p. 24, §D.2 · p. 24

D.3 Adaptive Weak-AICN Algorithm

  • Weak-AdaAICN backtracks on a local regularity estimate, doubling it when observed loss decrease misses the cubic model’s prediction and recomputing the stepsize.The check needs one loss evaluation and scalar operations, without recomputing the Hessian or weak learner; the estimate is bounded by 2 max(C0, Cssc).Source: §D.3 · p. 24

D.4 Experimental Validation of weak-AdaAICN

The experiments test adaptive AICN in full-space and coordinate-descent settings, then compare Newton boosting methods on the Charbonnier loss. AdaAICN accelerates convergence in both settings, while weak-AICN and weak-GRN robustly converge where undamped vanilla Newton boosting fails.

D.4 Experimental Validation of weak-AdaAICN

  • The adaptive experiments compare full-space AICN and Newton coordinate descent against optimally tuned and conservative fixed regularity constants.They use dimensions d = 100 and d = 20, respectively, with learning rate η = 1.0 and regularization µ = 10^-3.Source: §D.4 · pp. 25–26
  • 2× fewer iterations and 2× less wall-clock time: exact AdaAICN reaches the minimum faster than non-adaptive AICN in the full-space setting.In coordinate descent, AdaAICN’s advantage is significant but smaller; the experiments use Nesterov’s second-order lower-bound function.Source: §D.4 · p. 26, Figure 2 · p. 26, Figure 3 · p. 26

E.1 Charbonnier Loss: Non-convergence of Vanilla Newton Boosting

  • At η = 1.0, vanilla Newton boosting fails to converge on UCI Wine Quality with Charbonnier loss, while weak-AICN, weak-GRN, and first-order boosting converge robustly.At η = 0.1, vanilla Newton boosting also converges; weak-AICN and weak-GRN are slightly slower than vanilla Newton in that setting.Source: §E.1 · p. 27, Figure 4 · p. 27

E.2 Binary Cross Entropy: Effects of Tree Depth and Weak Learner Edge

The appendix compares weak-learner alignment metrics across tree depths and develops deterministic bounds for empirical tree cosines. It also gives a worst-case obstruction: below a leaf-count threshold, empirical axis-aligned trees need not have a positive cosine lower bound.

E.2 Binary Cross Entropy: Effects of Tree Depth and Weak Learner Edge

  • On HIGGS, weak-AICN’s dampening factor αk approaches 1.0 as optimization progresses, while Figure 5 also tracks training loss, weak-GRN regularization, and directional improvement.The appendix states that δk shrinks as the residual becomes harder to fit, and that the Hessian cosine angle and weak gradient edge average about 0.1 while their infima are near 0.05.Source: §E.2 · p. 28, Figure 5 · p. 29
  • Across tree depths J = 2, 4, and 6, stabilized alignment averages are roughly 0.05, 0.1, and 0.2, respectively, doubling with every two added levels.The comparison includes weak-AICN’s Hessian-induced cosine, weak-GRN’s gradient edge, and the Euclidean cosine; empirical angles stay above the no-signal reference values.Source: §E.2 · pp. 28–29, Figure 6 · p. 29

F.2 Deterministic empirical tree geometry

  • For every configuration of n distinct sample points, depth-J axis-aligned trees cannot represent every empirical function when 2^J < n, but can when J ≥ n − 1.This is a worst-case geometric statement about exact representation in the empirical space.Source: §F.2 · p. 30
  • A parity example has zero intrinsic tree cosine at depth d − 1, ruling out an assumption-free deterministic positive lower bound below the leaf-count regime.The appendix cautions that this is a worst-case obstruction, not a model of typical boosting iterations.Source: §F.2 · p. 31

F.3 Random model and dyadic lower bounds

The section compares a metric-matched random tree-angle proxy with coupled Newton directions and proves dyadic lower bounds for the proxy. Its bounds apply uniformly over metric models and distinguish the first-iteration proxy comparison from stronger conjectures about optimization trajectories.

Random model

  • The proxy preserves the realized sample and Hessian geometry but replaces the coupled Newton direction with a generic isotropic direction in that metric.The proxy averages over generic directions in the realized metric and then over random sample–metric pairs.Source: §F.3 · pp. 31–33
  • The proposed first-iteration comparison is conjectural and interpreted as a structured-signal hypothesis, not a universal claim about later optimization dynamics.The stronger late-time stochastic-domination conjecture is not proved or directly verified; it would require additional control of limiting weak-Newton residual geometry.Source: §F.3 · p. 32

Dyadic lower bounds

  • For 2^J < n, the random tree cosine proxy admits a dyadic stochastic lower bound, and the section derives corresponding expectation bounds uniformly over metric models.The squared-angle estimate is the main quantity because weak-AICN rates depend on squared cosine factors.Source: §F.3 · pp. 33–35
  • The dyadic construction yields a depth-J tree subspace of dimension min(2^J, n), becoming the full space when 2^J ≥ n.The proof sorts points by the first coordinate and recursively bisects consecutive blocks.Source: §F.3 · pp. 33–34

G Experimental Appendix: Proxy Tree-Angle Evaluation

The experiments compare fitted tree angles for coupled Newton directions with uncoupled proxies across label models, losses, tree-fitting rules, and depths. They support a model-dependent coupling advantage for structured signals, while unstructured controls remain near the proxy.

Experimental setup

  • The comparison treats tree-readable coordinate signals as structured cases and Rademacher labels as an unstructured control against metric-isotropic proxies.The experiments use n = 64, p = 16, and depths J = 0, . . . , 6.Source: G Experimental Appendix: Proxy… · p. 36

Squared-loss comparison

  • For squared loss, the zero warm start makes the Newton direction equal to the labels and the Hessian equal to the identity.Thus the comparison uses an uncoupled identity-isotropic proxy.Source: G Experimental Appendix: Proxy… · pp. 36–37

Logistic-loss comparison

  • For logistic loss, the nonconstant initial Hessian defines a metric-matched proxy, and adaptive CART shows a positive gap for structured labels while the control stays close.This tests the comparison in nontrivial Hessian geometry.Source: G Experimental Appendix: Proxy… · p. 37, Figure 8 · p. 38

Experimental findings

  • Figs. 7–9 support a first-iteration coupling advantage for structured linear and smooth models, while Rademacher controls remain near the uncoupled proxy.The advantage is especially clear for adaptive CART; dyadic fits mainly benefit when the signal matches their fixed first-coordinate splits.Source: Figure 7 · p. 37, Figure 9 · p. 38, Figure 8 · p. 38

H Alternative Decision Tree Angle Bound

This result bounds weak-learner cosine alignment when the Newton direction combines a fixed tree-aligned signal with Gaussian noise in Hessian geometry. It also identifies a Beta-distributed noise-only benchmark when the signal is absent.

Signal-plus-noise bound

  • With a fixed tree-aligned signal and independent Gaussian noise in an Hk-orthonormal basis, Theorem H.1 gives a lower expectation bound for the weak-learner cosine angle.The tree has exactly 2^J nonempty leaves, with 2^J < n.Source: H Alternative Decision Tree Angle Bound · p. 40

Proof strategy

  • The proof decomposes the signal-plus-noise direction into tree-subspace and orthogonal components, whose squared Hessian norms follow scaled chi-squared distributions.The independent projected components support the ratio-based expectation argument.Source: H Alternative Decision Tree Angle Bound · p. 40

Noise-only case

Related papers

Loading 2610.33516v1…