Had larger regret follow the regularized leader algorithmin this section

CS229T/STATS231: Statistical Learning Theory

Lecturer: Tengyu Ma Scribe: Maxwell Allman, Faidra Monachou

“Follow The Leader” (FTL) algorithm

On each iteration t = 1, . . . , T, we select

possible regret. In today’s lecture, our goal is to fix FTL.

2 “Be The Leader” Algorithm

would end up with zero regret.

Lemma 1 (BTL). For the regret of the BTL algorithm, it holds that

�ft(wt+1) − min w∈Ω�ft(w) = f1(w2) + . . . + fT (wT+1) − (f1(wT+1) + . . . + fT (wT+1)) =

= f1(w2) + . . . + fT−1(wT ) − (f1(wT+1) + . . . + fT−1(wT+1))

	ft(wt+1) − min w∈Ω	T �	ft(w) ≤ f1(w2) + . . . +	fT−1(wT ) − (f1(wT ) + . . . +
	ft(wt+1) − min w∈Ω	T �

By recursively repeating the same argument, we eventually get that

�	ft(wt+1) − min w∈Ω	�	ft(w) ≤ f1(w2) − f1(w3) ≤ 0.

R =	T �	ft(wt) − min w∈Ω	T �	ft(w) ≤

In this section, we introduce and study the properties of the “Follow the Regularized Leader”(FTRL) algorithm.

“Follow The Regularized Leader” (FTRL) algorithm On each iteration t = 1, . . . , T, we select

	�		(3)

∀x, y, f(x) − f(y) ≥ ⟨∇f(y), x − y⟩.

We expand this property to define the notion of a-stong convexity.

	(4)

and	G(w) ≜	F(w) ≜		�
and		t �
Then it follows that		t �

		wt+1 = arg min ω∈ΩG(w).

Lemma 3. Suppose F is α-strongly convex, f is convex, and let

	w′= arg min z	G(z).

Similarly, we get	F(w′) − F(w) ≥α 2\|\|w − w′\|\|2 2.	(5)
Similarly, we get		(6)

Definition 4. F is α-strongly convex w.r.t. norm || · || on Ω if ∀x, y ∈ Ω,

f(x) − f(y) ≥ ⟨∇f(x), x − y⟩ +α 2||x − y||2.

Then,	w′= arg min z
Then,

We can now bound the regret of the FTRL algorithm.

Theorem 6 (Regret bound of FTRL). Suppose φ is 1-strongly convex w.r.t. || · ||. Then,

R ≤D η+ η	T �


gives	R ≤ O(G√TD).

Proof. Let

Then, using the BTL lemma,

T T T

�ft(wt) − arg min�ft(w) ≥ f0(w0) +�ft(wt) −�ft(w∗)

=�ft(wt) −�ft(w∗) + f0(w0) − f0(w∗).

By Lemma 5 with F =�t−1 i=0fi, G = �t i=0fi, f = ft and α = 1

T
η, we get that

�