The regret is the cost of not choosing the best option at a given time.
where u ∈ S is the best solution.
with f : S → ℛ+, a "measurement of the complexity" of vector in S, and L ∈ ℛ+ related to a generalized Lipschitz property.
Convex
lhinge(hw, (x, y)) = [1 − y⟨x, y⟩]+
where [a]+ = max(a, 0)
Hard-result