Understanding Machine Learning: From Theory to Algorithms

300 Online Learning

21.3 Online Convex Optimization

In Chapter 12 we studied convex learning problems and showed learnability

results for these problems in the agnostic PAC learning framework. In this section

we show that similar learnability results hold for convex problems in the online

learning framework. In particular, we consider the following problem.

Online Convex Optimization

definitions:

hypothesis classH ; domainZ ; loss function`:H×Z→R

assumptions:

His convex

∀z∈Z,`(·,z) is a convex function

fort= 1, 2 ,...,T

learner predicts a vectorw(t)∈H

environment responds withzt∈Z

learner suffers loss`(w(t),zt)

As in the online classification problem, we analyze theregretof the algorithm.

Recall that the regret of an online algorithm with respect to a competing hy-

pothesis, which here will be some vectorw?∈H, is defined as

RegretA(w?,T) =

∑T

t=1

`(w(t),zt)−

∑T

t=1

`(w?,zt). (21.5)

As before, the regret of the algorithm relative to a set of competing vectors,H,

is defined as

RegretA(H,T) = sup

w?∈H

RegretA(w?,T).

In Chapter 14 we have shown that Stochastic Gradient Descent solves convex

learning problems in the agnostic PAC model. We now show that a very similar

algorithm, Online Gradient Descent, solves online convex learning problems.

Online Gradient Descent

parameter:η > 0

initialize: w(1)= 0

fort= 1, 2 ,...,T

predictw(t)

receiveztand letft(·) =`(·,zt)

choosevt∈∂ft(w(t))

update:

1.w(t+^12 )=w(t)−ηvt

2.w(t+1)= argminw∈H‖w−w(t+^12 )‖