Tighter Regret Bounds for Shampoo = Shampoo에 대한 개선된 후회 상계

다국어 초록 (Multilingual Abstract)

Shampoo is a Kronecker-factored second-order optimizer that is widely used for large-scale deep learning, yet its existing regret guarantee is qualitatively looser than those of Adagrad and scales unfavorably with dimension, partly due to an explicit dependence on the gradient rank.

In this work we develop a tighter online convex optimization analysis for structured preconditioners. Our first contribution is a refined regret bound for preconditioned online gradient descent when the preconditioner admits a Kronecker product structure $H_t=L_t\otimes R_t$ with increasing factors, yielding a stability term controlled by $\lambda_{\max}(L_T)\mathrm{tr}(R_T)+\mathrm{tr}(L_T)\lambda_{\max}(R_T)$.

Specializing to Shampoo gives a new tighter data-dependent regret bound that removes the $\sqrt{r_G}$ factor from the original analysis and adapts to the effective ranks of the left and right accumulators.

We further compare our guarantee with bounds for Adagrad (full), Adagrad-Norm, and One-sided Shampoo, showing that the new bound is competitive and can be strictly sharper on certain sequences.

To the best of our knowledge, this is the first work to provide a tighter regret bound for Shampoo that compares similarly with the regret bounds for Adagrad and One-sided Shampoo.

국문 초록 (Abstract)

Shampoo는 대규모 딥러닝 학습에서 널리 사용되는 Kronecker 곱 기반의 2차(곡률 활용) 최적화 기법이지만, 기존의 후회(regret) 상계는 Adagrad에 비해 느슨하며, 특히 그래디언트의 랭크에 대한 의존성 때문에 차원에 불리하게 의존한다는 문제가 있다.

본 연구에서는 preconditioner가 특정 구조를 갖는 경우에 대한 더 좋은 온라인 볼록 최적화 분석을 제시한다. 첫째, preconditioner가 Kronecker 곱 구조 $H_t = L_t \otimes R_t$를 가지며 두 항 $L_t, R_t$가 Lowner 순서에서 증가하는 경우의 Preconditioned Online Gradient Descent에 대해 정교한 후회 상계를 도출한다. 이때 stability 항은 $\lambda_{\max}(L_T)\mathrm{tr}(R_T)+\mathrm{tr}(L_T)\lambda_{\max}(R_T)$.로 제어된다.

이를 Shampoo에 적용하여, 기존 분석에 존재하던 $\sqrt{r_G}$ 항을 제거하고 좌/우 그래디언트 누적 행렬의 유효 랭크(effective rank)에 적응하는 더 좋은 후회 상계를 얻는다.

또한 Adagrad (full), Adagrad-Norm, One-sided Shampoo 등과 우리의 후회 상계를 비교하여, 제안한 새로운 상계가 이 알고리즘들의 상계와 비교하여 경쟁력 있으며 특정 그래디언트 순열에서는 더 날카로울 수 있음을 보인다.

본 연구는 Adagrad, One-sided Shampoo의 후회 상계들과 유사한 수준으로 비교 가능한 Shampoo에 대한 더 좋은 후회 상계를 최초로 제시한다.

목차 (Table of Contents)

• Abstract i
• Contents ii
• 1 Introduction 1
• 2 Preliminaries 3
• 2.1 Online Convex Optimization 3
• 2.2 Adaptive Online Mirror Descent 4
• 2.3 Mathematical Preliminaries 6
• 2.4 Shampoo 7
• 2.5 The Problem with Shampoo’s Regret Bound 8
• 2.6 Previous Work 10
• 3 Tighter Regret Analysis for Shampoo 13
• 3.1 Tighter Regret Bound for Structured Preconditioners 13
• 3.2 Tighter Regret Bound for Shampoo 16
• 3.3 Comparison of Regret Bounds 18
• 4 Conclusion 21
• Appendix 23
• Bibliography 26
• Abstract (In Korean) 30