How does combining CaCuTe with SESOP improve smooth convex minimization under Lipschitz Hessians?

CaCuSESOP closes the gap CaCuTe leaves open

CaCuTe separates two regimes of the cubic Taylor model. When the quadratic Hessian term is small, a scaled gradient step decreases the cubic model and yields an O(k^-2) rate while that regime holds, and one Hessian-vector product (HVP) checks the curvature condition. When the quadratic term dominates, that certificate fails and the method falls back to standard gradient-descent decrease, whose general convex guarantee is only O(k^-1).

The paper starts from that second regime. The model is nearly quadratic, but gradient scaling alone does not use its curvature efficiently. The question is how to spend a fixed number of HVPs to minimize the model without forming or factorizing the Hessian. The answer is to build the cubic model inside a small SESOP space and minimize that model instead of the original objective. Three HVPs suffice for the convergence theory, so the inner solve needs no further objective-oracle calls.

The resulting method, CaCuSESOP, combines both regimes under a fixed HVP budget and admits automatic local acceleration through restarts. In the practical configuration it uses a five-direction space, while the stated three-direction variants use at most three HVPs per accepted step.

A reduced cubic model replaces exact subspace minimization

Classical SESOP prescribes no HVP oracle: each outer iteration instead requires an exact minimizer of the original objective over its current subspace. Under the stated smooth-convex assumptions that is a general low-dimensional smooth convex optimization problem, and no finite uniform oracle budget returns the exact minimizer over the whole class. The rate alone therefore does not describe the cost of a subspace method.

CaCuSESOP replaces exact minimization of the original objective with minimization of a low-dimensional cubic upper model that needs only be solved to a computable accuracy. Once the reduced model coefficients have been formed, its exact solve requires no more objective-oracle calls. The paper is explicit that this is a statement about oracle cost, not a claim of a fixed number of arithmetic operations for the reduced solve.

The algorithm first completes a one-HVP backtracking search for the scaled-gradient step. If its projected model residual is too large, the already computed HVP becomes a direction of the full subspace model and the remaining columns are formed. Only a failed residual test activates the full subspace fallback. The cubic regularization parameter is chosen by backtracking rather than supplied as a smoothness bound.

The global rate holds with a fixed HVP budget

CaCuSESOP achieves the global rate O(k^-2) with a fixed number of Hessian-vector products per iteration. The discussion states the global rate of order sqrt(log K)/K^2 with at most three HVPs per iteration, and deterministic restarts improve the global rate to O(K^-2) with the same oracle cost.

The comparison table separates global rate from directional curvature work and inner-problem complexity. For CaCuSESOP with controlled restarts, the table lists O(k^-2), one to five HVPs, inner-problem complexity O(1), and parameter-freeness with respect to problem constants. Classical SESOP is listed at O(k^-2) but with an unbounded worst-case budget for the exact inner solve, and CaCuAdGD at O(k^-1) with one HVP.

The table also records that the four displayed Cubic SESOP algorithms use three directions, and that Corollary 4.7 shows the previous step may be retained as an optional fourth practical direction without changing their theoretical rates. CaCuSESOP uses the five-direction space in the practical comparison and the same controlled restart schedule.

Local acceleration arrives without supplied problem constants

If the Hessian at the minimizer is positive definite, CaCuSESOP automatically attains an accelerated local linear rate with complexity O(sqrt(kappa*) log(1/epsilon)). Neither the local strong-convexity parameter, the condition number kappa*, nor the optimal value is supplied to the algorithm.

The paper gives finite bounds for entering this regime and for adapting the restart schedule. Corollary 4.6 separates three costs: reaching a sufficiently small sublevel, adapting the epoch length, and subsequently reducing the objective gap to the requested accuracy. The local objective threshold is epsilon_loc = mu*^3 / (2^27 H^2), and the sufficient number of accepted steps is O(1 + D_0 sqrt((3/2)(L_0 + sqrt(4 H L_0 D_0))) + (2048/3) H D_0 / epsilon_loc + sqrt(kappa*) [log(2 + kappa*) + log(epsilon_loc / epsilon)]), with a universal implicit constant.

The paper is careful about what this local claim is. It is an R-rate for objective gaps, not the same contraction at every individual step, and the corresponding root bounds for iterate errors and gradient norms have half the exponent. The entry cost depends on the initial point, Hessian variation, and curvature at the minimizer. The bound is an accuracy guarantee, not a stopping test involving the unknown optimal value.

The global O(k^-2) exponent is optimal for this oracle class

The paper proves that the global O(k^-2) rate is optimal for the considered fixed-budget gradient/Hessian-vector-product linear-span oracle class, even with momentum and unrestricted memory. The discussion describes this as an adaptation of the classical sharp CG/Krylov bound showing that the global exponent is sharp in the stated oracle class.

This sharpness claim is scoped to the oracle class the paper defines, not to every possible second-order method. It is a statement about what a fixed budget of gradient and HVP information can achieve within a linear-span construction, and it holds even when momentum and unrestricted memory are allowed.

The comparison table places this against alternatives whose faster outer rates require different resources: the full/exact rows require m = d and dense O(d^3) algebra, and the table explicitly declines to combine m and k into a fictitious rate.

The W8A experiment favors CaCuSESOP in iterations and time

On regularized logistic regression on W8A with lambda = 10^-7, CaCuSESOP gives the fastest decrease in both accepted outer iterations and elapsed time. Both panels of the figure use the same objective, starting point, and reference value.

The mechanism behind that result is the one-HVP gradient branch, which avoids a reduced solve whenever the residual certificate passes; otherwise the five-dimensional cubic fallback is formed once and reused throughout backtracking. Controlled restarts prevent the accumulated SESOP directions from becoming ineffective.

The baselines were run in their authors' advocated configurations rather than tuned on W8A. SESOP uses the current gradient, one previous step, and the two Nemirovski directions, with the restricted nonlinear objective minimized by Newton's method with Armijo backtracking and the authors' SESOP_PACK inner settings: at most seven Newton iterations, a projected-gradient threshold of 10^-10, initial line-search step 1, reduction factor 1/4, and at most 40 line-search trials. Generic Type-I uses the nonaccelerated variant with memory m = 25, orthogonal forward estimates, forward-difference step h = 10^-9, and the initial regularization rule from the cited appendix. The linked repository contained no implementation when checked on October 1, 2026, so that baseline was reimplemented from the published algorithms.

Where the guarantees stop and what they do not promise

The optional fourth memory direction is permitted without changing the theoretical rates, but the paper states plainly that this statement does not predict better iteration counts or running time. It only permits the memory direction while keeping the guarantees.

The reduced cubic solve need not be solved to an exact argmin. A relative stationarity test uses only already computed coefficients and preserves the basic, adaptive, and deterministic-epoch guarantees, with Corollary 4.9 extending the accelerated restart controller and its finite-time bounds to the same criterion. The required absolute accuracy decreases with the step, so a fixed absolute solver tolerance does not provide this guarantee.

The local PL result gives linear convergence and finite trajectory length without a nondegenerate or unique minimum, but for adaptive coefficients it assumes the accepted coefficients are eventually bounded away from zero, and the algorithm does not need to know that bound. The accumulation-point qualification in that theorem is essential: objective convergence does not imply entry near an arbitrary prescribed minimizer.

Compare oracle budget and inner-solve cost, not rate alone

The decision-relevant comparison in this paper is not the headline rate but the pairing of rate with oracle budget and inner-problem cost. CaCuSESOP with controlled restarts is listed at O(k^-2) with one to five HVPs and inner-problem complexity O(1), while classical SESOP reaches O(k^-2) only with an unbounded worst-case budget for its exact inner solve, and CaCuAdGD sits at O(k^-1) with one HVP.

The inner-problem complexity convention matters for reading that table. It is measured after the reduced problem coefficients have been formed and excludes objective-oracle calls, construction of the subspace basis, and lifting the reduced solution back to R^d. A dense reduced problem of dimension r costs O(r^3) under this convention, so the three-, four-, and five-direction Cubic SESOP variants have IPC O(1), an m-dimensional Krylov or Scieur subproblem has IPC O(m^3), and a full-space problem has IPC O(d^3). The excluded basis operations cost O(d r^2) to form or orthogonalize a dense basis and O(d r) to apply it.

For a reader deciding whether the method fits a problem, the paper's own split is therefore: accuracies epsilon at or above epsilon_loc are covered by the global estimate alone, while the accelerated local regime requires the finite entry and adaptation budget of Corollary 4.6. The practical five-direction space gives the fallback two additional directions and imposes a stronger gradient-trial test, and the one-HVP gradient branch is what avoids a reduced solve whenever its residual certificate passes.

Sources used in this answer