Introduction to Online Convex Optimization

Preface

This book serves as an introduction to the expanding theory of online convex optimization (OCO). It was written as an advanced textbook to serve as a basis for a graduate course, and/or as a reference to researchers diving into this fascinating world at the intersection of optimization and machine learning.

Such a course was given at the Technion in 2010–2014, with slight variations from year to year, and later at Princeton University in 2015–2020. The core material in these courses is fully covered in this book, along with exercises that allow students to complete parts of proofs, or that were found illuminating and thought-provoking by those taking the course. Most of the material is given with examples of applications, which are interlaced throughout various topics. These include prediction from expert advice, portfolio selection, matrix completion and recommendation systems, and support vector machine training.

Our hope is that this compendium of material and exercises will be useful to you; the researcher and/or educator.

The broad field of machine learning, as in the sub-disciplines of online learning, boosting, regret minimization in games, universal prediction, and other related topics, have seen a plethora of introductory books in recent years. With this note, we can hardly do justice to all of these, but perhaps point to the most related books on the topics of machine learning, learning in games, and optimization, whose intersection is our main focus.

The most closely related book, which served as an inspiration to the current, and indeed an inspiration to the entire field of learning in games, is the wonderful text of Cesa-Bianchi and Lugosi (2006). From the literature on mathematical optimization theory, there are the numerous introductory essays to convex optimization and convex analysis, to name only a few (Boyd and Vandenberghe, 2004; Nesterov, 2004; Nemirovski and Yudin, 1983; Nemirovskii, 2004; Borwein and Lewis, 2006; Rockafellar, 1997). The author fondly recommends the text from which he has learned about mathematical optimization theory (Nemirovskii, 2004). The more broad texts on machine learning are too numerous to state here.

The primary purpose of this is to serve as an educational textbook for a dedicated course on OCO and the convex optimization approach to machine learning. Online convex optimization has already had enough impact to appear in several surveys and introductory texts (Hazan, 2011; Shalev-Shwartz, 2011; Rakhlin, 2009; Rakhlin and Sridharan, 2014). We hope this compilation of material and exercises will further enrich the literature.

Book’s tructure

This book is intended to serve as a reference for a self-contained course for graduate students in computer science/electrical engineering/operations research/statistics and related fields. As such, its organization follows the structure of the course “Decision Analysis”, taught at the Technion, and later “Theoretical Machine Learning”, taught at Princeton University.

Each chapter should take one or two weeks of classes, depending on the depth and breadth of the intended course. Chapter 1 is designed to be a teaser for the field, and it is less rigorous than the rest of the book.

Roughly speaking, the book can be conceived as three units. The first, from chapter 2 through 4, contains the basic definitions, framework and core algorithms for OCO. Chapters 5 to 7 contain more advanced algorithms and in-depth analysis of the framework and its extensions to other computational and information access models. The rest of the book deals with more advanced algorithms, more difficult settings, and relationships to well-known machine learning paradigms.

This book can assist educators in designing a complete course on the topic of online convex optimization, or it can serve as a component in a comprehensive course on machine learning. A accompanying manual of solutions to selected exercises given in the book is available for educators only.

The main additions to the second edition of this book include the following:

Expanded coverage of optimization in chapter 2, with a unified gradient descent analysis of the Polyak stepsize.

Expanded coverage of learning theory in chapter 9, with an introduction to compression and its use in generalization theory.

An expanded chapter 4, with addition of the exponential weighted optimizer for exp-concave loss functions.

A revised chapter 5, with the addition of mirror descent analysis, as well as a revised section on adaptive gradient methods.

New chapter 10 on the notion of adaptive regret and algorithms for OCO with near-optimal adaptive regret bounds.

New chapter 11 on boosting and its relationship to OCO. Derivation of boosting algorithms from regret minimization.

New chapter 13 on Blackwell approachability and its strong connection to OCO.

In addition, numerous typos are fixed, exercises are corrected, and solutions to several questions have been made available in a separate manual for educators.

Acknowledgements

First of all, I gratefully acknowledge the numerous contributions and insight of the students of the course “decision analysis” given at the Technion during 2010-2014, as well as the students of “theoretical machine learning” taught at Princeton University during 2015-2016.

I would like to thank the friends, colleagues and students that have contributed many suggestions and corrections. A partial list includes: Sanjeev Arora, Shai Shalev-Shwartz, Aleksander Madry, Yoram Singer, Satyen Kale, Alon Gonen, Roi Livni, Gal Lavee, Maayan Harel, Daniel Khasabi, Shuang Liu, Jason Altschuler, Haipeng Luo, Zeyuan Allen-Zhu, Mehrdad Mahdavi, Jaehyun Park, Baris Ungun, Maria Gregori, Tengyu Ma, Kayla McCue, Esther Rolf, Jeremy Cohen, Daniel Suo, Lydia Liu, Fermi Ma, Mert Al, Amir Reza Asadi, Carl Gabel, Nati Srebro, Abbas Mehrabian, Chris Liaw, Nikhil Bansal, Naman Agarwal, Raunak Kumar, Zhize Li, Sheng Zhang, Swati Gupta, Xinyi Chen, Liang Zeng and Kunal Mittal.

I thank Udi Aharoni for his artwork and illustrations depicting algorithms in this book.

I am forever indebted to my teacher and mentor, Sanjeev Arora, without him this book would not be possible.

Finally, I am grateful for the love and support of my wife and children: Dana, Hadar, Yoav, and Oded.

The Second Version

I am most thankful to my students and colleagues that have collaborated with me on research, some of which appears in the second version of this book. Notably my collaborators on boosting methods including Nataly Brukhim, Xinyi Chen, Shay Moran, Naman Agarwal and Karan Singh.

Thanks to my students that helped me proof check new and existing sections: Edgar Minasyan, Paula Gradu, Karan Singh, Nataly Brukhim, Xinyi Chen, Naman Agarwal and Udaya Ghai.

I am thankful to Shay Moran for explaining compression schemes and how they simplify generalization for boosting.

I gratefully acknowledges the help of Ahmed Farah, Charlie Cowen-Breen and the students of “COS 597C: Computational Control Theory” for many helpful suggestions, corrections and solutions to many of the problem sets.

I am very thankful to Wouter Koolen-Wijkstra for a helpful suggestion in the analysis of the Online Newton Step algorithm.

Thanks to Shiyun Lin for finding typos and improving the presentation of the randomized regularization section.

I thank the extremely helpful and rigorous reviewers of this book found by MIT press who gave fantastic suggestions and improve the final manuscript.

As in the first version and even more so, I am grateful for the love and support of my wife and children: Dana, Hadar, Yoav, and Oded.

List of Symbols

Geometry and Calculus

Learning Theory

Optimization

Regularization

Chapter 1 Introduction

This book considers optimization as a process. In many practical applications, the environment is so complex that it is not feasible to lay out a comprehensive theoretical model and use classical algorithmic theory and mathematical optimization. It is necessary, as well as beneficial, to take a robust approach, by applying an optimization method that learns as more aspects of the problem are observed. This view of optimization as a process has become prominent in various fields, which has led to spectacular successes in modeling and systems that are now part of our daily lives.

The growing body of literature of machine learning, statistics, decision science, and mathematical optimization blurs the classical distinctions between deterministic modeling, stochastic modeling, and optimization methodology. We continue this trend in this book, studying a prominent optimization framework whose precise location in the mathematical sciences is unclear: the framework of online convex optimization (OCO), which was first defined in the machine learning literature (see section 1.4, later in this chapter). The metric of success is borrowed from game theory, and the framework is closely tied to statistical learning theory and convex optimization.

We embrace these fruitful connections and, on purpose, do not try to use any particular jargon in the discussion. Rather, this book will start with actual problems that can be modeled and solved via OCO. We will proceed to present rigorous definitions, backgrounds, and algorithms. Throughout, we provide connections to the literature in other fields. It is our hope that you, the reader, will contribute to our understanding of these connections from your domain of expertise, and expand the growing amount of literature on this fascinating subject.

In OCO, an online player iteratively makes decisions. At the time of each decision, the outcome or outcomes associated with it are unknown to the player.

After committing to a decision, the decision maker suffers a loss: every possible decision incurs a (possibly different) loss. These losses are unknown to the decision maker beforehand. The losses can be adversarially chosen, and even depend on the action taken by the decision maker.

Already at this point, several restrictions are necessary in order for this framework to make any sense at all:

The losses determined by an adversary should not be allowed to be unbounded 1Alternatively and equivalently, any performance metric for this setting should depend on the magnitude of the largest loss. This is the viewpoint taken later in the rest of this book. . Otherwise, the adversary could keep decreasing the scale of the loss at each step, and never allow the algorithm to recover from the loss of the first step. Thus, we assume that the losses lie in some bounded region.

The decision set must be somehow bounded and/or structured, though not necessarily finite.

To see why this is necessary, consider decision making with an infinite set of possible decisions. An adversary can assign high loss to all the strategies chosen by the player indefinitely, while setting apart some strategies with zero loss. This precludes any meaningful performance metric.

The OCO framework can be seen as a structured repeated game. The protocol of this learning framework is as follows.

What would make an algorithm a good OCO algorithm? As the framework is game-theoretic and adversarial in nature, the appropriate performance metric also comes from game theory: define the regret of the decision maker to be the difference between the total cost she has incurred and that of the best fixed decision in hindsight. In OCO, we are usually interested in an upper bound on the worst-case regret of an algorithm.

Let ${\mathcal{A}}$ be an algorithm for OCO, which maps a certain game history to a decision in the decision set:

We formally define the regret of ${\mathcal{A}}$ after $T$ iterations as:

The running time of an algorithm for OCO is defined to be the worst-case expected time to produce $\mathbf{x}_{t}$, for an iteration $t\in[T]$2Here and henceforth, we denote as $[n]$ the set of integers $\{1,...,n\}$. in a $T$-iteration repeated game. Typically, the running time will depend on $n$ (the dimensionality of the decision set $\mathcal{K}$), $T$ (the total number of game iterations), and the parameters of the cost functions and underlying convex set.

2 Examples of Problems That Can Be Modeled via Online Convex Optimization

Perhaps the main reason that OCO has become a leading online learning framework in recent years is its powerful modeling capability: problems from diverse domains such as online routing, ad selection for search engines, and spam filtering can all be modeled as special cases. In this section, we briefly survey a few special cases and how they fit into the OCO framework.

Perhaps the most well known problem in prediction theory is the experts problem. The decision maker has to choose among the advice of $n$ given experts. After making her choice, a loss between zero and $1$ is incurred. This scenario is repeated iteratively, and at each iteration, the costs of the various experts are arbitrary (and possibly even adversarial, trying to mislead the decision maker). The goal of the decision maker is to do as well as the best expert in hindsight.

The fundamental importance of the experts problem in machine learning warrants special attention, and we shall return to it and analyze it in detail at the end of this chapter.

2.2 Online spam filtering

Consider an online spam-filtering system. Repeatedly, emails arrive in the system and are classified as spam or valid. Obviously, such a system has to cope with adversarially generated data and dynamically change with the varying input—a hallmark of the OCO model.

At this point the reader may wonder - why use a square loss rather than any other function? The most natural choice being perhaps a loss of one if $b=\hat{b}$ and zero otherwise.

To answer this, notice first that if both $b$ and $\hat{b}$ are binary and in $\{-1,1\}$, then the square loss is indeed one or zero. However, moving to a continuous function allows us much more flexibility in the decision making process. We can allow, for example, the algorithm to return a number in the interval $$ depending on its confidence.

Another reason has to do with the algorithmic efficiency of finding a a good solution. This will be the subject of future chapters.

2.3 Online shortest paths

The discrete description of this problem as an experts problem, where we have an expert for each path, presents an efficiency challenge. There are potentially exponentially many paths in terms of the graph representation size.

2.4 Portfolio selection

In this section we consider a portfolio selection model that does not make any statistical assumptions about the stock market (as opposed to the standard geometric Brownian motion model for stock prices), and is called the “universal portfolio selection” model.

The goal of regret minimization, which in this case corresponds to minimizing the difference $\max_{\mathbf{x}^{\star}\in\Delta_{n}}{\textstyle\sum}_{t=1}^{T}\log(\mathbf{r}_{t}^{\top}\mathbf{x}^{\star})-{\textstyle\sum}_{t=1}^{T}\log(\mathbf{r}_{t}^{\top}\mathbf{x}_{t})$, has an intuitive interpretation. The first term is the logarithm of the wealth accumulated by the best possible in-hindsight distribution $\mathbf{x}^{\star}$. Since this distribution is fixed, it corresponds to a strategy of rebalancing the position after every trading period, and hence, is called a constant rebalanced portfolio. The second term is the logarithm of the wealth accumulated by the online decision maker. Hence regret minimization corresponds to maximizing the ratio of the investor’s wealth to the wealth of the best benchmark from a pool of investing strategies.

A universal portfolio selection algorithm is defined to be one that, in this setting, attains regret converging to zero. Such an algorithm, albeit requiring exponential time, was first described by Cover (see bibliographic notes at the end of this chapter). The online convex optimization framework has given rise to much more efficient algorithms based on Newton’s method. We shall return to study these in detail in chapter 4.

2.5 Matrix completion and recommendation systems

The prevalence of large-scale media delivery systems such as the Netflix online video library, Spotify music service and many others, give rise to very large scale recommendation systems. One of the most popular and successful models for automated recommendation is the matrix completion model.

In this mathematical model, recommendations are thought of as composing a matrix. The customers are represented by the rows, the different media are the columns, and at the entry corresponding to a particular user/media pair we have a value scoring the preference of the user for that particular media.

For example, for the case of binary recommendations for music, we have a matrix $X\in\{0,1\}^{n\times m}$ where $n$ is the number of persons considered, $m$ is the number of songs in our library, and $0/1$ signifies dislike/like respectively:

In the online setting, for each iteration the decision maker outputs a preference matrix $X_{t}\in\mathcal{K}$, where $\mathcal{K}\subseteq\{0,1\}^{n\times m}$ is a subset of all possible zero/one matrices. An adversary then chooses a user/song pair $(i_{t},j_{t})$ along with a “real” preference for this pair $y_{t}\in\{0,1\}$. Thus, the loss experienced by the decision maker can be described by the convex loss function,

The natural comparator in this scenario is a low-rank matrix, which corresponds to the intuitive assumption that preference is determined by few unknown factors. Regret with respect to this comparator means performing, on the average, as few preference-prediction errors as the best low-rank matrix.

We return to this problem and explore efficient algorithms for it in chapter 7.

3 A Gentle Start: Learning from Expert Advice

Consider the following fundamental iterative decision making problem:

At each time step $t=1,2,\ldots,T$, the decision maker faces a choice between two actions $A$ or $B$ (i.e., buy or sell a certain stock). The decision maker has assistance in the form of $N$ “experts” that offer their advice. After a choice between the two actions has been made, the decision maker receives feedback in the form of a loss associated with each decision. For simplicity one of the actions receives a loss of zero (i.e., the “correct” decision) and the other a loss of one.

We make the following elementary observations:

A decision maker that chooses an action uniformly at random each iteration, trivially attains a loss of $\frac{T}{2}$ and is “correct” $50\%$ of the time.

In terms of the number of mistakes, no algorithm can do better in the worst case! In a later exercise, we will devise a randomized setting in which the expected number of mistakes of any algorithm is at least $\frac{T}{2}$.

We are thus motivated to consider a relative performance metric: can the decision maker make as few mistakes as the best expert in hindsight? The next theorem shows that the answer in the worst case is negative for a deterministic decision maker.

Let $L\leq\frac{T}{2}$ denote the number of mistakes made by the best expert in hindsight. Then there does not exist a deterministic algorithm that can guarantee less than $2L$ mistakes.

Assume that there are only two experts and one always chooses option $A$ while the other always chooses option $B$. Consider the setting in which an adversary always chooses the opposite of our prediction (she can do so, since our algorithm is deterministic). Then, the total number of mistakes the algorithm makes is $T$. However, the best expert makes no more than $\frac{T}{2}$ mistakes (at every iteration exactly one of the two experts is mistaken). Therefore, there is no algorithm that can always guarantee less than $2L$ mistakes.

This observation motivates the design of random decision making algorithms, and indeed, the OCO framework gracefully models decisions on a continuous probability space. Henceforth we prove Lemmas 1.3 and 1.4 that show the following:

Let $\varepsilon\in(0,\frac{1}{2})$. Suppose the best expert makes $L$ mistakes. Then:

There is an efficient deterministic algorithm that can guarantee less than $2(1+\varepsilon)L+\frac{2\log N}{\varepsilon}$ mistakes;

There is an efficient randomized algorithm for which the expected number of mistakes is at most $(1+\varepsilon)L+\frac{\log N}{\varepsilon}$.

The weighted majority (WM) algorithm is intuitive to describe: each expert $i$ is assigned a weight $W_{t}(i)$ at every iteration $t$. Initially, we set $W_{1}(i)=1$ for all experts $i\in[N]$. For all $t\in[T]$ let $S_{t}(A),S_{t}(B)\subseteq[N]$ be the set of experts that choose $A$ (and respectively $B$) at time $t$. Define,

Next, update the weights $W_{t}(i)$ as follows:

where $\varepsilon$ is a parameter of the algorithm that will affect its performance. This concludes the description of the WM algorithm. We proceed to bound the number of mistakes it makes.

Denote by $M_{t}$ the number of mistakes the algorithm makes until time $t$, and by $M_{t}(i)$ the number of mistakes made by expert $i$ until time $t$. Then, for any expert $i\in[N]$ we have

We can optimize $\varepsilon$ to minimize the above bound. The expression on the right hand side is of the form $f(x)=ax+b/x$, that reaches its minimum at $x=\sqrt{b/a}$. Therefore the bound is minimized at $\varepsilon^{\star}=\sqrt{\log N/M_{T}(i)}$. Using this optimal value of $\varepsilon$, we get that for the best expert $i^{\star}$

Of course, this value of $\varepsilon^{\star}$ cannot be used in advance since we do not know which expert is the best one ahead of time (and therefore we do not know the value of $M_{T}(i^{\star})$). However, we shall see later on that the same asymptotic bound can be obtained even without this prior knowledge.

Let $\Phi_{t}=\sum_{i=1}^{N}W_{t}(i)$ for all $t\in[T]$, and note that $\Phi_{1}=N$.

Notice that $\Phi_{t+1}\leq\Phi_{t}$. However, on iterations in which the WM algorithm erred, we have

the reason being that experts with at least half of total weight were wrong (else WM would not have erred), and therefore

On the other hand, by definition we have for any expert $i$ that

Since the value of $W_{T}(i)$ is always less than the sum of all weights $\Phi_{T}$, we conclude that

Taking the logarithm of both sides we get

which follow from the Taylor series of the logarithm function, to obtain that

3.2 Randomized weighted majority

In the randomized version of the WM algorithm, denoted RWM, we choose expert $i$ w.p. $p_{t}(i)=W_{t}(i)/\sum_{j=1}^{N}W_{t}(j)$ at time $t$.

Let $M_{t}$ denote the number of mistakes made by RWM until iteration $t$. Then, for any expert $i\in[N]$ we have

The proof of this lemma is very similar to the previous one, where the factor of two is saved by the use of randomness:

On the other hand, by definition we have for any expert $i$ that

Since the value of $W_{T}(i)$ is always less than the sum of all weights $\Phi_{T}$, we conclude that

Taking the logarithm of both sides we get

3.3 Hedge

Historically, this was observed by a different and closely related algorithm called Hedge, whose total loss bound will be of interest to us later on in the book.

Henceforth, denote in vector notation the expected loss of the algorithm by

As before, let $\Phi_{t}=\sum_{i=1}^{N}W_{t}(i)$ for all $t\in[T]$, and note that $\Phi_{1}=N$.

On the other hand, by definition, for expert $i^{\star}$ we have that

Since the value of $W_{T}(i^{\star})$ is always less than the sum of all weights $\Phi_{t}$, we conclude that

Taking the logarithm of both sides we get

and the theorem follows by simplifying. ∎

4 Bibliographic Remarks

The OCO model was first defined by Zinkevich (2003) and has since become widely influential in the learning community and significantly extended since (see thesis and surveys (Hazan, 2006, 2011; Shalev-Shwartz, 2011)).

The problem of prediction from expert advice and the Weighted Majority algorithm were devised in (Littlestone and Warmuth, 1989, 1994). This seminal work was one of the first uses of the multiplicative updates method—a ubiquitous meta-algorithm in computation and learning, see the survey (Arora et al., 2012) for more details. The Hedge algorithm was introduced by Freund and Schapire (1997).

The Universal Portfolios model was put forth in (Cover, 1991), and is one of the first examples of a worst-case online learning model. Cover gave an optimal-regret algorithm for universal portfolio selection that runs in exponential time. A polynomial time algorithm was given in (Kalai and Vempala, 2003), which was further sped up in (Agarwal et al., 2006; Hazan et al., 2007). Numerous extensions to the model also appeared in the literature, including addition of transaction costs (Blum and Kalai, 1999) and relation to the Geometric Brownian Motion model for stock prices (Hazan and Kale, 2009).

In their influential paper, Awerbuch and Kleinberg (2008) put forth the application of online convex optimization to online routing. A great deal of work has been devoted since then to improve the initial bounds, and generalize it into a complete framework for decision making with limited feedback. This framework is an extension of OCO, called Bandit Convex Optimization (BCO). We defer further bibliographic remarks to chapter 6 which is devoted to the BCO framework.

5 Exercises

1. (Attributed to Claude Shannon) Construct market returns over two stocks for which the wealth accumulated over any single stock decreases exponentially, whereas the best constant rebalanced portfolio increases wealth exponentially. More precisely, construct two sequences of numbers in the range $(0,\infty)$, that represent returns, such that:

(a) Investing in any of the individual stocks results in exponential decrease in wealth. This means that the product of the prefix of numbers in each of these sequences decreases exponentially.

(b) Investing evenly on the two assets and rebalancing after every iteration increases wealth exponentially.

(a) Consider the experts problem in which the losses are between zero and a positive real number $G>0$. Give an algorithm that attains expected loss upper bounded by:

for the best constant $c$ you can (the constant $c$ should be independent of the number of game iterations $T$, and the number of experts $N$. Assume that $T$ is known in advance).

(b) Suppose the upper bound $G$ is not known in advance. Give an algorithm whose performance is asymptotically as good as your algorithm in part (a), up to an additive and/or multiplicative constant which is independent of $T,N,G$. Prove your claim.

3. Consider the experts problem in which the losses can be negative and are real numbers in the range $$. Give an algorithm with regret guarantee of$O(\sqrt{T\log N})$ and prove your claim.

Chapter 2 Basic Concepts in Convex Optimization

In this chapter we give a gentle introduction to convex optimization and present some basic algorithms for solving convex mathematical programs. Although offline convex optimization is not our main topic, it is useful to recall the basic definitions and results before we move on to OCO. This will help in assessing the advantages and limitations of OCO. Furthermore, we describe some tools that will be our bread-and-butter later on.

The material in this chapter is far from being new. A broad and significantly more detailed literature exists, and the reader is deferred to the bibliography at the end of this chapter for references. We give here only the most elementary analysis, and focus on the techniques that will be of use to us later on.

A set $\mathcal{K}$ is convex if for any $\mathbf{x},\mathbf{y}\in\mathcal{K}$, all the points on the line segment connecting $\mathbf{x}$ and $\mathbf{y}$ also belong to $\mathcal{K}$, i.e.,

This inequality, and generalizations thereof, is also known as Jensen’s inequality. Equivalently, if $f$ is differentiable, that is, its gradient $\nabla f(\mathbf{x})$ exists for all $\mathbf{x}\in\mathcal{K}$, then it is convex if and only if $\forall\mathbf{x},\mathbf{y}\in\mathcal{K}$

For convex and non-differentiable functions $f$, the subgradient at $\mathbf{x}$ is defined to be any member of the set of vectors $\{\nabla f(\mathbf{x})\}$ that satisfies the above for all $\mathbf{y}\in\mathcal{K}$.

We denote by $G>0$ an upper bound on the norm of the subgradients of $f$ over $\mathcal{K}$, i.e., $\|\nabla f(\mathbf{x})\|\leq G$ for all $\mathbf{x}\in\mathcal{K}$. Such an upper bound implies that the function $f$ is Lipschitz continuous with parameter $G$, that is, for all $\mathbf{x},\mathbf{y}\in\mathcal{K}$

The optimization and machine learning literature studies special types of convex functions that admit useful properties, which in turn allow for more efficient optimization. Notably, we say that a function is $\alpha$-strongly convex if

The latter condition is equivalent to a Lipschitz condition over the gradients, i.e.,

If the function is twice differentiable and admits a second derivative, known as a Hessian for a function of several variables, the above conditions are equivalent to the following condition on the Hessian, denoted $\nabla^{2}f(\mathbf{x})$:

where $A\preccurlyeq B$ if the matrix $B-A$ is positive semidefinite.

When the function $f$ is both $\alpha$-strongly convex and $\beta$-smooth, we say that it is $\gamma$-well-conditioned where $\gamma$ is the ratio between strong convexity and smoothness, also called the condition number of $f$

In the following algorithms we shall make use of a projection operation onto a convex set, which is defined as the closest point in terms of Euclidean distance 3 We will discuss projections with respect to other distance notions in chapter 5. inside the convex set to a given point. Formally,

The computational complexity of projections is a subtle issue that depends much on the characterization of $\mathcal{K}$ itself. Most generally, $\mathcal{K}$ can be represented by a membership oracle—an efficient procedure that is capable of deciding whether a given $\mathbf{x}$ belongs to $\mathcal{K}$ or not. In this case, projections can be computed in polynomial time. In certain special cases, projections can be computed very efficiently in near-linear time. The computational cost of projections, as well as optimization algorithms that avoid them altogether, is discussed in chapter 7.

A crucial property of projections that we shall make extensive use of is the Pythagorean theorem, which we state here for completeness:

We note that there exists a more general version of the Pythagorean theorem. The above theorem and the definition of projections are true and valid not only for Euclidean norms, but for projections according to other distances that are not norms. In particular, an analogue of the Pythagorean theorem remains valid with respect to Bregman divergences (see chapter 5).

1.2 Introduction to optimality conditions

The standard curriculum of high school mathematics contains the basic facts concerning when a function (usually in one dimension) attains a local optimum or saddle point. The generalization of these conditions to more than one dimension is called the KKT (Karush-Kuhn-Tucker) conditions, and the reader is referred to the bibliographic material at the end of this chapter for an in-depth rigorous discussion of optimality conditions in general mathematical programming.

We will require a slightly more general, but equally intuitive, fact for constrained optimization: at a minimum point of a constrained convex function, the inner product between the negative gradient and direction towards the interior of $\mathcal{K}$ is non-positive. This is depicted in figure 2.2, which shows that $-\nabla f(\mathbf{x}^{\star})$ defines a supporting hyperplane to $\mathcal{K}$. The intuition is that if the inner product were positive, one could improve the objective by moving in the direction of the projected negative gradient. This fact is stated formally in the following theorem.

2 Gradient Descent

Gradient descent (GD) is the simplest and oldest of optimization methods. It is an iterative method—the optimization procedure proceeds in iterations, each improving the objective value. The basic method amounts to iteratively moving the current point in the direction of the gradient, which is a linear time operation if the gradient is given explicitly (indeed, for many functions computing the gradient at a certain point is a simple linear-time operation).

The basic template algorithm, for unconstrained optimization, is given in 2, and a depiction of the iterates it produced in figure 2.3.

For a convex function there always exists a choice of step sizes that will cause GD to converge to the optimal solution. The rates of convergence, however, differ greatly and depend on the smoothness and strong convexity properties of the objective function. The following table summarises the convergence rates of GD variants for convex functions with different convexity parameters. The rates described omit the (usually small) constants in the bounds—we focus on asymptotic rates.

In this section we address only the first row of Table 2.1. For accelerated methods and their analysis see references at the bibliographic section.

Luckily, there exists a simple choice of step sizes that yields the optimal convergence rate, called the Polyak stepsize. It has a huge advantage of not depending on the strong convexity and/or smoothness parameters of the objective function.

However, it does depend on the distance in function value to optimality and gradient norm. While the latter can be efficiently estimated, the distance to optimality is not always available if $f(\mathbf{x}^{*})$ is not known ahead of time. This can be remedied, as referred to in the bibliography.

Distance to optimality in value: $h_{t}=h(\mathbf{x}_{t})=f(\mathbf{x}_{t})-f(\mathbf{x}^{*})$

Euclidean distance to optimality: $d_{t}=\|\mathbf{x}_{t}-\mathbf{x}^{*}\|$

Current gradient norm $\|\nabla_{t}\|=\|\nabla f(\mathbf{x}_{t})\|$

With these notations we can describe the algorithm precisely in Algorithm 3:

To prove precise convergence bounds, assume $\|\nabla_{t}\|\leq G$, and define:

We can now state the main guarantee of GD with the Polyak stepsize:

(GD with the Polyak Step Size) Algorithm 3 guarantees the following after $T$ steps:

2.2 Measuring distance to optimality

When analyzing convergence of gradient methods, it is useful to use potential functions in lieu of function distance to optimality, such as gradient norm and/or Euclidean distance. The following relationships hold between these quantities.

$\frac{1}{2\beta}\|\nabla_{t}\|^{2}\leq h_{t}$

$h_{t}\leq\frac{1}{2\alpha}\|\nabla_{t}\|^{2}$

where the last inequality follows since the gradient at the global optimum is zero.

where the last inequality follows since the gradient at the global optimum is zero.

$h_{t}\geq\frac{1}{2\beta}\|\nabla_{t}\|^{2}$: Using smoothness, and let $\mathbf{x}_{t+1}=\mathbf{x}_{t}-\eta\nabla_{t}$ for $\eta=\frac{1}{\beta}$,

$h_{t}\leq\frac{1}{2\alpha}\|\nabla_{t}\|^{2}$:

In particular, taking $\mathbf{x}=\mathbf{x}_{t}\ ,\ \mathbf{y}=\mathbf{x}^{\star}$, we get

2.3 Analysis of the Polyak stepsize

We are now ready to prove Theorem 2.3, which directly follows from the following lemma.

Suppose that a sequence $\mathbf{x}_{0},\ldots\mathbf{x}_{t}$ satisfies:

then for $\bar{\mathbf{x}}$ as defined in the algorithm, we have:

For convex functions with gradient bounded by $G$,

Summing up over $T$ iterations, and using Cauchy-Schwartz on the $T$-dimensional vectors of $\frac{1}{T}\mathbf{1}$ and $(h_{1},...,h_{T})$, we have

For smooth functions whose gradient is bounded by $G$, Lemma 2.4 implies:

For strongly convex functions, Lemma 2.4 implies:

In other words, $d_{t+1}^{2}\leq d_{t}^{2}(1-\frac{\alpha^{2}d_{t}^{2}}{4G^{2}})\,.$ Defining $a_{t}:=\frac{\alpha^{2}d_{t}^{2}}{4G^{2}}$, we have:

This implies that $a_{t}\leq\frac{1}{t+1}$, which can be seen by induction5That $a_{0}\leq 1$ follows from Lemma 2.4. For $t=1$, $a_{1}\leq\frac{1}{2}$ since $a_{1}\leq a_{0}(1-a_{0})$ and $0\leq a_{0}\leq 1$. For the induction step, $a_{t}\leq a_{t-1}(1-a_{t-1})\leq\frac{1}{t}(1-\frac{1}{t})=\frac{t-1}{t^{2}}=\frac{1}{t+1}(\frac{t^{2}-1}{t^{2}})\leq\frac{1}{t+1}$.. The proof is completed as follows6This assumes $T$ is even. $T$ odd leads to the same constants. :

Thus, there exists a $t$ for which $h_{t}^{2}\leq\frac{9G^{4}}{\alpha^{2}T^{2}}$. Taking the square root completes the claim.

For both strongly convex and smooth functions:

3 Constrained Gradient/Subgradient Descent

The vast majority of the problems considered in this text include constraints. Consider the examples given in section 1.2: a path is a point in the flow polytope, a portfolio is a point in the simplex and so on. In the language of optimization, we require $\mathbf{x}$ not only to minimize a certain objective function, but also to belong to a convex set $\mathcal{K}$.

In this section we describe and analyze constrained gradient descent. Algorithmically, the change from the previous section is small: after updating the current point in the direction of the gradient, one may need to project back to the decision set. However, the analysis is somewhat more involved, and instructive for the later parts of this text.

Algorithmic box 4 describes a template for gradient descent over a constrained set. It is a template since the sequence of step sizes $\{\eta_{t}\}$ is left as an input parameter, and the several variants of the algorithm differ on its choice.

As opposed to the unconstrained setting, here we require a precise setting of the learning rate to obtain the optimal convergence rate.

For constrained minimization of $\gamma$-well-conditioned functions and $\eta_{t}=\frac{1}{\beta}$, Algorithm 4 converges as

By strong convexity we have for every $\mathbf{x},\mathbf{x}_{t}\in\mathcal{K}$ (where we denote $\nabla_{t}=\nabla f(\mathbf{x}_{t})$ as before):

Next, appealing to the algorithm’s definition and the choice $\eta_{t}=\frac{1}{\beta}$, we have

The minimum can only grow if we take it over a subset of $\mathcal{K}$. Thus we can restrict our attention to all points that are convex combination of $\mathbf{x}_{t}$ and $\mathbf{x}^{\star}$, which we denote by the interval $[\mathbf{x}_{t},\mathbf{x}^{\star}]=\{(1-\mu)\mathbf{x}_{t}+\mu\mathbf{x}^{\star},\mu\in\}$, and write

Where the equality is by writing $\mathbf{x}$ as $\mathbf{x}=(1-\mu)\mathbf{x}_{t}+\mu\mathbf{x}^{\star}$. Using strong convexity, we have for any $\mathbf{x}_{t}$ and the minimizer $\mathbf{x}^{\star}$:

Thus, plugging this into equation (2.3.1), we get

This gives the theorem statement by induction. ∎

4 Reductions to Non-smooth and Non-strongly Convex Functions

The previous section dealt with $\gamma$-well-conditioned functions, which may seem like a significant restriction over vanilla convexity. Indeed, many interesting convex functions are not strongly convex nor smooth, and as we have seen, the convergence rate of gradient descent greatly differs for these functions. We have completed the picture for unconstrained optimization, and in this section we complete it for a bounded set.

The literature on first order methods is abundant with specialized analyses that explore the convergence rate of gradient descent for more general functions. In this manuscript we take a different approach: instead of analyzing variants of GD from scratch, we use reductions to derive near-optimal convergence rates for smooth functions that are not strongly convex, or strongly convex functions that are not smooth, or general convex functions without any further restrictions.

While attaining sub-optimal convergence bounds (by logarithmic factors), the advantage of this approach is two-fold: first, the reduction method is very simple to state and analyze, and its analysis is significantly shorter than analyzing GD from scratch. Second, the reduction method is generic, and thus extends to the analysis of accelerated gradient descent (or any other first order method) along the same lines. We turn to these reductions next.

Our first reduction applies the GD algorithm to functions that are $\beta$-smooth but not strongly convex.

The idea is to add a controlled amount of strong convexity to the function $f$, and then apply the algorithm 4 to optimize the new function. The solution is distorted by the added strong convexity, but a tradeoff guarantees a meaningful convergence rate.

where we ignore constants and terms depending on $D$ and $h_{1}^{g}$. ∎

Stronger convergence rates of $O(\frac{\beta}{t})$ can be obtained by analyzing GD from scratch, and these are known to be tight. Thus, our reduction is suboptimal by a factor of $O(\log T)$, which we tolerate for the reasons stated at the beginning of this section.

4.2 Reduction to strongly convex, non-smooth functions

Our reduction from non-smooth functions to $\gamma$-well-conditioned functions is similar in spirit to the one of the previous subsection. However, whereas for strong convexity the obtained rates were off by a factor of $\log T$, in this section we will also be off by factor of $d$, the dimension of the decision variable $\mathbf{x}$, as compared to the standard analyses in convex optimization. For tight bounds, the reader is referred to the excellent reference books and surveys listed in the bibliography section 2.6.

We apply the GD algorithm to a smoothed variant of the objective function. In contrast to the previous reduction, smoothing cannot be obtained by simple addition of a smooth (or any other) function. Instead, we need a smoothing operation. The one we describe is particularly simple and amounts to taking a local integral of the function. More sophisticated, but less general, smoothing operators exist that are based on the Moreau-Yoshida regularization, see bibliographic section for more details.

Let $f$ be $G$-Lipschitz continuous and $\alpha$-strongly convex. Define for any $\delta>0$,

$\hat{f}_{\delta}$ has the following properties:

If $f$ is $\alpha$-strongly convex, then so is ${\hat{f}}_{\delta}$

$\hat{f}_{\delta}$ is $\frac{dG}{\delta}$-smooth

$|\hat{f}_{\delta}(\mathbf{x})-f(\mathbf{x})|\leq\delta G$ for all $\mathbf{x}\in\mathcal{K}$ .

Before proving this lemma, let us first complete the reduction. Using Lemma 2.8 and the convergence for $\gamma$-well-conditioned functions the following approximation bound is obtained.

For $\delta=\frac{dG}{\alpha}\frac{\log{t}}{t}$ Algorithm 6 converges as

Before proving this lemma, notice that the gradient descent method is applied with gradients of the smoothed function ${\hat{f}}_{\delta}$ rather than gradients of the original objective $f$. In this section we ignore the computational cost of computing such gradients given only access to gradients of $f$, which may be significant. Techniques for estimating these gradients are further explored in chapter 6.

Note that by Lemma 2.8 the function ${\hat{f}}_{\delta}$ is $\gamma$-well-conditioned for $\gamma=\frac{\alpha\delta}{dG}.$

We proceed to prove that ${\hat{f}}_{\delta}$ is indeed a good approximation to the original function.

Recall that a function $f$ is $\beta$-smooth if and only if for all $\mathbf{x},\mathbf{y}\in\mathcal{K}$, it holds that $\|\nabla f(\mathbf{x})-\nabla f(\mathbf{y})\|\leq\beta\|\mathbf{x}-\mathbf{y}\|$. Now,

This proves the second property of Lemma 2.8. We proceed to show the third property, namely that ${\hat{f}}_{\delta}$ is a good approximation to $f$.

We note that GD variants for $\alpha$-strongly convex functions, even without the smoothing approach used in our reduction, are known to converge quickly and without dependence on the dimension. We state the known algorithm and result here without proof (see bibliography for references).

Let $f$ be $\alpha$-strongly convex, and let $\mathbf{x}_{1},...,\mathbf{x}_{t}$ be the iterates of Algorithm 4 applied to $f$ with $\eta_{t}=\frac{2}{\alpha(t+1)}$. Then

4.3 Reduction to general convex functions

5 Example: Support Vector Machine Training

To illustrate the usefulness of the gradient descent method, let us describe an optimization problem that has gained much attention in machine learning and can be solved efficiently using the methods we have just analyzed.

A very basic and successful learning paradigm is the linear classification model. In this model, the learner is presented with positive and negative examples of a concept. Each example, denoted by $\mathbf{a}_{i}$, is represented in Euclidean space by a $d$ dimensional feature vector. For example, a common representation for emails in the spam-classification problem are binary vectors in Euclidean space, where the dimension of the space is the number of words in the language. The $i$’th email is a vector $\mathbf{a}_{i}$ whose entries are given as ones for coordinates corresponding to words that appear in the email, and zero otherwise7Such a representation may seem naïve at first as it completely ignores the words’ order of appearance and their context. Extensions to capture these features are indeed studied in the Natural Language Processing literature.. In addition, each example has a label $b_{i}\in\{-1,+1\}$, corresponding to whether the email has been labeled spam/not spam. The goal is to find a hyperplane separating the two classes of vectors: those with positive labels and those with negative labels. If such a hyperplane, which completely separates the training set according to the labels, does not exist, then the goal is to find a hyperplane that achieves a separation of the training set with the smallest number of mistakes.

where $\mathop{\mbox{\rm sign}}(x)\in\{-1,+1\}$ is the sign function, and $\delta(z)\in\{0,1\}$ is the indicator function that takes the value $1$ if the condition $z$ is satisfied and zero otherwise.

This optimization problem, which is at the heart of the linear classification formulation, is NP-hard, and in fact NP-hard to even approximate non-trivially 8see bibliography for references to these results.. However, in the special case that a linear classifier (a hyperplane $\mathbf{x}$) that classifies all of the examples correctly exists, the problem is solvable in polynomial time via linear programming.

Various relaxations have been proposed to solve the more general case, when no perfect linear classifier exists. One of the most successful in practice is the Support Vector Machine (SVM) formulation.

The soft margin SVM relaxation replaces the $0/1$ loss in (2.7) with a convex loss function, called the hinge-loss, given by

In figure 2.4 we depict how the hinge loss is a convex relaxation for the non-convex $0/1$ loss.

Further, the SVM formulation adds to the loss minimization objective a term that regularizes the size of the elements in $\mathbf{x}$. The reason and meaning of this additional term shall be addressed in later sections. For now, let us consider the SVM convex program:

This is an unconstrained non-smooth and strongly convex program. It follows from Theorems 2.3 and 2.10 that ${O}(\frac{1}{\varepsilon})$ iterations suffice to attain an $\varepsilon$-approximate solution. We spell out the details of applying the subgradient descent algorithm to this formulation in Algorithm 7.

Notice that the learning rates are left unspecified, even though they can be explicitly set as in Theorem 2.10, or using the Polyak rate. The Polyak rate requires knowing the function value at optimality, although this can be relaxed (see bibliography).

A caveat of using gradient descent for SVM is the requirement to compute the full gradient, which may require a full pass over the data for each iteration. We will see a significantly more efficient algorithm in the next chapter!

6 Bibliographic Remarks

The reader is referred to dedicated books on convex optimization for much more in-depth treatment of the topics surveyed in this background chapter. For background in convex analysis see the texts (Borwein and Lewis, 2006; Rockafellar, 1997). The classic textbook of Boyd and Vandenberghe (2004) gives a broad introduction to convex optimization with numerous applications, see also (Boyd, 2014). For detailed rigorous convergence proofs and in depth analysis of first order methods, see lecture notes by Nesterov (2004) and books by Nemirovski and Yudin (1983); Nemirovskii (2004), as well as more recent lecture notes and texts (Bubeck, 2015; Hazan, 2019). Theorem 2.10 is taken from (Bubeck, 2015) Theorem 3.9.

The logarithmic overhead in the reductions of section 2.4 can be removed with a more careful reduction and analysis, for details see (Allen-Zhu and Hazan, 2016). A more sophisticated smoothing operator is the Moreau-Yoshida regularization: it avoids the dimension factor loss. However, it is sometimes less computationally efficient to work with (Parikh and Boyd, 2014).

The Polyak learning rate is detailed in (Polyak, 1987). A recent exposition allows obtaining the same optimal rate without knowledge of the optimal function value (Hazan and Kakade, 2019).

Using linear separators and halfspaces to learn and separate data was considered in the very early days of AI (Rosenblatt, 1958; Minsky and Papert, 1969). Notable the Perceptron algorithm was one of the first learning algorithms, and closely related to gradient descent. Support vector machines were introduced in (Cortes and Vapnik, 1995; Boser et al., 1992), see also the book of Schölkopf and Smola (2002).

Learning halfspaces with the zero-one loss is computationally hard, and hard to even approximate non-trivially (Daniely, 2016). Proving that a problem is hard to approximate is at the forefront of computational complexity, and based on novel characterizations of the complexity class NP (Arora and Barak, 2009).

7 Exercises

(a) $f(\mathbf{y})\geq f(\mathbf{x})+(\mathbf{y}-\mathbf{x})^{\top}\nabla{}f(\mathbf{x})+\frac{\alpha}{2}\|{\mathbf{x}-\mathbf{y}}\|^{2}$

(b) $f(\mathbf{y})\leq f(\mathbf{x})+(\mathbf{y}-\mathbf{x})^{\top}\nabla{}f(\mathbf{x})+\frac{\beta}{2}\|{\mathbf{x}-\mathbf{y}}\|^{2}$ Prove that if $f$ is twice differentiable and it holds that $\beta\textbf{I}\succcurlyeq\nabla^{2}f(\mathbf{x})\succcurlyeq\alpha\textbf{I}$ for any $\mathbf{x}\in\mathcal{K}$, then the condition number of $f$ over $\mathcal{K}$ is $\alpha/\beta$.

(a) The sum of convex functions is convex.

(b) Let $f$ be $\alpha_{1}$-strongly convex and $g$ be $\alpha_{2}$-strongly convex. Then $f+g$ is $(\alpha_{1}+\alpha_{2})$-strongly convex.

(c) Let $f$ be $\beta_{1}$-smooth and $g$ be $\beta_{2}$-smooth. Then $f+g$ is $(\beta_{1}+\beta_{2})$-smooth.

8. * Extending Nesterov’s accelerated GD algorithm: Assume a black-box access to Nesterov’s algorithm that attains the rate of $e^{-\sqrt{\gamma}\ T}$ for $\gamma$-well-conditioned functions, as in Table 2.1. Apply a reduction to obtain the $\frac{\beta}{T^{2}}$ rate for $\beta$-smooth functions, as in Table 2.1, up to logarithmic factors.

Chapter 3 First-Order Algorithms for Online Convex Optimization

In this chapter we describe and analyze the most simple and basic algorithms for online convex optimization (recall the definition of the model as introduced in chapter 1), which are also surprisingly useful and applicable in practice. We use the same notation introduced in §2.1. However, in contrast to the previous chapter, the goal of the algorithms introduced in this chapter is to minimize regret, rather than the optimization error (which is ill-defined in an online setting).

Table 3.1 details known upper and lower bounds on the regret for different types of convex functions as it depends on the number of prediction iterations.

The reader may recall Table 2.1 describing offline convergence of first order methods: as opposed to offline optimization, smoothness does not improve asymptotic regret rates. However, exp-concavity, a weaker property than strong convexity, comes into play and gives improved regret rates.

This chapter will present algorithms and lower bounds that realize the above known results for OCO. The property of exp-concavity and its applications, as well as logarithmic regret algorithms for exp-concave functions are deferred to the next chapter.

Perhaps the simplest algorithm that applies to the most general setting of online convex optimization is online gradient descent. This algorithm, which is based on standard gradient descent from offline optimization, was introduced in its online form by Zinkevich (see bibliography at the end of this section).

Pseudo-code for the algorithm is given in Algorithm 8, and a conceptual illustration is given in figure 3.1.

In each iteration, the algorithm takes a step from the previous point in the direction of the gradient of the previous cost. This step may result in a point outside of the underlying convex set. In such cases, the algorithm projects the point back to the convex set, i.e. finds its closest point in the convex set. Despite the fact that the next cost function may be completely different than the costs observed thus far, the regret attained by the algorithm is sublinear. This is formalized in the following theorem (recall the definition of $G$ and $D$ from the previous chapter).

Online gradient descent with step sizes $\{\eta_{t}=\frac{D}{G\sqrt{t}},\ t\in[T]\}$ guarantees the following for all $T\geq 1$:

Let $\mathbf{x}^{\star}\in\operatorname*{\arg\min}_{\mathbf{x}\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(\mathbf{x})$. Define $\nabla_{t}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\nabla f_{t}(\mathbf{x}_{t})$. By convexity

We first upper-bound $\nabla_{t}^{\top}(\mathbf{x}_{t}-\mathbf{x}^{\star})$ using the update rule for $\mathbf{x}_{t+1}$ and Theorem 2.1 (the Pythagorean theorem):

Summing (3.1) and (3.1) from $t=1$ to $T$, and setting $\eta_{t}=\frac{D}{G\sqrt{t}}$ (with $\frac{1}{\eta_{0}}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}0$):

The last inequality follows since $\eta_{t}=\frac{D}{G\sqrt{t}}$ and $\sum_{t=1}^{T}\frac{1}{\sqrt{t}}\leq 2\sqrt{T}$. ∎

The online gradient descent algorithm is straightforward to implement, and updates take linear time given the gradient. However, there is a projection step which may take significantly longer, as discussed in §2.1.1 and chapter 7.

2 Lower Bounds

The previous section introduces and analyzes a very simple and natural approach to online convex optimization. Before continuing our venture, it is worthwhile to consider whether the previous bound can be improved? We measure performance of OCO algorithms both by regret and by computational efficiency. Therefore, we ask ourselves whether even simpler algorithms that attain tighter regret bounds exist.

The computational efficiency of online gradient descent seemingly leaves little room for improvement, putting aside the projection step it runs in linear time per iteration. What about obtaining better regret?

Perhaps surprisingly, the answer is negative: online gradient descent attains, in the worst case, tight regret bounds up to small constant factors! This is formally given in the following theorem.

Any algorithm for online convex optimization incurs $\Omega(DG\sqrt{T})$ regret in the worst case. This is true even if the cost functions are generated from a fixed stationary distribution.

We give a sketch of the proof; filling in all details is left as an exercise at the end of this chapter.

Consider an instance of OCO where the convex set $\mathcal{K}$ is the $n$-dimensional hypercube, i.e.

There are $2^{n}$ linear cost functions, one for each vertex $\mathbf{v}\in\{\pm 1\}^{n}$, defined as

Notice that both the diameter of $\mathcal{K}$ and the bound on the norm of the cost function gradients, denoted G, are bounded by

The cost functions in each iteration are chosen at random, with uniform probability, from the set $\{f_{\mathbf{v}},\mathbf{v}\in\{\pm 1\}^{n}\}$. Denote by $\mathbf{v}_{t}\in\{\pm 1\}^{n}$ the vertex chosen in iteration $t$, and denote $f_{t}=f_{\mathbf{v}_{t}}$. By uniformity and independence, for any $t$ and $\mathbf{x}_{t}$ chosen online, $\mathop{\mbox{\bf E}}_{\mathbf{v}_{t}}[f_{t}(\mathbf{x}_{t})]=\mathop{\mbox{\bf E}}_{\mathbf{v}_{t}}[\mathbf{v}_{t}^{\top}\mathbf{x}_{t}]=0$. However,

The last equality is left as an exercise.

The facts above nearly complete the proof of Theorem 3.2; see the exercises at the end of this chapter.

3 Logarithmic Regret

At this point, the reader may wonder: we have introduced a seemingly sophisticated and obviously general framework for learning and prediction, as well as a linear-time algorithm for the most general case, complete with tight regret bounds, and done so with elementary proofs! Is this all OCO has to offer?

Simple is good: the philosophy behind OCO treats simplicity as a merit. The main reason OCO has taken the stage in online learning in recent years is the simplicity of its algorithms and their analysis, which allow for numerous variations and tweaks in their host applications.

A very wide class of settings, which will be the subject of the next sections, admit more efficient algorithms, in terms of both regret and computational complexity.

In §2 we surveyed optimization algorithms with convergence rates that vary greatly according to the convexity properties of the function to be optimized. Do the regret bounds in online convex optimization vary as much as the convergence bounds in offline convex optimization over different classes of convex cost functions?

Indeed, next we show that for important classes of loss functions significantly better regret bounds are possible.

The first algorithm that achieves regret logarithmic in the number of iterations is a twist on the online gradient descent algorithm, changing only the step size. The following theorem establishes logarithmic bounds on the regret if the cost functions are strongly convex.

For $\alpha$-strongly convex loss functions, online gradient descent with step sizes $\eta_{t}=\frac{1}{\alpha{t}}$ achieves the following guarantee for all $T\geq 1$

Let $\mathbf{x}^{\star}\in\operatorname*{\arg\min}_{\mathbf{x}\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(\mathbf{x})$. Recall the definition of regret

Define $\nabla_{t}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\nabla f_{t}(\mathbf{x}_{t})$. Applying the definition of $\alpha$-strong convexity to the pair of points $\{\mathbf{x}_{t}$,$\mathbf{x}^{*}\}$, we have

We proceed to upper-bound $\nabla_{t}^{\top}(\mathbf{x}_{t}-\mathbf{x}^{\star})$. Using the update rule for $\mathbf{x}_{t+1}$ and the Pythagorean theorem 2.1, we get

Summing (3.5) from $t=1$ to $T$, setting $\eta_{t}=\frac{1}{\alpha t}$ (define $\frac{1}{\eta_{0}}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}0$), and combining with (3.4), we have:

4 Application: Stochastic Gradient Descent

A special case of Online Convex Optimization is the well-studied setting of stochastic optimization. In stochastic optimization, the optimizer attempts to minimize a convex function over a convex domain as given by the mathematical program:

However, unlike standard offline optimization, the optimizer is given access to a noisy gradient oracle, defined by

That is, given a point in the decision set, a noisy gradient oracle returns a random vector whose expectation is the gradient at the point and whose variance is bounded by $G^{2}$.

We will show that regret bounds for OCO translate to convergence rates for stochastic optimization. As a special case, consider the online gradient descent algorithm whose regret is bounded by

Applying the OGD algorithm over a sequence of linear functions that are defined by the noisy gradient oracle at consecutive points, and finally returning the average of all points along the way, we obtain the stochastic gradient descent algorithm, presented in Algorithm 9.

Algorithm 9 with step sizes $\eta_{t}=\frac{D}{G\sqrt{t}}$ guarantees

It is important to note that in the proof above, we have used the fact that the regret bounds of online gradient descent hold against an adaptive adversary. This need arises since the cost functions $f_{t}$ defined in Algorithm 9 depend on the choice of decision $\mathbf{x}_{t}\in\mathcal{K}$.

Recall our example of Support Vector Machine training from §2.5. The task of training an SVM over a given data set amounts to solving the following convex program (equation (2.8)):

Using the technique described in this chapter, namely the OGD and SGD algorithms, we can devise a much faster algorithm than the one presented in the previous chapter. The idea is to generate an unbiased estimator for the gradient of the objective using a single example in the dataset, and use it in lieu of the entire gradient. This is given formally in the SGD algorithm for SVM training presented in Algorithm 10.

This matches the convergence rate of standard offline gradient descent. However, observe that each iteration is significantly cheaper—only one example in the data set need be considered! That is the magic of SGD; we have matched the nearly optimal convergence rate of first order methods using extremely cheap iterations. This makes it the method of choice in numerous applications.

5 Bibliographic Remarks

The OCO framework was introduced by Zinkevich (2003), where the OGD algorithm was introduced and analyzed. Precursors to this algorithm, albeit for less general settings, were introduced and analyzed in (Kivinen and Warmuth, 1997). Logarithmic regret algorithms for Online Convex Optimization were introduced and analyzed in (Hazan et al., 2007).

The stochastic gradient descent (SGD) algorithm dates back to Robbins and Monro (1951), where it was called “stochastic approximation”. The importance of SGD for machine learning was advocated for in (Bottou, 1998; Bottou and Bousquet, 2008). The literature on SGD is vast and the reader is referred to the text of Bubeck (2015) and paper by Lan (2012).

Application of SGD to soft-margin SVM training was explored in (Shalev-Shwartz et al., 2011a). Tight convergence rates of SGD for strongly convex and non-smooth functions were only recently obtained in (Hazan and Kale, 2011; Rakhlin et al., 2012; Shamir and Zhang, 2013).

6 Exercises

2. ∗ In this exercise we show how to remove some a-priory knowledge from the design of online convex optimization algorithms.

(a) Design an OCO algorithm that attains the same asymptotic regret bound as OGD, up to factors logarithmic in $G$ without knowing the parameter $G$ ahead of time.

(b) Do the same for the parameter $D$: design an OCO algorithm that attains the same asymptotic regret bound as OGD, up to factors logarithmic in $D$ without knowing the parameter $D$ ahead of time. This time you may assume $G$ is known. You may assume that it is possible to compute projections onto $\mathcal{K}$ without knowing its diameter.

3. In this exercise we prove a tight lower bound on the regret of any algorithm for online convex optimization.

(a) For any sequence of $T$ fair coin tosses, let $N_{h}$ be the number of head outcomes and $N_{t}$ be the number of tails. Give an asymptotically tight upper and lower bound on $\mathop{\mbox{\bf E}}[\left|N_{h}-N_{t}\right|]$. That is, give an order of growth of this random variable as a function of $T$, up to multiplicative and additive constants.

(b) Consider a 2-expert problem, in which the losses are inversely correlated: either expert one incurs a loss of one and the second expert negative one, or vice versa. Use the fact above to design a setting in which any experts algorithm incurs regret asymptotically matching the upper bound.

(c) Consider the general OCO setting over a convex set $\mathcal{K}$. Design a setting in which the cost functions have gradients whose norm is bounded by $G$, and obtain a lower bound on the regret as a function of $G$, the diameter of $\mathcal{K}$, and the number of game iterations.

4. Implement the SGD algorithm for SVM training. Apply it on the MNIST dataset. Compare your results to the offline GD algorithm from the previous chapter.

Chapter 4 Second-Order Methods

The motivation for this chapter is the application of online portfolio selection, considered in the first chapter of this book. We begin with a detailed description of this application. We proceed to describe a new class of convex functions that model this problem. This new class of functions is more general than the class of strongly convex functions discussed in the previous chapter. It allows for logarithmic regret algorithms, which are based on second order methods from convex optimization. In contrast to first order methods, which have been our focus thus far and relied on (sub)gradients, second order methods exploit information about the second derivative of the objective function.

In this subsection we give the formal definition of the universal portfolio selection problem that was informally described in §1.2.

Mainstream financial theory models stock prices as a stochastic process known as Geometric Brownian Motion (GBM). This model assumes that the fluctuations in the prices of the stocks behave essentially as a random walk. It is perhaps easier to think about a price of an asset (stock) on time segments, obtained from a discretization of time into equal segments. Thus, the logarithm of the price at segment $t+1$, denoted $l_{t+1}$, is given by the sum of the logarithm of the price at segment $t$ and a Gaussian random variable with a particular mean and variance,

This is only an informal way of thinking about GBM. The formal model is a continuous time process, similar to the discrete time stochastic process we have just described, obtained as the time intervals, means, and variances approach zero.

The GBM model gives rise to particular algorithms for portfolio selection (as well as more sophisticated applications such as options pricing). Given the means and variances of the stock prices over time of a set of assets, as well as their cross-correlations, a portfolio with maximal expected gain (mean) for a specific risk (variance) threshold can be formulated.

The fundamental question is, of course, how does one obtain the mean and variance parameters, not to mention the cross-correlations, of a given set of stocks? One accepted solution is to estimate these from historical data, e.g., by taking the recent history of stock prices.

1.2 Universal portfolio theory

The theory of universal portfolio selection is very different from the GBM model. The main difference being the lack of statistical assumptions about the stock market. The idea is to model investing as a repeated decision making scenario, which fits nicely into our OCO framework, and to measure regret as a performance metric.

How does the decision maker’s wealth change? Let $W_{t}$ be her total wealth at iteration $t$. Then, ignoring transaction costs, we have

Over $T$ iterations, the total wealth of the investor is given by

The goal of the decision maker, to maximize the overall wealth gain ${W_{T}}/{W_{0}}$, can be attained by maximizing the following more convenient logarithm of this quantity, given by

The above formulation is already very similar to our OCO setting, albeit phrased as a gain maximization rather than a loss minimization setting. Let

The convex set is the $n$-dimensional simplex $\mathcal{K}=\Delta_{n}$, and define the regret to be

The functions $f_{t}$ are concave rather than convex, which is perfectly fine as we are framing the problem as a maximization rather than a minimization. Note also that the regret is the negation of the usual regret notion (1.1) we have considered for minimization problems.

Since this is an online convex optimization instance, we can use the online gradient descent algorithm from the previous chapter to invest, which ensures $O(\sqrt{T})$ regret (see exercises). What guarantee do we attain in terms of investing? To answer this, in the next section we reason about what $\mathbf{x}^{\star}$ in the above expression may be.

1.3 Constant rebalancing portfolios

As $\mathbf{x}^{\star}\in\mathcal{K}=\Delta_{n}$ is a point in the $n$-dimensional simplex, consider the special case of $\mathbf{x}^{\star}=\mathbf{e}_{1}$, i.e., the first standard basis vector (the vector that has zero in all coordinates except the first, which is set to one). The term $\sum_{t=1}^{T}f_{t}(\mathbf{e}_{1})$ becomes $\sum_{t=1}^{T}\log\mathbf{r}_{t}(1)$, or

As $T$ becomes large, any sublinear regret guarantee (e.g., the $O(\sqrt{T})$ regret guarantee achieved using online gradient descent) achieves an average regret that approaches zero. In this context, this implies that the log-wealth gain achieved (in average over $T$ rounds) is as good as that of the first stock. Since $\mathbf{x}^{\star}$ can be taken to be any vector, sublinear regret guarantees average log-wealth growth as good as any stock!

However, $\mathbf{x}^{\star}$ can be significantly better, as shown in the following example. Consider a market of two stocks that fluctuate wildly. The first stock increases by $100\%$ every even day and returns to its original price the following (odd) day. The second stock does exactly the opposite: decreases by $50\%$ on even days and rises back on odd days. Formally, we have

Clearly, any investment in either of the stocks will not gain in the long run. However, the portfolio $\mathbf{x}^{\star}=(0.5,0.5)$ increases wealth by a factor of $\mathbf{r}_{t}^{\top}\mathbf{x}^{\star}=(\frac{1}{2})^{2}+1=1.25$ daily! Such a mixed distribution is called a fixed rebalanced portfolio, as it needs to rebalance the proportion of total capital invested in each stock at each iteration to maintain this fixed distribution strategy.

Thus, vanishing average regret guarantees long-run growth as the best constant rebalanced portfolio in hindsight. Such a portfolio strategy is called universal. We have seen that the online gradient descent algorithm gives essentially a universal algorithm with regret $O(\sqrt{T})$. Can we get better regret guarantees?

2 Exp-Concave Functions

For convenience, we return to considering losses of convex functions, rather than gains of concave functions as in the application for portfolio selection. The two problems are equivalent: we simply replace the maximization of the concave $f(\mathbf{x})=\log(\mathbf{r}_{t}^{\top}\mathbf{x})$ with the minimization of the convex $f(\mathbf{x})=-\log(\mathbf{r}_{t}^{\top}\mathbf{x})$.

In the previous chapter we have seen that the OGD algorithm with carefully chosen step sizes can deliver logarithmic regret for strongly convex functions. However, the loss function for the OCO setting of portfolio selection, $f_{t}(\mathbf{x})=-\log(\mathbf{r}_{t}^{\top}\mathbf{x}),$ is not strongly convex. Instead, the Hessian of this function is given by

which is a rank one matrix. Recall that the Hessian of a twice-differentiable strongly convex function is larger than a multiple of identity matrix and is positive definite and in particular has full rank. Thus, the loss function above is quite far from being strongly convex.

However, an important observation is that this Hessian is large in the direction of the gradient. This property is called exp-concavity. We proceed to define this property rigorously and show that it suffices to attain logarithmic regret.

For the following discussion, recall the notation of §2.1, and in particular our convention over matrices that $A\succcurlyeq B$ if and only if $A-B$ is positive semidefinite. Exp-concavity implies strong-convexity in the direction of the gradient. This reduces to the following property:

The proof of this lemma is given as a guided exercise at the end of this chapter. We prove a slightly stronger lemma below.

The composition of a concave and non-decreasing function with another concave function is concave 9see exercises.. Therefore, since $2\gamma\leq\alpha$, the composition of $g(x)=x^{2\gamma/\alpha}$ with $f(\mathbf{x})=\exp(-\alpha f(\mathbf{x}))$ is concave. It follows that the function $h(\mathbf{x})\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\exp(-2\gamma f(\mathbf{x}))$ is concave. Then by the concavity of $h(\mathbf{x})$,

Plugging in $\nabla h(\mathbf{y})=-2\gamma\exp(-2\gamma f(\mathbf{y}))\nabla f(\mathbf{y})$ gives

Next, note that $|2\gamma\nabla f(\mathbf{y})^{\top}(\mathbf{x}-\mathbf{y})|\ \leq\ 2\gamma GD\leq 1$ and that using the Taylor approximation, for $z\geq-1$, it holds that $-\log(1-z)\geq z+\frac{1}{4}{z^{2}}$. Applying the inequality for $z=2\gamma\nabla f(\mathbf{y})^{\top}(\mathbf{x}-\mathbf{y})$ implies the lemma. ∎

3 Exponentially Weighted Online Convex Optimization

Before diving into efficient second order methods, we first describe a simple algorithm based on the multiplicative updates method which gives logarithmic regret for exp-concave losses. Algorithm (11) below, called EWOO, is a close relative to the Hedge Algorithm (1). Its regret guarantee is robust: it does not include a Lipschitz constant or a diameter bound. In addition, it is particularly simple to describe and analyze.

The downside of EWOO is its running time. A naive implementation would run in exponential time of the dimension. It is possible to given a randomized polynomial time implementation based on random sampling techniques, where the polynomial depends both on the dimension as well as the number of iterations, see bibliographic section for more details.

In the analysis below, it can be observed that choosing $\mathbf{x}_{t}$ at random with density proportional to $w_{t}(\mathbf{x})$, instead of computing the entire integral, also guarantees our regret bounds on the expectation. This is the basis for the polynomial time implementation. We proceed to give the logarithmic regret bounds.

Let $h_{t}(\mathbf{x})=e^{-\alpha f_{t}(\mathbf{x})}$. Since $f_{t}$ is $\alpha$-exp-concave, we have that $h_{t}$ is concave and thus

By definition of $\mathbf{x}^{\star}$ we have $\mathbf{x}^{\star}\in\arg\max_{\mathbf{x}\in\mathcal{K}}\prod_{t=1}^{T}h_{t}(\mathbf{x})$. Denote by $S_{\delta}\subset\mathcal{K}$ the translated Minkowski set given by

By concavity of $h_{t}$ and the fact that $h_{t}$ is non-negative, we have that,

Finally, since $S_{\delta}=(1-\delta)\mathbf{x}^{\star}+\delta\mathcal{K}$ is simply a rescaling of $\mathcal{K}$ followed by a translation, and we are in $d$ dimensions, $\mbox{vol}(S_{\delta})=\mbox{vol}(\mathcal{K})\times\delta^{d}$. Putting this together with equation (4.1), we have

We can now simplify by taking logarithms and changing sides,

where the last step is by choosing $\delta=\frac{1}{T}$. ∎

4 The Online Newton Step Algorithm

Thus far we have only considered first order methods for regret minimization. In this section we consider a quasi-Newton approach, i.e., an online convex optimization algorithm that approximates the second derivative, or Hessian in more than one dimension. However, strictly speaking, the algorithm we analyze is also first order, in the sense that it only uses gradient information.

The algorithm we introduce and analyze, called online Newton step, is detailed in Algorithm 12. At each iteration, this algorithm chooses a vector that is the projection of the sum of the vector chosen at the previous iteration and an additional vector. Whereas for the online gradient descent algorithm this added vector was the gradient of the previous cost function, for online Newton step this vector is different: it is reminiscent to the direction in which the Newton-Raphson method would proceed if it were an offline optimization problem for the previous cost function. The Newton-Raphson algorithm would move in the direction of the vector which is the inverse Hessian times the gradient. In online Newton step, this direction is $A_{t}^{-1}\nabla_{t}$, where the matrix $A_{t}$ is related to the Hessian as will be shown in the analysis.

Since adding a multiple of the Newton vector $A_{t}^{-1}\nabla_{t}$ to the current vector may result in a point outside the convex set, an additional projection step is required to obtain $\mathbf{x}_{t}$, the decision at time $t$. This projection is different than the standard Euclidean projection used by online gradient descent in Section 3.1. It is the projection according to the norm defined by the matrix $A_{t}$, rather than the Euclidean norm.

The advantage of the online Newton step algorithm is its logarithmic regret guarantee for exp-concave functions, as defined in the previous section. The following theorem bounds the regret of online Newton step.

Algorithm 12 with parameters $\gamma=\frac{1}{2}\min\{\frac{1}{GD},\alpha\}$, $\varepsilon=\frac{1}{\gamma^{2}D^{2}}$ and $T\geq 4$ guarantees

As a first step, we prove the following lemma.

The regret of online Newton step is bounded by

Let $\mathbf{x}^{\star}\in\arg\min_{\mathbf{x}\in\mathcal{K}}\sum_{t=1}^{T}f_{t}(\mathbf{x})$ be the best decision in hindsight. By Lemma 4.3, we have for $\gamma=\frac{1}{2}\min\{\frac{1}{GD},\alpha\}$,

According to the update rule of the algorithm $\mathbf{x}_{t+1}=\mathop{\Pi}_{\mathcal{K}}^{{A}_{t}}(\mathbf{y}_{t+1})$. Now, by the definition of $\mathbf{y}_{t+1}$:

Multiplying the transpose of (4.2) by (4.3) we get

Since $\mathbf{x}_{t+1}$ is the projection of $\mathbf{y}_{t+1}$ in the norm induced by ${A}_{t}$, we have by the Pythagorean theorem (see §2.1.1)

This inequality is the reason for using generalized projections as opposed to standard projections, which were used in the analysis of online gradient descent (see §3.1 Equation (3.2)). This fact together with (4.4) gives

Now, summing up over $t=1$ to $T$ we get that

In the last inequality we use the fact that $A_{t}-A_{t-1}=\nabla_{t}\nabla_{t}^{\top}$, and the fact that the matrix $A_{T}$ is PSD and hence the last term before the inequality is negative. Thus,

Using the algorithm parameters ${A}_{1}-\nabla_{1}\nabla_{1}^{\top}=\varepsilon\mathbf{I}_{n}$ , $\varepsilon=\frac{1}{\gamma^{2}D^{2}}$ and our notation for the diameter $\|\mathbf{x}_{1}-\mathbf{x}^{\star}\|^{2}\leq D^{2}$ we have

Since $\gamma=\frac{1}{2}\min\{\frac{1}{GD},\alpha\}$, we have $\frac{1}{\gamma}\leq 2(\frac{1}{\alpha}+GD)$. This gives the lemma. ∎

First we show that the term $\sum_{t=1}^{T}\nabla_{t}^{\top}{A}_{t}^{-1}\nabla_{t}$ is upper bounded by a telescoping sum. Notice that

Since $A_{T}=\sum_{t=1}^{T}\nabla_{t}\nabla_{t}^{\top}+\varepsilon I_{n}$ and $\|\nabla_{t}\|\leq G$, the largest eigenvalue of $A_{T}$ is at most $TG^{2}+\varepsilon$. Hence the determinant of $A_{T}$ can be bounded by $|A_{T}|\leq(TG^{2}+\varepsilon)^{n}$. Hence recalling that $\varepsilon=\frac{1}{\gamma^{2}D^{2}}$ and $\gamma=\frac{1}{2}\min\{\frac{1}{GD},\alpha\}$, for $T>4$,

which implies the theorem for $n>1,\ T\geq 4$.

It remains to prove the technical lemma for positive semidefinite (PSD) matrices used above.

Let $A\succcurlyeq B\succ 0$ be positive definite matrices. Then

For any positive definite matrix $C$, denote by $\lambda_{1}(C),\ldots,\lambda_{n}(C)$ its eigenvalues (which are positive).

In the last equality we use the facts $|AB|=|A||B|$ and $|A^{-1}|=\frac{1}{|A|}$ for positive definite matrices (see exercises). ∎

The online Newton step algorithm requires $O(n^{2})$ space to store the matrix $A_{t}$. Every iteration requires the computation of the matrix $A_{t}^{-1}$, the current gradient, a matrix-vector product, and possibly a projection onto the underlying convex set $\mathcal{K}$.

A naïve implementation would require computing the inverse of the matrix $A_{t}$ on every iteration. However, in the case that $A_{t}$ is invertible, the matrix inversion lemma (see bibliography) states that for invertible matrix $A$ and vector $\mathbf{x}$,

Thus, given $A_{t-1}^{-1}$ and $\nabla_{t}$ one can compute $A_{t}^{-1}$ in time $O(n^{2})$ using only matrix-vector and vector-vector products.

The online Newton step algorithm also needs to make projections onto $\mathcal{K}$, but of a slightly different nature than online gradient descent and other online convex optimization algorithms. The required projection, denoted by $\mathop{\Pi}_{\mathcal{K}}^{A_{t}}$, is in the vector norm induced by the matrix $A_{t}$, viz. $\|\mathbf{x}\|_{A_{t}}=\sqrt{\mathbf{x}^{\top}A_{t}\mathbf{x}}$. It is equivalent to finding the point $\mathbf{x}\in\mathcal{K}$ which minimizes $(\mathbf{x}-\mathbf{y})^{\top}A_{t}(\mathbf{x}-\mathbf{y})$ where $\mathbf{y}$ is the point we are projecting. This is a convex program which can be solved up to any degree of accuracy in polynomial time.

Modulo the computation of generalized projections, the online Newton step algorithm can be implemented in time and space $O(n^{2})$. In addition, the only information required is the gradient at each step (and the exp-concavity constant $\alpha$ of the loss functions).

5 Bibliographic Remarks

The Geometric Brownian Motion model for stock prices was suggested and studied as early as 1900 in the PhD thesis of Louis Bachelier (Bachelier, 1900), see also (Osborne, 1959), and used in the Nobel Prize winning work of Black and Scholes on options pricing (Black and Scholes, 1973). In a strong deviation from standard financial theory, Thomas Cover (Cover, 1991) put forth the universal portfolio model, whose algorithmic theory we have historically sketched in chapter 1. The EWOO algorithm was essentially given in Cover’s paper for the application of portfolio selection and logarithmic loss functions, and extended to exp-concave loss functions in (Hazan et al., 2006). The randomized extension of Cover’s algorithm that runs in polynomial running time is due to Kalai and Vempala (2003), and it naturally extends to EWOO.

Some bridges between classical portfolio theory and the universal model appear in (Abernethy et al., 2012). Options pricing and its relation to regret minimization was recently also explored in the work of (DeMarzo et al., 2006).

Exp-concave functions have been considered in the context of prediction in (Kivinen and Warmuth, 1999), see also (Cesa-Bianchi and Lugosi, 2006) (chapter 3.3 and bibliography). A more general condition than exp-concavity called mixability was used by Vovk (1990) to give a general multiplicative update algorithm, see also (Foster et al., 2018). For a thorough discussion of various conditions that allow logarithmic regret in online learning see (van Erven et al., 2015).

For the square-loss, (Azoury and Warmuth, 2001) gave a specially tailored and near-optimal prediction algorithm. Logarithmic regret algorithms for online convex optimization and the Online Newton Step algorithm were presented in (Hazan et al., 2007).

The Sherman-Morrison formula, a.k.a. the matrix inversion lemma, gives the form of the inverse of a matrix after a rank-1 update, see (Riedel, 1991).

6 Exercises

1. For this question, assume all functions are twice differentiable. Prove that exp-concave functions are a larger class than strongly convex and Lipschitz functions. That is, prove that a strongly convex function over a bounded domain that is also $G$-Lipschitz is also exp-concave. Show that the converse is not necessarily true.

2. Prove that a twice-differentiable function $f$ is $\alpha$-exp-concave over $\mathcal{K}$ if and only if for all $\mathbf{x}\in\mathcal{K}$,

Hint: consider the Hessian of the function $e^{-\alpha f(\mathbf{x})}$, and use the fact that the Hessian of a convex function is always positive semidefinite.

3. Write pseudo-code for a portfolio selection algorithm based on online gradient descent. That is, given a set of return vectors, spell out the exact constants and updates based upon the gradients of the reward functions. Derive the regret bound based on Theorem 3.1. You may assume that the multiplicative change in price for any single asset is bounded, and use this quantity in your regret bound. Do the same (pseudo-code and regret bound) for the Online Newton Step algorithm applied to portfolio selection. Note: you are not required to give pseudo-code for projections onto the simplex.

4. Download stock prices from your favorite online finance website over a period of at least three years. Create a dataset for testing portfolio selection algorithms by creating price-return vectors. Implement the OGD and ONS algorithms and benchmark them on your data.

5. Prove that for positive definite matrices, $A,B\succ 0$, the following hold: $|AB|=|A||B|$ and $|A^{-1}|=\frac{1}{|A|}$, where $|A|$ denotes the determinant of $A$.

Chapter 5 Regularization

In the previous chapters we have explored algorithms for OCO that are motivated by convex optimization. However, unlike convex optimization, the OCO framework optimizes the Regret performance metric. This distinction motivates a family of algorithms, called “Regularized Follow The Leader” (RFTL), which we introduce in this chapter.

In an OCO setting of regret minimization, the most straightforward approach for the online player is to use at any time the optimal decision (i.e., point in the convex set) in hindsight. Formally, let

This flavor of strategy is known as “fictitious play” in economics, and has been named “Follow the Leader” (FTL) in machine learning. It is not hard to see that this simple strategy fails miserably in a worst-case sense. That is, this strategy’s regret can be linear in the number of iterations, as the following example shows: Consider $\mathcal{K}=$, let $f_{1}(x)=\frac{1}{2}x$, and let $f_{\tau}$ for $\tau=2,\ldots,T$ alternate between $-x$ or $x$. Thus,

The FTL strategy will keep shifting between $x_{t}=-1$ and $x_{t}=1$, always making the wrong choice.

The intuitive FTL strategy fails in the example above because it is unstable. Can we modify the FTL strategy such that it won’t change decisions often, thereby causing it to attain low regret?

This question motivates the need for a general means of stabilizing the FTL method. Such a means is referred to as “regularization”.

Although it is not strictly necessary, we assume that the regularization functions in this chapter are twice differentiable over $\mathcal{K}$ and, for all points $\mathbf{x}\in\text{int}(\mathcal{K})$ in the interior of the decision set, have a Hessian $\nabla^{2}R(\mathbf{x})$ that is, by the strong convexity of $R$, positive definite.

We denote the diameter of the set $\mathcal{K}$ relative to the function $R$ as

Henceforth we make use of general norms and their dual. The dual norm to a norm $\|\cdot\|$ is given by the following definition:

A positive definite matrix $A$ gives rise to the matrix norm $\|\mathbf{x}\|_{A}=\sqrt{\mathbf{x}^{\top}A\mathbf{x}}$. The dual norm of a matrix norm is $\|\mathbf{x}\|_{A}^{*}=\|\mathbf{x}\|_{A^{-1}}$.

The generalized Cauchy-Schwarz theorem asserts $\mathbf{x}^{\top}\mathbf{y}\leq\|\mathbf{x}\|\|\mathbf{y}\|^{*}$ and in particular for matrix norms, $\mathbf{x}^{\top}\mathbf{y}\leq\|\mathbf{x}\|_{A}\|\mathbf{y}\|_{A}^{*}$ (see exercises).

In our derivations, we usually consider matrix norms with respect to $\nabla^{2}R(\mathbf{x})$, the Hessian of the regularization function $R(\mathbf{x})$, as well as the inverse Hessian denoted $\nabla^{-2}R(\mathbf{x})$. In such cases, we use the notation

A crucial quantity in the analysis of OCO algorithms that use regularization is the remainder term of the Taylor approximation of the regularization function, and especially the remainder term of the first order Taylor approximation. The difference between the value of the regularization function at $\mathbf{x}$ and the value of the first order Taylor approximation is known as the Bregman divergence, given by

Denote by $B_{R}(\mathbf{x}||\mathbf{y})$ the Bregman divergence with respect to the function ${R}$, defined as

For twice differentiable functions, Taylor expansion and the mean-value theorem assert that the Bregman divergence is equal to the second derivative at an intermediate point, i.e., (see exercises)

for some point $\mathbf{z}\in[\mathbf{x},\mathbf{y}]$, meaning there exists some $\alpha\in$ such that $\mathbf{z}=\alpha\mathbf{x}+(1-\alpha)\mathbf{y}$. Therefore, the Bregman divergence defines a local norm, which has a dual norm. We shall denote this dual norm by

In online convex optimization, we commonly refer to the Bregman divergence between two consecutive decision points $\mathbf{x}_{t}$ and $\mathbf{x}_{t+1}$. In such cases, we shorthand notation for the norm defined by the Bregman divergence with respect to ${R}$ on the intermediate point in $[\mathbf{x}_{t},\mathbf{x}_{t+1}]$ as $\|\cdot\|_{t}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\|\cdot\|_{\mathbf{x}_{t},\mathbf{x}_{t+1}}$. The latter norm is called the local norm at iteration $t$. With this notation, we have $B_{R}(\mathbf{x}_{t}||\mathbf{x}_{t+1})=\frac{1}{2}\|\mathbf{x}_{t}-\mathbf{x}_{t+1}\|_{t}^{2}$.

Finally, we consider below generalized projections that use the Bregman divergence as a distance instead of a norm. Formally, the projection of a point $\mathbf{y}$ according to the Bregman divergence with respect to function $R$ is given by

2 The RFTL Algorithm and its Analysis

Recall the caveat with straightforward use of follow-the-leader: as in the bad example we have considered, the predictions of FTL may vary wildly from one iteration to the next. This motivates the modification of the basic FTL strategy in order to stabilize the prediction. By adding a regularization term, we obtain the RFTL (Regularized Follow the Leader) algorithm.

We proceed to formally describe the RFTL algorithmic template and analyze it. The analysis gives asymptotically optimal regret bounds. However, we do not optimize the constants in the regret bounds in order to improve clarity of presentation.

Throughout this chapter, recall the notation of $\nabla_{t}$ to denote the gradient of the current cost function at the current point, i.e.,

In the OCO setting, the regret of convex cost functions can be bounded by a linear function via the inequality $f_{t}(\mathbf{x}_{t})-f_{t}(\mathbf{x}^{\star})\leq\nabla_{t}^{\top}(\mathbf{x}_{t}-\mathbf{x}^{\star})$. Thus, the overall regret (recall definition (1.1)) of an OCO algorithm can be bounded by

The generic RFTL meta-algorithm is defined in Algorithm 13. The regularization function ${R}$ is assumed to be strongly convex, smooth, and twice differentiable.

2.2 The regret bound

The RFTL Algorithm 13 attains for every $\mathbf{u}\in\mathcal{K}$ the following bound on the regret:

If an upper bound on the local norms is known, i.e., $\|\nabla_{t}\|_{t}^{*}\leq G_{R}$ for all times $t$, then we can further optimize over the choice of $\eta$ to obtain

To prove Theorem 5.2, we first relate the regret to the “stability” in prediction. This is formally captured by the following lemma10Historically, this lemma is known as the “FTL-BTL,” which stands for follow-the-leader vs. be-the-leader. BTL is a hypothetical algorithm that predicts $\mathbf{x}_{t+1}$ at iteration $t$, where $\mathbf{x}_{t}$ is the prediction made by FTL. These terms were coined by Kalai and Vempala (Kalai and Vempala, 2005)..

Algorithm 13 guarantees the following regret bound

For convenience of the derivations, define the functions

By equation (5.1), it suffices to bound $\sum_{t=1}^{T}[g_{t}(\mathbf{x}_{t})-g_{t}(\mathbf{u})]$. As a first step, we prove the following inequality:

by induction on $T$: Induction base: By definition, we have that $\mathbf{x}_{1}=\operatorname*{\arg\min}_{\mathbf{x}\in\mathcal{K}}\{R(\mathbf{x})\}$, and thus $g_{0}(\mathbf{u})\geq g_{0}(\mathbf{x}_{1})$ for all $\mathbf{u}$. Induction step: Assume that for $T$, we have

and let us prove the statement for $T+1$. Since $\mathbf{x}_{T+2}=\operatorname*{\arg\min}_{\mathbf{x}\in\mathcal{K}}\{\sum_{t=0}^{T+1}g_{t}(\mathbf{x})\}$ we have:

Where in the third line we used the induction hypothesis for $\mathbf{u}=\mathbf{x}_{T+2}$. ∎

Recall that ${R}(\mathbf{x})$ is a convex function and $\mathcal{K}$ is a convex set. Denote:

By the Taylor expansion (with its explicit remainder term via the mean-value theorem) at $\mathbf{x}_{t+1}$, and by the definition of the Bregman divergence,

The inequality holds since $\mathbf{x}_{t+1}$ is a minimum of $\Phi_{t}$ over $\mathcal{K}$, as in Theorem 2.2. The last equality holds since the component $\nabla_{s}^{\top}\mathbf{x}$ is linear and thus does not affect the Bregman divergence. Thus,

To proceed, recall the shorthand for the norm induced by the Bregman divergence with respect to ${R}$ on point $\mathbf{x}_{t},\mathbf{x}_{t+1}$ as $\|\cdot\|_{t}=\|\cdot\|_{\mathbf{x}_{t},\mathbf{x}_{t+1}}$. Similarly for the dual local norm $\|\cdot\|^{*}_{t}=\|\cdot\|^{*}_{\mathbf{x}_{t},\mathbf{x}_{t+1}}$. With this notation, we have $B_{R}(\mathbf{x}_{t}||\mathbf{x}_{t+1})=\frac{1}{2}\|\mathbf{x}_{t}-\mathbf{x}_{t+1}\|_{t}^{2}$. By the generalized Cauchy-Schwarz inequality,

Combining this inequality with Lemma 5.3 we obtain the theorem statement. ∎

3 Online Mirror Descent

In the convex optimization literature, “Mirror Descent” refers to a general class of first order methods generalizing gradient descent. Online Mirror descent (OMD) is the online counterpart of this class of methods. This relationship is analogous to the relationship of online gradient descent to traditional (offline) gradient descent.

For the RFTL algorithm the intuition was straightforward—the regularization was used to ensure stability of the decision. For OMD, regularization has an additional purpose: regularization transforms the space in which gradient updates are performed. This transformation enables better bounds in terms of the geometry of the space.

The OMD algorithm comes in two flavors: an agile and a lazy version. The lazy version keeps track of a point in Euclidean space and projects onto the convex decision set $\mathcal{K}$ only at decision time. In contrast, the agile version maintains a feasible point at all times, much like OGD.

Both versions can be analyzed to give roughly the same regret bounds as the RFTL algorithm. In light of what we will see next, this is not surprising: for linear cost functions, the RFTL and lazy-OMD algorithms are equivalent!

Thus, we get regret bounds for free for the lazy version. The agile version can be shown to attain similar regret bounds, and is in fact superior in certain settings that require adaptivity. This issue is further explored in chapter 10. The analysis of the agile version is of independent interest and we give it below.

The OMD (lazy version) and RFTL are identical for linear cost functions, as we show next.

Let $f_{1},...,f_{T}$ be linear cost functions. The lazy OMD and RFTL algorithms produce identical predictions, i.e.,

First, observe that the unconstrained minimum

By definition, $\mathbf{y}_{t}$ also satisfies the above equation, but since ${R}(\mathbf{x})$ is strictly convex, there is only one solution for the above equation and thus $\mathbf{y}_{t}=\mathbf{x}^{\star}_{t}$. Hence,

Since ${R}(\mathbf{y}_{t})$ and $\sum_{s=1}^{t-1}\nabla_{s}^{\top}\mathbf{y}_{t}$ are independent of $\mathbf{x}$, it follows that $B_{R}(\mathbf{x}||\mathbf{y}_{t})$ is minimized at the point $\mathbf{x}$ that minimizes ${R}(\mathbf{x})+\eta\,\sum_{s=1}^{t-1}\nabla_{s}^{\top}\mathbf{x}$ over $\mathcal{K}$ which, in turn, implies that

3.2 Regret bounds for Mirror Descent

In this subsection we prove regret bounds for the agile version of the RFTL algorithm. The analysis is quite different than the one for the lazy version, and of independent interest.

The OMD Algorithm 14 attains for every $\mathbf{u}\in\mathcal{K}$ the following bound on the regret:

If an upper bound on the local norms is known, i.e., $\|\nabla_{t}\|_{t}^{*}\leq G_{R}$ for all times $t$, then we can further optimize over the choice of $\eta$ to obtain

Since the functions $\mathbf{f}_{t}$ are convex, for any $\mathbf{x}^{*}\in K$,

The following property of Bregman divergences follows from the definition: for any vectors $\mathbf{x},\mathbf{y},\mathbf{z}$,

where the last inequality follows from the generalized Pythagorean theorem, as $\mathbf{x}_{t+1}$ is the projection w.r.t the Bregman divergence of $\mathbf{y}_{t+1}$ and $\mathbf{x}^{*}\in K$ is in the convex set. Summing over all iterations,

We proceed to bound $B_{\mathcal{R}}(\mathbf{x}_{t},\mathbf{y}_{t+1})$. By definition of Bregman divergence, and the generalized Cauchy-Schwartz inequality,

where in the last inequality follows from $(a-b)^{2}\geq 0$. Thus, we have

Plugging back into Equation (5.3), and by non-negativity of the Bregman divergence, we get

by taking $\eta=\frac{D_{R}}{\sqrt{T}G_{R}}$

4 Application and Special Cases

In this section we illustrate the generality of the regularization technique: we show how to derive the two most important and famous online algorithms—the online gradient descent algorithm and the online exponentiated gradient (based on the multiplicative update method)—from the RFTL meta-algorithm.

Other important special cases of the RFTL meta-algorithm are derived with matrix-norm regularization—namely, the von Neumann entropy function, and the log-determinant function, as well as self-concordant barrier regularization—which we shall explore in detail in the next chapter.

To derive the online gradient descent algorithm, we take ${R}(\mathbf{x})=\frac{1}{2}\|\mathbf{x}-\mathbf{x}_{0}\|_{2}^{2}$ for an arbitrary $\mathbf{x}_{0}\in\mathcal{K}$. Projection with respect to this divergence is the standard Euclidean projection (see exercises), and in addition, $\nabla{R}(\mathbf{x})=\mathbf{x}-\mathbf{x}_{0}$. Hence, the update rule for the OMD Algorithm 14 becomes:

The latter algorithm is exactly online gradient descent, as described in Algorithm 8 in chapter 3. However, both variants behave very differently, as explored in chapter 10 (see also exercises).

Theorem 5.2 gives us the following bound on the regret (where $D_{R},\|\cdot\|_{t}$ are the diameter and local norm defined with respect to the regularizer $R$ as defined in the beginning of this chapter, and $D$ is the Euclidean diameter as defined in chapter 2)

where the second inequality follows since for ${R}(\mathbf{x})=\frac{1}{2}\|\mathbf{x}-\mathbf{x}_{0}\|^{2}$, the local norm $\|\cdot\|_{t}$ reduces to the Euclidean norm.

4.2 Deriving multiplicative updates

Let ${R}(\mathbf{x})=\mathbf{x}\log\mathbf{x}=\sum_{i}\mathbf{x}_{i}\log\mathbf{x}_{i}$ be the negative entropy function, where $\log\mathbf{x}$ is to be interpreted element-wise. Then $\nabla{R}(\mathbf{x})=\mathbf{1}+\log\mathbf{x}$, and hence the update rules for the OMD algorithm become:

which is exactly the Hedge algorithm from the first chapter!

Theorem 5.6 gives us the following bound on the regret:

If the costs per individual expert are in the range $$, it can be shown that

In addition, when $R$ is the negative entropy function, the diameter over the simplex can be shown to be bounded by $D_{R}^{2}\leq\log n$ (see exercises), giving rise to the bound

For an arbitrary range of costs, we obtain the exponentiated gradient algorithm described in Algorithm 15.

The regret achieved by the exponentiated gradient algorithm can be bounded using the following corollary of Theorem 5.2:

The exponentiated gradient algorithm with gradients bounded by $\|\nabla_{t}\|_{\infty}\leq G_{\infty}$ and parameter $\eta=\sqrt{\frac{\log n}{2TG_{\infty}^{2}}}$ has regret bounded by

5 Randomized Regularization

The connection between stability in decision making and low regret has motivated our discussion of regularization thus far. However, this stability need not be achieved only using strongly convex regularization functions. An alternative method to achieve stability in decisions is by introducing randomization into the algorithm. In fact, historically, this method preceded methods based on strongly convex regularization (see bibliography).

In this section we first describe a deterministic algorithm for online convex optimization that is easily amenable to speedup via randomization. We then give an efficient randomized algorithm for the special case of OCO with linear losses.

For simplicity, we consider ourselves in this section with a slightly restricted version of OCO. So far, we have not restricted the cost functions in any way, and they could depend on the choice of decision by the online learner. However, when dealing with randomized algorithms, this issue becomes a bit more subtle: can the cost functions depend on the randomness of the decision making algorithm itself? Furthermore, when analyzing the regret, which is now a random variable, dependencies across different iterations require probabilistic machinery which adds little to the fundamental understanding of randomized OCO algorithms. To avoid these complications, we make the following assumption throughout this section: the cost functions $\{\mathbf{f}_{t}\}$ are adversarially chosen ahead of time, and do not depend on the actual decisions of the online learner. This version of OCO is called the oblivious setting, to distinguish it from the adaptive setting.

5.1 Perturbation for convex losses

The prediction in Algorithm 16 is according to a version of the follow-the-leader algorithm, augmented with an additional component of randomization. It is a deterministic algorithm that computes the expected decision according to a random variable. The random variable is the minimizer over the decision set according to the sum of gradients of the cost functions and an additional random vector.

In practice, the expectation need not be computed exactly. Estimation (via random sampling) up to a precision that depends linearly on the number of iterations would suffice.

The first parameter, $\sigma$, is related to the variance of ${\mathcal{D}}$, while the second, $L$, is a measure of the sensitivity of the distribution11In harmonic analysis of Boolean functions, a similar quantity is called “average sensitivity”.. For example, if ${\mathcal{D}}$ is the uniform distribution over the hypercube $^{n}$, then it holds that (see exercises) for the Euclidean norm

Reusing notation from previous chapters, denote by $D=D_{a}$ the diameter of the set $\mathcal{K}$ according to the norm $\|\cdot\|_{a}$, and by $D^{*}=D_{a}^{*}$ the diameter according to its dual norm. Similarly, denote by $G=G_{a}$ and $G^{*}=G_{a}^{*}$ an upper bound on the norm (and dual norm) of the gradients.

Let the distribution ${\mathcal{D}}$ be $(\sigma,L)$-stable with respect to norm $\|\cdot\|_{a}$. The FPL algorithm attains the following bound on the regret:

We can further optimize over the choice of $\eta$ to obtain

Define the random variable $\mathbf{x}_{t}^{\mathbf{n}}=\operatorname*{\arg\min}_{\mathbf{x}\in\mathcal{K}}\left\{\eta\sum_{s=1}^{t}\nabla_{s}^{\top}\mathbf{x}+\mathbf{n}^{\top}\mathbf{x}\right\}$, and the random function $g_{0}^{\mathbf{n}}$ as

It follows from Lemma 5.4 applied to the functions $\{g_{t}(\mathbf{x})=\nabla_{t}^{\top}\mathbf{x}\}$ that

We now argue that $\|\mathbf{x}_{t}-\mathbf{x}_{t+1}\|=O(\eta)$. Let

Notice that $\mathbf{x}_{t},\mathbf{x}_{t+1}$ may depend on each other. However, by linearity of expectation, we have that

Substituting this bound back into (5.5) we have

For the choice of ${\mathcal{D}}$ as the uniform distribution over the unit hypercube $^{n}$, which has parameters $\sigma_{2}\leq\sqrt{n}$ and $L_{2}\leq 1$ for the Euclidean norm, the optimal choice of $\eta$ gives a regret bound of $DGn^{1/4}\sqrt{T}$. This is a factor ${n}^{1/4}$ worse than the online gradient descent regret bound of Theorem 3.1. For certain decision sets $\mathcal{K}$ a better choice of distribution ${\mathcal{D}}$ results in near-optimal regret bounds.