Online Learning:Is it(provably)solvable? In general,the online learning formulation is hard to solve. At each round t=1,2,... (1)the player first picks a model wtEW; (2)and simultaneously environments pick an online function fr:W->R; (3)the player suffers loss fi(wt),observes some information about fr and updates the model. A Trackable Case:Online Convex Optimization requiring feasible domain and online functions to be convex Advanced Optimization(Fall 2023) Lecture 5.Online Convex Optimization 16
Advanced Optimization (Fall 2023) Lecture 5. Online Convex Optimization 16 Online Learning: Is it (provably) solvable? • In general, the online learning formulation is hard to solve. A Trackable Case: Online Convex Optimization requiring feasible domain and online functions to be convex
Online Learning:Is it(provably)solvable? In general,the online learning formulation is hard to solve. At each round t=l,2,.· (1)the player first picks a modelwew (2)and simultaneously environments pick an online function f:W-R (3)the player suffers loss fi(w),observes some information about fi and updates the model. A Trackable Case:Online Convex Optimization requiring feasible domain and online functions to be convex Advanced Optimization(Fall 2023) Lecture 5.Online Convex Optimization 17
Advanced Optimization (Fall 2023) Lecture 5. Online Convex Optimization 17 Online Learning: Is it (provably) solvable? • In general, the online learning formulation is hard to solve. A Trackable Case: Online Convex Optimization requiring feasible domain and online functions to be convex
Online Convex Optimization ·OCO framework feasible domain is a convex set online functions are convex At each round t=l,2,.… (1)the player first picks a model xt from a convex set Rd; (2)and environments pick an online convex function fi:A-R; (3)the player suffers loss fi(xt),observes some information about f and updates the model. From this point forward,we use x(and )instead of w(and W)for consistency with opt.language. Advanced Optimization(Fall 2023) Lecture 5.Online Convex Optimization 18
Advanced Optimization (Fall 2023) Lecture 5. Online Convex Optimization 18 Online Convex Optimization • OCO framework • feasible domain is a convex set • online functions are convex
OCO:Different Setups At each round t=1,2,... (1)the player first picks a model xt from a convex set CRd; (2)and environments pick an online convex function f:->R; (3)the player suffers loss fi(xt),observes some information about f and updates the model. on the feedback information: full information partial information -full information:observe entire f(or at least gradient Vfi(x)) partial information (bandits):observe function value fi(xt)only less information horse racing multi-armed bandits Advanced Optimization(Fall 2023) Lecture 5.Online Convex Optimization 19
Advanced Optimization (Fall 2023) Lecture 5. Online Convex Optimization 19 OCO: Different Setups on the feedback information: less information full information horse racing partial information multi-armed bandits
OCO:Different Setups At each round t=l,2,· (1)the player first picks a model xt from a convex set CRd; (2)and environments pick an online convex function f:->R; (3)the player suffers loss fi(xt),observes some information about ft and updates the model. on the difficulty of environments: oblivious adversary adaptive adversary -stochastic setting less restricted adversarial setting oblivious but harder adaptive examination interview (non-oblivious) Advanced Optimization(Fall 2023) Lecture 5.Online Convex Optimization 20
Advanced Optimization (Fall 2023) Lecture 5. Online Convex Optimization 20 OCO: Different Setups less restricted but harder oblivious adversary examination interview adaptive adversary on the difficulty of environments: - stochastic setting - adversarial setting oblivious adaptive (non-oblivious)