Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

Martin Jaggi

article2013ICML1,542 citations

Establishes an affine-invariant primal-dual convergence framework for the Frank-Wolfe algorithm that supports approximate linear subproblems and provides explicit duality gap certificates for sparse vector and matrix optimization.

Listen

Modern data analysis and machine learning frequently require solving large-scale constrained convex optimization problems where the desired solution is sparse or low-rank. Standard methods, such as projected gradient descent and proximal algorithms, often become computationally intractable at scale because they require expensive projections or full singular value decompositions at every step. This makes projection-free alternatives increasingly vital for scalable enterprise and machine learning applications.

The article establishes a unified theoretical foundation for Frank-Wolfe (conditional gradient) algorithms across general domains. It evaluates their convergence behavior, robustness under approximate calculations, and ability to generate sparse solutions across a wide range of structured vector and matrix settings.

To conduct this evaluation, the article develops a theoretical framework based on duality gap certificates, which quantify the difference between the current objective value and the theoretical optimum. It analyzes four algorithmic variants: the standard fixed step-size method, inexact linear subproblem approximations, line search, and a fully corrective variant. The analysis models function complexity using a geometric curvature constant rather than norm-dependent parameters, extending to diverse problem classes including matrix factorizations and submodular polyhedra.

The findings provide key guarantees for optimization performance. First, the article demonstrates that all four Frank-Wolfe variants converge at a rate inversely proportional to the number of iterations, successfully bounding both the primal error and the duality gap. Second, these convergence guarantees hold even when solving linear subproblems approximately or with inexact gradient information, provided error tolerances are controlled. Third, the trade-off between the sparsity of the solution and approximation accuracy is shown to be worst-case optimal; no algorithm adding a single basic component per step can achieve better sparsity. Finally, the analysis proves that the algorithm is fully invariant under linear coordinate distortions, meaning performance does not degrade with poorly conditioned problem representations.

These results establish that Frank-Wolfe methods provide significant operational advantages over projection-heavy algorithms. By replacing complex quadratic subproblems with simple linear subproblems, iteration costs drop substantially—for instance, reducing matrix calculations from full cubic-time decompositions to fast, top-eigenvector updates. This reduces computational runtime and memory usage while delivering built-in, easily computable stopping certificates to guarantee solution quality without knowing the optimal value in advance.

Organizations handling large-scale sparse regression, structured machine learning, or matrix completion tasks should adopt Frank-Wolfe frameworks when projection steps dominate computation time. Implementers can comfortably use approximate linear solvers (such as iterative Lanczos methods for matrix trace norms) to further accelerate runtime without sacrificing theoretical convergence guarantees. Future development should focus on applying this framework to emerging combinatorial relaxations and structured matrix factorizations.

The findings are supported by rigorous mathematical proofs, offering high confidence in the stated convergence rates. However, practical users should note that the global convergence rate represents a worst-case upper bound that cannot guarantee faster linear rates without specialized modifications such as away-steps, and performance remains bounded by the hardness of underlying linear subproblems on certain complex matrix domains.

École Polytechnique computational efficiency eigenvectors matrix factorizations Projection-Free Sparse Convex Optimization Frank-Wolfe Algorithms Conditional Gradient Algorithms

Jaggi (2013).pdf

Paper: Efficient projections onto the l1-ball for learning in high dimensions, John C. Duchi et al. (2008). Understanding efficient Euclidean projection algorithms and their scaling bottlenecks provides the core motivation for adopting projection-free Frank-Wolfe alternatives in sparse constrained optimization.
Paper: Online Convex Programming and Generalized Infinitesimal Gradient Ascent, Martin A. Zinkevich (2003). This paper establishes foundational concepts of constrained convex programming and projection dynamics over convex domains that underpin the theoretical analysis of conditional gradient methods.
Paper: The Tradeoffs of Large Scale Learning, Léon Bottou et al. (2007). It provides essential context on computational versus statistical trade-offs in large-scale machine learning, justifying why per-iteration cost reductions via linear subproblems matter.
Paper: Full regularization path for sparse principal component analysis, Alexandre d'Aspremont et al. (2007). It introduces semidefinite relaxations and greedy path constructions for sparse matrix settings, serving as important background for Frank-Wolfe applications on structured matrix domains.
Paper: Online Learning for Matrix Factorization and Sparse Coding, Julien Mairal et al. (2010). It illustrates classical iterative optimization approaches for sparse coding and matrix factorization, highlighting the structured convex problems that conditional gradient methods aim to solve efficiently.

Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). It synthesizes online convex optimization frameworks, extending the analysis of first-order methods and duality-based regret guarantees to adversarial and streaming environments.
Paper: Optimization Methods for Large-Scale Machine Learning, Léon Bottou et al. (2016). This survey contextualizes projection-free conditional gradient techniques within the broader landscape of modern large-scale optimization methods and stochastic trade-offs in machine learning.
Paper: CVXPY: A Python-Embedded Modeling Language for Convex Optimization, Steven Diamond et al. (2016). It presents a domain-specific modeling language for expressing and solving the broad classes of structured convex optimization problems analyzed in the Frank-Wolfe framework.
Paper: A Reductions Approach to Fair Classification, Alekh Agarwal et al. (2018). It applies iterative convex optimization and duality-gap reduction techniques to train fair classification models subject to structured linear moment constraints.

Cover for Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

Abstract

We provide stronger and more general primal-dual convergence results for Frank-Wolfe-type algorithms (a.k.a. conditional gradient) for constrained convex optimization, enabled by a simple framework of duality gap certificates. Our analysis also holds if the linear subproblems are only solved approximately (as well as if the gradients are inexact), and is proven to be worst-case optimal in the sparsity of the obtained solutions.

On the application side, this allows us to unify a large variety of existing sparse greedy methods, in particular for optimization over convex hulls of an atomic set, even if those sets can only be approximated, including sparse (or structured sparse) vectors or matrices, low-rank matrices, permutation matrices, or max-norm bounded matrices.

We present a new general framework for convex optimization over matrix factorizations, where every Frank-Wolfe iteration will consist of a low-rank update, and discuss the broad application areas of this approach.

1. Introduction
2. The Duality Gap and Certificates
3. Frank-Wolfe Algorithms
4. Optimizing over Atomic Sets
4.1. Optimizing over Vectors
4.2. Optimizing over Matrices
4.3. Factorized Matrix Norms
4.4. Optimizing over Submodular Polyhedra
References
A. Primal Convergence
B. Primal-Dual Convergence
C. Optimality of the Trade-Off between Sparsity and Approximation Quality
D. Relating Curvature to Lipschitz-Continuous Gradient
E. Approximating the Top Eigenvalue of a Matrix

Knowls

Knowl 1 — Primal-Dual Convergence of Frank-Wolfe Algorithms
theoretical result
For any constrained convex optimization problem of the form $\min_{x \in \mathcal{D}} f(x)$ where $f: \mathcal{X} \to \mathbb{R}$ is convex and continuously differentiable on a compact convex domain $\mathcal{D}$ in a Hilbert space $\mathcal{X}$ :

If the Frank-Wolfe algorithm (using predefined step-sizes $\gamma = \frac{2}{k+2}$ , line-search, or fully-corrective re-optimization, with approximate linear subproblem parameter $\delta \ge 0$ ) is executed for $K \ge 2$ iterations, there exists an iterate $x^{(\hat{k})}$ with $1 \le \hat{k} \le K$ whose surrogate duality gap $g(x^{(\hat{k})}) := \max_{s \in \mathcal{D}} \langle x^{(\hat{k})} - s, \nabla f(x^{(\hat{k})}) \rangle$ satisfies:
$g(x^{(\hat{k})}) \le \frac{2\beta C_f}{K + 2}(1 + \delta)$
where $\beta = \frac{27}{8} = 3.375$ , and $C_f$ is the curvature constant of $f$ over $\mathcal{D}$ . This iterate $\hat{k}$ is guaranteed to occur in the final third of the iterations, i.e., $\lceil \frac{2}{3}(K+2) \rceil - 2 \le \hat{k} \le K$ .

In the two-regimes variant, if the algorithm is run for $K \ge 1$ iterations with $\gamma = \frac{2}{k+2}$ and then continued for another $K + 1$ iterations with fixed step-size $\gamma^{(k)} := \frac{2}{K+2}$ for all $K \le k \le 2K+1$ , there exists an iterate $x^{(\hat{k})}$ with $K \le \hat{k} \le 2K+1$ satisfying:
$g(x^{(\hat{k})}) \le \frac{2 C_f}{K + 2}(1 + \delta)$
Knowl 2 — Primal Convergence Rate of Frank-Wolfe Algorithms
theoretical result
Let $f: \mathcal{X} \to \mathbb{R}$ be a continuously differentiable convex objective function over a compact convex domain $\mathcal{D}$ in a Hilbert space $\mathcal{X}$ , and let $x^* \in \arg\min_{x \in \mathcal{D}} f(x)$ . For each iteration $k \ge 1$ , the iterate $x^{(k)}$ produced by the Frank-Wolfe algorithm (with predefined step size $\gamma = \frac{2}{k+2}$ , line-search, or fully-corrective updates, and approximate subproblem tolerance $\delta \ge 0$ ) satisfies:
$f(x^{(k)}) - f(x^*) \le \frac{2 C_f}{k + 2}(1 + \delta)$
where $C_f$ is the curvature constant of $f$ over $\mathcal{D}$ , and $\delta = 0$ corresponds to solving the internal linear subproblems exactly. Consequently, achieving an $\varepsilon$ -approximate primal solution $f(x^{(k)}) - f(x^*) \le \varepsilon$ requires at most $O(1/\varepsilon)$ iterations.
Knowl 3 — Curvature Constant of a Convex Function over a Compact Domain
definition
For a continuously differentiable convex function $f: \mathcal{X} \to \mathbb{R}$ defined on a compact convex subset $\mathcal{D}$ of a Hilbert space $\mathcal{X}$ , the curvature constant $C_f$ measures the non-linearity of $f$ over $\mathcal{D}$ and is defined as:
$C_f := \sup_{\substack{x, s \in \mathcal{D}, \\ \gamma \in (0, 1], \\ y = x + \gamma(s - x)}} \frac{2}{\gamma^2} \left( f(y) - f(x) - \langle y - x, \nabla f(x) \rangle \right)$
The term $f(y) - f(x) - \langle y - x, \nabla f(x) \rangle$ represents the Bregman divergence induced by $f$ .

Properties of $C_f$ :
1. For linear functions $f$ , $C_f = 0$ .
2. For $f(x) := \frac{1}{2}\|x\|_2^2$ on $\mathbb{R}^n$ , $C_f = \text{diam}_{\|\cdot\|_2}(\mathcal{D})^2$ .
3. If $\nabla f$ is $L$ -Lipschitz continuous on $\mathcal{D}$ with respect to an arbitrary norm $\|\cdot\|$ (i.e., $\|\nabla f(x) - \nabla f(y)\|_* \le L \|x - y\|$ ), then:
$C_f \le L \cdot \text{diam}_{\|\cdot\|}(\mathcal{D})^2$
where $\text{diam}_{\|\cdot\|}(\mathcal{D}) := \sup_{x, y \in \mathcal{D}} \|x - y\|$ . 4. $C_f$ is an intrinsic geometric property that does not depend on the choice of a specific norm.
Knowl 4 — Frank-Wolfe Algorithm and Algorithmic Variants
algorithm
The Frank-Wolfe (conditional gradient) method solves $\min_{x \in \mathcal{D}} f(x)$ for convex differentiable $f$ over a compact convex domain $\mathcal{D}$ without orthogonal projections onto $\mathcal{D}$ . In each iteration $k$ , it minimizes a linear approximation of $f$ over $\mathcal{D}$ up to additive accuracy $\frac{1}{2}\delta\gamma C_f = \frac{\delta C_f}{k+2}$ , where $\delta \ge 0$ is a fixed accuracy parameter, and updates the iterate along the line segment toward the minimizer $s$ .
Input: Initial feasible point $x^{(0)} \in \mathcal{D}$ , number of iterations $K$ , subproblem tolerance $\delta \ge 0$ , curvature constant $C_f$
Output: Iterate $x^{(K+1)} \in \mathcal{D}$
for $k = 0, 1, \dots, K$ do
     $\gamma := \frac{2}{k+2}$
    Find $s \in \mathcal{D}$ such that $\langle s, \nabla f(x^{(k)}) \rangle \le \min_{\hat{s} \in \mathcal{D}} \langle \hat{s}, \nabla f(x^{(k)}) \rangle + \frac{1}{2}\delta\gamma C_f$
    Update the iterate according to one of the following variants:
        Standard update: $x^{(k+1)} := (1 - \gamma) x^{(k)} + \gamma s$
        Line-search update: $x^{(k+1)} := (1 - \gamma^*) x^{(k)} + \gamma^* s$ , where $\gamma^* := \arg\min_{\gamma' \in [0, 1]} f(x^{(k)} + \gamma'(s - x^{(k)}))$
        Fully-corrective update: $x^{(k+1)} := \arg\min_{x \in \text{conv}(s^{(0)}, \dots, s^{(k+1)})} f(x)$ with $s^{(0)} := x^{(0)}$
end for
return $x^{(K+1)}$
Knowl 5 — Surrogate Duality Gap Certificate for Constrained Convex Optimization
definition
For a constrained convex optimization problem $\min_{x \in \mathcal{D}} f(x)$ with continuously differentiable convex objective $f$ on a compact convex domain $\mathcal{D}$ , the surrogate duality gap at any feasible point $x \in \mathcal{D}$ is defined as:
$g(x) := \max_{s \in \mathcal{D}} \langle x - s, \nabla f(x) \rangle$
Because $f$ is convex, its first-order Taylor linearization $f(x) + \langle s - x, \nabla f(x) \rangle$ supports $f$ from below, implying that $g(x)$ provides an upper bound certificate on the unknown primal error:
$g(x) \ge f(x) - f(x^*)$
where $x^* \in \arg\min_{x \in \mathcal{D}} f(x)$ .

In the Frank-Wolfe algorithm, whenever $s$ is the minimizer of the linearized subproblem $\min_{s' \in \mathcal{D}} \langle s', \nabla f(x) \rangle$ , the duality gap is obtained as a direct computational byproduct: $g(x) = \langle x - s, \nabla f(x) \rangle$ . The gap $g(x)$ corresponds to Fenchel duality where the dual variable is chosen to be the current gradient.
Knowl 6 — Affine Invariance of Frank-Wolfe Optimization
theoretical result
The Frank-Wolfe algorithm and its convergence rate are invariant under surjective affine transformations and re-parameterizations of the domain. Let $M: \hat{\mathcal{D}} \to \mathcal{D}$ be a surjective affine map between compact convex sets $\hat{\mathcal{D}}$ and $\mathcal{D}$ . The problem $\min_{x \in \mathcal{D}} f(x)$ is equivalent to $\min_{\hat{x} \in \hat{\mathcal{D}}} \hat{f}(\hat{x})$ where $\hat{f}(\hat{x}) := f(M\hat{x})$ .

Under this transformation:
1. The gradient transforms as $\nabla \hat{f}(\hat{x}) = M^T \nabla f(M\hat{x})$ .
2. The curvature constant is invariant: $C_{\hat{f}} = C_f$ .
3. The algorithmic iterates in $\hat{\mathcal{D}}$ map directly to the iterates in $\mathcal{D}$ under $M$ , executing identical steps and maintaining the $O(C_f / k)$ convergence guarantee without sensitivity to coordinate distortions or pre-conditioning.
Knowl 7 — Sparsity Lower Bound and Trade-off Optimality in Frank-Wolfe Optimization
theoretical result
For convex optimization over the unit simplex $\Delta_n := \{x \in \mathbb{R}^n \mid x \ge 0, \sum_{i=1}^n x_i = 1\}$ with objective $f(x) := \|x\|_2^2$ , every point $x \in \Delta_n$ with sparsity $\text{card}(x) \le k$ (where $1 \le k \le n$ ) satisfies:
$\min_{\substack{x \in \Delta_n \\ \text{card}(x) \le k}} f(x) = \frac{1}{k}$
Since the global unconstrained minimum on the simplex is $f(x^*) = \frac{1}{n}$ , the primal error for any $k$ -sparse vector is lower bounded by:
$f(x) - f(x^*) \ge \frac{1}{k} - \frac{1}{n}$
Furthermore, for any $k < n$ and any $x \in \Delta_n$ with $\text{card}(x) \le k$ , the surrogate duality gap is lower bounded by:
$g(x) \ge \frac{2}{k}$
Because the Frank-Wolfe algorithm adds at most one atom (non-zero coordinate) per iteration, obtaining an $\varepsilon$ -approximate primal solution or duality gap requires $\Omega(1/\varepsilon)$ atoms in the worst case, proving that the $O(1/\varepsilon)$ sparsity achieved by Frank-Wolfe is worst-case optimal.
Knowl 8 — Convex Optimization over Factorized Matrix Norms via Low-Rank Updates
model/method
Optimization over factorizations of a matrix $M \in \mathbb{R}^{m \times n}$ of the form $M = L R^T$ (with $L \in \mathbb{R}^{m \times r}$ and $R \in \mathbb{R}^{n \times r}$ for a fixed rank parameter $r$ ) can be structured over the convex hull of atomic products:
$\mathcal{A} := \left\{ L R^T \;\middle|\; L \in \mathcal{A}_{\text{left}} \subseteq \mathbb{R}^{m \times r},\; R \in \mathcal{A}_{\text{right}} \subseteq \mathbb{R}^{n \times r} \right\}, \quad \mathcal{D} = \text{conv}(\mathcal{A})$
where $\mathcal{A}_{\text{left}}$ and $\mathcal{A}_{\text{right}}$ are compact sets.

In each iteration of the Frank-Wolfe algorithm over $\mathcal{D}$ , the linear subproblem minimizes $\langle S, \nabla f(X^{(k)}) \rangle$ over $S \in \mathcal{A}$ , generating a rank- $\le r$ atom $S = L R^T$ . The updated iterate $X^{(k+1)} = (1-\gamma)X^{(k)} + \gamma S$ has rank at most $r(k+1)$ , enabling optimization directly over factorized representations without full matrix eigendecompositions or SVDs.

Knowl 9 — Linear Subproblem Complexities for Frank-Wolfe Optimization across Atomic Domains

data/table

When optimizing over atomic domains $\mathcal{D} = \text{conv}(\mathcal{A})$ , the linear subproblem $\sup_{s \in \mathcal{D}} \langle s, y \rangle$ reduces to evaluating the support function $\Omega^*_{\mathcal{D}}(y) = \sup_{s \in \mathcal{A}} \langle s, y \rangle$ . The table below summarizes the support functions and per-iteration computational complexities across standard atomic vector and matrix domains, where $N_f$ is the number of non-zero entries in $\nabla f(x)$ and $\varepsilon' = \frac{\delta C_f}{k+2}$ is the target linear subproblem accuracy:

Domain Space $\mathcal{X}$	Domain $\mathcal{D} = \text{conv}(\mathcal{A})$	Support Function $\Omega^*_{\mathcal{D}}(y)$	Linear Subproblem Complexity
$\mathbb{R}^n$	$\ell_1$ -ball (sparse vectors)	$\\|y\\|_\infty$	$O(n)$
$\mathbb{R}^n$	$\ell_\infty$ -ball (sign-vectors)	$\\|y\\|_1$	$O(n)$
$\mathbb{R}^n$	$\ell_p$ -ball ( $p \in [1, \infty]$ )	$\\|y\\|_q$ ( $1/p + 1/q = 1$ )	$O(n)$
$\mathbb{R}^n$	Simplex $\Delta_n$	$\max_i \{y_i\}$	$O(n)$
$\mathbb{R}^n$	Latent group sparse $\\|\cdot\\|_{\mathcal{G}}$ -ball	$\max_{g \in \mathcal{G}} \\|y_{(g)}\\|^*_g$	$\sum_{g \in \mathcal{G}} \|g\|$
$\mathbb{R}^{m \times n}$	Trace norm $\\|\cdot\\|_{\text{tr}}$ -ball	$\\|y\\|_{\text{op}} = \sigma_1(y)$	$\tilde{O}(N_f / \sqrt{\varepsilon'})$ (Lanczos)
$\mathbb{R}^{m \times n}$	Operator norm $\\|\cdot\\|_{\text{op}}$ -ball	$\\|y\\|_{\text{tr}} = \\|\sigma(y)\\|_1$	$O(\min\{mn^2, m^2n\})$ (SVD)
$\mathbb{R}^{m \times n}$	Schatten $\ell_p$ -norm ball	$\\|\sigma(y)\\|_q$ ( $1/p + 1/q = 1$ )	$O(\min\{mn^2, m^2n\})$ (SVD)
$\mathbb{R}^{m \times n}$	Matrix max-norm $\\|\cdot\\|_{\text{max}}$ -ball	SDP formulation	$\tilde{O}(N_f (n+m)^{1.5} / {\varepsilon'}^{2.5})$
$\mathbb{R}^{n \times n}$	Birkhoff polytope (permutations)	Hungarian algorithm	$O(n^3)$
$\mathbb{R}^{n \times n}$	Rotation matrices	Procrustes problem	$O(n^3)$ (SVD)
$\mathcal{S}^{n \times n}$	Rank-1 PSD unit-trace $\{X \succeq 0, \text{Tr}(X)=1\}$	$\lambda_{\max}(y)$	$\tilde{O}(N_f / \sqrt{\varepsilon'})$ (Lanczos)
$\mathcal{S}^{n \times n}$	PSD bounded diagonal $\{X \succeq 0, X_{ii} \le 1\}$	SDP approximation	$\tilde{O}(N_f n^{1.5} / {\varepsilon'}^{2.5})$

Knowl 10 — Convex Optimization over Bounded Matrix Max-Norm
theoretical result
Convex optimization over the matrix max-norm ball $\mathcal{D} = \{M \in \mathbb{R}^{m \times n} \mid \|M\|_{\text{max}} \le 1\}$ can be solved with provable convergence via Frank-Wolfe by solving approximate semidefinite programming (SDP) subproblems.

The max-norm is defined as $\|M\|_{\text{max}} := \min_{M = LR^T} \|L\|_{2,\infty} \|R\|_{2,\infty}$ . Maximizing a linear objective over this domain is equivalent to linear optimization over the set of positive semidefinite matrices of dimension $(n+m) \times (n+m)$ with all diagonal elements bounded by 1.

Using the multiplicative weights SDP algorithm of Arora, Hazan, and Kale (2005), an additive $\varepsilon'$ -approximate linear minimizer (where $\varepsilon' = \frac{\delta C_f}{k+2}$ ) is found in time:
$\tilde{O}\left( \frac{(n+m)^{1.5} L^{2.5}}{{\varepsilon'}^{2.5}} N_f \right)$
where $N_f$ is the number of non-zeros in the gradient and $L$ bounds the linear objective value. Plugging this approximate solver into the Frank-Wolfe framework yields an $\varepsilon$ -approximate primal solution and duality gap in $O(1/\varepsilon)$ total outer iterations.

Coverage note — Optimization over submodular polyhedra via the greedy algorithm (Edmonds, 1970) and Wolfe's away-steps variant were discussed as existing extensions and were covered within the atomic domain framework rather than separated into dedicated result knowls.

References

1.Alon, N and Naor, A. Approximating the Cut-Norm via Grothendieck’s Inequality. SIAM J. Computing, 2006.
2.Arora, S, Hazan, E, and Kale, S. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. FOCS, 2005.
3.Bach, F. Learning with Submodular Functions: A Convex Optimization Perspective. 2011.
4.Bach, F, Mairal, J, and Ponce, J. Convex Sparse Matrix Factorizations. Technical report, 2008.
5.Bach, F, Lacoste-Julien, S, and Obozinski, G. On the Equivalence between Herding and Conditional Gradient Algorithms. In ICML, 2012.
6.Boyd, S and Vandenberghe, L. Convex optimization. 2004.
7.Cai, J-F, Candes, E J, and Shen, Z. A Singular Value Thresholding Algorithm for Matrix Completion. SIAM Journal on Optimization, 20(4):1956–1982, 2010.
8.Canon, M D and Cullum, C D. A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm. SIAM Journal on Control, 6(4):509–516, 1968.
9.Chandrasekaran, V, Recht, B, Parrilo, P A, and Willsky, A S. The Convex Geometry of Linear Inverse Problems. Found. Comp. Math., 12(6):805–849, 2012.
10.Clarkson, K L. Coresets, Sparse Greedy Approximation, and the Frank-Wolfe Algorithm. ACM Transactions on Algorithms, 6(4), 2010.
11.Demyanov, V F and Rubinov, A M. Approximate methods in optimization problems. Elsevier, 1970.
12.Dudik, M, Harchaoui, Z, and Malick, J. Lifted coordinate descent for learning with trace-norm regularization. In AISTATS, 2012.
13.Dunn, J C and Harshbarger, S. Conditional gradient algorithms with open loop step size rules. Journal of Mathematical Analysis and Applications, 62(2):432–444, 1978.
14.Edmonds, J. Submodular Functions, Matroids, and Certain Polyhedra. In Comb. Struct. and Appl., 69–87, 1970.
15.Frank, M and Wolfe, P. An algorithm for quadratic programming. Naval Res. Logis. Quart., 3:95–110, 1956.
16.G¨artner, B and Jaggi, M. Coresets for polytope distance. ACM SCG, 2009.
17.Giesen, J, Jaggi, M, and Laue, S. Regularization Paths with Guarantees for Convex Semidefinite Optimization. AISTATS, 2012.
18.Goemans, M and Williamson, D. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6), 1995.
19.Gu´eLat, J and Marcotte, P. Some comments on Wolfe’s ‘away step’. Mathematical Programming, 35(1), 1986.
20.Harchaoui, Z, Juditsky, A, and Nemirovski, A. Conditional gradient algorithms for machine learning. In NIPS Workshop on Optimization for ML, December 2012.
21.Hazan, E. Sparse Approximate Solutions to Semidefinite Programs. In LATIN, pp. 306–316, 2008.
22.Hazan, E and Kale, S. Projection-free Online Learning. In ICML, 2012.
23.Hazan, E, Kale, S, and Warmuth, M.K. Learning rotations with little regret. In COLT, pp. 144–154, 2010.
24.Jaggi, M. Sparse Convex Optimization Methods for Machine Learning. PhD thesis, ETH Z¨urich, 2011.
25.Jaggi, M and Sulovsk´y, M. A Simple Algorithm for Nuclear Norm Regularized Problems. ICML, 2010.
26.Jenatton, R, Audibert, J-Y, and Bach, F. Structured Variable Selection with Sparsity-Inducing Norms. JMLR, 12: 2777–2824, 2011.
27.Jones, L K. A Simple Lemma on Greedy Approximation in Hilbert Space and Convergence Rates for Projection Pursuit Regression and Neural Network Training. The Annals of Statistics, 20(1):608–613, 1992.
28.Kuczy´nski, J and Wo´zniakowski, H. Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start. SIAM Journal on Matrix Analysis and Applications, 13(4):1094–1122, 1992.
29.Lacoste-Julien, S, Jaggi, M, Schmidt, M, and Pletscher, P. Block-Coordinate Frank-Wolfe Optimization for Structural SVMs. In ICML, 2013.
30.Lee, J, Recht, B, Salakhutdinov, R, Srebro, N, and Tropp, J A. Practical Large-Scale Optimization for Max-Norm Regularization. NIPS, 2010.
31.Levitin, E S and Polyak, B T. Constrained minimization methods. USSR Comp. Math. & M. Phys., 6(5), 1966.
32.Li, J and Barron, A. Mixture density estimat.. NIPS, 2000.
33.Lov´asz, L. Submodular functions and convexity. Mathematical programming: the state of the art, 1983.
34.Lov´asz, L and Plummer, M D. Matching Theory. American Mathematical Society, 2009.
35.Mallat, S G and Zhang, Z. Matching pursuits with timefrequency dictionaries. IEEE Transactions on Signal Processing, 41(12):3397–3415, 1993.
36.Murty, K G and Kabadi, S N. Some NP-complete problems in quadratic and nonlinear programming. Mathematical Programming, 39(2):117–129, 1987.
37.Nesterov, Y. Introductory Lectures on Convex Optimization. A Basic Course. Kluwer, 2004.
38.Obozinski, G, Jacob, L, and Vert, JP. Group Lasso with Overlaps: the Latent Group Lasso approach. arXiv, 2011.
39.Orabona, F, Argyriou, A, and Srebro, N. PRISMA: PRoximal Iterative SMoothing Algorithm. arXiv.org, 2012.
40.Ouyang, H. and Gray, A. Fast Stochastic Frank-Wolfe Algorithms for Nonlinear SVMs. SDM, 2010.
41.Patriksson, M. Partial linearization methods in nonlinear programming. Journal of Optimization Theory and Applications, 78(2):227–246, 1993.
42.Rockafellar, R T. Convex analysis. 1997.
43.Shalev-Shwartz, S, Srebro, N, and Zhang, T. Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints. SIAM J. on Optimization, 20, 2010.
44.Srebro, N and Shraibman, A. Rank, Trace-Norm and MaxNorm. In COLT, 545–560, 2005.
45.Temlyakov, V N. Greedy approximation in convex optimization. arXiv.org, stat.ML, 2012.
46.Tewari, A, Ravikumar, P, and Dhillon, I S. Greedy Algorithms for Structurally Constrained High Dimensional Problems. In NIPS, 2011.
47.Tibshirani, R. Regression Shrinkage and Selection via the Lasso. J. Royal Statistical Society. Series B, 1996.
48.Tropp, J A and Gilbert, A. Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit. IEEE Trans. on Information Theory, 53(12):4655–4666, 2007.
49.Yuan, M and Lin, Y. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society: Series B, 68(1):49–67, 2006.
50.Yuan, X-T and Yan, S. Forward Basis Selection for Sparse Approximation over Dictionary. In AISTATS, 2012.
51.Zhang, T. Sequential greedy approximation for certain convex optimization problems. IEEE Transactions on Information Theory, 49(3):682–691, 2003.
52.Zhang, X, Yu, Y, and Schuurmans, D. Accelerated Training for Matrix-norm Regularization: A Boosting Approach. In NIPS, 2012.

Citation

MLA

Jaggi, M. “Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization”. Infoscience (Ecole Polytechnique Fédérale De Lausanne), 2013, http://infoscience.epfl.ch/record/229246.

APA

Jaggi, M. (2013). Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. Infoscience (Ecole Polytechnique Fédérale De Lausanne). http://infoscience.epfl.ch/record/229246

Chicago

Jaggi, M. 2013. “Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization”. Infoscience (Ecole Polytechnique Fédérale De Lausanne). http://infoscience.epfl.ch/record/229246.

Harvard

Jaggi, M. (2013) “Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization”, Infoscience (Ecole Polytechnique Fédérale de Lausanne) [Preprint]. Available at: http://infoscience.epfl.ch/record/229246.

Vancouver

1. Jaggi M (2013) Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. Infoscience (Ecole Polytechnique Fédérale de Lausanne)

BibTeX

@article{jaggi2013revisiting,
  title = {Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization},
  author = {Jaggi, Martin},
  year = {2013},
  journal = {Infoscience (Ecole Polytechnique Fédérale de Lausanne)},
  url = {http://infoscience.epfl.ch/record/229246}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Primal-Dual Convergence of Frank-Wolfe Algorithms

Knowl 2 — Primal Convergence Rate of Frank-Wolfe Algorithms

Knowl 3 — Curvature Constant of a Convex Function over a Compact Domain

Knowl 4 — Frank-Wolfe Algorithm and Algorithmic Variants

Knowl 5 — Surrogate Duality Gap Certificate for Constrained Convex Optimization

Knowl 6 — Affine Invariance of Frank-Wolfe Optimization

Knowl 7 — Sparsity Lower Bound and Trade-off Optimality in Frank-Wolfe Optimization

Knowl 8 — Convex Optimization over Factorized Matrix Norms via Low-Rank Updates

Knowl 9 — Linear Subproblem Complexities for Frank-Wolfe Optimization across Atomic Domains

Knowl 10 — Convex Optimization over Bounded Matrix Max-Norm

References

Citation

BibTeX

Access the Paper