统一分析自适应优化中结构化预条件器，发现更简化的算法反而更优。
Structured Preconditioners in Adaptive Optimization: A Unified Analysis
- 构建统一框架分析多种结构化预条件算法的性能。
- 一端式Shampoo理论与实验均优于原始全矩阵AdaGrad。
- 挑战了复杂度越高越好的直觉，适合优化算法研究者。
我们提出一种新的统一分析方法，适用于具有结构化预条件器（如层间、对角、克罗内克分解）的广义自适应优化算法，涵盖在线回归最小化和离线凸优化问题。该分析不仅为对角AdaGrad、全矩阵AdaGrad及AdaGrad-Norm等重要算法提供了匹配的收敛速率，还揭示了一端式Shampoo相比原版Shampoo具有更优的收敛速度。值得注意的是，通常认为更结构化的预条件器（如对角AdaGrad、AdaGrad-Norm）是全矩阵AdaGrad在空间与计算效率上的近似，旨在通过更好逼近提升性能。然而，我们的统一分析挑战了这一主流观点，揭示出尽管更结构化的预条件器每步所需空间与计算更少，却可能优于其非结构化版本。为此，我们证明了一端式Shampoo虽远比全矩阵AdaGrad廉价，却能在理论上和实验上实现更优表现。
原文摘要 · Abstract (English)
We present a novel unified analysis for a broad class of adaptive optimization algorithms with structured (e.g., layerwise, diagonal, and kronecker-factored) preconditioners for both online regret minimization and offline convex optimization. Our analysis not only provides matching rate to several important structured preconditioned algorithms including diagonal AdaGrad, full-matrix AdaGrad, and AdaGrad-Norm, but also gives an improved convergence rate for a one-sided variant of Shampoo over that of original Shampoo. Interestingly, more structured preconditioners (e.g., diagonal Adagrad, AdaGrad-Norm which use less space and compute) are often presented as computationally efficient approximations to full-matrix Adagrad, aiming for improved optimization performance through better approximations. Our unified analysis challenges this prevailing view and reveals, perhaps surprisingly, that more structured preconditioners, despite using less space and computation per step, can outperform their less structured counterparts. To demonstrate this, we show that one-sided Shampoo, which is relatively much cheaper than full-matrix AdaGrad could outperform it both theoretically and experimentally.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。