Parameter-free version of Adaptive Gradient Methods for Strongly-Convex Functions

Theorem: Suppose all loss functions are $λ - S C$ , then OGD with $η_{t} = \frac{1}{λ t}$ achieves $R e g_{T}^{A} \leq \frac{G^{2}}{λ} (1 + \log T)$

Proof:

Step 1: $\forall t \in [T]$ , find upper bound for $f_{t} (w_{t}) - f_{t} (w^{*})$

\begin{aligned} f_{t} (w_{t}) - f_{t} (w^{*}) & \leq \nabla f_{t} (w_{t})^{T} (w_{t} - w^{*}) - \frac{λ}{2} ‖ w_{t} - w^{*} ‖_{2}^{2} & (λ - S C) \\ \leq \frac{‖ w_{t} - w^{*} ‖_{2}^{2} - ‖ w_{t + 1} - w^{*} ‖_{2}^{2}}{2 η_{t}} + \frac{η_{t}}{2} G^{2} - \frac{λ}{2} ‖ w_{t} - w^{*} ‖_{2}^{2} \end{aligned}

Step 2: find $R e g_{T}^{OGD}$

\begin{aligned} R e g_{T}^{OGD} & = \sum_{t = 1}^{T} (f_{t} (w_{t}) - f_{t} (w^{*})) \\ = \sum_{t = 1}^{T} (\frac{‖ w_{t} - w^{*} ‖_{2}^{2} - ‖ w_{t + 1} - w^{*} ‖_{2}^{2}}{2 η_{t}} + \frac{η_{t}}{2} G^{2} - \frac{λ}{2} ‖ w_{t} - w^{*} ‖_{2}^{2}) \\ = \sum_{t = 2}^{T} ‖ w_{t} - w^{*} ‖_{2}^{2} (\frac{1}{2 η_{t}} - \frac{1}{2 η_{t - 1}}) + ‖ w_{1} - w^{*} ‖_{2}^{2} \frac{1}{2 η_{1}} - ‖ w_{T + 1} - w^{*} ‖_{2}^{2} \frac{1}{2 η_{T}} + G^{2} \sum_{t = 1}^{T} \frac{η_{t}}{2} - \sum_{t = 1}^{T} \frac{λ}{2} ‖ w_{t} - w^{*} ‖_{2}^{2} \\ = \sum_{t = 2}^{T} ‖ w_{t} - w^{*} ‖_{2}^{2} (\frac{1}{2 η_{t}} - \frac{1}{2 η_{t - 1}} - \frac{λ}{2}) + ‖ w_{1} - w^{*} ‖_{2}^{2} \frac{1}{2 η_{1}} - ‖ w_{T + 1} - w^{*} ‖_{2}^{2} \frac{1}{2 η_{T}} + G^{2} \sum_{t = 1}^{T} \frac{η_{t}}{2} - \frac{λ}{2} ‖ w_{1} - w^{*} ‖_{2}^{2} \end{aligned}

Note that $η_{t} = 1 / (λ t)$ . Thus, $\frac{1}{2 η_{t}} - \frac{1}{2 η_{t - 1}} - \frac{λ}{2} = (λ t - λ (t - 1) - λ) / 2 = 0.$ Moreover, $\frac{1}{2 η_{1}} - \frac{λ}{2} = 0.$ Thus, we get

\begin{aligned} R e g_{T}^{OGD} & = \sum_{t = 1}^{T} (f_{t} (w_{t}) - f_{t} (w^{*})) \\ \leq G^{2} \sum_{t = 1}^{T} \frac{η_{t}}{2} = \frac{G^{2}}{2 λ} \sum_{t = 1}^{T} \frac{1}{t} \leq \frac{G^{2}}{λ} (\log T + 1) . \end{aligned}

The algorithm has a hyperparameter $η$ which in turn depends on $λ$ . We propose a parameter-free version which is also data-dependent, hence achieving faster convergence. Our algorithm is inspired from AdaGrad and MALER. We show that this algorithm has $R e g_{T}^{A} = O (\log T)$ .

Full paper on arXiv.