Faster Rates for the Frank-Wolfe Algorithm Using Jacobi Polynomials

Consider constrained optimization problems of the form

$$\mathrel{\mathop{\kern 0.0pt\text{minimize}}\limits_{{{\mathbf{x}}}}}\hskip 8.53581ptf({{\mathbf{x}}})\quad\quad\text{subject to}\quad\quad{{\mathbf{x}}}\in\mathcal{C},$$

(1)

where $f:{\textbf{dom}}(f)\rightarrow\mathbb{R}$ is a smooth convex function and the constraint set $\mathcal{C}\subseteq{\textbf{dom}}(f)$ is compact and compact. Projected gradient descent [1] is a popular technique to solve constrained optimization problems, wherein gradient descent iterates are projected onto the constraint set. The constraint set in many large-scale problems that are commonly encountered in machine learning and signal processing, such as lasso, matrix completion, regularized logistic or robust regression, has a nice structure, but the projection operation onto the constraint set can be computationally expensive.

The Frank-Wolfe (FW) algorithm (also popularly known as the conditional gradient method) [2] is a projection-free alternative to the projected gradient descent algorithm for solving constrained optimization problems. The FW algorithm avoids the projection step and instead has a direction-finding step that minimizes a local linear approximation of the objective function over the constraint set. The update is then computed by taking a convex combination of the previous iterate with the solution from the linear minimization step. The linear minimization step in FW is often easy to compute for $\ell_{p}$-norm ball or polytope constraint sets that frequently appear in machine learning and signal processing problems, thereby making FW an attractive choice.

In [3], convergences results are provided for the FW algorithm. The FW algorithm has iteration complexity bounds that are independent of the problem size but limited by a sublinear convergence rate of $\mathcal{O}(1/k)$. With a carefully selected step size, for minimizing a strongly convex function over a strongly convex constraint set, the FW algorithm can achieve convergence rates of $\mathcal{O}(1/k^{2})$ and linear convergence rate when the solution lies in the interior of the convex constraint set [4]. The FW algorithm can even achieve linear rates under weaker conditions than strongly convex functions over polytopes by removing carefully chosen directions (referred to as away steps) that hinder the convergence rate [5]. By finding an optimal step size at each iteration, faster convergence of the FW algorithm may be obtained [4, 6].

For unconstrained optimization problems, Nesterov’s acceleration technique [7] and Polyak’s heavy-ball momentum technqiue [8] provide faster rates of ${\mathcal{O}}(1/k^{2})$. Central to Polyak’s heavy-ball method [8] is the so-called multistep method, which keeps track of all the previous iterates and computes successive updates by taking a weighted combination of the past iterates. Doing so yields a smoother trajectory and helps attain faster convergence rates. In a similar vein, several variants of the multistep method have been proposed for FW. In [9], a momentum-guided accelerated FW (AFW) algorithm that can achieve a convergence rate of $\mathcal{O}(1/{k^{2}})$ for smooth convex minimization problems over $\ell_{p}$-norm balls, but an order of $\mathcal{O}(1/k)$ in the general setting has been proposed. The FW iterates zig-zag as we approach the optimal solution and might affect the convergence rate. In [6], the zig-zag trajectory is alleviated by using the concept of parallel tangents for FW, wherein a significant improvement in convergence has been reported but without any theoretical guarantees. In [10], the zig-zag phenomenon is controlled by keeping track of the past gradients and taking its weighted average with different heuristic choices for the weights. When using multistep-based methods, finding the optimal updates and combining weights that can achieve faster convergence without much computational overhead is important.

The main aim of this work is, therefore, to determine an optimal technique independent of the problem size, to combine the previous iterates as in the multistep method, and obtain faster convergence rates. To this end, we draw inspiration from polynomial-based iteration methods for unconstrained problems [11] and extend that to the FW setting. The main contributions of the paper are as follows.

• •

  We express the linear combination of the past FW iterates as a polynomial and show that the optimal polynomial that yields the maximum error reduction is given by a set of orthogonal Jacobi polynomials.

• •

  We then modify the FW algorithm to incorporate a Jacobi recursion, wherein the weights from the recurrence relation of the Jacobi polynomials are used to combine the past iterate with the current iterate.

• •

  We show that for carefully selected parameters of the Jacobi polynomials, we obtain a faster convergence rate of ${\mathcal{O}}(1/k^{2})$ when minimizing a smooth convex function over a compact convex constraint set.

Through numerical experiments on real datasets, we demonstrate the efficacy of the proposed algorithm.

We use boldface lowercase (uppercase) letters to represent vectors (respectively, matrices). We use $\langle{{\mathbf{x}}},{{\mathbf{y}}}\rangle$ to denote the inner product between vectors ${{\mathbf{x}}}$ and ${{\mathbf{y}}}$. We denote an arbitrary norm using $\|\cdot\|$, $\ell_{2}$-norm using $||\cdot||_{2}$, and nuclear norm using $\|\cdot\|_{\star}$. We say that a function $f:{\textbf{dom}}(f)\rightarrow\mathbb{R}$ is $L$ smooth over a convex set ${\mathcal{C}}\subseteq{\textbf{dom}}(f)$ if for all ${{\mathbf{x}}},{{\mathbf{y}}}\in{\mathcal{C}}$ it holds that

$$f({{\mathbf{y}}})\leq f({{\mathbf{x}}})+\langle\nabla f({{\mathbf{x}}}),{{\mathbf{y}}}-{{\mathbf{x}}}\rangle+\frac{L}{2}\|{{\mathbf{y}}}-{{\mathbf{x}}}\|^{2}.$$

A classic technique to accelerate iterative methods is the so-called multistep method, which uses past iterates to construct the successive iterate [8]. In this section, we apply this technique to FW and find an optimal procedure to use the past iterates.

Suppose we take a linear combination of all the past iterates from Step $4$ of Algorithm 1 with a fixed step size $\gamma$, we get

$${{\mathbf{z}}}_{k+1}=\sum_{i=0}^{k}\theta_{i}{{\mathbf{x}}}_{i}=\sum_{i=0}^{k}\theta_{i}[(1-\gamma){{\mathbf{x}}}_{i-1}+\gamma{{\mathbf{s}}}_{i-1}],$$

(5)

where we constrain the combining coefficients such that $\sum_{i=0}^{k}\theta_{i}=1$ with $\theta_{i}\in[0,1]$ for $i=0,1,\ldots,k$. This constraint ensures that the weighted average is a feasible point, i.e., ${{\mathbf{z}}}_{k+1}\in\mathcal{C}$.

Now an important question to ask is, can we find optimal coefficients that can possibly accelerate the FW algorithm? To answer this question, we express (5) as a polynomial and then select the best polynomial that speeds up the convergence rate. To do so, let us first unroll (5) and express it in terms of ${{\mathbf{x}}}_{0}$ as

$\displaystyle{{\mathbf{z}}}_{k+1}$

$\displaystyle=\sum\limits_{i=0}^{k}\theta_{i}[(1-\gamma)^{i}{{\mathbf{x}}}_{0}+\gamma\sum\limits_{j=0}^{i-1}(1-\gamma)^{i-j}{{\mathbf{s}}}_{j}].$

Let us define the polynomial $p_{k}(1-\gamma)$ of degree $k$ as

$$p_{k}(1-\gamma)=\theta_{k}(1-\gamma)^{k}+\theta_{k-1}(1-\gamma)^{k-1}+\cdots+\theta_{0},$$

with $p_{0}(1-\gamma)=1$. Then we can express ${{\mathbf{z}}}_{k+1}$ as

$\displaystyle{{\mathbf{z}}}_{k+1}$

$\displaystyle=p_{k}(1-\gamma){{\mathbf{x}}}_{0}+\gamma p_{k-1}(1-\gamma){{\mathbf{s}}}_{0}+\cdots+\gamma p_{0}(1-\gamma){{\mathbf{s}}}_{k-1},$

where $p_{k}(1-\gamma)+\gamma\sum_{i=1}^{k}p_{k-i}(1-\gamma)=1$ and thus ${{\mathbf{z}}}_{k+1}\in\textbf{conv}\{{{\mathbf{x}}}_{0},{{\mathbf{s}}}_{0},\cdots,{{\mathbf{s}}}_{k-1}\}$. The best polynomial is the one that minimizes the distance of the $k+1$st iterate to ${{\mathbf{x}}}^{\star}$, i.e.,

	$\displaystyle{{\mathbf{z}}}_{k+1}-{{\mathbf{x}}}^{\star}$	$\displaystyle=p_{k}(1-\gamma){{\mathbf{x}}}_{0}+\gamma p_{k-1}(1-\gamma){{\mathbf{s}}}_{0}$
		$\displaystyle\quad\quad\quad+\dots+\gamma p_{0}(1-\gamma)-{{\mathbf{x}}}^{\star}$
		$\displaystyle=p_{k}(1-\gamma)({{\mathbf{x}}}_{0}-{{\mathbf{x}}}^{\star})+\gamma p_{k-1}({{\mathbf{s}}}_{0}-{{\mathbf{x}}}^{\star})$
		$\displaystyle\quad\quad\quad+\cdots+\gamma p_{0}(1-\gamma)({{\mathbf{s}}}_{k-1}-{{\mathbf{x}}}^{\star})$

for each $k$, and is bounded from above as

	$\displaystyle\|{{\mathbf{z}}}_{k+1}-{{\mathbf{x}}}^{\star}\|$	$\displaystyle\leq\>|p_{k}(1-\gamma)|\,\|{{\mathbf{x}}}_{0}-{{\mathbf{x}}}^{\star}\|$
		$\displaystyle\quad\quad+|\gamma p_{k-1}(1-\gamma)|\,\|{{\mathbf{s}}}_{0}-{{\mathbf{x}}}^{\star}\|$
		$\displaystyle\quad\quad\,+\,\cdots+|\gamma p_{0}(\gamma-1)|\,\|{{\mathbf{s}}}_{k-1}-{{\mathbf{x}}}^{\star}\|$		(6)

due to the triangle inequality. Thus minimizing this upper bound would provide updates that are as close as possible to the optimal path. Next, we find the best polynomial that minimizes the above bound in the following theorem.

The above theorem suggests that combining all the past iterates using orthogonal Jacobi polynomials yields the best successive update. Based on this insight, we modify the vanilla Frank-Wolfe method in the next section.

In this section, we present the proposed Jacobi accelerated Frank-Wolfe method (JFW), which is a polynomial-based technique for using the past iterates. For a convex and $L$-smooth function $f$, we show that to reach error of at most $\varepsilon$, for carefully chosen Jacobi polynomial parameters $(\alpha,\beta)$, JFW only needs $\mathcal{O}(1/\sqrt{\varepsilon})$ instead of $\mathcal{O}(1/{\varepsilon})$ as needed by FW.

We validate the JFW algorithm on real datasets for three tasks, namely, logistic and robust regression with an $\ell_{2}$-norm constraint and robust matrix completion. We compare JFW with the vanilla FW in Algorithm 1 and the momentum-guided AFW [9] algorithms^†††Software to reproduce the plots in the paper is available at https://colab.research.google.com/drive/1P1_DsP4nN2YYykWanNuasdbfQ4j6EAhB?usp=sharing.

The FW algorithm is a viable alternative for solving constrained optimization problems for which projection onto the constraint set is a computationally expensive operation. Motivated by polynomial-based acceleration techniques for unconstrained problems, we show that a set of orthogonal Jacobi polynomials with carefully chosen parameters can yield faster convergence rates. We have proposed Jacobi accelerated FW algorithm that provably has a faster sublinear convergence rate for minimizing a smooth convex function over a compact convex constraint set.