通过数据域插值提升梯度下降效率，降低优化复杂度。
On the Oracle Complexity of Interpolation-Based Gradient Descent
- 用数据空间中的多项式插值近似梯度，减少梯度查询次数。
- 在数据维度为样本数的多对数函数时，优于多种梯度下降变体。
- 适用于光滑损失函数场景，适合追求高效优化的研究者。
近期研究表明，可利用训练数据中经验风险最小化（ERM）损失函数的光滑性，而非优化参数空间的光滑性，来改进梯度下降（GD）方法的预言机复杂度。本文提出一种不精确梯度方法——分段多项式插值梯度下降（PPI-GD），每轮迭代中在数据域等距采样点查询一阶预言机，构建局部数据块上梯度样本的多项式插值，并据此近似全梯度。我们在数据空间维度为样本数的多对数函数条件下，分析了PPI-GD在强凸与非凸损失函数下的预言机复杂度，发现当损失函数足够光滑时，在关键场景下性能优于多个经典GD变体。此外，我们的分析将双三次样条误差分析技术推广至d维张量积多项式插值，对插值分析本身可能具有独立价值。
原文摘要 · Abstract (English)
Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of $d$-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。