Fast and Scalable Caputo Fractional Gradient Descent via Perturbation-Preserving Memory Compression

2026-07-16 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, quick

Summary

A new paper introduces methods to overcome the high computational cost of Caputo Fractional Gradient Descent (FGD), an optimization technique known for improving stability in ill-conditioned and nonconvex problems. FGD's practical use is limited by its quadratic scaling with iterations due to history-dependent convolutions. The authors reformulate the fractional descent direction as a discrete convolution over past gradients. To reduce memory costs, they propose two complementary mechanisms: a sum-of-exponentials (SOE) approximation of the power-law kernel, enabling efficient recursive updates, and a novel Dyadic Hierarchical Discrete Convolution (DHDC) for multiscale aggregation of gradient history. These approximations are analyzed as perturbations of the ideal Caputo operator. The resulting method, under standard μ-strong convexity and L-smoothness assumptions, demonstrates monotone descent and linear convergence, provided the approximation error is controlled.

Key takeaway

For research scientists developing optimization algorithms for ill-conditioned or nonconvex problems, this work offers a path to scale Caputo Fractional Gradient Descent. You can now consider FGD's stability benefits without incurring prohibitive quadratic computational costs. Implement the proposed sum-of-exponentials or Dyadic Hierarchical Discrete Convolution techniques. This achieves efficient, linearly convergent optimization, provided approximation errors are carefully managed.

Key insights

Caputo Fractional Gradient Descent's high computational cost can be mitigated by perturbation-preserving memory compression, maintaining convergence guarantees.

Principles

• FGD enhances stability in complex optimization.
• Memory compression can maintain optimization dynamics.
• Controlled approximation error ensures linear convergence.

Method

Reformulate fractional descent as a discrete convolution. Reduce memory cost using sum-of-exponentials (SOE) approximation for recursive updates and Dyadic Hierarchical Discrete Convolution (DHDC) for multiscale gradient history compression.

In practice

• Apply FGD to ill-conditioned problems.
• Consider FGD for nonconvex optimization.
• Implement SOE or DHDC for FGD acceleration.

Topics

• Caputo Fractional Gradient Descent
• Optimization Algorithms
• Memory Compression
• Sum-of-Exponentials
• Dyadic Hierarchical Discrete Convolution
• Nonconvex Optimization

Best for: AI Scientist, Research Scientist

Related on AIssential

• Functional Gradient Descent with Adaptive Representations — Adaptive representation in functional gradient descent ensures convergence to global minimizers by dynamically refining gradient approximations.
• Memory-Efficient LLM Training with Dynamic Sparsity: From Stability to Practical Scaling — SMET stabilizes dynamic sparse training for LLMs by addressing cold-start issues and optimizing memory, making sparse pre-training practical.
• Communication-Efficient, 2D Parallel Stochastic Gradient Descent for Distributed-Memory Optimization — HybridSGD combines 1D s-step SGD and FedAvg via a 2D processor grid for communication-efficient distributed optimization.
• Gradient descent at the Edge of Stability: free energy model and kinetic description of the two-layer network — A new model tracks average trajectory and oscillation covariance, revealing an effective free energy for Edge of Stability dynamics.
• On the Oracle Complexity of Interpolation-Based Gradient Descent — PPI-GD improves gradient descent oracle complexity by approximating gradients via polynomial interpolation over data domain patches.
• Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent — ScaledGD offers provably fast, condition-number-independent convergence for low-rank tensor estimation using t-SVD.

See Counsel's argued verdicts on the open AI decisions leaders are weighing →

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.