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.

\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.

Convex

*l*_{hinge}(*h*_{w}, (**x**, *y*)) = [1 − *y*⟨**x**, **y**⟩]_{+}

where [*a*]_{+} = *m**a**x*(*a*, 0)

Hard-result