Block-Coordinate Frank-Wolfe Optimization for Structural SVMs

Introduction

To solve the dual structural SVM problem, in this paper we consider the Frank-Wolfe (1956) algorithm, which has seen a recent surge of interest in machine learning and signal processing (Mangasarian, 1995; Clarkson, 2010; Jaggi, 2011, 2013; Bach et al., 2012), including in the context of binary SVMs (Gärtner & Jaggi, 2009; Ouyang & Gray, 2010). A key advantage of this algorithm is that the iterates are sparse, and we show that this allows us to efficiently apply it to the dual structural SVM objective even though there are an exponential number of variables. A second key advantage of this algorithm is that the iterations only require optimizing linear functions over the constrained domain, and we show that this is equivalent to the maximization oracle used by subgradient and cutting-plane methods (Joachims et al., 2009; Teo et al., 2010). Thus, the Frank-Wolfe algorithm has the same wide applicability as subgradient methods, and can be applied to problems such as low-treewidth graphical models (Taskar et al., 2003), graph matchings (Caetano et al., 2009), and associative Markov networks (Taskar, 2004). In contrast, other approaches must use more expensive (and potentially intractable) oracles such as computing marginals over labels (Collins et al., 2008; Zhang et al., 2011) or doing a Bregman projection onto the space of structures (Taskar et al., 2006). Interestingly, for structural SVMs we also show that existing batch subgradient and cutting-plane methods are special cases of Frank-Wolfe algorithms, and this leads to stronger and simpler $O(1/\varepsilon)$ convergence rate guarantees for these existing algorithms.

As in other batch structural SVM solvers like cutting-plane methods (Joachims et al., 2009; Teo et al., 2010) and the excessive gap technique (Zhang et al., 2011) (see Table 1 at the end for an overview), each Frank-Wolfe iteration unfortunately requires calling the appropriate oracle once for all training examples, unlike the single oracle call needed by stochastic subgradient methods. This can be prohibitive for data sets with a large number of training examples. To reduce this cost, we propose a novel randomized block-coordinate version of the Frank-Wolfe algorithm for problems with block-separable constraints. We show that this algorithm still achieves the $O(1/\varepsilon)$ convergence rate of the full Frank-Wolfe algorithm, and in the context of structural SVMs, it only requires a single call to the maximization oracle. Although the stochastic subgradient and the novel block-coordinate Frank-Wolfe algorithms have a similar iteration cost and theoretical convergence rate for solving the structural SVM problem, the new algorithm has several important advantages for practitioners:

The optimal step-size can be efficiently computed in closed-form, hence no step-size needs to be selected.

The algorithm yields a duality gap guarantee, and (at the cost of computing the primal objective) we can compute the duality gap as a proper stopping criterion.

The convergence rate holds even when using approximate maximization oracles.

Further, our experimental results show that the optimal step-size leads to a significant advantage during the first few passes through the data, and a systematic (but smaller) advantage in later passes.

Structural Support Vector Machines

where $\bm{\psi}_{i}(\bm{y}):=\bm{\phi}(\bm{x}_{i},\bm{y}_{i})-\bm{\phi}(\bm{x}_{i},\bm{y})$, and $L_{i}(\bm{y}):=L(\bm{y}_{i},\bm{y})$ denotes the task-dependent structured error of predicting output $\bm{y}$ instead of the observed output $\bm{y}_{i}$ (typically a Hamming distance between the two labels). The slack variable $\xi_{i}$ measures the surrogate loss for the $i$-th datapoint and $\lambda$ is the regularization parameter. The convex problem (1) is what Joachims et al. (2009, Optimization Problem 2) call the $n$-slack structural SVM with margin-rescaling. A variant with slack-rescaling was proposed by Tsochantaridis et al. (2005), which is equivalent to our setting if we replace all vectors $\bm{\psi}_{i}(\bm{y})$ by $L_{i}(\bm{y})\bm{\psi}_{i}(\bm{y})$.

Unfortunately, the above problem can have an exponential number of constraints due to the combinatorial nature of $\mathcal{Y}$. We can replace the $\sum_{i}|\mathcal{Y}_{i}|$ linear constraints with $n$ piecewise-linear ones by defining the structured hinge-loss:

The Lagrange dual of the above $n$-slack-formulation (1) has $m:=\sum_{i}|\mathcal{Y}_{i}|$ variables or potential ‘support vectors’. Writing $\alpha_{i}(\bm{y})$ for the dual variable associated with the training example $i$ and potential output $\bm{y}\in\mathcal{Y}_{i}$, the dual problem is given by

The Frank-Wolfe Algorithm

We consider the convex optimization problem $\min_{\bm{\alpha}\in\mathcal{M}}\,f(\bm{\alpha})$, where the convex feasible set $\mathcal{M}$ is compact and the convex objective $f$ is continuously differentiable. The Frank-Wolfe algorithm (1956) (shown in Algorithm 1) is an iterative optimization algorithm for such problems that only requires optimizing linear functions over $\mathcal{M}$, and thus has wider applicability than projected gradient algorithms, which require optimizing a quadratic function over $\mathcal{M}$. At every iteration, a feasible search corner $\bm{s}$ is first found by minimizing over $\mathcal{M}$ the linearization of $f$ at the current iterate $\bm{\alpha}$ (see picture in inset).

The next iterate is then obtained as a convex combination of $\bm{s}$ and the previous iterate, with step-size $\gamma$. These simple updates yield two interesting properties. First, every iterate $\bm{\alpha}^{(k)}$ can be written as a convex combination of the starting point $\bm{\alpha}^{(0)}$ and the search corners $\bm{s}$ found previously. The parameter $\bm{\alpha}^{(k)}$ thus has a sparse representation, which makes the algorithm suitable even for cases where the dimensionality of $\bm{\alpha}$ is exponential. Second, since $f$ is convex, the minimum of the linearization of $f$ over $\mathcal{M}$ immediately gives a lower bound on the value of the yet unknown optimal solution $f(\bm{\alpha}^{*})$. Every step of the algorithm thus computes for free the following ‘linearization duality gap’ defined for any feasible point $\bm{\alpha}\in\mathcal{M}$ (which is in fact a special case of the Fenchel duality gap as explained in Appendix D):

As $g(\bm{\alpha})\geq f(\bm{\alpha})-f(\bm{\alpha}^{*})$ by the above argument, $\bm{s}$ thus readily gives at each iteration the current duality gap as a certificate for the current approximation quality (Jaggi, 2011, 2013), allowing us to monitor the convergence, and more importantly to choose the theoretically sound stopping criterion $g(\bm{\alpha}^{(k)})\leq\varepsilon$.

In terms of convergence, it is known that after $O(1/\varepsilon)$ iterations, Algorithm 1 obtains an $\varepsilon$-approximate solution (Frank & Wolfe, 1956; Dunn & Harshbarger, 1978) as well as a guaranteed $\varepsilon$-small duality gap (Clarkson, 2010; Jaggi, 2013), along with a certificate to (5). For the convergence results to hold, the internal linear subproblem does not need to be solved exactly, but only to some error. We review and generalize the convergence proof in Appendix C. The constant hidden in the $O(1/\varepsilon)$ notation is the curvature constant $C_{f}$, an affine invariant quantity measuring the maximum deviation of $f$ from its linear approximation over $\mathcal{M}$ (it yields a weaker form of Lipschitz assumption on the gradient, see e.g. Appendix A for a formal definition).

Frank-Wolfe for Structural SVMs

Note that classical algorithms like the projected gradient method cannot be tractably applied to the dual of the structural SVM problem (4), due to the large number of dual variables. In this section, we explain how the Frank-Wolfe method (Algorithm 1) can be efficiently applied to this dual problem, and discuss its relationship to other algorithms. The main insight here is to notice that the linear subproblem employed by Frank-Wolfe is actually directly equivalent to the loss-augmented decoding subproblem (2) for each datapoint, which can be solved efficiently (see Appendix B.1 for details). Recall that the optimization domain for the dual variables $\bm{\alpha}$ is the product of $n$ simplices, $\mathcal{M}=\Delta_{|\mathcal{Y}_{1}|}\times\mathellipsis\times\Delta_{|\mathcal{Y}_{n}|}$. Since each simplex consists of a potentially exponential number $|\mathcal{Y}_{i}|$ of dual variables, we cannot maintain a dense vector $\bm{\alpha}$ during the algorithm. However, as mentioned in Section 3, each iterate $\bm{\alpha}^{(k)}$ of the Frank-Wolfe algorithm is a sparse convex combination of the previously visited corners $\bm{s}$ and the starting point $\bm{\alpha}^{(0)}$, and so we only need to maintain the list of previously seen solutions to the loss-augmented decoding subproblems to keep track of the non-zero coordinates of $\bm{\alpha}$, avoiding the problem of its exponential size. Alternately, if we do not use kernels, we can avoid the quadratic explosion of the number of operations needed in the dual by not explicitly maintaining $\bm{\alpha}^{(k)}$, but instead maintaining the corresponding primal variable $\bm{w}^{(k)}$.

Applying Algorithm 1 with line search to the dual of the structural SVM (4), but only maintaining the corresponding primal primal iterates $\bm{w}^{(k)}:=A\bm{\alpha}^{(k)}$, we obtain Algorithm 2. Note that the Frank-Wolfe search corner $\bm{s}=(\mathbf{e}^{\bm{y}_{1}^{*}},\dots,\mathbf{e}^{\bm{y}_{n}^{*}})$, which is obtained by solving the loss-augmented subproblems, yields the update $\bm{w}_{\bm{s}}=A\bm{s}$. We use the natural starting point $\bm{\alpha}^{(0)}:=(\mathbf{e}^{\bm{y}_{1}},\dots,\mathbf{e}^{\bm{y}_{n}})$ which yields $\bm{w}^{(0)}=\mathbf{0}$ as $\bm{\psi}_{i}(\bm{y}_{i})=\mathbf{0}$ $\forall i$.

The duality gap (5) for our structural SVM dual formulation (4) is given by

Because the objective of the structural SVM dual (4) is simply a quadratic function in $\bm{\alpha}$, the optimal step-size for any given candidate search point $\bm{s}\in\mathcal{M}$ can be obtained analytically. Namely, \gamma_{LS}:=\operatornamewithlimits{argmin}_{\gamma\in}\,f\left(\bm{\alpha}+\gamma\big{(}\bm{s}-\bm{\alpha}\big{)}\right) is obtained by setting the derivative of this univariate quadratic function in $\gamma$ to zero, which here (before restricting to $$) gives$\gamma_{opt}:=\frac{\langle\bm{\alpha}-\bm{s},\nabla f(\bm{\alpha})\rangle}{\lambda\left\lVert A(\bm{\alpha}-\bm{s})\right\rVert^{2}}=\frac{g(\bm{\alpha})}{\lambda\left\lVert\bm{w}-\bm{w}_{\bm{s}}\right\rVert^{2}}$ (used in Algorithms 2 and 4).

In the following, we write $R$ for the maximal length of a difference feature vector, i.e. $R\!:=\!\max_{i\in[n],\bm{y}\in\mathcal{Y}_{i}}\!\left\lVert\bm{\psi}_{i}(\bm{y})\right\rVert_{2}$, and we write the maximum error as $L_{\text{\tiny{max}}}:=\max_{i,\bm{y}}L_{i}(\bm{y})$. By bounding the curvature constant $C_{f}$ for the dual SVM objective (4), we can now directly apply the known convergence results for the standard Frank-Wolfe algorithm to obtain the following primal-dual rate (proof in Appendix B.3):

Algorithm 2 obtains an $\varepsilon$-approximate solution to the structural SVM dual problem (4) and duality gap $g(\bm{\alpha}^{(k)})\leq\varepsilon$ after at most $O\left(\frac{R^{2}}{\lambda\varepsilon}\right)$ iterations, where each iteration costs $n$ oracle calls.

Since we have proved that the duality gap is smaller than $\varepsilon$, this implies that the original SVM primal objective (3) is actually solved to accuracy $\varepsilon$ as well.

Surprisingly, the batch Frank-Wolfe method (Algorithm 2) is equivalent to the batch subgradient method in the primal, though Frank-Wolfe allows a more clever choice of step-size, since line-search can be used in the dual. To see the equivalence, notice that a subgradient of (3) is given by $\bm{d}_{sub}=\lambda\bm{w}-\frac{1}{n}\sum_{i}\bm{\psi}_{i}(\bm{y}_{i}^{*})=\lambda(\bm{w}-\bm{w}_{\bm{s}}),$ where $\bm{y}_{i}^{*}$ and $\bm{w}_{\bm{s}}$ are as defined in Algorithm 2. Hence, for a step-size of $\beta$, the subgradient method update becomes $\bm{w}^{(k+1)}:=\bm{w}^{(k)}-\beta\bm{d}_{sub}=\bm{w}^{(k)}-\beta\lambda(\bm{w}^{(k)}-\bm{w}_{\bm{s}})=(1-\beta\lambda)\bm{w}^{(k)}+\beta\lambda\bm{w}_{\bm{s}}.$ Comparing this with Algorithm 2, we see that each Frank-Wolfe step on the dual problem (4) with step-size $\gamma$ is equivalent to a batch subgradient step in the primal with a step-size of $\beta=\gamma/\lambda$, and thus our convergence results also apply to it. This seems to generalize the equivalence between Frank-Wolfe and the subgradient method for a quadratic objective with identity Hessian as observed by Bach et al. (2012, Section 4.1).

In each iteration, the cutting plane algorithm of Joachims et al. (2009) and the Frank-Wolfe method (Algorithm 2) solve the loss-augmented decoding problem for each datapoint, selecting the same new ‘active’ coordinates to add to the dual problem. The only difference is that instead of just moving towards the corner $\bm{s}$, as in classical Frank-Wolfe, the cutting plane algorithm re-optimizes over all the previously added ‘active’ dual variables (this task is a quadratic program). This shows that the method is exactly equivalent to the ‘fully corrective’ variant of Frank-Wolfe, which in each iteration re-optimizes over all previously visited corners (Clarkson, 2010; Shalev-Shwartz et al., 2010b). Note that the convergence results for the ‘fully corrective’ variant directly follow from the ones for Frank-Wolfe (by inclusion), thus our convergence results apply to the cutting plane algorithm of Joachims et al. (2009), significantly simplifying its analysis.

Faster Block-Coordinate Frank-Wolfe

A major disadvantage of the standard Frank-Wolfe algorithm when applied to the structural SVM problem is that each iteration requires a full pass through the data, resulting in $n$ calls to the maximization oracle. In this section, we present the main new contribution of the paper: a block-coordinate generalization of the Frank-Wolfe algorithm that maintains all appealing properties of Frank-Wolfe, but yields much cheaper iterations, requiring only one call to the maximization oracle in the context of structural SVMs. The new method is given in Algorithm 3, and applies to any constrained convex optimization problem of the form

The following main theorem shows that after $O(1/\varepsilon)$ many iterations, Algorithm 3 obtains an $\varepsilon$-approximate solution to (6), and guaranteed $\varepsilon$-small duality gap (proof in Appendix C). Here the constant $C_{f}^{\otimes}:=\sum_{i=1}^{n}C_{f}^{(i)}$ is the sum of the (partial) curvature constants of $f$ with respect to the individual domain block $\mathcal{M}^{(i)}$. We discuss this Lipschitz assumption on the gradient in more details in Appendix A, where we compute the constant precisely for the structural SVM and obtain $C_{f}^{\otimes}=C_{f}/n$, where $C_{f}$ is the classical Frank-Wolfe curvature.

For each $k\geq 0$, the iterate $\bm{\alpha}^{(k)}$ of Algorithm 3 (either using the predefined step-sizes, or using line-search) satisfies \operatorname*{\rm E}\!\big{[}f(\bm{\alpha}^{(k)})\big{]}-f(\bm{\alpha}^{*})\leq\frac{2n}{k+2n}\big{(}C_{f}^{\otimes}+h_{0}\big{)}\,, where $\bm{\alpha}^{*}\in\mathcal{M}$ is a solution to problem (6), $h_{0}:=f(\bm{\alpha}^{(0)})-f(\bm{\alpha}^{*})$ is the initial error at the starting point of the algorithm, and the expectation is over the random choice of the block $i$ in the steps of the algorithm.

Furthermore, if Algorithm 3 is run for $K\geq 0$ iterations, then it has an iterate $\bm{\alpha}^{(\hat{k})}$, $0\leq\hat{k}\leq K$, with duality gap bounded by \operatorname*{\rm E}\!\big{[}g(\bm{\alpha}^{(\hat{k})})\big{]}\leq\frac{6n}{K+1}\big{(}C_{f}^{\otimes}+h_{0})\,.

By applying Theorem 2 to the SVM case where $C_{f}^{\otimes}=C_{f}/n=4R^{2}/\lambda n$ (in the worst case), we get that the number of iterations needed for our new block-wise Algorithm 4 to obtain a specific accuracy $\varepsilon$ is the same as for the batch version in Algorithm 2 (under the assumption that the initial error $h_{0}$ is smaller than $4R^{2}/\lambda n$), even though each iteration takes $n$ times fewer oracle calls. If $h_{0}>4R^{2}/\lambda n$, we can use the fact that Algorithm 4 is using line-search to get a weaker dependence on $h_{0}$ in the rate (Theorem C.4). We summarize the overall rate as follows (proof in Appendix B.3):

If $L_{\text{\tiny{max}}}\leq\frac{4R^{2}}{\lambda n}$ (so $h_{0}\leq\frac{4R^{2}}{\lambda n}$), then Algorithm 4 obtains an $\varepsilon$-approximate solution to the structural SVM dual problem (4) and expected duality gap $\operatorname*{\rm E}[g(\bm{\alpha}^{(k)})]\leq\varepsilon$ after at most $O\left(\frac{R^{2}}{\lambda\varepsilon}\right)$ iterations, where each iteration costs a single oracle call.

If $L_{\text{\tiny{max}}}>\frac{4R^{2}}{\lambda n}$, then it requires at most an additional (constant in $\varepsilon$) number of $O\left(n\log\left(\frac{\lambda nL_{\text{\tiny{max}}}}{R^{2}}\right)\right)$ steps to get the same error and duality gap guarantees.

In terms of $\varepsilon$, the $O(1/\varepsilon)$ convergence rate above is similar to existing stochastic subgradient and cutting-plane methods. However, unlike stochastic subgradient methods, the block-coordinate Frank-Wolfe method allows us to compute the optimal step-size at each iteration (while for an additional pass through the data we can evaluate the duality gap (5) to allow us to decide when to terminate the algorithm in practice). Further, unlike cutting-plane methods which require $n$ oracle calls per iteration, this rate is achieved ‘online’, using only a single oracle call per iteration.

Interestingly, we can show that all the convergence results presented in this paper also hold if only approximate minimizers of the linear subproblems are used instead of exact minimizers. If we are using an approximate oracle giving candidate directions $\bm{s}_{(i)}$ in Algorithm 3 (or $\bm{s}$ in Algorithm 1) with a multiplicative accuracy $\nu\in(0,1]$ (with respect to the the duality gap (5) on the current block), then the above convergence bounds from Theorem 2 still apply. The only change is that the convergence is slowed by a factor of $1/\nu^{2}$. We prove this generalization in the Theorems of Appendix C. For structural SVMs, this significantly improves the applicability to large-scale problems, where exact decoding is often too costly but approximate loss-augmented decoding may be possible.

Both Algorithms 2 and 4 can directly be used with kernels by maintaining the sparse dual variables $\bm{\alpha}^{(k)}$ instead of the primal variables $\bm{w}^{(k)}$. In this case, the classifier is only given implicitly as a sparse combination of the corresponding kernel functions, i.e. $\bm{w}=A\bm{\alpha}$. Using our Algorithm 4, we obtain the currently best known bound on the number of support vectors, i.e. a guaranteed $\varepsilon$-approximation with only $O(\frac{R^{2}}{\lambda\varepsilon})$ support vectors. In comparison, the standard cutting plane method (Joachims et al., 2009) adds $n$ support vectors $\bm{\psi}_{i}(\bm{y}_{i}^{*})$ at each iteration. More details on the kernelized variant of Algorithm 4 are discussed in Appendix B.5.

Experiments

We compare our novel Frank-Wolfe approach to existing algorithms for training structural SVMs on the OCR dataset ($n=6251,d=4028$) from Taskar et al. (2003) and the CoNLL dataset ($n=8936,d=1643026$) from Sang & Buchholz (2000). Both datasets are sequence labeling tasks, where the loss-augmented decoding problem can be solved exactly by the Viterbi algorithm. Our third application is a word alignment problem between sentences in different languages in the setting of Taskar et al. (2006) ($n=5000,d=82$). Here, the structured labels are bipartite matchings, for which computing marginals over labels as required by the methods of Collins et al. (2008); Zhang et al. (2011) is intractable, but loss-augmented decoding can be done efficiently by solving a min-cost flow problem.

We compare Algorithms 2 and 4, the batch Frank-Wolfe method (FW)This is equivalent to the batch subgradient method with an adaptive step-size, as mentioned in Section 4. and our novel block-coordinate Frank-Wolfe method (BCFW), to the cutting plane algorithm implemented in SVMstruct (Joachims et al., 2009) with its default options, the online exponentiated gradient (online-EG) method of Collins et al. (2008), and the stochastic subgradient method (SSG) with step-size chosen as in the ‘Pegasos’ version of Shalev-Shwartz et al. (2010a). We also include the weighted average $\bar{\bm{w}}^{(k)}:=\frac{2}{k(k+1)}\sum_{t=1}^{k}t\bm{w}^{(t)}$ of the iterates from SSG (called SSG-wavg) which was recently shown to converge at the faster rate of $O(1/k)$ instead of $O\left((\log{k})/k\right)$ (Lacoste-Julien et al., 2012; Shamir & Zhang, 2013). Analogously, we average the iterates from BCFW the same way to obtain the BCFW-wavg method (implemented efficiently with the optional line in Algorithm 4), which also has a provable $O(1/k)$ convergence rate (Theorem C.3). The performance of the different algorithms according to several criteria is visualized in Figure 1. The results are discussed in the caption, while additional experiments can be found in Appendix F. In most of the experiments, the BCFW-wavg method dominates all competitors. The superiority is especially striking for the first few iterations, and when using a small regularization strength $\lambda$, which is often needed in practice. In term of test error, a peculiar observation is that the weighted average of the iterates seems to help both methods significantly: SSG-wavg sometimes slightly outperforms BCFW-wavg despite having the worst objective value amongst all methods. This phenomenon is worth further investigation.

Related Work

There has been substantial work on dual coordinate descent for SVMs, including the original sequential minimal optimization (SMO) algorithm. The SMO algorithm was generalized to structural SVMs (Taskar, 2004, Chapter 6), but its convergence rate scales badly with the size of the output space: it was estimated as $O\left(n|\mathcal{Y}|/\lambda\varepsilon\right)$ in Zhang et al. (2011). Further, this method requires an expectation oracle to work with its factored dual parameterization. As in our algorithm, Rousu et al. (2006) propose updating one training example at a time, but using multiple Frank-Wolfe updates to optimize along the subspace. However, they do not obtain any rate guarantees and their algorithm is less general because it again requires an expectation oracle. In the degenerate binary SVM case, our block-coordinate Frank-Wolfe algorithm is actually equivalent to the method of Hsieh et al. (2008), where because each datapoint has a unique dual variable, exact coordinate optimization can be accomplished by the line-search step of our algorithm. Hsieh et al. (2008) show a local linear convergence rate in the dual, and our results complement theirs by providing a global primal convergence guarantee for their algorithm of $O\left(1/\varepsilon\right)$. After our paper had appeared on arXiv, Shalev-Shwartz & Zhang (2012) have proposed a generalization of dual coordinate descent applicable to several regularized losses, including the structural SVM objective. Despite being motivated from a different perspective, a version of their algorithm (Option II of Figure 1) gives the exact same step-size and update direction as BCFW with line-search, and their Corollary 3 gives a similar convergence rate as our Theorem 3. Balamurugan et al. (2011) propose to approximately solve a quadratic problem on each example using SMO, but they do not provide any rate guarantees. The online-EG method implements a variant of dual coordinate descent, but it requires an expectation oracle and Collins et al. (2008) estimate its primal convergence at only $O\left(1/\varepsilon^{2}\right)$.

Besides coordinate descent methods, a variety of other algorithms have been proposed for structural SVMs. We summarize a few of the most popular in Table 1, with their convergence rates quoted in number of oracle calls to reach an accuracy of $\varepsilon$. However, we note that almost no guarantees are given for the optimization of structural SVMs with approximate oracles. A regret analysis in the context of online optimization was considered by Ratliff et al. (2007), but they do not analyze the effect of this on solving the optimization problem. The cutting plane algorithm of Tsochantaridis et al. (2005) was considered with approximate maximization by Finley & Joachims (2008), though the dependence of the running time on the the approximation error was left unclear. In contrast, we provide guarantees for batch subgradient, cutting plane, and block-coordinate Frank-Wolfe, for achieving an $\varepsilon$-approximate solution as long as the error of the oracle is appropriately bounded.

Discussion

This work proposes a novel randomized block-coordinate generalization of the classic Frank-Wolfe algorithm for optimization with block-separable constraints. Despite its potentially much lower iteration cost, the new algorithm achieves a similar convergence rate in the duality gap as the full Frank-Wolfe method. For the dual structural SVM optimization problem, it leads to a simple online algorithm that yields a solution to an issue that is notoriously difficult to address for stochastic algorithms: no step-size sequence needs to be tuned since the optimal step-size can be efficiently computed in closed-form. Further, at the cost of an additional pass through the data (which could be done alongside a full Frank-Wolfe iteration), it allows us to compute a duality gap guarantee that can be used to decide when to terminate the algorithm. Our experiments indicate that empirically it converges faster than other stochastic algorithms for the structural SVM problem, especially in the realistic setting where only a few passes through the data are possible.

Although our structural SVM experiments use an exact maximization oracle, the duality gap guarantees, the optimal step-size, and a computable bound on the duality gap are all still available when only an appropriate approximate maximization oracle is used. Finally, although the structural SVM problem is what motivated this work, we expect that the block-coordinate Frank-Wolfe algorithm may be useful for other problems in machine learning where a complex objective with block-separable constraints arises.

We thank Francis Bach, Bernd Gärtner and Ronny Luss for helpful discussions, and Robert Carnecky for the 3D illustration. MJ is supported by the ERC Project SIPA, and by the Swiss National Science Foundation. SLJ and MS are partly supported by the ERC (SIERRA-ERC-239993). SLJ is supported by a Research in Paris fellowship. MS is supported by a NSERC postdoctoral fellowship.

References

In Appendix A, we discuss the curvature constants and compute them for the structural SVM problem. In Appendix B, we give additional details on applying the Frank-Wolfe algorithms to the structural SVM and provide proofs for Theorems 1 and 3. In the main Appendix C, we give a self-contained presentation and analysis of the new block-coordinate Frank-Wolfe method (Algorithm 3), and prove the main convergence Theorem 2. In Appendix D, the ‘linearization’-duality gap is interpreted in terms of Fenchel duality. For completeness, we include a short derivation of the dual problem to the structural SVM in Appendix E. Finally, we present in Appendix F additional experimental results as well as more detailed information about the implementation.

The curvature constant $C_{f}$ is given by the maximum relative deviation of the objective function $f$ from its linear approximations, over the domain $\mathcal{M}$ (Clarkson, 2010; Jaggi, 2013). Formally,

The assumption of bounded $C_{f}$ corresponds to a slightly weaker, affine invariant form of a smoothness assumption on $f$. It is known that $C_{f}$ is upper bounded by the Lipschitz constant of the gradient $\nabla f$ times the squared diameter of $\mathcal{M}$, for any arbitrary choice of a norm (Jaggi, 2013, Lemma 8); but it can also be much smaller (in particular, when the dimension of the affine hull of $\mathcal{M}$ is smaller than the ambient space), so it is a more fundamental quantity in the analysis of the Frank-Wolfe algorithm than the Lipschitz constant of the gradient. As pointed out by Jaggi (2013, Section 2.4), $C_{f}$ is invariant under affine transformations, as is the Frank-Wolfe algorithm.

The curvature concept can be generalized to our setting of product domains $\mathcal{M}:=\mathcal{M}^{(1)}\times\mathellipsis\times\mathcal{M}^{(n)}$ as follows: over each individual coordinate block, the curvature is given by

where the notation ${\bm{x}}_{[i]}$ refers to the zero-padding of ${\bm{x}}_{(i)}$ so that ${\bm{x}}_{[i]}\in\mathcal{M}$. By considering the Taylor expansion of $f$, it is not hard to see that also the ‘partial’ curvature $C_{f}^{(i)}$ is upper bounded by the Lipschitz constant of the partial gradient $\nabla_{\!(i)}f$ times the squared diameter of just one domain block $\mathcal{M}^{(i)}$. See also the proof of Lemma A.2 below.

We define the global product curvature constant as the sum of these curvatures for each block, i.e.

Observe that for the classical Frank-Wolfe case when $n=1$, we recover the original curvature constant.

For the dual structural SVM objective function (4) over the domain $\mathcal{M}:=\Delta_{|\mathcal{Y}_{1}|}\times\mathellipsis\times\Delta_{|\mathcal{Y}_{n}|}$, the curvature constant $C_{f}$, as defined in (7), is upper bounded by

where $R$ is the maximal length of a difference feature vector, i.e. $R:=\displaystyle\max_{i\in[n],\bm{y}\in\mathcal{Y}_{i}}\left\lVert\bm{\psi}_{i}(\bm{y})\right\rVert_{2}$ .

If the objective function is twice differentiable, we can plug-in the second degree Taylor expansion of $f$ into the above definition (7) of the curvature, see e.g. (Jaggi, 2011, Inequality (2.12)) or (Clarkson, 2010, Section 4.1). In our case, the gradient at $\bm{\alpha}$ is given by $\lambda A^{T}A\bm{\alpha}-\bm{b}$, so that the Hessian is $\lambda A^{T}A$, being a constant matrix independent of $\bm{\alpha}$. This gives the following upper boundBecause our function is a quadratic function, this is actually an equality. on $C_{f}$, which we can separate into two identical matrix-vector products with our matrix $A$:

By definition of our compact domain $\mathcal{M}$, we have that each vector ${\bm{v}}\in A\mathcal{M}$ is precisely the sum of $n$ vectors, each of these being a convex combination of the feature vectors for the possible labelings for datapoint $i$.

Therefore, the norm $\left\lVert{\bm{v}}\right\rVert_{2}$ is upper bounded by $n$ times the longest column of the matrix $A$, or more formally $\left\lVert{\bm{v}}\right\rVert_{2}\leq n\frac{1}{\lambda n}R$ with $R$ being the longestThis choice of the radius $R$ then gives $\frac{1}{\lambda n}R=\max_{i\in[n],\bm{y}\in\mathcal{Y}_{i}}\left\lVert\frac{1}{\lambda n}\bm{\psi}_{i}(\bm{y})\right\rVert_{2}=\max_{i\in[n],\bm{y}\in\mathcal{Y}_{i}}\left\lVert A_{(i,\bm{y})}\right\rVert$. feature vector, i.e.

Altogether, we have obtained that the curvature $C_{f}$ is upper bounded by $\frac{4R^{2}}{\lambda}$.

We also note that in the worst case, this bound is tight. For example, we can make $C_{f}=\frac{4R^{2}}{\lambda}$ by having for each datapoint $i$, two labelings which give opposite difference feature vectors $\psi_{i}$ of the same maximal norm $R$. ∎

For the dual structural SVM objective function (4) over the domain $\mathcal{M}:=\Delta_{|\mathcal{Y}_{1}|}\times\mathellipsis\times\Delta_{|\mathcal{Y}_{n}|}$, the total curvature constant $C_{f}^{\otimes}$ on the product domain $\mathcal{M}$, as defined in (9), is upper bounded by

where $R$ is the maximal length of a difference feature vector, i.e. $R:=\displaystyle\max_{i\in[n],\bm{y}\in\mathcal{Y}_{i}}\left\lVert\bm{\psi}_{i}(\bm{y})\right\rVert_{2}$ .

We follow the same lines as in the above proof of Lemma A.1, but now applying the same bound to the block-wise definition (8) of the curvature on the $i$-th block. Here, the change from ${\bm{x}}$ to ${\bm{y}}$ is now restricted to only affect the coordinates in the $i$-th block $\mathcal{M}^{(i)}$. To simplify the notation, let $\mathcal{M}^{[i]}$ be $\mathcal{M}^{(i)}$ augmented with the zero domain for all the other blocks – i.e. the analog of ${\bm{x}}_{(i)}\in\mathcal{M}^{(i)}$ is ${\bm{x}}_{[i]}\in\mathcal{M}^{[i]}$. ${\bm{x}}_{(i)}$ is the $i$-th block of ${\bm{x}}$ whereas ${\bm{x}}_{[i]}\in\mathcal{M}$ is ${\bm{x}}_{(i)}$ padded with zeros for all the other blocks. We thus require that ${\bm{y}}-{\bm{x}}\in\mathcal{M}^{[i]}$ for a valid change from ${\bm{x}}$ to ${\bm{y}}$. Again by the degree-two Taylor expansion, we obtain

In other words, by definition of our compact domain $\mathcal{M}^{(i)}=\Delta_{|\mathcal{Y}_{i}|}$, we have that each vector ${\bm{v}}\in A\mathcal{M}^{(i)}$ is a convex combination of the feature vectors corresponding to the possible labelings for datapoint $i$. Therefore, the norm $\left\lVert{\bm{v}}\right\rVert_{2}$ is again upper bounded by the longest column of the matrix $A$, which means $\left\lVert{\bm{v}}\right\rVert_{2}\leq\frac{1}{\lambda n}R$ with $R:=\max_{i\in[n],\bm{y}\in\mathcal{Y}_{i}}\left\lVert\bm{\psi}_{i}(\bm{y})\right\rVert_{2}$. Summing up over the $n$ blocks $\mathcal{M}^{(i)}$, we obtain that the product curvature $C_{f}^{\otimes}$ is upper bounded by $\frac{4R^{2}}{\lambda n}$.

For the same argument as at the end of the proof for Lemma A.1, this bound is actually tight in the worst case. ∎

Appendix B More Details on the Algorithms for Structural SVMs

To see that the proposed Algorithm 2 indeed exactly corresponds to the standard Frank-Wolfe Algorithm 1 applied to the SVM dual problem (4), we verify that the search direction $\bm{s}$ giving the update $\bm{w}_{\bm{s}}=A\bm{s}$ is in fact an exact Frank-Wolfe step, which can be seen as follows:

Over the product domain $\mathcal{M}=\Delta_{|\mathcal{Y}_{1}|}\times\mathellipsis\times\Delta_{|\mathcal{Y}_{n}|}$, the minimization $\min_{\bm{s}^{\prime}\in\mathcal{M}}\langle\bm{s}^{\prime},\nabla f(\bm{\alpha})\rangle$ decomposes as $\sum_{i}\min_{\bm{s}_{i}\in\Delta_{|\mathcal{Y}_{i}|}}\langle\bm{s}_{i},\nabla_{i}f(\bm{\alpha})\rangle$. The minimization of a linear function over the simplex reduces to a search over its corners – in this case, it amounts for each $i$ to find the minimal component of $-H_{i}(\bm{y};\bm{w})$ over $\bm{y}\in\mathcal{Y}_{i}$, i.e. solving the loss-augmented decoding problem as used in Algorithm 2 to construct the domain vertex $\bm{s}$. To see this, note that for our choice of primal variables $\bm{w}=A\bm{\alpha}$, the gradient of the dual objective, $\nabla f(\bm{\alpha})=\lambda A^{T}A\bm{\alpha}-\bm{b}$, writes as $\lambda A^{T}\bm{w}-\bm{b}$. This vector is precisely the loss-augmented decoding function $-\frac{1}{n}H_{i}(\bm{y};\bm{w})$, for $i\in[n],\,\bm{y}\in\mathcal{Y}_{i}$, as defined in (2). ∎

B.2 Relation between the Lagrange Duality Gap and the ‘Linearization’ Gap for the Structural SVM

We show here that the simple ‘linearization’ gap (5), evaluated on the structural SVM dual problem (4) is actually equivalent to the standard Lagrangian duality gap for the structural SVM primal objective (1) (these two duality gaps are not the same in generalFor example, the two gaps are different when evaluated on the dual of the conditional random field objective (see, for example, Collins et al. (2008) for the formulation), which does not have a Lipschitz continuous gradient.). This is important for the duality gap convergence rate results of our Frank-Wolfe algorithms to be transferable as primal convergence rates on the original structural SVM objective (3), which is the one with statistical meaning (for example with generalization error bounds as given in Taskar et al. (2003)).

So consider the difference of our objective at $\bm{w}:=A\bm{\alpha}$ in the primal problem (3), and the dual objective at $\bm{\alpha}$ in problem (4) (in the maximization version). This difference is

Now recall that by the definition of $A$ and $\bm{b}$, we have that $\frac{1}{n}H_{i}(\bm{y};\bm{w})=(\bm{b}-\lambda A^{T}\bm{w})_{(i,\bm{y})}=(-\nabla f(\bm{\alpha}))_{(i,\bm{y})}$. By summing up over all points and re-using a similar argument as in Lemma B.1 above, we get that

B.3 Convergence Analysis

Algorithm 2 obtains an $\varepsilon$-approximate solution to the structural SVM dual problem (4) and duality gap $g(\bm{\alpha}^{(k)})\leq\varepsilon$ after at most $O\left(\frac{R^{2}}{\lambda\varepsilon}\right)$ iterations, where each iteration costs $n$ oracle calls.

We apply the known convergence results for the standard Frank-Wolfe Algorithm 1, as given e.g. in (Frank & Wolfe, 1956; Dunn & Harshbarger, 1978; Jaggi, 2013), or as given in the paragraph just after the proof of Theorem C.1: For each $k\geq 1$, the iterate $\bm{\alpha}^{(k)}$ of Algorithm 1 (either using the predefined step-sizes, or using line-search) satisfies $\operatorname*{\rm E}[f(\bm{\alpha}^{(k)})]-f(\bm{\alpha}^{*})\leq\frac{2C_{f}}{k+2}\ ,$ where $\bm{\alpha}^{*}\in\mathcal{M}$ is an optimal solution to problem (4).

Furthermore, if Algorithm 1 is run for $K\geq 1$ iterations, then it has an iterate $\bm{\alpha}^{(\hat{k})}$, $1\leq\hat{k}\leq K$, with duality gap bounded by $\operatorname*{\rm E}[g(\bm{\alpha}^{(\hat{k})})]\leq\frac{6C_{f}}{K+1}$. This was shown e.g. in (Jaggi, 2013) with slightly different constants, or also in our analysis presented below (see the paragraph after the generalized analysis provided in Theorem C.3, when the number of blocks $n$ is set to one).

Now for the SVM problem and the equivalent Algorithm 2, the claim follows from the curvature bound $C_{f}\leq\frac{4R^{2}}{\lambda}$ for the dual structural SVM objective function (4) over the domain $\mathcal{M}:=\Delta_{|\mathcal{Y}_{1}|}\times\mathellipsis\times\Delta_{|\mathcal{Y}_{n}|}$, as given in the above Lemma A.1.∎

B.3.2 Convergence of the Block-Coordinate Frank-Wolfe Algorithm 4 on the Structural SVM Dual

If $L_{\text{\tiny{max}}}\leq\frac{4R^{2}}{\lambda n}$ (so $h_{0}\leq\frac{4R^{2}}{\lambda n}$), then Algorithm 4 obtains an $\varepsilon$-approximate solution to the structural SVM dual problem (4) and expected duality gap $\operatorname*{\rm E}[g(\bm{\alpha}^{(k)})]\leq\varepsilon$ after at most $O\left(\frac{R^{2}}{\lambda\varepsilon}\right)$ iterations, where each iteration costs a single oracle call.

If $L_{\text{\tiny{max}}}>\frac{4R^{2}}{\lambda n}$, then it requires at most an additional (constant in $\varepsilon$) number of $O\left(n\log\left(\frac{\lambda nL_{\text{\tiny{max}}}}{R^{2}}\right)\right)$ steps to get the same error and duality gap guarantees, whereas the predefined step-size variant will require an additional $O\left(\frac{nL_{\text{\tiny{max}}}}{\varepsilon}\right)$ steps.

Writing $h_{0}=f(\bm{\alpha}^{(0)})-f(\bm{\alpha}^{*})$ for the error at the starting point used by the algorithm, the convergence Theorem 2 states that if $k\geq 0$ and $k\geq\frac{2n}{\varepsilon}(C_{f}^{\otimes}+h_{0})$, then the expected error is $\operatorname*{\rm E}[f(\bm{\alpha}^{(k)})]-f(\bm{\alpha}^{*})\leq\varepsilon$ and analogously for the expected duality gap. The result then follows by plugging in the curvature bound $C_{f}^{\otimes}\leq\frac{4R^{2}}{\lambda n}$ for the dual structural SVM objective function (4) over the domain $\mathcal{M}:=\Delta_{|\mathcal{Y}_{1}|}\times\mathellipsis\times\Delta_{|\mathcal{Y}_{n}|}$, as detailed in Lemma A.2 (notice that it is $n$ times smaller than the curvature $C_{f}$ needed for the batch algorithm) and then bounding $h_{0}$. To bound $h_{0}$, we observe that by the choice of the starting point $\bm{\alpha}^{(0)}$ using only the observed labels, the initial error is bounded as $h_{0}\leq g(\bm{\alpha}^{(0)})=\bm{b}^{T}\bm{s}=\frac{1}{n}\sum_{i=1}^{n}\max_{\bm{y}\in\mathcal{Y}_{i}}L_{i}(\bm{y})\leq L_{\text{\tiny{max}}}$. Thus, if $L_{\text{\tiny{max}}}\leq\frac{4R^{2}}{\lambda n}$, then we have $C_{f}^{\otimes}+h_{0}\leq\frac{8R^{2}}{\lambda n}$, which proves the first part of the theorem.

In the case $L_{\text{\tiny{max}}}>\frac{4R^{2}}{\lambda n}$, then the predefined step-size variant will require an additional $\frac{2nh_{0}}{\varepsilon}\leq\frac{2nL_{\text{\tiny{max}}}}{\varepsilon}$ steps as we couldn’t use the fact that $h_{0}\leq C_{f}^{\otimes}$. For the line-search variant, on the other hand, we can use the improved convergence Theorem C.4, which shows that the algorithm require at most $k_{0}\leq n\log(h_{0}/C_{f}^{\otimes})$ steps to reach the condition $h_{0}\leq C_{f}^{\otimes}$; once this condition is satisfied, we can simply re-use Theorem 2 with $k$ redefined as $k-k_{0}$ to get the final convergence rates. We also point out that the statement of Theorem C.4 stays valid by replacing $C_{f}^{\otimes}$ with any $C_{f}^{\otimes}{{}^{\prime}}\geq C_{f}^{\otimes}$ in it. So plugging in $C_{f}^{\otimes}{{}^{\prime}}=\frac{R^{2}}{\lambda n}$ and the bound $h_{0}\leq L_{\text{\tiny{max}}}$ in the $k_{0}$ quantity gives back the number of additional steps mentioned in the second part of the theorem statement an $\varepsilon$-approximate solution. A similar argument can be made for the expected duality gap by using the improved convergence Theorem C.5, which simply adds the requirement $K\geq 5k_{0}$. ∎

We note that the condition $L_{\text{\tiny{max}}}\leq\frac{4R^{2}}{\lambda n}$ is not necessarily too restrictive in the case of the structural SVM setup. In particular, the typical range of $\lambda$ which is needed for a problem is around $O(1/n)$ – and so the condition becomes $L_{\text{\tiny{max}}}\leq 4R^{2}$ which is typically satisfied when the loss function is normalized.

B.4 Implementation

We comment on three practical implementation aspects of Algorithm 4 on large structural SVM problems:

B.5 More details on the Kernelized Algorithm

Appendix C Analysis of the Block-Coordinate Frank-Wolfe Algorithm 3

This section gives a self-contained presentation and analysis of the new block-coordinate Frank-Wolfe optimization Algorithm 3. The main goal is to prove the convergence Theorem 2, which here is split into two parts, the primal convergence rate in Theorem C.1, and the primal-dual convergence rate in Theorem C.3. Finally, we will present a faster convergence result for the line-search variant in Theorem C.4 and Theorem C.5, which we have used in the convergence for the structural SVM case as presented above in Theorem 3.

Despite their simplicity and very early appearance in the literature, surprisingly few results were known on the convergence (and convergence rates in particular) of coordinate descent type methods. Recently, the interest in these methods has grown again due to their good scalability to very large scale problems as e.g. in machine learning, and also sparked new theoretical results such as (Nesterov, 2012).

We consider the general constrained convex optimization problem

In some large-scale applications, the above computation of the update direction $\bm{s}_{(i)}$ can be problematic, e.g. if the Lipschitz constants $L_{i}$ are unknown, or —more importantly— if the domains $\mathcal{M}^{(i)}$ are such that the quadratic term makes the subproblem for $\bm{s}_{(i)}$ hard to solve.

The structural SVM is a nice example where this makes a big difference. Here, each domain block $\mathcal{M}^{(i)}$ is a simplex of exponentially many variables, but nevertheless the linear subproblem over one such factor (also known as loss-augmented decoding) is often relatively easy to solve.

We would therefore like to replace the above computation of $\bm{s}_{(i)}$ by a simpler one, as proposed in the following algorithm variant:

This natural coordinate descent type optimization method picks a single one of the $n$ blocks uniformly at random, and in each step leaves all other blocks unchanged.

If there is only one factor ($n=1$), then Algorithm C.2 becomes the standard Frank-Wolfe (or conditional gradient) algorithm, which is known to converge at a rate of $O(1/k)$ (Frank & Wolfe, 1956; Dunn & Harshbarger, 1978; Clarkson, 2010; Jaggi, 2013).

If approximate linear minimizers are used internally in Algorithm C.2, then the necessary approximation quality for the candidate directions $\bm{s}_{(i)}$ is determined as follows (in either additive or multiplicative quality):

In the additive case, we choose a fixed additive error parameter $\delta\geq 0$ such that the candidate direction $\bm{s}_{(i)}$ satisfies

In the multiplicative case, we choose a fixed multiplicative error parameter $0<\nu\leq 1$ such that the candidate directions $\bm{s}_{(i)}$ attain the current ‘duality gap’ on the $i$-th factor up to a multiplicative approximation error of $\nu$, i.e.

If a multiplicative approximate internal oracle is used together with the predefined step-size instead of doing line-search, then the step-size in Algorithm C.2 needs to be increased to $\gamma_{k}:=\frac{2n}{\nu k+2n}$ instead of the original $\frac{2n}{k+2n}$.

Both types of errors can be combined together with the following property for the candidate direction $\bm{s}_{(i)}$:

In the above Algorithm C.2 we have also added an optional last line which maintains the following weighted average $\bar{{\bm{x}}}_{w}^{(k)}$ which is defined for $k\geq 1$ as

and by convention we also define $\bar{{\bm{x}}}_{w}^{(0)}:={\bm{x}}^{(0)}$. As our convergence analysis will show, the weighted average of the iterates can yield more robust duality gap convergence guarantees when the duality gap function $g$ is convex in ${\bm{x}}$ (see Theorem C.3) – this is for example the case for quadratic functions such as in the structural SVM objective (4). We will also consider in our proofs a scheme which averages the last $(1-\mu)$-fraction of the iterates for some fixed $0<\mu<1$:

This is what Rakhlin et al. (2012) calls $(1-\mu)$-suffix averaging and it appeared in the context of getting a stochastic subgradient method with $O(1/k)$ convergence rate for strongly convex functions instead of the standard $O((\log k)/k)$ rate that one can prove for the individual iterates ${\bm{x}}^{(k)}$. The problem with $(1-\mu)$-suffix averaging is that to implement it for a fixed $\mu$ (say $\mu=0.5$) without storing a fraction of all the iterates, one needs to know when they will stop the algorithm. An alternative mentioned in Rakhlin et al. (2012) is to maintain a uniform average over rounds of exponentially increasing size (the so-called ‘doubling trick’). This can give very good performance towards the end of the rounds as we will see in our additional experiments in Appendix F, but the performance varies widely towards the beginning of the rounds. This motivates the simpler and more robust weighted averaging scheme (14), which in the case of the stochastic subgradient method, was also recently proven to have $O(1/k)$ convergence rate by Lacoste-Julien et al. (2012)In this paper, they considered a $(k+1)$-weight instead of our $k$-weight, but similar rates can be proven for shifted versions. We motivate skipping the first iterate ${\bm{x}}^{(0)}$ in our weighted averaging scheme as sometimes bounds can be proven on the quality of ${\bm{x}}^{(1)}$ irrespective of ${\bm{x}}^{(0)}$ for Frank-Wolfe (see the paragraph after the proof of Theorem C.1 for example, looking at the $n=1$ case). and independently by Shamir & Zhang (2013), who called such schemes ‘polynomial-decay averaging’.

In contrast to the randomized choice of coordinate which we use here, the analysis of cyclic coordinate descent algorithms (going through the blocks sequentially) seems to be notoriously difficult, such that until today, no analysis proving a global convergence rate has been obtained as far as we know. \citetsupLuo:1992fy has proven a local linear convergence rate for the strongly convex case.

For product domains, such a cyclic analogue of our Algorithm C.2 has already been proposed in \citetsupPatriksson:1998hg, using a generalization of Frank-Wolfe iterations under the name ‘cost approximation’. The analysis of \citetsupPatriksson:1998hg shows asymptotic convergence, but since the method goes through the blocks sequentially, no convergence rates could be proven so far.

C.1 Setup for Convergence Analysis

We review below the important concepts needed for analyzing the convergence of the block-coordinate Frank-Wolfe Algorithm C.2.

The product structure of our domain has a crucial effect on the duality gap, namely that it decomposes into a sum over the $n$ components of the domain. The ‘linearization’ duality gap as defined in (5) (see also Jaggi (2013)) for any constrained convex problem of the above form (10), for a fixed feasible point ${\bm{x}}\in\mathcal{M}$, is given by

Also, the curvature can now be defined on the individual factors,

We recall that the notation ${\bm{x}}_{[i]}$ and ${\bm{x}}_{(i)}$ is defined just below (10). We define the global product curvature as the sum of these curvatures for each block, i.e.

C.2 Primal Convergence on Product Domains

The following main theorem shows that after O\big{(}\frac{1}{\varepsilon}\big{)} many iterations, Algorithm C.2 obtains an $\varepsilon$-approximate solution.

For each $k\geq 0$, the iterate ${\bm{x}}^{(k)}$ of the exact variant of Algorithm C.2 satisfies

For the approximate variant of Algorithm C.2 with additive approximation quality (11) for $\delta\geq 0$, it holds that

For the approximate variant of Algorithm C.2, with multiplicative approximation quality (12) for $0<\nu\leq 1$, it holds that

All convergence bounds hold both if the predefined step-sizes, or line-search is used in the algorithm. Here ${\bm{x}}^{*}\in\mathcal{M}$ is an optimal solution to problem (10), and the expectation is with respect to the random choice of blocks during the algorithm. (In other words all three algorithm variants deliver a solution of (expected) primal error at most $\varepsilon$ after $O(\frac{1}{\varepsilon})$ many iterations.)

The proof of the above theorem on the convergence rate of the primal error crucially depends on the following Lemma C.2 on the improvement in each iteration.

Let $\gamma\in$ be an arbitrary fixed step-size. Moving only within the $i$-th block of the domain, we consider two variants of steps towards a direction $\bm{s}_{(i)}\in\mathcal{M}^{(i)}$: Let ${\bm{x}}^{(k+1)}_{\gamma}:={\bm{x}}(\gamma)$ be the point obtained by moving towards $\bm{s}_{(i)}$ using step-size $\gamma$, and let ${\bm{x}}^{(k+1)}_{LS}:={\bm{x}}(\gamma_{LS})$ be the corresponding point obtained by line-search, i.e. $\gamma_{LS}:=\displaystyle\operatornamewithlimits{argmin}_{\bar{\gamma}\in}\,f\left({\bm{x}}(\bar{\gamma})\right)$. Here for convenience we have used the notation {\bm{x}}(\bar{\gamma}):={\bm{x}}^{(k)}+\bar{\gamma}\big{(}\bm{s}_{[i]}-{\bm{x}}^{(k)}_{[i]}\big{)} for $\bar{\gamma}\in$.

On the other hand, if $\bm{s}_{(i)}$ attains the duality gap $g^{(i)}({\bm{x}})$ on the $i$-th block up to a multiplicative approximation quality (12) for $0<\nu\leq 1$, then

All expectations are taken over the random choice of the block $i$ and conditioned on ${\bm{x}}^{(k)}$.

We write ${\bm{x}}:={\bm{x}}^{(k)}$, ${\bm{y}}:={\bm{x}}^{(k+1)}_{\gamma}={\bm{x}}+\gamma(\bm{s}_{[i]}-{\bm{x}}_{[i]})$, with ${\bm{x}}_{[i]}$ and $\bm{s}_{[i]}$ being zero everywhere except in their $i$-th block. We also write $d_{\bm{x}}:=\nabla_{(i)}f({\bm{x}})$ to simplify the notation. From the definition (17) of the curvature constant $C_{f}^{(i)}$ of our convex function $f$ over the factor $\mathcal{M}^{(i)}$, we have

by the definition (16) of the duality gap. Altogether, we have obtained

Using that the line-search by definition must lead to an objective value at least as good as the one at the fixed $\gamma$, we therefore have shown the inequality

Finally the claimed bound on the expected improvement directly follows by taking the expectation: With respect to the (uniformly) random choice of the block $i$, the expected value of the gap $g^{(i)}({\bm{x}}^{(k)})$ corresponding to the picked $i$ is exactly $\frac{1}{n}g({\bm{x}}^{(k)})$. Also, the expected curvature of the $i$-th factor is $\frac{1}{n}C_{f}^{\otimes}$.

The proof for the case of multiplicative approximation follows completely analogously, using $\langle\bm{s}_{(i)}-{\bm{x}}_{(i)},d_{\bm{x}}\rangle\leq-\nu\,g^{(i)}({\bm{x}}),$ which then gives a step improvement of $f({\bm{y}})\leq f({\bm{x}})-\gamma\nu g^{(i)}({\bm{x}})+\frac{\gamma^{2}}{2}C_{f}^{(i)}\ .$ ∎

Having Lemma C.2 at hand, we will now prove our above primal convergence Theorem C.1 using similar ideas as for general domains, such as in Jaggi (2013).

We first prove the theorem for the approximate variant of Algorithm C.2 with multiplicative approximation quality (12) of $0<\nu\leq 1$ – the exact variant of the algorithm is simply the special case $\nu=1$. From the above Lemma C.2, we know that for every inner step of Algorithm C.2 and conditioned on ${\bm{x}}^{(k)}$, we have that $\operatorname*{\rm E}[f({\bm{x}}_{\gamma}^{(k+1)})\,|\,{\bm{x}}^{(k)}]\leq f({\bm{x}}^{(k)})-\frac{\gamma\nu}{n}g({\bm{x}}^{(k)})+\frac{\gamma^{2}}{2n}C_{f}^{\otimes}$, where the expectation is over the random choice of the block $i$ (this bound holds independently whether line-search is used or not). Writing $h({\bm{x}}):=f({\bm{x}})-f({\bm{x}}^{*})$ for the (unknown) primal error at any point ${\bm{x}}$, this reads as

where in the second line, we have used weak duality $h({\bm{x}})\leq g({\bm{x}})$ (which follows directly from the definition of the duality gap, together with convexity of $f$). The inequality (20) is conditioned on ${\bm{x}}^{(k)}$, which is a random quantity given the previous random choices of blocks to update. We get a deterministic inequality by taking the expectation of both sides with respect to the random choice of previous blocks, yielding:

We observe that the resulting inequality (21) with $\nu=1$ is of the same form as the one appearing in the standard Frank-Wolfe primal convergence proof such as in Jaggi (2013), though with a crucial difference of the $1/n$ factor (and that we are now working with the expected values $\operatorname*{\rm E}[h({\bm{x}}^{(k)})]$ instead of the original $h({\bm{x}}^{(k)})$). We will thus follow a similar induction argument over $k$, but we will see that the $1/n$ factor will yield a slightly different induction base case (which for $n=1$ can be analyzed separately to obtain a better bound). To simplify the notation, let $h_{k}:=\operatorname*{\rm E}[h({\bm{x}}^{(k)})]$.

By induction, we are now going to prove that

for the choice of constant $C:=\frac{1}{\nu}C_{f}^{\otimes}+h_{0}$.

The base-case $k=0$ follows immediately from the definition of $C$, given that $C\geq h_{0}$.

Now we consider the induction step for $k\geq 0$. Here the bound (21) for the particular choice of step-size $\gamma_{k}:=\frac{2n}{\nu k+2n}\in$ given by Algorithm C.2 gives us (the same bound also holds for the line-search variant, given that the corresponding objective value $f({\bm{x}}^{(k+1)}_{\text{\tiny Line-Search}})\leq f({\bm{x}}^{(k+1)}_{\gamma})$ only improves):

where in the first line we have used that $C_{f}^{\otimes}\leq C\nu$, and in the last inequality we have plugged in the induction hypothesis for $h_{k}$. Simply rearranging the terms gives

which is our claimed bound for $k\geq 0$.

Our above convergence result also holds for the case of the standard Frank-Wolfe algorithm, when no product structure on the domain is assumed, i.e. for the case $n=1$. In this case, the constant in the convergence can even be improved for the variant of the algorithm without a multiplicative approximation ($\nu=1$), since the additive term given by $h_{0}$, i.e. the error at the starting point, can be removed. This is because already after the first step, we obtain a bound for $h_{1}$ which is independent of $h_{0}$. More precisely, plugging $\gamma_{0}:=1$ and $\nu=1$ in the bound (21) when $n=1$ gives $h_{1}\leq 0+C_{f}^{\otimes}(1+\delta)\leq C$. Using $k=1$ as the base case for the same induction proof as above, we obtain that for $n=1$:

which matches the convergence rate given in Jaggi (2013). Note that in the traditional Frank-Wolfe setting, i.e. $n=1$, our defined curvature constant becomes $C_{f}^{\otimes}=C_{f}$.

We note that the only use of including $h_{0}$ in the constant $C=\nu^{-1}C_{f}^{\otimes}+h_{0}$ was to satisfy the base case in the induction proof, at $k=0$. If from the structure of the problem we can get a guarantee that $h_{0}\leq\nu^{-1}C_{f}^{\otimes}$, then the smaller constant $C^{\prime}=\nu^{-1}C_{f}^{\otimes}$ will satisfy the base case and the whole proof will go through with it, without needing the extra $h_{0}$ factor. See also Theorem C.4 for a better convergence result with a weaker dependence on $h_{0}$ in the case where the line-search is used.

C.3 Obtaining Small Duality Gap

The following theorem shows that after O\big{(}\frac{1}{\varepsilon}\big{)} many iterations, Algorithm C.2 will have visited a solution with $\varepsilon$-small duality gap in expectation. Because the block-coordinate Frank-Wolfe algorithm is only looking at one block at a time, it doesn’t know what is its current true duality gap without doing a full (batch) pass over all blocks. Without monitoring this quantity, the algorithm could miss which iterate had a low duality gap. This is why, if one is interested in having a good duality gap (such as in the structural SVM application), then the averaging schemes considered in (14) and (15) become interesting: the following theorem also says that the bound hold for each of the averaged iterates, if the duality gap function $g$ is convex, which is the case for example when $f$ is a quadratic function.To see that $g$ is convex when $f$ is quadratic, we refer to the equivalence between the gap $g({\bm{x}})$ and the Fenchel duality $p({\bm{x}})-d(\nabla f({\bm{x}})))$ as shown in Appendix D. The dual function $d(\cdot)$ is concave, so if $\nabla f({\bm{x}}))$ is an affine function of ${\bm{x}}$ (which is the case for a quadratic function), then $d$ will be a concave function of ${\bm{x}}$, implying that $g({\bm{x}})=p({\bm{x}})-d(\nabla f({\bm{x}})))$ is convex in ${\bm{x}}$, since the primal function $p$ is convex.

For each $K\geq 0$, the variants of Algorithm C.2 (either using the predefined step-sizes, or using line-search) will yield at least one iterate ${\bm{x}}^{(\hat{k})}$ with $\hat{k}\leq K$ with expected duality gap bounded by

where $\beta=3$ and $C=\nu^{-1}C_{f}^{\otimes}(1+\delta)+f({\bm{x}}^{(0)})-f({\bm{x}}^{*})$. $\delta\geq 0$ and $0<\nu\leq 1$ are the approximation quality parameters as defined in (13) – use $\delta=0$ and $\nu=1$ for the exact variant.

Moreover, if the duality gap $g$ is a convex function of ${\bm{x}}$, then the above bound also holds both for \operatorname*{\rm E}\big{[}g(\bar{{\bm{x}}}_{w}^{(K)})\big{]} and \operatorname*{\rm E}\big{[}g(\bar{{\bm{x}}}_{0.5}^{(K)})\big{]} for each $K\geq 0$, where $\bar{{\bm{x}}}_{w}^{(K)}$ is the weighted average of the iterates as defined in (14) and $\bar{{\bm{x}}}_{0.5}^{(K)}$ is the $0.5$-suffix average of the iterates as defined in (15) with $\mu=0.5$.

To simplify notation, we will again denote the expected primal error and expected duality gap for any iteration $k\geq 0$ in the algorithm by $h_{k}:=\operatorname*{\rm E}[h({\bm{x}}^{(k)})]:=\operatorname*{\rm E}[f({\bm{x}}^{(k)})-f({\bm{x}}^{*})]$ and $g_{k}:=\operatorname*{\rm E}[g({\bm{x}}^{(k)})]$ respectively.

The proof starts again by using the crucial improvement Lemma C.2 with $\gamma=\gamma_{k}:=\frac{2n}{\nu k+2n}$ to cover both variants of Algorithm C.2 at the same time. As in the beginning of the proof of Theorem C.1, we take the expectation with respect to ${\bm{x}}^{(k)}$ in Lemma C.2 and subtract $f({\bm{x}}^{*})$ to get that for each $k\geq 0$ (for the general approximate variant of the algorithm):

The general proof idea to get an handle on $g_{k}$ is to take a convex combination over multiple $k$’s of the inequality (22), to obtain a new upper bound. Because a convex combination of numbers is upper bounded by its maximum, we know that the new bound has to upper bound at least one of the $g_{k}$’s (this gives the existence $\hat{k}$ part of the theorem). Moreover, if $g$ is convex, we can also obtain an upper bound for the expected duality gap of the same convex combination of the iterates.

So let $\{w_{k}\}_{k=0}^{K}$ be a set of non-negative weights, and let $\rho_{k}:=w_{k}/S_{K}$, where $S_{K}:=\sum_{k=0}^{K}w_{k}$. Taking the convex combination of inequality (22) with coefficient $\rho_{k}$, we get

using $h_{K+1}\geq 0$. Inequality (23) can be seen as a master inequality to derive various bounds on $g_{k}$. In particular, if we define $\bar{{\bm{x}}}:=\sum_{k=0}^{K}\rho_{k}{\bm{x}}^{(k)}$ and we suppose that $g$ is convex (which is the case for example when $f$ is a quadratic function), then we have $\operatorname*{\rm E}[g(\bar{{\bm{x}}})]\leq\sum_{k=0}^{K}\rho_{k}g_{k}$ by convexity and linearity of the expectation.

We first consider the weights $w_{k}=k$ which appear in the definition of the weighted average of the iterates $\bar{{\bm{x}}}_{w}^{(K)}$ in (14) and suppose $K\geq 1$. In this case, we have $\rho_{k}=k/S_{K}$ where $S_{K}=K(K+1)/2$. With the predefined step-size $\gamma_{k}=2n/(\nu k+2n)$, we then have

Plugging this in the master inequality (23) as well as using the convergence rate $h_{k}\leq\frac{2nC}{\nu k+2n}$ from Theorem C.1, we obtain

Hence we have proven the bound with $\beta=3$ for $K\geq 1$. For $K=0$, the master inequality (23) becomes

since $h_{0}\leq C$ and $\nu\leq 1$. Given that $n\geq 1$, we see that the bound also holds for $K=0$.

For the proof of convergence of the $0.5$-suffix averaging of the iterates $\bar{{\bm{x}}}_{0.5}^{(K)}$, we refer the reader to the proof of Theorem C.5 which can be re-used for this case (see the last paragraph of the proof to explain how). ∎

As we mentioned after the proof of the primal convergence Theorem C.1, we note that if $n=1$, then we can replace $C$ in the statement of Theorem C.3 by $C_{f}^{\otimes}(1+\delta)$ for $K\geq 1$ when $\nu=1$, as then we can ensure that $h_{1}\leq C$ which is all what was needed for the primal convergence induction. Again, $C_{f}^{\otimes}=C_{f}$ when $n=1$.

C.4 An Improved Convergence Analysis for the Line-Search Case

If line-search is used, we can improve the convergence results of Theorem C.1 by showing a weaker dependence on the starting condition $h_{0}$ thanks to faster progress in the starting phase of the first few iterations:

For each $k\geq k_{0}$, the iterate ${\bm{x}}^{(k)}$ of the line-search variant of Algorithm C.2 (where the linear subproblem is solved with a multiplicative approximation quality (12) of $0<\nu\leq 1$) satisfies

where k_{0}:=\max\big{\{}0,\left\lceil\log\left(\frac{2\nu h({\bm{x}}^{(0)})}{C_{f}^{\otimes}}\right)\Big{/}(-\log\xi_{n})\right\rceil\big{\}} is the number of steps required to guarantee that \operatorname*{\rm E}\big{[}f({\bm{x}}^{(k)})\big{]}-f({\bm{x}}^{*})\leq\nu^{-1}C_{f}^{\otimes}, with ${\bm{x}}^{*}\in\mathcal{M}$ being an optimal solution to problem (10), and $h({\bm{x}}^{(0)}):=f({\bm{x}}^{(0)})-f({\bm{x}}^{*})$ is the primal error at the starting point, and $\xi_{n}:=1-\frac{\nu}{n}<1$ is the geometric decrease rate of the primal error in the first phase while $k<k_{0}$ — i.e. \operatorname*{\rm E}\big{[}f({\bm{x}}^{(k)})\big{]}-f({\bm{x}}^{*})\leq(\xi_{n})^{k}\ h({\bm{x}}^{(0)})+C_{f}^{\otimes}/2\nu for $k<k_{0}$.

If the linear subproblem is solved with an additive approximation quality (11) of $\delta\geq 0$ instead, then replace all appearances of $C_{f}^{\otimes}$ above with $C_{f}^{\otimes}(1+\delta)$.

For the line-search case, the expected improvement guaranteed by Lemma C.2 for the multiplicative approximation variant of Algorithm C.2, in expectation as in (21), is valid for any choice of $\gamma\in$:

Because the bound (25) holds for any $\gamma$, we are free to choose the one which minimizes it subject to $\gamma\in$, that is $\gamma^{*}:=\min\left\{1,\frac{\nu h_{k}}{C_{f}^{\otimes}}\right\}$, where we have again used the identification h_{k}:=\operatorname*{\rm E}\big{[}h({\bm{x}}^{(k)}_{LS})\big{]}. Now we distinguish two cases:

If $\gamma^{*}=1$, then $\nu h_{k}\geq C_{f}^{\otimes}$. By unrolling the inequality (25) recursively to the beginning and using $\gamma=1$ at each step, we get:

We thus have a geometric decrease with rate $\xi_{n}:=1-\frac{\nu}{n}$ in this phase. We then get $h_{k}\leq\nu^{-1}C_{f}^{\otimes}$ as soon as $(\xi_{n})^{k}h_{0}\leq C_{f}^{\otimes}/2\nu$, i.e. when $k\geq\log_{1/\xi_{n}}(2\nu h_{0}/C_{f}^{\otimes})=\log(2\nu h_{0}/C_{f}^{\otimes})/-\log(1-\frac{\nu}{n})$. We thus have obtained a logarithmic bound on the number of steps that fall into the first regime case here, i.e. where $h_{k}$ is still ‘large’. Here it is crucial to note that the primal error $h_{k}$ is always decreasing in each step, due to the line-search, so once we leave this regime of $h_{k}\geq\nu^{-1}C_{f}^{\otimes}$, then we will never enter it again in subsequent steps.

On the other hand, as soon as we reach a step $k$ (e.g. when $k=k_{0})$ such that $\gamma^{*}<1$ or equivalently $h_{k}<\nu^{-1}C_{f}^{\otimes}$, then we are always in the second phase where $\gamma^{*}=\frac{\nu h_{k}}{C_{f}^{\otimes}}$. Plugging this value of $\gamma^{*}$ in (25) yields the recurrence bound:

where $\zeta:=\frac{2nC_{f}^{\otimes}}{\nu^{2}}$, with the initial condition $h_{k_{0}}\leq\frac{C_{f}^{\otimes}}{\nu}=\frac{\nu\zeta}{2n}$. This is a standard recurrence inequality which appeared for example in Joachims et al. (2009, Theorem 5, see their Equation (23)) or in the appendix of \citetsupTeo:2007bi. We can solve the recurrence (26) by following the argument of \citetsupTeo:2007bi, where it was pointed out that since $h_{k}$ is monotonically decreasing, we can upper bound $h_{k}$ by the solution to the corresponding differential equations $h^{\prime}(t)=-h^{2}(t)/\zeta$, with initial condition $h(k_{0})=h_{k_{0}}$. Integrating both sides, we get the solution $h(t)=\frac{\zeta}{t-k_{0}+\zeta/h_{k_{0}}}$. Plugging in the value for $h_{k_{0}}$ and since $h_{k}\leq h(k)$, we thus get the bound:

which completes the proof for the multiplicative approximation variant.

For the additive approximation variant, the inequality (25) with $\gamma=1$ in Lemma C.2 becomes:

We now make some observations in the case of $\delta=0$ (for simplicity). Note that since for $n>0.5$ and $-\log\left(1-\frac{\nu}{n}\right)>\frac{\nu}{n}$ for the natural logarithm, we get that $k_{0}\leq\left\lceil\frac{n}{\nu}\log\left(\frac{2\nu h({\bm{x}}^{(0)})}{C_{f}^{\otimes}}\right)\right\rceil$ and so unless the structure of our problem can guarantee that $h({\bm{x}}^{(0)})\leq C_{f}^{\otimes}/\nu$, we get a linear number of steps in $n$ required to reach the second phase, but the dependence is logarithmic in $h({\bm{x}}^{(0)})$ – instead of linear in $h({\bm{x}}^{(0)})$ as given by our previous convergence Theorem C.1 for the fixed step-size variant (in the fixed step-size variant, we would need $k_{0}=\left\lceil 2n\frac{h({\bm{x}}^{(0)})}{C_{f}^{\otimes}}\right\rceil$ steps to guarantee $h_{k_{0}}\leq C_{f}^{\otimes}/\nu$). Therefore, for the line-search variant of our Algorithm C.2, we have obtained guaranteed $\varepsilon$-small error after

It is also interesting to point out that even though we were using the optimal step-size in the second phase of the above proof (which yielded the recurrence (26)), the second phase bound is not better than what we could have obtained by using a fixed step-size schedule of $\frac{2n}{\nu(k-k_{0})+2n}$ and following the same induction proof line as in the previous Theorem C.1 (using the base case $h_{k_{0}}\leq C_{f}^{\otimes}/\nu$ and so we could let $C:=\nu^{-1}C_{f}^{\otimes}$). This thus means that the advantage of the line-search over the fixed step-size schedule only appears in knowing when to switch from a step-size of $1$ (in the first phase, when $h_{k}\geq\nu^{-1}C_{f}^{\otimes}$) to a step-size of $\frac{2n}{\nu(k-k_{0})+2n}$ (in the second phase), which unless we know the value of $f({\bm{x}}^{*})$, we cannot know in general. In the standard Frank-Wolfe case where $n=1$ and $\nu=1$, there is no difference in the rates for line-search or fixed step-size schedule as in this case we know $h_{1}\leq C_{f}^{\otimes}$ as explained at the end of the proof of Theorem C.1. This also suggests that if $k_{0}>n$, it might be more worthwhile in theory to first do one batch Frank-Wolfe step to ensure that $h_{1}\leq C_{f}^{\otimes}$, and then proceed with the block-coordinate Frank-Wolfe algorithm afterwards.

C.4.2 Improved Primal-Dual Convergence for Line-Search

Using the improved primal convergence theorem for line-search, we can also get a better rate for the expected duality gap (getting rid of the dependence of $h_{0}$ in the constant $C$):