A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization

Introduction

First-order optimization methods, such as (sub)gradient-descent methods and conditional-gradient methods , are often the method of choice for coping with very large scale optimization tasks. While theoretically attaining inferior convergence rate compared to other efficient optimization algorithms (e.g. interior point methods ), modern optimization problems are often so large that using second-order information or other super-linear operations becomes practically infeasible.

The computational bottleneck of (sub)gradient descent methods in many settings is the computation of orthogonal projections onto the convex domain. This is also the case with proximal methods . Computing such projections is very efficient for simple domains such as the euclidean ball, the hypercube and the simplex but much more involved for more complicated domains, making these methods impractical for such problems in high-dimensional settings.

On the other hand, for many convex sets of interest, optimizing a linear objective over the domain could be done by a very efficient and simple combinatorial algorithm. Prominent examples for this phenomena are the matroid polytope for which there is a simple greedy algorithm for linear optimization, and the flow polytope (convex hull of all $s-t$ paths in a directed acyclic graph) for which linear optimization amounts to finding a minimum-weight path . Other important examples include the set of rotations for which linear optimization is very efficient using Wahba’s algorithm , and the bounded cone of positive semidefinite matrices, for which linear optimization amounts to a leading eigenvector computation whereas projections require cimputing the singular value decomposition.

This phenomena motivates the study of optimization algorithms that require only linear optimization steps over the domain and their linear oracle complexity - that is, the number of linear objectives that the algorithm needs to minimize over the domain in order to achieve a desired accuracy with respect to the optimization objective.

The main contribution of this work is a conditional gradient (aka Frank-Wolfe) algorithm for oflline smooth and strongly convex optimization over polyhedral sets that requires only a single linear optimization step over the domain on each iteration and enjoys a linear convergence rate, an exponential improvement over previous results in this setting.

We also consider the setting of online convex optimization . In this setting, a decision maker is iteratively required to choose a point in a fixed convex decision set. After choosing his point, an adversary chooses some convex function and the decision maker incurs a loss that is equal to the function evaluated at the point chosen. In this adversarial setting there is no hope to play as well as an optimal offline algorithm that has the benefit of hindsight. Instead the standard benchmark is an optimal naive offline algorithm that has the benefit of hindsight but must play the same fixed point on each round. The difference between the cumulative loss of the decision maker and that of of this offline benchmark is known as regret. Based on our new linearly converging conditional gradient algorithm, we give algorithms for online convex optimization over polyhedral sets that perform only a single linear optimization step over the domain on each iteration while enjoying optimal regret guarantees in terms of the game length, answering an open question of Kalai and Vempala , and Hazan and Kale . Using existing techniques we give an extension of this algorithm to the partial information setting which obtains the best known regret bound for this setting.

Finally, our online algorithms also imply conditional gradient-like algorithms for offline non-smooth convex optimization and stochastic convex optimization that enjoys the same convergence rates as projected (sub)gradient methods in terms of the accuracy parameter $\epsilon$(albeit different dependency on constants and the dimension), but replacing the projection step of (sub)gradient methods with a single linear optimization step, again improving over the previous state of the art in these settings.

Conditional gradient methods for offline minimization of convex and smooth functions date back to the work of Frank and Wolfe which presented a method for smooth convex optimization over polyhedral sets whose iteration complexity amounts to a single linear optimization step over the convex domain. More recent works of Clarkson , Hazan and Jaggi consider the conditional gradient method for the cases of smooth convex optimization over the simplex, semidefinite cone and arbitrary convex and compact sets respectively. Despite its relatively slow convergence rate - additive error of the order $1/t$ after $t$ iterations, the benefit of the method is twofold: i) its computational simplicity - each iteration is comprised of optimizing a linear objective over the set and ii) it is known to produce sparse solutions (for the simplex this means only a few non zeros entries, for the semidefinite cone this means that the solution has low rank). Due to these two properties, conditional gradient methods have attracted much attention in the machine learning community in recent years, see .

It is known that in general the convergence rate $1/t$ is also optimal for this method without further assumptions, as shown in . In case the objective function is both smooth and strongly convex, there exist extensions of the basic method which achieve faster rates under various assumptions. One such extension of the conditional-gradient algorithm with linear convergence rate was presented by Migdalas , however the algorithm requires to solve a regularized linear problem on each iteration which is computationally equivalent to computing projections. This is also the case with the algorithm for smooth and strongly convex optimization in the recent work of Lan . In case the convex set is a polytope, GuéLat and Marcotte has shown that the algorithm of Frank and Wolfe converges in linear rate assuming that the optimal point in the polytope is bounded away from the boundary. The convergence rate is proportional to a quadratic of the distance of the optimal point from the boundary. We note that in case the optimum lies in the interior of the convex domain, then the problem is in fact an unconstrained convex optimization problem and solvable via much more efficient methods. GuéLat and Marcotte also gave an improved algorithm based on the concept of “away steps” with a linear convergence rate that holds under weaker conditions, however this linear rate still depends on the location of the optimum with respect to the boundary of the set which may result in an arbitrarily bad convergence rate. We note that the suggestion of using “away steps” to accelerate the convergence of the FW algorithm for strongly convex objectives was already made by Wolfe himself in . Beck and Taboule gave a linearly converging conditional gradient algorithm for solving convex linear systems, but as in , their convergence rate depends on the distance of the optimum from the boundary of the set. Here we emphasize that in this work we do not make any assumptions on the location of the optimum in the convex domain and our convergence rates are independent of it.

Ahipasaoglu, Sun and Todd gave a variant of the conditional gradient algorithm with away steps that achieves a linear convergence rate for the specific case in which the convex domain is the unit simplex. Their work also does not specify the precise dependency of the convergence rate on parameters of the problem such as the dimension, which is of great importance. In this work we derive, as an illustrating example, a linearly converging algorithm for the unit simplex. Our generalization to arbitrary polytopes is highly non-trivial and is indeed the technical heart of this work. We also provide convergence rates with detailed dependencies on natural parameters of the problem.

After our work first appeared , Jaggi and Lacoste-Julien presented a refined analysis of a variant of the conditional gradient algorithm with away steps from that achieves a linear convergence rate without the assumption on the location of the optimum as in the original work of . Their algorithm is also shown to be affine invariant. Their convergence rate however is not given explicitly and its dependency on the dimension or other natural parameters of the problem is not clear.

The two closest works to ours are those of Kalai and Vempala and Hazan and Kale , both present projection-free algorithms for online convex optimization in which the only optimization carried out by the algorithms on each iteration is the minimization of a single linear objective over the decision set. gives a random algorithm for the online setting in the special case in which all loss functions are linear, also known as online linear optimization. In this setting their algorithm achieves regret of $O(\sqrt{T})$ which is optimal . On iteration $t$ their algorithm plays a point in the decision set that minimizes the cumulative loss on all previous iterations plus a vector whose entries are independent random variables. The work of introduces algorithms for stochastic and online optimization which are based on ideas similar to ours - using the conditional gradient update step to approximate the steps a meta-algorithm for online convex optimization known as Regularized Follow the Leader (RFTL) . For stochastic optimization, in case that all loss functions are smooth they achieve an optimal convergence rate of $1/\sqrt{T}$, however for non-smooth stochastic optimization they only get convergence rate of $T^{-1/3}$ and for the full adversarial setting of online convex optimization they get suboptimal regret that scales like $T^{3/4}$.

In a recent work, Lan showed how to apply the conditional gradient algorithm to offline non-smooth optimization via a well known smoothing technique (also employed in ). His analysis shows that an $\epsilon$ additive error is guaranteed after a total of $O(\epsilon^{-2})$ linear optimization steps over the domain and $O(\epsilon^{-4})$ calls to the subgradient oracle of the objective. Our algorithm for the non-smooth setting guarantees an $\epsilon$ additive error after $O(\epsilon^{-2})$ linear optimization steps over the domain and $O(\epsilon^{-2})$ calls to the subgradient oracle.

Also relevant to our work is the very recent work of Harchaoui, Juditsky and Nemirovski who give methods for i) minimizing a norm over the intersection of a cone and the level set of a convex smooth function and ii) minimizing the sum of a convex smooth function and a multiple of a norm over a cone. Their algorithms are extensions of the conditional gradient method that assume the availability of a stronger oracle that can minimize a linear objective over the intersection of the cone and a unit ball induced by the norm of interest. They present several problems of interest for which such an oracle could be implemented very efficiently, however in general such an oracle could be computationally much less efficient than the linear oracle required by standard conditional gradient methods.

2 Paper Structure

The rest of the paper is organized as follows. In section 2 we give preliminaries, including notation and definitions that will be used throughout this work, overview of the conditional gradient method and describe the settings of online convex optimization and stochastic optimization. In section 3 we give an informal statement of the results presented in this work. In section 4 we present our main result - a new linearly convergent conditional gradient algorithm for offline smooth and strongly convex optimization over polyhedral sets. In section 5 we present and analyse our main new algorithmic machinery which we refer to as a local linear optimization oracle. In section 6 we present and analyze our algorithms for online and stochastic optimization, and finally in section 7 we discuss a lower bound for the problem of minimizing a smooth and strongly convex function using only linear optimization steps - showing that the oracle complexity of our new algorithm presented in section 4 is nearly optimal.

Preliminaries

The above definition together with first order optimality conditions imply that for a $\sigma$-strongly convex $f$, if $x^{*}$ is the unique minimizer of $f$ over $\mathcal{K}$, then for all $x\in\mathcal{K}$ it holds that

Note that a sufficient condition for a twice-differential function $f$ to be $\beta$-smooth and $\sigma$-strongly convex over a domain $\mathcal{K}$ is that

Let $\mathcal{P}$ be a polytope described by linear equations and inequalities, i.e.,

The conditional gradient method is a simple algorithm for minimizing a smooth and convex function $f$ over a convex set $\mathcal{P}$ - which in this work we assume to be a polytope. The appeal of the method is that it is a first order feasible point method, i.e., the iterates always lie inside the convex set and thus no projections are needed. Further more, the update step on each iteration simply requires to minimize a linear objective over the set. The basic algorithm is given below.

Let $x^{*}$ denote the unique minimizer of $f$ over $\mathcal{P}$ that is, $x^{*}=\arg\min_{x\in\mathcal{K}}f(x)$. The convergence of algorithm 1 is due to the following simple observations.

Thus for an appropriate choice for the sequence of step sizes $\{{\alpha_{t}}\}_{t=1}^{\infty}$, the approximation error strictly decreases on each iteration. This leads to the following theorem (for a proof see for instance the modern survey of ).

There is an explicit choice for the sequence of step sizes $\{{\alpha_{t}}\}_{t=1}^{\infty}$ such that for every $t\geq 2$, the iterate $x_{t}$ of Algorithm 1 satisfies that $f(x_{t})-f(x^{*})=O\left({\frac{\beta{}D^{2}}{t-1}}\right)$.

The relatively slow convergence of the conditional gradient algorithm is due to the term $\|{p_{t}-x_{t}}\|$ in Eq. (2), that may remain as large as the diameter of $\mathcal{P}$ while the term $f(x_{t})-f(x^{*})$ keeps on shrinking, that forces choosing values of $\alpha_{t}$ that decrease like $\frac{1}{t}$ in order to guarantee convergence .

In this case the term $\|{p_{t}-x_{t}}\|^{2}$ in Eq. (2) will be of the same magnitude as $f(x_{t})-f(x^{*})$ (or even smaller) and as observable in Eq. (2), a linear convergence rate will follow.

However, solving Problem (3) is potentially much more difficult than solving the original linear problem $\min_{p\in\mathcal{P}}p\cdot\nabla{}f(x_{t})$, and is not straight-forward solvable using the linear optimization oracle of $\mathcal{P}$.

The local linear optimization oracle (LLOO) relaxes Problem (3) by solving the linear problem on a larger set, but one that still has a diameter that is not much larger than $\sqrt{f(x_{t})-f(x^{*})}$. Our main contribution is in showing that for a polytope $\mathcal{P}$, a LLOO can be constructed such that the parameter $\rho$ depends only on the dimension $n$ and the quantity $\mu(\mathcal{P})$. Moreover, the algorithmic construction requires only a single call to the original linear optimization oracle $\mathcal{O}_{\mathcal{P}}$. Hence, the complexity per iteration, in terms of the number of calls to the linear optimization oracle $\mathcal{O}_{\mathcal{P}}$, remains the same as the original conditional gradient algorithm (Algorithm 1).

2 Online convex optimization and its application to stochastic and offline optimization

The problem of online convex optimization (OCO) takes the form of the following repeated game. A decision maker is required on each iteration $t$ of the game to choose a point $x_{t}\in\mathcal{K}$, where $\mathcal{K}$ is a fixed convex set. After choosing the point $x_{t}$, a convex loss function $f_{t}(x)$ is reveled, and the decision maker incurs loss $f_{t}(x_{t})$. The emphasis in this model is that the loss function on time $t$ may be chosen completely arbitrarily and even in an adversarial manner given the current and past decisions of the decision maker. In the full information setting, after making his decision on time $t$, the decision maker gets full knowledge of the function $f_{t}$. In the partial information setting (bandit) the decision maker only learns the value $f_{t}(x_{t})$ and does not gain any other knowledge about $f_{t}$.

The standard goal in this setting is to have overall loss which is not much larger than that of the best fixed point in $\mathcal{K}$, in hindsight. Formally the goal is to minimize a quantity known has regret which is given by

In certain cases, such as in the bandit setting, the decision maker must use randomness in order to make his decisions. In this case we consider the expected regret, where the expectation is taken over the randomness in the algorithm of the decision maker.

In the full information setting and for general convex losses the optimal regret bound attainable scales like $\sqrt{T}$ where $T$ is the length of the game. In the case that all loss functions are strongly convex, the optimal regret bound attainable scales like $\log(T)$ .

A simple algorithm that attains optimal regret of $O(\sqrt{T})$ for general convex losses is known as the Regularized Follows The Leader algorithm (RFTL) . On time $t$ the algorithm predicts according to the following rule.

Where $\eta$ is a parameter known as the learning rate and $\mathcal{R}$ is a strongly convex function known as the regularization. From an offline optimization point of view, achieving low regret is thus equivalent to minimizing a single strongly-convex objective over the feasible set per iteration. In fact, with the popular choice $\mathcal{R}(x)=\|{x}\|^{2}$, we get that Problem (4) is just the minimization of a function that is both smooth and strongly-convex over the feasible domain $\mathcal{K}$, and is in fact equivalent to computing an Euclidean projection onto $\mathcal{K}$.

In case of strongly-convex losses a slight variant of Eq. (4), which also takes the form of minimizing a smooth and strongly convex function when choosing $\mathcal{R}(x)=\|{x}\|^{2}$, guarantees optimal $O(\log(T))$ regret.

In the partial information setting the RFTL rule (4) with the algorithmic conversion of the bandit problem to that of the full information problem established in , yields an algorithm with regret $O(T^{3/4})$, which is the best to date.

Our algorithms for online optimization are based on iteratively approximating the RFTL objective in Eq. (4) using our new linearly convergent CG algorithm for smooth and strongly convex optimization, thus replacing the projection step in (4) (in case $\mathcal{R}(x)=\|{x}\|^{2}$) with a single linear optimization step over the domain.

We note that while the update rule in Eq. (4) uses the gradients of the loss functions which are denoted by $\nabla{}f_{\tau}$, it is in fact not required to assume that the loss functions are differentiable everywhere in the domain. It suffices to assume that the loss functions only have a sub-gradient everywhere in the domain, making the algorithm suitable also for non-smooth settings. Throughout this work we do not differentiate between these two cases and the notation $\nabla{}f(x)$ should be understood as a gradient of $f$ at the point $x$ in case $f$ is differentiable and as a sub-gradient of $f$ in case $f$ only has a sub-gradient in this point.

2.2 Stochastic optimization

In stochastic optimization the goal is to minimize a convex function $F(x)$ given by

where $\mathcal{D}$ is a fixed, yet unknown distribution over convex functions. In this setting we don’t have direct access to the function $F$, instead we assume to have a stochastic oracle for $F$ that when queried, returns a function $f$ sampled from $\mathcal{D}$, independently of previous samples.

The general setting of online convex optimization is harder than stochastic optimization in the sense that an algorithm for OCO could be directly applied to stochastic optimization as follows. We simulate an online game of $T$ rounds for the OCO algorithm, where on each iteration $t$ the loss function $f_{t}(x)$ is generated by a query to the stochastic oracle of $\mathcal{D}$. Let us denote by $\textrm{regret}_{T}$ an upper bound on the regret of the online algorithm with respect to any sample of $T$ functions from the distribution $\mathcal{D}$. Thus, given such a sample - $\{f_{t}\}_{t=1}^{T}$, it holds that

Denoting $x^{*}\in\arg\min_{x\in\mathcal{K}}F(x)$ we thus in particular have that

Denoting $\bar{x}=\frac{1}{T}\sum_{t=1}^{T}x_{t}$ we have by convexity of $F$ that

Thus the same regret rates that are attainable for online convex optimization hold as convergence rates, or sample complexity, for stochastic convex optimization. We note that using standard concentration results for martingales, one can also derive error bounds that hold with high probability and not only in expectation, but these are beyond the scope of this paper. We refer the interested reader to for more details.

2.3 Non-smooth optimization

As in stochastic optimization (see previous subsection), an algorithm for OCO also implies an algorithm for offline convex optimization. Thus a conditional gradient-like algorithm for OCO implies a conditional gradient-like algorithm for non-smooth convex optimization. This is in contrast to the original conditional gradient method which is suitable for smooth optimization only.

Applying an OCO algorithm to the minimization of a, potentially non-smooth, convex function $f(x)$ over a feasible convex set $\mathcal{K}$, is as follows. As in the previous subsection, we simulate a game of length $T$ for the OCO algorithm in which the loss function $f_{t}$ on each round is just the function to minimize $f(x)$. As in the stochastic case, denoting $\bar{x}=\frac{1}{T}\sum_{t=1}^{T}x_{t}$, i.e., the average of iterates returned by the online algorithm, we have that

where the first inequality follows from convexity of $f$. Hence the regret bound immediately translates to a convergence rate for offline optimization problem.

Our Results

Given a $\beta$-smooth, $\sigma$-strongly convex function $f(x)$ we present an iterative algorithm that after $t$ iterations returns a point $x_{t+1}\in\mathcal{P}$ such that

where $x^{*}=\arg\min_{x\in\mathcal{P}}f(x)$ and $C$ satisfies that $C\geq f(x_{1})-f(x^{*})$. Each iteration is comprised of a single call to the linear optimization oracle of $\mathcal{P}$ and a single evaluation of a gradient vector of $f$.

As we show in section 7, the above convergence rate is nearly tight in certain settings for a conditional gradient-like method.

An algorithm for OCO with arbitrary convex loss functions whose sequence of predictions - $\{{x_{t}}\}_{t=1}^{T}$ satisfies that

An algorithm for OCO with $\sigma$-strongly convex loss functions whose sequence of predictions - $\{{x_{t}}\}_{t=1}^{T}$ satisfies that

This bound is also optimal in terms of $T$ .

A randomized algorithm for the partial information setting whose sequence of predictions - $\{{x_{t}}\}_{t=1}^{T}$ satisfies that

Here we assume for simplicity that $\mathcal{P}$ is full-dimensional and we denote by $r_{0}$ the size of the largest Euclidean ball enclosed in it. This bound matches the current state-of-the-art in this setting in terms of $T$ .

If $\mathcal{D}$ is a distribution over arbitrary convex functions then

If $\mathcal{D}$ is a distribution over $\sigma$-strongly convex functions then

As described in Subsection 2.2.3, the above rates (without the expectation) hold also for non-smooth convex and strongly convex optimization.

A Linearly Convergent Conditional Gradient Algorithm for Smooth and Strongly Convex Optimization over Polyhedral Sets

In this section we consider the following offline optimization problem.

where we assume that $f$ is $\beta$-smooth and $\sigma$-strongly convex, and $\mathcal{P}$ is a polytope. We further assume that we have a LLOO oracle for $\mathcal{P}$ - $\mathcal{A}(x,r,c)$, as defined in Subsection 2.1 . In section 5 we show that given an oracle for linear minimization over $\mathcal{P}$ , such a LLOO oracle could be efficiently constructed.

Algorithm 2, instanciated with the LLOO implementation given in Algorithm 4 (for which $\rho=\sqrt{n}\mu$, see Section 5), satisfies that for each $t\geq 1$, the iterate $x_{t+1}$ is feasible ($x_{t+1}\in\mathcal{P}$) and

where $x^{*}=\arg\min_{x\in\mathcal{P}}f(x)$. Furthermore, after $t$ iterations the algorithm has made a total of $t$ calls to the linear optimization oracle of $\mathcal{P}$ and $t$ gradient vector evaluations of $f(x)$.

The theorem is a consequence of the following Lemma 2 and Lemma 8 (see Section 5). Lemma 2 proves the convergence rate of the algorithm given a black-box access to a LLOO with some arbitrary parameter $\rho$. Lemma 8 then gives an explicit construction of a LLOO with parameter $\rho=\sqrt{n}\mu$ that requires only a single call to the linear optimization oracle per invocation.

We now turn to analyze the convergence rate of Algorithm 2. The following lemma is of general interest and will be also used in the section on online optimization.

Assume that $f(x)$ is $\beta$-smooth and let $x^{*}\in\arg\min_{x\in\mathcal{P}}f(x)$. Assume that on iteration $t$ it holds that $\|{x_{t}-x^{*}}\|\leq r_{t}$, and let $x_{t+1}\leftarrow x_{t}+\alpha(p_{t}-x_{t})$, where $p_{t}$ is the output of a LLOO with parameter $\rho$ with respect to the input $(x_{t},r_{t},\nabla{}f(x_{t}))$, and let $\alpha\in$. Then it holds that

By the $\beta$-smoothness of $f(x)$ and the definition of $x_{t+1}$ we have that

Since $\|{x_{t}-x^{*}}\|\leq r_{t}$, by the definition of the oracle $\mathcal{A}$ it holds that i) $p_{t}\cdot\nabla{}f(x_{t})\leq{x^{*}}\cdot\nabla{}f_{t}(x_{t})$ and ii) $\|{x_{t}-p_{t}}\|\leq\min\{{\rho{}r_{t},D}\}$. Thus we have that

Using the convexity of $f(x)$ and subtracting $f(x^{*})$ from both sides we have,

[Convergence of Algorithm 2] Denote $h_{t}=f(x^{*})-f(x_{t})$. Then for all $t\geq 1$ it holds that

The proof is by a simple induction. For $t=1$ we have by definition that $h_{1}=f(x^{*})-f(x_{1})\leq C$.

Now assume that the lemma holds for $t\geq 1$. This implies via the the strong convexity of $f(x)$ (see Eq. 1) that

where the second inequality follows from the induction hypothesis.

By plugging the value of $\alpha$ from Algorithm 2 and using $(1-x)\leq e^{-x}$ we have that

Construction of a Local Linear Optimization Oracle

In this section we present an efficient construction of a Local Linear Optimization Oracle for a polytope $\mathcal{P}$, given only an oracle for minimizing a linear objective over $\mathcal{P}$.

for some $d>0$. Let us denote by $p^{*}$ an optimal solution to Problem (3) when we set $d=\sqrt{n}r$. Then $p^{*}$ is the output of a LLOO with parameter $\rho=\sqrt{n}$ for $\mathcal{S}_{n}$. That is,

Problem (3) with parameter $d=\sqrt{n}r$ is solved optimally by the following simple algorithm.

The algorithm basically modifies the input point $x$ by moving the largest amount of mass which will not violate the constraint $\|{x-p}\|_{1}\leq d$ from the entries that correspond to the largest (signed) entries in the objective $c$ to the single entry that corresponds to the smallest (signed) entry in the objective $c$.

In Algorithm 3, we fix the value of $d$ to $\sqrt{n}r$ to correspond to Lemma 3. However, as the following lemma shows, the algorithm finds an optimal solution to Problem (3) for any $d\geq 0$.

Fix $d\geq 0$. Algorithm 3 finds an optimal solution to Problem (3) with parameter $d$.

Fix an optimal solution $p^{*}$ to Problem (3). We can write $p^{*}$ in the following way:

It is now a simple observation that the vectors $p_{+},p_{-}$ computed in Algorithm 3 are exactly solutions to the optimization problems

Two important observations regarding the implementation of Algorithm 3 are that i) the running time of the algorithm does not explicitly depends on the dimension $n$ but rather on the number of non-zero entries in $x$ and the time to compute the index $i^{*}$ and ii) computing the index $i^{*}$ is equivalent to finding a vertex of $\mathcal{S}_{n}$ that minimizes the dot product with the objective $c$, and hence is equivalent to a single call to the linear optimization oracle of $\mathcal{S}_{n}$.

2 Construction of a Local Linear Optimization Oracle for an Arbitrary Polytope

Thus, following our approach for the probabilistic simplex, it is tempting to consider as the output of a LLOO for $\mathcal{P}$, the point $p=\sum_{i=1}^{N}\lambda^{*}_{i}v_{i}$, where $\lambda^{*}$ is an optimal solution to the following optimization problem:

where $\lambda_{x}\in\mathcal{S}_{N}$ is a mapping of the LLOO input point - $x$ to $\mathcal{S}_{N}$ and $d$ is a positive scalar. Note that since $\lambda^{*}\in\mathcal{S}_{N}$, the solution $p$ is always a feasible point of the polytope $\mathcal{P}$.

The main question is whether we can find a value of $d$ such that a solution to Problem (5.2) indeed corresponds to the output of a LLOO for $\mathcal{P}$ with a reasonable parameter $\rho$, as in the case of the simplex.

Our implementation of a LLOO for an arbitrary polytope $\mathcal{P}$ based on solving Problem (5.2) and outputting the corresponding point in $\mathcal{P}$ is given below (Algorithm 4). The algorithm is a clear extension of Algorithm 3 for the simplex, and basically moves mass from vertices in the support of the input point $x$ (that is, vertices with non-zero weight in the convex decomposition of $x$) which have large (signed) product with the linear objective $c$, to a single vertex (possibly not in the support of the input point $x$) which minimizes the dot product with $c$. The latter is just the result of calling the linear optimization oracle of the polytope with respect to the linear objective $c$.

Note that the algorithm assumes that the input point $x$ is given in the form of a convex combination of vertices of the polytope. Later on we show that maintaining such a decomposition of the input point $x$ is straightforward and efficient when the LLOO is used with any of the optimization algorithms considered in this work. Note also that in the algorithm we implicitly fix the value $d$ in Problem (5.2) to $d=2\frac{\sqrt{n}\psi}{\xi}r$ (recall that $\psi,\xi$ are geometric quantities of the polytope at hand, defined formally in Section 2), which is justified by our analysis.

It is important to note that, as in the case of Algorithm 3 for the simplex, the running time of Algorithm 4 does not explicitly depends on the number of vertices $N$, but only on the number of non-zeros in the vector $\lambda$ (the mapping of the input point $x$ to $\mathcal{S}_{N}$), the natural dimension of $\mathcal{P}$ - $n$ and the time to complete a single call to the linear optimization oracle of the polytope - $\mathcal{O}_{\mathcal{P}}(\cdot)$. In particular, observe that in the computations in lines 3-10 of the algorithm, one needs to consider only the vertices $v_{i}$ for which $\lambda_{i}>0$.

We turn to prove that there is indeed a choice for the parameter $d$ in Problem (5.2) (the one used to set $\Delta$ in Algorithm 4) such that Algorithm 4 is indeed a LLOO for $\mathcal{P}$. Towards this end, the main step is to show that there exists a constant $c(\mathcal{P})$, such that given a query point $x\in\mathcal{P}$ in the form $x=\sum_{i=1}^{N}\lambda_{x}(i)v_{i}$ where $\lambda_{x}\in\mathcal{S}_{N}$, and a point $y\in\mathcal{P}$, there exists a mapping of $y$ to $\mathcal{S}_{N}$, i.e., a point $\lambda_{y}\in\mathcal{S}_{N}$ satisfying $y=\sum_{i=1}^{N}\lambda_{y}(i)v_{i}$, such that

This fact is a consequence of Lemmas 5, 7. Lemma 5 considers a certain way to map a point $y\in\mathcal{P}$ to $\lambda_{y}\in\mathcal{S}_{N}$ which has useful properties. Lemma 7 then builds on these properties to give a consequence in the spirit of Eq. (17) by considering the projection of the vector $(x-y)$ onto a certain set of constraints defining the polytope $\mathcal{P}$.

Let $x\in\mathcal{P}$ and $\lambda\in\mathcal{S}_{N}$ such that $x=\sum_{i=1}^{N}\lambda_{i}v_{i}$, and let $y\in\mathcal{P}$. Write $y=\sum_{i=1}^{N}(\lambda_{i}-\Delta_{i})v_{i}+(\sum_{i=1}^{N}\Delta_{i})z$ for values $\Delta_{i}\in[0,\lambda_{i}]\,\forall{i\in[N]}$ and $z\in\mathcal{P}$, such that the sum $\Delta=\sum_{i=1}^{N}\Delta_{i}$ is minimized. Then, for all $i\in[N]$ for which $\Delta_{i}>0$, there exists an index $j_{i}\in[m]$ such that $A_{2}(j_{i})\cdot v_{i}<b_{2}(j_{i})$ and $A_{2}(j_{i})\cdot z=b_{2}(j_{i})$.

By way of contradiction, suppose the lemma is false and let $i^{\prime}\in[N]$ such that $\Delta_{i^{\prime}}>0$ and $\forall{}j\in[m]$ it holds that if $A_{2}(j)\cdot v_{i^{\prime}}<b_{2}(j)$ then $A_{2}(j)\cdot z<b_{2}(j)$. Fixing some $j\in[m]$ we consider two cases. If $A_{2}(j)\cdot v_{i^{\prime}}=b_{2}(j)$ then we have that

On the other hand, if $A_{2}(j)\cdot v_{i^{\prime}}<b_{2}(j)$, then by the assumption we have that $A_{2}(j)\cdot z<b_{2}(j)$. Denote

and note that $\delta_{j}>0$ and $\epsilon_{j}>0$.

Combining Eq. (18), (19) for all $j\in[m]$, we have that

Since $v_{i^{\prime}},z$ are both feasible, it also holds that $A_{1}(z-\gamma{}v_{i^{\prime}})=(1-\gamma)b_{1}$ and thus we arrive at the conclusion that

In Lemma 7 we are going to examine the projection of a vector $(x-y)$ onto a set of constraints of $\mathcal{P}$ satisfied by a certain feasible point $z\in\mathcal{P}$. However, we would like that this set will not be too large. The following simple lemma shows that it suffices to consider a basis for the set of constraints satisfied by $z$.

Let $z\in\mathcal{P}$ and denote $C(z)=\{{i\in[m]\,|\,A_{2}(i)\cdot z=b_{2}(i)}\}$ and let $C_{0}(z)\subseteq{}C(z)$ be such that the set $\{{A_{2}(i)}\}_{i\in{}C_{0}(z)}$ is a basis for the set $\{{A_{2}(i)}\}_{i\in{}C(z)}$. Then given a point $y\in\mathcal{P}$, if there exists $i\in{}C(z)$ such that $A_{2}(i)\cdot y<b_{2}(i)$, then there exists $i_{0}\in{}C_{0}(z)$ such that $A_{2}(i_{0})\cdot y<b_{2}(i_{0})$.

Fix $z\in\mathcal{P}$ and let $C(z),C_{0}(z)$ be as in the lemma. Assume by way of contradiction that there exists $y\in\mathcal{P}$ and $i\in{}C(z)$ such that $A_{2}(i)\cdot y<b_{2}(i)$ and for any $j\in{}C_{0}(z)$ it holds that $A_{2}(j)\cdot y=b_{2}(j)$. Since $A_{2}(i)$ is a linear combination of vectors from $\{{A_{2}(j)}\}_{j\in{}C_{0}(z)}$, there exists scalars $\{\alpha_{j}\}_{j\in{}C_{0}(z)}$, not all zeros, such that $A_{2}(i)=\sum_{j\in C_{0}(z)}\alpha_{j}A_{2}(j)$. From our assumption on $y$ it follows that

However, since for all $j\in C(z)$ it holds that $A_{2}(j)\cdot z=b_{2}(j)$, we have that

Thus we arrive at a contradiction and the lemma follows. ∎

Let $x\in\mathcal{P}$ and $\lambda\in\mathcal{S}_{N}$ such that $x=\sum_{i=1}^{N}\lambda_{i}x_{i}$, and let $y\in\mathcal{P}$. Write $y=\sum_{i=1}^{N}(\lambda_{i}-\Delta_{i})v_{i}+(\sum_{i=1}^{N}\Delta_{i})z$, where $\forall i\in[N]:\Delta_{i}\in[0,\lambda_{i}]$ and $z\in\mathcal{P}$, such that the sum $\sum_{i=1}^{N}\Delta_{i}$ is minimized (as in Lemma 5). Then it holds that

As a consequence, $y$ could be mapped to a point $\lambda_{y}\in\mathcal{S}_{N}$ such that

Combining Lemma 5 and Lemma 6, we have that for all $i\in[N]$ such that $\Delta_{i}>0$ there exists $j\in{}C_{0}(z)$ such that $A_{2}(j)\cdot v_{i}\leq b_{2}(j)-\xi$. Hence,

Thus we conclude that $\sum_{i=1}^{N}\Delta_{i}\leq\frac{\sqrt{n}\psi}{\xi}\|{x-y}\|$. ∎

The following lemma establishes that Algorithm 4 is indeed a local linear optimization oracle for $\mathcal{P}$ with parameter $\rho=\sqrt{n}\mu$ ($\mu$ is a geometric parameter of $\mathcal{P}$ that was formally defined in Section 2).

Let $p$ be the point returned by algorithm 4 when called with the input $x=\sum_{i=1}^{N}\lambda_{i}v_{i}$, $r$, $c$. Then the following conditions hold:

Condition 1. holds since $p$ is clearly given as a convex combination of points in $\mathcal{V}$. For conditions 2,3, note that we can write the returned point $p$ as $p=\sum_{i=1}^{N}(\lambda_{i}-\Delta_{i})v_{i}+\Delta{}v^{*}$, where $\Delta$ is as in Algorithm 4, for all $i\in[N]:\Delta_{i}\in[0,\lambda_{i}]$, $\sum_{i=1}^{N}\Delta_{i}=\Delta$ and $v^{*}\in\mathcal{V}$. Thus we have that

Algorithm 4 assumes that the input point $x$ is given by its convex decomposition into vertices. All optimization algorithms in this work use Algorithm 4 in the following way: they give as input to Algrotihm 4 the current feasible iterate $x_{t}\in\mathcal{P}$, and then given the output of Algorithm 4, denoted in all algorithms by $p_{t}$, they produce the next iterate $x_{t+1}$ by taking a convex combination $x_{t+1}\leftarrow(1-\alpha)x_{t}+\alpha{}p_{t}$, for some parameter $\alpha\in$. Note that Algorithm 4 implicitly produces the convex decomposition of the returned point $p_{t}$ and thus, given the convex decomposition of $x_{t}$, updating it to the convex decomposition of $x_{t+1}$ is straightforward.

Moreover, denoting $\mathcal{V}_{t}\subseteq\mathcal{V}$ the set of vertices that forms the convex decomposition of $x_{t}$ (i.e. the vertices with non-zero weight in the decomposition), it is clear from Algorithm 4 and the discussion above that $|{\mathcal{V}_{t+1}\setminus\mathcal{V}_{t}}|\leq 1$, since at most a single vertex ($v^{*}$ in Algorithm 4) is added to the decomposition.

Algorithm 4 admits an implementation such that each invocation of the algorithm requires a single call to the oracle $\mathcal{O}_{\mathcal{P}}$ and additional $O(T(n+\log{T}))$ time, where $T$ is the overall number of calls to the algorithm.

Note that we can get rid of the linear dependence on $T$ in the bound in lemma 9 by decomposing the iterate $x_{t}$ into a convex sum of fewer vertices in case the number of vertices in the current decomposition - $N_{t}$ becomes too large. From Carathéodory’s theorem we know that we can find such a decomposition with at most $n+1$ vertices. Moreover, for many polytopes of interest (such as the flow polytope), there is an even more efficient algorithm for computing such a decomposition (however these are beyond the scope of this paper). It follows from previous discussions that we will need to invoke such a decomposition procedure only every $O(n)$ iterations which will keep the amortized iteration complexity low.

Assume that on every invocation of the LLOO algorithm, the input $r$ to the LLOO is lower-bounded by some $r_{0}>0$. Then there exists an implementation for a LLOO with parameter $\rho=2\sqrt{n}\mu+1$, such that the amortized linear optimization oracle complexity per iteration is 2, and the additional amortized complexity per iteration is $O\left({n\mu^{2}\log(1/r_{0})\left({n+\log(n\mu^{2}\log(1/r_{0})}\right)}\right)$.

The proof follows the same lines as that of Lemma 9.

We note that in our online algorithms the lower bound $r_{0}$ in Lemma 10 will always satisfy: $\log(1/r_{0})=O(\log(T))$, where $T$ is the overall length of the game, and thus the running time per iteration will depend only logarithmically on $T$.

It is also worth mentioning that we can significantly accelerate Algorithm 4 by using parallel computations. Note that all dot product computations in line 3 of the algorithm (recall again that in practice we need to carry out these computations only for vertices $v_{i}$ for which $\lambda_{i}>0$) are independent of each other and could be computed in parallel.

Online and Stochastic Convex Optimization

In this section we present algorithms for the general setting of online convex optimization that are suitable when the decision set is a polytope. We present regret bounds for both general convex losses and for strongly convex losses. These regret bounds imply convergence rates for stochastic convex optimization and non-smooth convex optimization over polyhedral sets as described in subsections 2.2.2, 2.2.3. In the sequel we also present an algorithm for the bandit setting.

Our algorithm for online convex optimization in the full information setting is given below (Algorithm 5) . The algorithm is based on the ideas presented in Subsection 2.2.1, i.e., iteratively approximating the steps of a regret-optimal algorithm known as Regularize Follow the Leader using the update step of our Algorithm 2, which amounts to a single call a local linear optimization oracle (which in turn, given the construction presented in Section 5, amounts to a single call to the linear optimization oracle of the polytope).

For ease of presentation, we use a standard assumption that the algorithm has knowledge on several parameters of the problem including the length of the game - $T$, an upper bound on the magnitude of the gradients of the observed loss functions - $G$, and a lower bound on the strong convexity of the observed functions - $\sigma$ (which may also be zero) in case one of these bounds is unknown, one can use standard techniques such as the well known “doubling trick”, which increases the overall regret only by a log factor. .

We prove the following two main theorems.

Denote $G=\sup_{x\in\mathcal{P},t\in[T]}\|{\nabla{}f_{t}(x)}\|$ and recall that we have a construction for a local linear optimization oracle with parameter $\rho=O(\sqrt{n}\mu)$ for the decision set $\mathcal{P}$.

In case Algorithm 5 is instanciated with the LLOO described in Section 5 (Algorithm 4), then for arbitrary convex loss fundtions, the regret of the algorithm is $O(GD\mu\sqrt{nT})$.

In case Algorithm 5 is instanciated with the LLOO described in Section 5 (Algorithm 4), then for $\sigma$-strongly convex loss functions, the regret of the algorithm is $O(\sigma{}D^{2}\rho^{4}+(G+\sigma{}D)^{2}n\mu^{2}/\sigma)\log{T})$.

Applying the above two theorems with the reduction of stochastic optimization to online optimization described in Subsection 2.2.2, yields the following two corollaries.

In the following two subsections we prove Theorems 3, 4.

In this subsection we analyze the regret of Algorithm 5 in case the observed loss functions are all convex but not necessarily strongly convex, that is, $\sigma=0$.

Consider the sequence of points $\{{x^{*}_{t}}\}_{t=1}^{T+1}$ such that for all $t\in[T+1]$, $x^{*}_{t}=\arg\min_{x\in\mathcal{P}}F_{t-1}(x)$, where for all $t\in[T]$, $F_{t}(x)$ is as defined in Algorithm 5 (for $\sigma=0)$ and for $t=0$ we define $F_{0}(x):=\|{x-x_{1}}\|^{2}$ . The regret analysis is comprised of two parts. Part 1 shows that on any time $t$, the point $x_{t}$ played by Algorithm 5 is close to the corresponding point $x^{*}_{t}$. Thus by a Lipschitz argument, the cumulative loss of the sequence $\{{x_{t}}\}_{t=1}^{T}$ is close to that of $\{{x^{*}_{t}}\}_{t=1}^{T}$. Part 2 then follows the analysis of an algorithm known as Regularized Follow the Leader (see ) to claim that the sequence of points $\{{x^{*}_{t}}\}_{t=1}^{T}$ achieves low regret with respect to the sequence of observed loss functions.

Then, the sequence of points $\{{x_{t}}\}_{t=1}^{T}$ produced by Algorithm 5 satisfies that for all $t\in[T]$, $\|{x_{t}-x_{t}^{*}}\|\leq\sqrt{\epsilon}$.

Observe that on any time $t\in\{0,1,...,T\}$ it holds that the function $F_{t}(x)$ is $2$-strongly convex and $2$-smooth.

We prove by induction that for all $t\in[T]$ it holds that $F_{t-1}(x_{t})-F_{t-1}(x_{t}^{*})\leq\epsilon$. By the strong-convexity of $F_{t-1}$ (Eq. 1) this yields that $\|{x_{t}-x_{t}^{*}}\|\leq\sqrt{\epsilon}$.

The proof is by induction on $t$. For $t=1$ it holds that $x_{1}=x_{1}^{*}$ and thus the claim holds. Assume now that for time $t\geq 1$ it holds that $F_{t-1}(x_{t})-F_{t-1}(x_{t}^{*})\leq\epsilon$. By the strong-convexity of $F_{t-1}(x)$ and the induction hypothesis we have that

By the definition of $F_{t}(x)$ and the optimality of $x_{t}^{*}$ we have that

and thus again by the strong convexity of $F_{t}(x)$ we have that

Using again the induction hypothesis, we have that

Setting $r_{t}=\sqrt{\epsilon}+\eta{}G$, we can apply Lemma 1 with respect to $F_{t}(x),x_{t},r_{t}$ and get,

Setting $\alpha=\frac{1}{3\rho^{2}}$ we get that

Finally, plugging $\eta=\frac{\sqrt{\epsilon}}{18G\rho^{2}}$ gives

We also need the following lemma, originally proved in , that states that playing on each time $t$ the point in $\mathcal{P}$ that minimizes the loss up to time $t$ (including), yields zero regret. A proof is given in the appendix for completeness.

Let $\{{f_{t}(x)}\}_{t=1}^{T}$ be a sequence of loss functions and let $\{{w^{*}_{t}}\}_{t=1}^{T}$ be a sequence of points such that for all $t\in[T]$, $w^{*}_{t}\in\arg\min_{w\in\mathcal{P}}\sum_{\tau=1}^{t}f_{\tau}(w)$. Then it holds that

Rearranging and using $\|{x^{*}-x_{1}}\|\leq D$ we have that

Fix $t\in[T]$. Since $F_{t}(x)$ is $2$-strongly convex, using Eq. (1) we have that

where the last inequality follows from the optimality of $x_{t}^{*}$ with respect to $F_{t-1}(x)$ and the Cauchy-Schwartz inequality.

Combining Eq. (26) and Eq. (27) for all $t\in[T]$ via the Cauchy-Schwartz inequality we have that

Rearranging and using the Cauchy-Schwartz inequality again we have that

Fix $\epsilon=\frac{(D\rho)^{2}}{T}$. Applying Lemma 11 with respect to our choice of $\epsilon$ and setting $\eta$ accordingly (and recalling that $\rho\geq 1$), we have that

where the first inequality follows from convexity of each $f_{t}(x)$. The theorem now follows since according to our results from Section 5 we can assume that $\rho=\sqrt{n}\mu$.

2 Analysis for strongly convex losses

Here we analyze the regret of Algorithm 5 in case all loss function are at least $\sigma$-strongly convex for some $\sigma>0$. The analysis goes along the same lines as the analysis for the non-strongly convex case, but requires a few modifications.

As in the previous subsection we define the sequence $\{{x^{*}_{t}}\}_{t=1}^{T+1}$ such that $x^{*}_{t}=\arg\min_{x\in\mathcal{P}}F_{t-1}(x)$, where $F_{t}(x)$ for $t\in\{1,...,T\}$ is defined as in Algorithm 5 (for $\sigma>0$) and in addition we define $F_{0}:=T_{0}\frac{\sigma}{2}\|{x-x_{1}}\|^{2}$.

where the last inequality uses the triangle inequality and the upper bounds $G,D$ for $\|{\nabla{}f_{t}(x_{t})}\|$ and $\|{y-x_{t}}\|$ respectively. Since the above inequality is symmetric in $y,z$, the lemma follows. ∎

The following Lemma is analogues to Lemma 11 for the non-strongly convex case.

Let $L=G+\sigma{}D$, $\alpha=\frac{1}{5\rho^{2}}$ and $T_{0}=(25\rho^{2})^{2}$. Let $\{{\epsilon_{t}}\}_{t=1}^{T}$ be a sequence of positive reals such that $\epsilon_{t}=\frac{(60\rho^{2}L)^{2}}{\sigma(t+T_{0})}$ $\forall t\in[T]$. Let

Then, for any $t\in[T]$ it holds that $\|{x_{t}-x_{t}^{*}}\|\leq\sqrt{\frac{\epsilon_{t}}{\sigma(t-1+T_{0})}}$.

The proof is similar to that of Lemma 11. Observe that on any time $t\in\{0,1,...,T\}$ it holds that the function $F_{t}(x)$ is $\sigma(t+T_{0})$-strongly convex and $\sigma(t+T_{0})$-smooth.

We prove that for any time $t\in[T]$ it holds that $F_{t-1}(x_{t})-F_{t-1}(x_{t}^{*})\leq\epsilon_{t}$, which by the strong convexity of $F_{t-1}(x)$ (see Eq. (1)) implies that $\|{x_{t}-x_{t}^{*}}\|\leq\sqrt{\frac{2\epsilon_{t}}{\sigma(t-1+T_{0})}}$.

Clearly for time $t=1$ the claim holds since $x_{1}=x_{1}^{*}$. Assume that on time $t\geq 1$ it holds that $F_{t-1}(x_{t})-F_{t-1}(x_{t}^{*})\leq\epsilon_{t}$. By the strong convexity of $F_{t-1}(x)$ we again have that

where the first inequality follows from the optimality of $x^{*}_{t}$ with respect to $F_{t-1}(x)$ and the second inequality follows from Lemma 13.

By the strong convexity of $F_{t}(x)$ we thus have that

Combining Eq. (28), (29) via the triangle inequality we have that

where the second inequality holds since $T_{0}\geq 1$.

Using the induction hypothesis we have that

where the inequality follows from Eq. (30) and Lemma 13.

Setting $r_{t}$ to equal the RHS of Eq. (30), and applying Lemma 1 with respect to $F_{t}(x)$ we have that

where the second inequality follows from Eq. (31), the value of $r_{t}$, and using $(a+b)^{2}\leq 2a^{2}+2b^{2}$ to upper bound $r_{t}^{2}$. The rest of the inequalities follows from simple algebraic manipulations.

Setting $\alpha=\frac{1}{5\rho^{2}}$ we have that

Plugging in our choice $\epsilon_{t}=\frac{(60\rho^{2}L)^{2}}{\sigma(t+T_{0})}$ we have that

Finally, setting $T_{0}=(25\rho^{2})^{2}$ we have that

Using the upper bound $\|{x^{*}-x_{1}}\|\leq D$ and plugging the value of $T_{0}$ in Algorithm 5 we have that

where the first inequality follows from the optimality of $x_{t}^{*}$ with respect to $F_{t-1}(x)$, and the second inequality follows from Lemma 13 and using $L=G+\sigma{}D$. Since $F_{t}(x)$ is $\sigma(t+T_{0})$-strongly convex, this implies via Eq. (1) that

Applying Lemma 14 with the triangle inequality we have that

where the equality follows since $T_{0}\geq 1$ and by definition $\rho\geq 1$.

Plugging the above for all $t\in[T]$ into Eq. (32) we have that

The theorem now follows from the observation that since for all $t\in[T]$, $f_{t}(x)$ is $\sigma$-strongly convex it holds that

3 Bandit Algorithm

In this section we give an online algorithm for the partial information setting (bandits). The derivation is basically straightforward using our algorithm for the full information setting (Algorithm 5) and the technique of .

We assume that the loss function $f_{t}(x)$ chosen by the adversary on time $t$ is chosen with knowledge of the history of the game but without any knowledge of possible randomization used by the decision maker on time $t$ to produce his prediction. We further assume without loss of generality that for each function $f_{t}(x)$ it holds that $f_{t}(0)=0$.

Note that since we assume that the gradients of each $f_{t}(x)$ are bounded in magnitude by $G$, it holds that $f_{t}(x)$ is $G$-Lipschitz. This follows since,

Also, since $f_{t}(0)=0$ and $0\in\mathcal{P}$ we have that

The regret analysis of Algorithm 6 closely follows the analysis in , but instead of using Zinkevich’s algorithm for the reduction from bandit feedback to full feedback, we use our Algorithm 5.

For a proof of the following Lemma see Lemma 2.1 in .

In order to derive the regret bound for Algorithm 6 we need the following technical lemma.

For all $t\in[T]$, let $\hat{f}_{t}(x)$ be as in Lemma 15. It holds that

Using the Cauchy-Schwartz inequality and the bound $\max_{x\in\mathcal{P}}\|{x}\|\leq D$ we have that

where the last equality follows since according to Lemma 15, the inner expectation is zero.

Plugging Eq. (37) into Eq. (36) for all $i<j$ we have that

where we have used Eq. (34) in the last inequality.

Plugging Eq. (38) into Eq. (35) we finally have that

For $T\geq\left({\frac{Dn}{r_{0}}}\right)^{2}$ it holds that the sequence of points $\{{y_{t}}\}_{t=1}^{T}$ produced by Algorithm 6 is feasible and satisfies

where the expectation is with respect to the randomness in choosing the vectors $\{{u_{t}}\}_{t=1}^{T}$.

For $t\in[T]$, denote $z_{t}=(1-\gamma)x_{t}$. Since $(1-\gamma)\in$, it holds that

Plugging in Lemma 16 and taking expectation we have that

Note that since $f_{t}(x)$ is a convex function, so is $\hat{f}_{t}(x)$ and thus we have that

Fix $t\in[T]$. Note that since $f_{t}(x)$ is $G$-Lipschitz (see Eq. (33)), for all $x\in\mathcal{P}$ it holds that

Plugging Eq. (41) for all $t\in[T]$ into Eq. (40) we have that

Since for all $t\in[T]$, $\|{y_{t}-z_{t}}\|\leq\delta$, using the Lipschits property of $f_{t}(x)$ we have that

Using again Eq. (33), (34) and the fact that $0\in\mathcal{P}$, $f_{t}(0)=0$, we have that for all $x\in\mathcal{P}$ and $t\in[T]$, $f_{t}((1-\gamma)x)\leq(1-\gamma)f_{t}(x)\leq f_{t}(x)+\gamma{}GD$. Thus we have that

Now, setting $\delta=\gamma{}r_{0}$ as in Algorithm 6, and recalling that $D\geq r_{0}$, we have that

Finally, setting $\gamma=\sqrt{\frac{Dn}{r_{0}}}T^{-1/4}$ we have that

Lower bound

In this section we revisit our main result from Section 4, that is, our linearly converging algorithm for smooth and strongly convex optimization over polytopes. We show that in certain settings our convergence rate (i.e., number of calls to the linear optimization oracle to reach a certain approximation error) is in fact nearly tight and cannot be improved beyond constants and logarithmic terms for conditional gradient-like algorithms, i.e., algorithms that can request a vertex of the polytope that minimizes the dot product with a certain linear objective and take linear combinations of these vertices. Similar arguments appear in .

Towards this end, consider the following optimization problem:

It thus follows that in order for a conditional gradient-like method to solve Problem (42) up to an error of at most $\frac{1}{4n}$, it requires $\Omega(n)$ calls to the linear optimization oracle of $\mathcal{S}_{n}$.

Acknowledgments.

The authors would like to thank Arkadi Nemirovski for numerous helpful comments on an earlier draft of this paper.

References

Appendix A Proof of Lemma 12

For clarity, we first restate the lemma and then prove it.

Let $\{{f_{t}(x)}\}_{t=1}^{T}$ be a sequence of loss functions and let $\{{x^{*}_{t}}\}_{t=1}^{T}$ be a sequence of points such that for all $t\in[T]$, $x^{*}_{t}\in\arg\min_{x\in\mathcal{P}}\sum_{\tau=1}^{t}f_{\tau}(x)$. Then it holds that

We prove by induction that for any $\tau\in[T]$ it holds that

For the base case $\tau=1$ the claim clearly holds since $x^{*}_{1}\in\arg\min_{x\in\mathcal{P}}f_{1}(x)$. Assume now that the claim holds for some $\tau\geq 1$. On time $\tau+1$ it holds that

where the first inequality follows from the induction hypothesis and the third one from the optimality of $x^{*}_{\tau+1}$. ∎