提出两种压缩方法,让分数阶优化更快更高效。
Fast and Scalable Caputo Fractional Gradient Descent via Perturbation-Preserving Memory Compression

- 用指数和与分层卷积压缩历史梯度记忆
- 保持线性收敛,误差可控下仍稳定下降
- 适合大规模非凸优化问题的快速求解
分数阶梯度下降(FGD)通过Caputo型算子引入长程记忆,在病态和非凸优化中表现出更好的稳定性。然而其实际应用受限于历史依赖卷积的高计算开销,随迭代次数呈二次增长。本文通过将分数阶下降方向表示为过去梯度的离散卷积,统一了方法视角。提出两种互补机制降低内存项开销:一是用指数和(SOE)近似幂律核,实现递归更新;二是新提出的二进制分层离散卷积(DHDC),通过多尺度聚合压缩梯度历史。将这些近似视为理想Caputo算子的扰动,分析压缩对优化动态的影响。在标准μ-强凸性和L-光滑性假设下,证明只要近似误差受控,算法仍具单调下降和线性收敛性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。