Fast and Scalable Caputo Fractional Gradient Descent via Perturbation-Preserving Memory Compression
Machine LearningNeural and Evolutionary Computing
Summary
The authors study a type of optimization called fractional gradient descent (FGD), which remembers past steps to help solve tricky problems more reliably. However, FGD is slow because it needs to consider all previous steps, which gets harder over time. To fix this, the authors propose two new ways to speed it up by approximating and compressing this memory without losing important information. They show that their faster methods still keep the optimization working well under common assumptions about the problem's shape. This makes FGD more practical for real use.
Authors
Hwanseo Lee, Junseo Lee, Hyunju Kim
Abstract
Fractional gradient descent (FGD) incorporates long-range memory through Caputo-type operators and has been shown to improve stability in ill-conditioned and nonconvex optimization problems. Despite these advantages, its practical use remains limited, mainly due to the high computational cost of evaluating history-dependent convolutions, which scales quadratically with the number of iterations. In this paper, we focus on making Caputo-based optimization computationally viable without sacrificing its intrinsic memory structure. We begin by expressing the fractional descent direction as a discrete convolution over past gradients, which provides a unified view of the method. Based on this formulation, we introduce two complementary mechanisms to reduce the cost of the memory term. The first uses a sum-of-exponentials (SOE) approximation of the power-law kernel, leading to efficient recursive updates. The second approach, newly proposed in this paper as dyadic hierarchical discrete convolution (DHDC), compresses the gradient history through a multiscale aggregation strategy. Rather than treating these approximations as purely numerical accelerations, we interpret them as perturbations of the ideal Caputo operator. This viewpoint allows us to analyze how the compressed memory affects the optimization dynamics. Under standard $μ$-strong convexity and $L$-smoothness assumptions, we show that the resulting method still exhibits monotone descent and linear convergence, provided that the approximation error remains controlled.