Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Stochastic Frank-Wolfe for Composite Convex Minimization
LIONS, Ecole Polytechnique Fed´ erale de Lausanne, Switzerland.ORCID iD: 0000-0001-7320-1506
2019 (English)In: Advances in Neural Information Processing Systems 32 (NeurIPS 2019) / [ed] H. Wallach and H. Larochelle; A. Beygelzimer; F. d'Alché-Buc; E. Fox; R. Garnett, 2019Conference paper, Published paper (Refereed)
Abstract [en]

A broad class of convex optimization problems can be formulated as a semidefinite program (SDP), minimization of a convex function over the positive-semidefinite cone subject to some affine constraints. The majority of classical SDP solvers are designed for the deterministic setting where problem data is readily available. In this setting, generalized conditional gradient methods (aka Frank-Wolfe-type methods) provide scalable solutions by leveraging the so-called linear minimization oracle instead of the projection onto the semidefinite cone. Most problems in machine learning and modern engineering applications, however, contain some degree of stochasticity. In this work, we propose the first conditional-gradient-type method for solving stochastic optimization problems under affine constraints. Our method guarantees O(k-1/3) convergence rate in expectation on the objective residual and O(k-5/12) on the feasibility gap.

Place, publisher, year, edition, pages
2019.
Keywords [en]
frank-wolfe, conditional gradient method, convex optimization, first-order method, projection-free, stochastic optimization, composite optimization, semidefinite programming
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-190522OAI: oai:DiVA.org:umu-190522DiVA, id: diva2:1621059
Conference
NeurIPS 2019, Thirty-third Conference on Neural Information Processing Systems, Vancouver, December 8-14, 2019
Available from: 2021-12-17 Created: 2021-12-17 Last updated: 2024-07-02Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

URLPDFPDF, Supplemental

Authority records

Yurtsever, Alp

Search in DiVA

By author/editor
Yurtsever, Alp
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 228 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf