Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
From MaRDI portal
(Redirected from Publication:2020608)
Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute'' gradient for structured convex optimization
Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute'' gradient for structured convex optimization
Abstract: The stochastic Frank-Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a more general feasible region. However, there has been a complexity gap in the guaranteed convergence rate for stochastic Frank-Wolfe compared to its deterministic counterpart. In this work, we present a new generalized stochastic Frank-Wolfe method which closes this gap for the class of structured optimization problems encountered in statistical and machine learning characterized by empirical loss minimization with a certain type of ``linear prediction property (formally defined in the paper), which is typically present loss minimization problems in practice. Our method also introduces the notion of a ``substitute gradient that is a not-necessarily-unbiased sample of the gradient. We show that our new method is equivalent to a particular randomized coordinate mirror descent algorithm applied to the dual problem, which in turn provides a new interpretation of randomized dual coordinate descent in the primal space. Also, in the special case of a strongly convex regularizer our generalized stochastic Frank-Wolfe method (as well as the randomized dual coordinate descent method) exhibits linear convergence. Furthermore, we present computational experiments that indicate that our method outperforms other stochastic Frank-Wolfe methods consistent with the theory developed herein.
Recommendations
- Frank-Wolfe style algorithms for large scale optimization
- Generalized self-concordant analysis of Frank-Wolfe algorithms
- New analysis and results for the Frank-Wolfe method
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
Cites work
- scientific article; zbMATH DE number 1807400 (Why is no real title available?)
- scientific article; zbMATH DE number 3562783 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 6253954 (Why is no real title available?)
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- An accelerated randomized proximal coordinate gradient method and its application to regularized empirical risk minimization
- An extended Frank-Wolfe method with ``in-face directions, and its application to low-rank matrix completion
- CUR matrix decompositions for improved data analysis
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Conditional gradient sliding for convex optimization
- Duality between subgradient and conditional gradient methods
- Efficiency of coordinate descent methods on huge-scale optimization problems
- Exact matrix completion via convex optimization
- Forward-backward splitting with Bregman distances
- Generalized conditional gradient for sparse estimation
- High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
- Incremental majorization-minimization optimization with application to large-scale machine learning
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- Katyusha: the first direct acceleration of stochastic gradient methods
- Minimizing finite sums with the stochastic average gradient
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- New analysis and results for the Frank-Wolfe method
- On the complexity analysis of randomized block-coordinate descent methods
- Online submodular minimization
- Regularization techniques for learning with matrices
- Relatively smooth convex optimization by first-order methods, and applications
- Ridge Regression: Biased Estimation for Nonorthogonal Problems
- Stochastic conditional gradient methods: from convex minimization to submodular maximization
- Stochastic dual coordinate ascent methods for regularized loss minimization
- Stochastic primal-dual coordinate method for regularized empirical risk minimization
- Subgradient methods for huge-scale optimization problems
Cited in
(11)- No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
- Inexact and stochastic generalized conditional gradient with augmented Lagrangian and proximal step
- Using Taylor-approximated gradients to improve the Frank-Wolfe method for empirical risk minimization
- Analysis of the Frank-Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier
- Frank-Wolfe style algorithms for large scale optimization
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- A generalized Frank-Wolfe method with ``dual averaging for strongly convex composite optimization
- Fast and scalable Lasso via stochastic Frank-Wolfe methods with a convergence guarantee
- Sequential quadratic optimization for nonlinear equality constrained stochastic optimization
- FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients
- A sequential quadratic programming method with high-probability complexity bounds for nonlinear equality-constrained stochastic optimization
This page was built for publication: Generalized stochastic Frank-Wolfe algorithm with stochastic ``substitute gradient for structured convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020608)
