Intro to OCO
ver 1.x

Table of contents for version 1.x:

Chapter 1 Introduction

1.1 The online convex optimization model

1.2 Examples of problems that can be modeled via OCO

1.3 A gentle start: learning from experts advice

Chapter 2 Convergence analysis in convex optimization

2.1 Basic definitions and setup

2.2 (Sub)-gradient descent

2.3 Reductions to non-smooth and non-strongly convex functions

2.4 Example: support vector machine (SVM) training

Chapter 3 First-order algorithms for online convex optimization

3.1 Online gradient descent

3.2 Lower bounds

3.3 Logarithmic regret

3.4 Application: stochastic gradient descent

Chapter 4 Second order methods

4.1 Motivation: universal portfolio selection

4.2 Exp-concave functions

4.3 The online Newton step algorithm

Chapter 5 Regularization

5.1 Regularization functions

5.2 The RFTL algorithm and its analysis

5.3 Online Mirrored Descent

5.4 Application and special cases

5.5 Randomized regularization

5.6 * Optimal regularization

Chapter 6 Bandit Convex Optimization

6.1 The Bandit Convex Optimization model

6.2 The Multi Armed Bandit (MAB) problem

6.3 A reduction from limited to full information: from BCO to OCO

6.4 Online gradient descent without a gradient

6.5 * Optimal regret algorithms for BLO

Chapter 7 Projection-free Algorithms

7.1 Review: relevant concepts from linear algebra

7.2 Motivation: matrix completion and recommendation systems

7.3 The conditional gradient method

7.4 Projections vs. linear optimization

7.5 The online conditional gradient algorithm

Chapter 8 Games, Duality and Regret

8.1 Linear programming and duality

8.2 Zero-sum games and equilibria

8.3 Proof of von Neumann Theorem

8.4 Approximating Linear Programs

Chapter 9 Learning Theory, Generalization and OCO

9.1 Statistical and computational learning theory

9.2 Agnostic learning using OCO