Abstract
This paper introduces the Runge–Kutta Chebyshev descent method (RKCD) for strongly convex optimisation problems. This new algorithm is based on explicit stabilised integrators for stiff differential equations, a powerful class of numerical schemes that avoid the severe step size restriction faced by standard explicit integrators. For optimising quadratic and strongly convex functions, this paper proves that RKCD nearly achieves the optimal convergence rate of the conjugate gradient algorithm, and the suboptimality of RKCD diminishes as the condition number of the quadratic function worsens. It is established that this optimal rate is obtained also for a partitioned variant of RKCD applied to perturbations of quadratic functions. In addition, numerical experiments on general strongly convex problems show that RKCD outperforms Nesterov’s accelerated gradient descent.
Introduction
In strongly convex optimization, practitioners often face a trade-off between simplicity and efficiency. Standard Gradient Descent (GD) is straightforward to implement but is limited by a "step-size bottleneck": stability requires steps no larger than $2/L$, where $L$ is the Lipschitz constant of the gradient. For "stiff" or poorly conditioned problems—where curvatures vary significantly across directions—GD becomes prohibitively slow. Conversely, implicit methods offer superior stability and allow for large steps but require solving expensive sub-problems at each iteration.
This paper proposes the Runge–Kutta Chebyshev Descent (RKCD) method as a "middle way." RKCD is an explicit method that maintains the computational ease of GD while achieving the stability and convergence rates typically associated with more complex techniques.
Methods: Explicit Stabilized Integration
The RKCD algorithm treats optimization as the discretization of a gradient flow ordinary differential equation (ODE). While GD corresponds to a simple Forward Euler discretization, RKCD utilizes explicit stabilized integrators based on Chebyshev polynomials.
Key Algorithmic Features
- Internal Stages ($s$): Each RKCD iteration consists of $s$ internal stages. While individual stages may be unstable, their combination—governed by Chebyshev recurrence relations—ensures the final update is stable. This allows the algorithm to move significantly further along the gradient flow than $s$ steps of standard GD.
- Damping Parameter ($\eta$): A small damping factor is introduced to enhance robustness against numerical round-off errors.
- Partitioned Variant (PRKCD): For composite functions (e.g., a quadratic term plus a non-linear perturbation), PRKCD evaluates the expensive non-linear gradient only once per iteration, regardless of the number of internal stages.
As shown in the figure above, the stability domains $\mathcal{D}_s$ (top panels) and the corresponding stability functions (bottom panel) illustrate how the method maintains stability over a wide range of eigenvalues. The damping parameter $\eta$ plays a crucial role in shaping these domains to ensure numerical stability.
Experimental Results
The authors evaluated RKCD and PRKCD across several challenging benchmarks:
- Synthetic Quadratics: Tests on random matrices from a Wishart distribution confirmed that RKCD nearly achieves the theoretical lower bound for first-order methods.
- Regularized Logistic Regression: On the Madelon UCI dataset ($d=500, m=2000$), which is highly ill-conditioned ($\kappa \approx 10^9$), RKCD demonstrated superior convergence.
- Image Processing: In Total Variation (TV) denoising tasks, RKCD reached high-accuracy solutions ($10^{-10}$ error) significantly faster than both GD and Nesterov’s Accelerated Gradient Descent (AGD).
- Scientific Computing: The method proved effective in solving discretized nonlinear elliptic PDEs.
A key finding is that RKCD's suboptimality compared to the Conjugate Gradient (CG) method actually decreases as the problem's condition number worsens, making it particularly effective for the most difficult optimization tasks.
Discussion and Limitations
RKCD provides a momentum-free path to acceleration, outperforming Nesterov’s AGD in various numerical experiments. However, some practical considerations remain:
- Parameter Tuning: Unlike GD which only requires an upper bound $L$ on the Hessian's eigenvalues, RKCD requires estimates for both the upper bound $L$ and the lower bound $\ell$.
- Scope of Theory: While empirical performance is strong for general functions, current proofs for optimal convergence rates are restricted to quadratic functions and their perturbations.
- Future Directions: Extending the method to general convex problems (where $\ell = 0$) and adapting it for stochastic optimization are identified as primary areas for future research.
Summary updated