Introduction to Online Convex Optimization

1 Introduction to Online Convex OptimizationSecond EditionElad [ ] 19 Dec 2021ii% - * - & . /W* W= ;* # % &( ! 3 XW% *"..you shall research and meditate therein day and " Yehoshua 1:8iiiTo my family: Dana, Hadar, Yoav, Oded and Deluca, EH [2021] Elad HazanivContentsPrefacexiAcknowledgements xvList of Symbolsxix1 The Online Convex Optimization Setting .. Examples of Problems That Can Be Modeled via Online Con-vex Optimization .. from expert advice .. spam filtering .. shortest paths .. selection .. completion and recommendation systems .. A Gentle Start: Learning from Expert Advice .. weighted majority algorithm .. weighted majority .. Bibliographic Remarks .. Exercises .. 152 Basic Concepts in Convex Basic Definitions and Setup .. onto Convex sets .. to optimality conditions .. Gradient Descent .. Polyak stepsize .. distance to optimality.)

2 Of the Polyak stepsize .. Constrained Gradient/Subgradient Descent .. gradient descent linear convergence .. Reductions to Non-smooth and Non-strongly Convex Functions to smooth, non strongly Convex functions . to strongly Convex , non-smooth functions . to general Convex functions .. Example: Support Vector Machine Training .. Bibliographic Remarks .. Exercises .. 383 First-Order Algorithms for Online Convex Online Gradient Descent .. Lower Bounds .. Logarithmic regret .. gradient descent for strongly Convex functions . Application: Stochastic Gradient Descent .. : stochastic gradient descent for SVM training Bibliographic Remarks .. Exercises .. 534 Second-Order Motivation: Universal Portfolio Selection .. portfolio theory .. portfolio theory .. rebalancing portfolios.

3 Exp-Concave Functions .. Exponentially Weighted Online Convex Optimization .. The Online Newton Step Algorithm .. Bibliographic Remarks .. Exercises .. 695 Regularization Functions .. The RFTL Algorithm and its Analysis .. definition .. regret bound .. Online Mirror Descent .. of lazy OMD and RFTL .. bounds for Mirror Descent .. Application and Special Cases .. Online gradient descent .. multiplicative updates .. Randomized Regularization .. for Convex losses .. for linear cost functions .. for expert advice .. * Adaptive Gradient Descent .. of adaptive regularization .. Bibliographic Remarks .. Exercises .. 986 Bandit Convex The Bandit Convex Optimization Setting .. The Multiarmed Bandit (MAB) Problem .. : simultaneous exploration and exploitation.

4 A Reduction from Limited Information to Full Information . 1: using unbiased estimators .. 2: point-wise gradient estimators .. Online Gradient Descent without a Gradient .. * Optimal regret Algorithms for Bandit Linear Optimization barriers .. near-optimal algorithm .. Bibliographic Remarks .. Exercises .. 1217 Projection-Free Review: Relevant Concepts from Linear Algebra .. Motivation: Recommender Systems .. The Conditional Gradient Method .. : matrix completion via CG .. Projections versus Linear Optimization .. The Online Conditional Gradient Algorithm .. Bibliographic Remarks .. Exercises .. 1388 Games, Duality, and Linear Programming and Duality .. Zero-sum Games and Equilibria .. of von Neumann Theorem and LP duality Proof of von Neumann Theorem .. Approximating Linear Programs.

5 Bibliographic Remarks .. Exercises .. 1499 Learning Theory, Generalization, and Online Convex Statistical Learning Theory .. free lunch? .. of learning problems .. generalization and learnability .. Agnostic Learning using Online Convex Optimization .. : measure concentration and martingales .. of the reduction .. Learning and Compression .. Bibliographic Remarks .. Exercises .. 16610 Learning in Changing A Simple Start: Dynamic regret .. The Notion of Adaptive regret .. Weakly and strongly adaptive algorithms .. Tracking the Best Expert .. Efficient Adaptive regret for Online Convex Optimization .. * Computationally Efficient Methods .. The pruning method .. Bibliographic Remarks .. Exercises .. 18411 Boosting and The Problem of Boosting .. Boosting by Online Convex Optimization .

6 Simplification of the setting .. Algorithm and analysis .. AdaBoost .. Completing the picture .. Bibliographic Remarks .. Exercises .. 194 CONTENTSix12 Online Motivation: Learning from a Huge Set of Experts .. Example: boosting Online binary classification .. Example: personalized article placement .. The Contextual Learning Model .. The Extension Operator .. The Online Boosting Method .. Bibliographic Remarks .. Exercises .. 20613 Blackwell Approachability and Online Convex Vector-Valued Games and Approachability .. From Online Convex Optimization to Approachability .. From Approachability to Online Convex Optimization .. Cones and polar cones .. The reduction .. Existence of a best response oracle .. Bibliographic Remarks .. Exercises .. 218xCONTENTSP refaceThis book serves as an Introduction to the expanding theory of Online convexoptimization (OCO).

7 It was written as an advanced textbook to serve asa basis for a graduate course, and/or as a reference to researchers divinginto this fascinating world at the intersection of Optimization and a course was given at the Technion in 2010 2014, with slight vari-ations from year to year, and later at Princeton University in 2015 core material in these courses is fully covered in this book, along withexercises that allow students to complete parts of proofs, or that were foundilluminating and thought-provoking by those taking the course. Most ofthe material is given with examples of applications, which are interlacedthroughout various topics. These include prediction from expert advice,portfolio selection, matrix completion and recommendation systems, andsupport vector machine hope is that this compendium of material and exercises will be usefulto you; the researcher and/or this Book in the Machine Learning LibraryThe broad field of machine learning, as in the sub-disciplines of Online learn-ing, boosting, regret minimization in games, universal prediction, and otherrelated topics, have seen a plethora of introductory books in recent this note, we can hardly do justice to all of these, but perhaps point tothe most related books on the topics of machine learning, learning in games,and Optimization , whose intersection is our main most closely related book, which served as an inspiration to thecurrent, and indeed an inspiration to the entire field of learning in games, isthe wonderful text of Cesa-Bianchi and Lugosi [2006].

8 From the literatureon mathematical Optimization theory, there are the numerous introductoryxixiiPrefaceessays to Convex Optimization and Convex analysis, to name only a few [Boydand Vandenberghe, 2004, Nesterov, 2004, Nemirovski and Yudin, 1983, Ne-mirovskii, 2004, Borwein and Lewis, 2006, Rockafellar, 1997]. The authorfondly recommends the text from which he has learned about mathematicaloptimization theory [Nemirovskii, 2004]. The more broad texts on machinelearning are too numerous to state primary purpose of this is to serve as an educational textbook foradedicatedcourse on OCO and the Convex Optimization approach to ma-chine learning. Online Convex Optimization has already had enough impactto appear in several surveys and introductory texts [Hazan, 2011, Shalev-Shwartz, 2011, Rakhlin, 2009, Rakhlin and Sridharan, 2014]. We hope thiscompilation of material and exercises will further enrich the s tructureThis book is intended to serve as a reference for a self-contained coursefor graduate students in computer science/electrical engineering/operationsresearch/statistic s and related fields.

9 As such, its organization follows thestructure of the course Decision Analysis , taught at the Technion, andlater Theoretical Machine Learning , taught at Princeton chapter should take one or two weeks of classes, depending on thedepth and breadth of the intended course. Chapter 1 is designed to be ateaser for the field, and it is less rigorous than the rest of the speaking, the book can be conceived as three units. The first,from chapter 2 through 4, contains the basic definitions, framework and corealgorithms for OCO. Chapters 5 to 7 contain more advanced algorithms andin-depth analysis of the framework and its extensions to other computationaland information access models. The rest of the book deals with more ad-vanced algorithms, more difficult settings, and relationships to well-knownmachine learning book can assist educators in designing a complete course on thetopic of Online Convex Optimization , or it can serve as a component in acomprehensive course on machine learning.

10 A accompanying manual of so-lutions to selected exercises given in the book is available for educators in the Second EditionThe main additions to the second edition of this book include the following: Expanded coverage of Optimization in chapter 2, with a unified gradi-ent descent analysis of the Polyak stepsize. Expanded coverage of learning theory in chapter 9, with an introduc-tion to compression and its use in generalization theory. An expanded chapter 4, with addition of the exponential weightedoptimizer for exp-concave loss functions. A revised chapter 5, with the addition of mirror descent analysis, aswell as a revised section on adaptive gradient methods. New chapter 10 on the notion of adaptive regret and algorithms forOCO with near-optimal adaptive regret bounds. New chapter 11 on boosting and its relationship to OCO. Derivationof boosting algorithms from regret minimization . New chapter 12 on Online boosting.