Generalized conditional gradient for sparse estimation
From MaRDI portal
Publication:4637076
Abstract: Structured sparsity is an important modeling tool that expands the applicability of convex formulations for data analysis, however it also creates significant challenges for efficient algorithm design. In this paper we investigate the generalized conditional gradient (GCG) algorithm for solving structured sparse optimization problems---demonstrating that, with some enhancements, it can provide a more efficient alternative to current state of the art approaches. After providing a comprehensive overview of the convergence properties of GCG, we develop efficient methods for evaluating polar operators, a subroutine that is required in each GCG iteration. In particular, we show how the polar operator can be efficiently evaluated in two important scenarios: dictionary learning and structured sparse estimation. A further improvement is achieved by interleaving GCG with fixed-rank local subspace optimization. A series of experiments on matrix completion, multi-class classification, multi-view dictionary learning and overlapping group lasso shows that the proposed method can significantly reduce the training cost of current alternatives.
Recommendations
- Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint
- Greedy sparsity-constrained optimization
- The alternating descent conditional gradient method for sparse inverse problems
- Screening for a reweighted penalized conditional gradient method
- Improved complexities of conditional gradient-type methods with applications to robust matrix recovery problems
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A generalized proximal point algorithm for certain non-convex minimization problems
- A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
- A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm
- Accelerated Frank–Wolfe Algorithms
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- An extension of the frank and Wolfe method of feasible directions
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient algorithms with open loop step size rules
- Convex functions. Constructions, characterizations and counterexamples
- Convex multi-task feature learning
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
- Duality between subgradient and conditional gradient methods
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Exact matrix completion via convex optimization
- Generalized conditional gradient for sparse estimation
- Gradient methods for minimizing composite functions
- scientific article; zbMATH DE number 3526459 (Why is no real title available?)
- Iterated Hard Shrinkage for Minimization Problems with Sparsity Constraints
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Local minima and convergence in low-rank semidefinite programming
- Low-rank optimization with trace norm penalty
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Model Selection and Estimation in Regression with Grouped Variables
- NESTA: A fast and accurate first-order method for sparse recovery
- New analysis and results for the Frank-Wolfe method
- On the complexity of nonnegative matrix factorization
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
- Regularizers for structured sparsity
- Smooth minimization of non-smooth functions
- Some comments on Wolfe's ‘away step’
- Sparse Approximate Solutions to Semidefinite Programs
- Sparse modeling for image and vision processing
- Statistics for high-dimensional data. Methods, theory and applications.
- Structured sparsity through convex optimization
- Sublinear time algorithms for approximate semidefinite programming
- The convex geometry of linear inverse problems
- Trace norm regularization: reformulations, algorithms, and multi-task learning
- Trading accuracy for sparsity in optimization problems with sparsity constraints
- Variational Analysis
Cited in
(16)- Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis
- Complexity bounds for primal-dual methods minimizing the model of objective function
- Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
- Screening for a reweighted penalized conditional gradient method
- Adaptive conditional gradient method
- Generalized conditional gradient for sparse estimation
- scientific article; zbMATH DE number 6866335 (Why is no real title available?)
- Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint
- Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods
- The alternating descent conditional gradient method for sparse inverse problems
- Affine Invariant Convergence Rates of the Conditional Gradient Method
- A unified analysis of stochastic gradient‐free Frank–Wolfe methods
- Asymptotic linear convergence of fully-corrective generalized conditional gradient methods
- Riemannian conditional gradient methods for composite optimization problems
- Extremal points and sparse optimization for generalized Kantorovich-Rubinstein norms
- A general theory for exact sparse representation recovery in convex optimization
This page was built for publication: Generalized conditional gradient for sparse estimation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4637076)
