提出随机子空间加速梯度法,提升优化效率。
Randomized Subspace Nesterov Accelerated Gradient

- 基于低维投影梯度设计新优化算法
- 在矩阵光滑条件下实现加速收敛
- 适合通信受限或自动微分场景
随机子空间方法通过仅使用低维投影梯度信息降低一阶优化成本,适用于前向模式自动微分和通信受限场景。尽管全梯度和坐标基方法的Nesterov加速已有充分研究,但针对一般子空间投影梯度、且能在查询复杂度上超越全维Nesterov加速的方法在技术上极具挑战。本文在矩阵光滑性和通用投影矩假设下,为光滑凸与光滑强凸优化问题构建了随机子空间Nesterov加速梯度方法。关键技术是适配矩阵光滑性的三序列构造,该方法在全维情况下可还原经典Nesterov方法。理论分析建立了加速的查询复杂度保证,并明确揭示了矩阵光滑性与投影分布对复杂度的影响。该框架统一比较不同投影族,识别出何时随机子空间加速优于全维Nesterov加速。
原文摘要 · Abstract (English)
Randomized-subspace methods reduce the cost of first-order optimization by using only low-dimensional projected-gradient information, a feature that is attractive in forward-mode automatic differentiation and communication-limited settings. While Nesterov acceleration is well understood for full-gradient and coordinate-based methods, obtaining accelerated methods for general subspace sketches that use only projected-gradient information and can improve over full-dimensional Nesterov acceleration in oracle complexity is technically nontrivial. We develop randomized-subspace Nesterov accelerated gradient methods for smooth convex and smooth strongly convex optimization under matrix smoothness and generic sketch moment assumptions. The key technical ingredient is a three-sequence formulation tailored to matrix smoothness, which recovers the corresponding classical Nesterov methods in the full-dimensional case. The resulting theory establishes accelerated oracle-complexity guarantees and makes explicit how matrix smoothness and the sketch distribution enter the complexity. It also provides a unified basis for comparing sketch families and identifying when randomized-subspace acceleration improves over full-dimensional Nesterov acceleration in oracle complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。