Revision as of 16:18, 10 December 2024

Author: Aolei Cao (ac3237), Ziyang Li (zl986), Junjia Liang (jl4439) (ChemE 6800 Fall 2024)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

Problem Formulation

Minimize the loss function f(x), where x ∈ ℝⁿ and x is the weight vector to be optimized.

2. Parameters

Gradient:
G_t = ∇f(x_t-1)
Second moment estimate:
Ĥ_Vt = Ĥ_β2t Ĥ_Vt-1 + (1 - Ĥ_β2t)(G_t² + ε₁ 1ₙ)
- Ĥ_Vt is the running average of the squared gradient.
- Ĥ_β2t is the corrected decay parameter.
- ε₁ is a regularization constant.
Step size:
α_t = max(ε₂, RMS(x_t-1)) ρ_t
- ρ_t is the relative step size.
- ε₂ is a regularization constant.
- RMS is the root mean square, defined as:
  u_xt = -g_xt / √Ĥ_vxt
  
  RMS(U_t) = RMS_{x ∈ X}(u_xt) = √Mean_{x ∈ X}(g_xt² / Ĥ_vxt)

3. Problem Formulation

Adafactor for Weighted Vectors

Inputs:

Initial point: X₀ ∈ ℝⁿ
Relative step sizes: ρ_t for t = 1 to T
Second moment decay: Ĥ_β2t for t = 1 to T, with Ĥ_β21 = 0
Regularization constants: ε₁, ε₂
Clipping threshold: d

Algorithm:

For t = 1 to T:
- Compute adaptive step size:
  α_t = max(ε₂, RMS(X_t-1)) ρ_t
- Compute gradient:
  G_t = ∇f_t(X_t-1)
- Update second moment estimate:
  Ĥ_Vt = Ĥ_β2t Ĥ_Vt-1 + (1 - Ĥ_β2t)(G_t² + ε₁ 1ₙ)
- Compute normalized gradient:
  U_t = G_t / √Ĥ_Vt
- Apply clipping:
  Ĥ_{U_t} = U_t / max(1, RMS(U_t) / d)
- Update parameter:
  X_t = X_t-1 - α_t Ĥ_{U_t}

Adafactor for Weighted Matrices

Inputs:

Initial point: X₀ ∈ ℝⁿ × ℝ^m
Relative step sizes: ρ_t for t = 1 to T
Second moment decay: Ĥ_β2t for t = 1 to T, with Ĥ_β21 = 0
Regularization constants: ε₁, ε₂
Clipping threshold: d

Algorithm:

For t = 1 to T:
- Compute adaptive step size:
  α_t = max(ε₂, RMS(X_t-1)) ρ_t
- Compute gradient:
  G_t = ∇f_t(X_t-1)
- Update row-wise second moment:
  R_t = Ĥ_β2t R_t-1 + (1 - Ĥ_β2t)(G_t² + ε₁ 1ₙ 1ₘᵀ) 1ₘ
- Update column-wise second moment:
  C_t = Ĥ_β2t C_t-1 + (1 - Ĥ_β2t) 1ₙᵀ (G_t² + ε₁ 1ₙ 1ₘᵀ)
- Update overall second moment estimate:
  Ĥ_Vt = R_t C_t / (1ₙᵀ R_t)
- Compute normalized gradient:
  U_t = G_t / √Ĥ_Vt
- Apply clipping:
  Ĥ_{U_t} = U_t / max(1, RMS(U_t) / d)
- Update parameter:
  X_t = X_t-1 - α_t Ĥ_{U_t}

@@ Line 5: / Line 5: @@
 == Introduction ==
 == Problem Formulation ==
-=== Objectives ===
+<p>Minimize the loss function <b>f(x)</b>, where <b>x ∈ ℝⁿ</b> and <b>x</b> is the weight vector to be optimized.</p>
-<h1>1. Objective</h1>
+    <h1>2. Parameters</h1>
+    <ul>
+        <li><b>Gradient:</b>
+            <div><i>G<sub>t</sub> = ∇f(x<sub>t-1</sub>)</i></div>
+        </li>
+        <li><b>Second moment estimate:</b>
+            <div><i>Ĥ<sub>Vt</sub> = Ĥ<sub>β2t</sub> Ĥ<sub>Vt-1</sub> + (1 - Ĥ<sub>β2t</sub>)(G<sub>t</sub>² + ε₁ 1ₙ)</i></div>
+            <ul>
+                <li><i>Ĥ<sub>Vt</sub></i> is the running average of the squared gradient.</li>
+                <li><i>Ĥ<sub>β2t</sub></i> is the corrected decay parameter.</li>
+                <li><i>ε₁</i> is a regularization constant.</li>
+            </ul>
+        </li>
+        <li><b>Step size:</b>
+            <div><i>α<sub>t</sub> = max(ε₂, RMS(x<sub>t-1</sub>)) ρ<sub>t</sub></i></div>
+            <ul>
+                <li><i>ρ<sub>t</sub></i> is the relative step size.</li>
+                <li><i>ε₂</i> is a regularization constant.</li>
+                <li><i>RMS</i> is the root mean square, defined as:
+                    <div><i>u<sub>xt</sub> = -g<sub>xt</sub> / √Ĥ<sub>vxt</sub></i></div>
+                    <div><i>RMS(U<sub>t</sub>) = RMS<sub>x ∈ X</sub>(u<sub>xt</sub>) = √Mean<sub>x ∈ X</sub>(g<sub>xt</sub>² / Ĥ<sub>vxt</sub>)</i></div>
+                </li>
+            </ul>
+        </li>
+    </ul>
+    <h1>3. Problem Formulation</h1>
+    <h2>Adafactor for Weighted Vectors</h2>
+    <h3>Inputs:</h3>
+    <ul>
+        <li>Initial point: <i>X₀ ∈ ℝⁿ</i></li>
+        <li>Relative step sizes: <i>ρ<sub>t</sub></i> for <i>t = 1</i> to <i>T</i></li>
+        <li>Second moment decay: <i>Ĥ<sub>β2t</sub></i> for <i>t = 1</i> to <i>T</i>, with <i>Ĥ<sub>β21</sub> = 0</i></li>
+        <li>Regularization constants: <i>ε₁, ε₂</i></li>
+        <li>Clipping threshold: <i>d</i></li>
+    </ul>
+    <h3>Algorithm:</h3>
+    <ul>
+        <li>For <i>t = 1</i> to <i>T</i>:
+            <ul>
+                <li>Compute adaptive step size:
+                    <div><i>α<sub>t</sub> = max(ε₂, RMS(X<sub>t-1</sub>)) ρ<sub>t</sub></i></div>
+                </li>
+                <li>Compute gradient:
+                    <div><i>G<sub>t</sub> = ∇f<sub>t</sub>(X<sub>t-1</sub>)</i></div>
+                </li>
+                <li>Update second moment estimate:
+                    <div><i>Ĥ<sub>Vt</sub> = Ĥ<sub>β2t</sub> Ĥ<sub>Vt-1</sub> + (1 - Ĥ<sub>β2t</sub>)(G<sub>t</sub>² + ε₁ 1ₙ)</i></div>
+                </li>
+                <li>Compute normalized gradient:
+                    <div><i>U<sub>t</sub> = G<sub>t</sub> / √Ĥ<sub>Vt</sub></i></div>
+                </li>
+                <li>Apply clipping:
+                    <div><i>Ĥ<sub>U<sub>t</sub></i> = U<sub>t</sub> / max(1, RMS(U<sub>t</sub>) / d)</i></div>
+                </li>
+                <li>Update parameter:
+                    <div><i>X<sub>t</sub> = X<sub>t-1</sub> - α<sub>t</sub> Ĥ<sub>U<sub>t</sub></i></div>
+                </li>
+            </ul>
+        </li>
+    </ul>
+    <h2>Adafactor for Weighted Matrices</h2>
+    <h3>Inputs:</h3>
+    <ul>
+        <li>Initial point: <i>X₀ ∈ ℝⁿ × ℝ<sup>m</sup></i></li>
+        <li>Relative step sizes: <i>ρ<sub>t</sub></i> for <i>t = 1</i> to <i>T</i></li>
+        <li>Second moment decay: <i>Ĥ<sub>β2t</sub></i> for <i>t = 1</i> to <i>T</i>, with <i>Ĥ<sub>β21</sub> = 0</i></li>
+        <li>Regularization constants: <i>ε₁, ε₂</i></li>
+        <li>Clipping threshold: <i>d</i></li>
+    </ul>
+    <h3>Algorithm:</h3>
+    <ul>
+        <li>For <i>t = 1</i> to <i>T</i>:
+            <ul>
+                <li>Compute adaptive step size:
+                    <div><i>α<sub>t</sub> = max(ε₂, RMS(X<sub>t-1</sub>)) ρ<sub>t</sub></i></div>
+                </li>
+                <li>Compute gradient:
+                    <div><i>G<sub>t</sub> = ∇f<sub>t</sub>(X<sub>t-1</sub>)</i></div>
+                </li>
+                <li>Update row-wise second moment:
+                    <div><i>R<sub>t</sub> = Ĥ<sub>β2t</sub> R<sub>t-1</sub> + (1 - Ĥ<sub>β2t</sub>)(G<sub>t</sub>² + ε₁ 1ₙ 1ₘᵀ) 1ₘ</i></div>
+                </li>
+                <li>Update column-wise second moment:
+                    <div><i>C<sub>t</sub> = Ĥ<sub>β2t</sub> C<sub>t-1</sub> + (1 - Ĥ<sub>β2t</sub>) 1ₙᵀ (G<sub>t</sub>² + ε₁ 1ₙ 1ₘᵀ)</i></div>
+                </li>
+                <li>Update overall second moment estimate:
+                    <div><i>Ĥ<sub>Vt</sub> = R<sub>t</sub> C<sub>t</sub> / (1ₙᵀ R<sub>t</sub>)</i></div>
+                </li>
+                <li>Compute normalized gradient:
+                    <div><i>U<sub>t</sub> = G<sub>t</sub> / √Ĥ<sub>Vt</sub></i></div>
+                </li>
+                <li>Apply clipping:
+                    <div><i>Ĥ<sub>U<sub>t</sub></i> = U<sub>t</sub> / max(1, RMS(U<sub>t</sub>) / d)</i></div>
+                </li>
+                <li>Update parameter:
+                    <div><i>X<sub>t</sub> = X<sub>t-1</sub> - α<sub>t</sub> Ĥ<sub>U<sub>t</sub></i></div>
+                </li>
+            </ul>
+        </li>
+    </ul>
 == Numerical Examples ==

Adafactor: Difference between revisions

Revision as of 16:18, 10 December 2024

Contents

Introduction

Problem Formulation

2. Parameters

3. Problem Formulation

Adafactor for Weighted Vectors

Inputs:

Algorithm:

Adafactor for Weighted Matrices

Inputs:

Algorithm:

Numerical Examples

Applications

Conclusion

Reference

Navigation menu