Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees

By Francesco Locatello, Michael Tschannen, Gunnar Rätsch, Martin Jaggi. 2017

29 citations recorded by the source corpus.

Greedy optimization methods such as Matching Pursuit (MP) and Frank-Wolfe (FW) algorithms regained popularity in recent years due to their simplicity, effectiveness and theoretical guarantees. MP and FW address optimization over the linear span and the convex hull of a set of atoms, respectively. In this paper, we consider the intermediate case of optimization over the convex cone, parametrized as the conic hull of a generic atom set, leading to the first principled definitions of non-negative MP algorithms for which we give explicit convergence rates and demonstrate excellent empirical performance. In particular, we derive sublinear ($\mathcal{O}(1/t)$) convergence on general smooth and convex objectives, and linear convergence ($\mathcal{O}(e^{-t})$) on strongly convex objectives, in both cases for general sets of atoms. Furthermore, we establish a clear correspondence of our algorithms to known algorithms from the MP and FW literature. Our novel algorithms and analyses target general atom sets and general objective functions, and hence are directly applicable to a large variety of learning settings.

Subfields: Artificial Intelligence, Computational Mechanics

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

Citations in the corpus

Coresets via Bilevel Optimization for Continual Learning and Streaming (2020, methodology): “Following [38], the convergence of the algorithm depends on properties of the atom set A, which we do not review here in full.”
Boosting Frank-Wolfe by Chasing Gradients (2020, methodology): “In fact, it implicitly addresses the cone constrained quadratic optimization subproblem min d∈cone(V−xt) 1 2 ‖ − ∇f(xt)− d‖2 (2) via the Non-Negative Matching Pursuit algorithm (NNMP) (Locatello et al., 2017), without however the aim of solving it.”
Bayesian Coreset Construction via Greedy Iterative Geodesic Ascent (2018, unknown): “…et al., 1989; Tropp, 2004), Frank–Wolfe and its variants (Frank & Wolfe, 1956; Guélat & Marcotte, 1986; Jaggi, 2013; Lacoste-Julien & Jaggi, 2015; Locatello et al., 2017), Hilbert space vector approximation methods (Barron et al., 2008), kernel herding (Chen et al., 2010), and AdaBoost…”
Sparse Variational Inference: Bayesian Coresets from Scratch (2019, methodology): “which can be solved with sparse optimization techniques [31, 32, 34–36, 45, 46, 48, 58–60].”