1 Regret

The regret is the cost of not choosing the best option at a given time.

R(\mathbf{u}, T) =\sum_{t=1}^T g_t(\mathbf{w_t}) - \sum_{t=1}^T g_t(\mathbf{u})

where u ∈ S is the best solution.

1.1 Boundary :

\forall \mathbf{u} \in S, R(\mathbf{u}, T) \leq (f(\mathbf{u}) + L) \sqrt{T}

with f : S → ℛ+, a "measurement of the complexity" of vector in S, and L ∈ ℛ+ related to a generalized Lipschitz property.

2 Hinge loss

Convex

lhinge(hw, (x, y)) = [1 − y⟨x, y⟩]+

where [a]+ = max(a, 0)

3 zero-one

Hard-result