Sparse Convex Optimization Methods for Machine Learning

By Martin Jaggi. 2011

88 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Frank-Wolfe Algorithms for Saddle Point Problems (2016, background): “By convex-concavity, h t can be upper-bounded by the following FW linearization gap (Jaggi, 2011, 2013; Larsson and Patriksson, 1994; Zhu and Marcotte, 1998): t .”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “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”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, background): “The classical Frank-Wolfe algorithm [31] has recently witnessed a surge of interest in machine learning [7, 15, 16, 2].”
Revisiting Projection-Free Optimization for Strongly Convex Constraint Sets (2018, background): “Thus, at iteration t , the solution is a combination of, at most, t + 1 vertices of the feasible set, thereby guaranteeing the sparsity of the eventual solution (Clarkson 2010; Jaggi 2013; Jaggi 2011).”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, methodology): “…and the crucial property that Algorithm 1 maintains its iterates as a convex combination of only few " atoms " s, enabling e.g. sparse and low-rank solutions (since at most one new extreme point of the domain D is added in each step) see e.g. (Clarkson, 2010; Jaggi, 2011) for an overview.”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, methodology): “thm attains a linear rate of convergence over polytopes, thus running in polynomial time for many combinatorial optimization problems. Setting Previous This paper Oﬄine smooth and strongly convex t−1 [13] e−O(t) Stochastic, smooth losses t−1/2 [12] t−1/2 Stochastic, non-smooth losses t−1/4 [12] t−1/”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, methodology): “olutions for CP problems with certain types of feasible sets X. However, the CndG method is invariant to the selection of k·k and thus self-adaptive to the geometry of the feasible region X (see also [28,29]). b) If f is a special nonsmooth function given by (1.6), we show that the CndG method can a”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, background): “Jaggi proves [15] that the rate of convergence of any method which only adds or removes one atom at a time must be at least sublinear in the first n iterations with n being the dimension of the space.”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, methodology): “Finally, note that for the `1-constrained case, matching pursuit (Tropp, 2004) greedily selects atoms in the same way as FW, although the updates are different (Jaggi, 2011).”
An Exponential Lower Bound on the Complexity of Regularization Paths (2009, background): “More recently, [18, 27, 19] have proposed to study approximate solution paths (with some continuous guarantee, e.”