Gradient Methods for Stochastic Optimization in Relative Scale

Yurii Nesterov () and Anton Rodomanov
Additional contact information
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium
Anton Rodomanov: ICTEAM

No 2024027, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We propose a new concept of a relatively inexact stochastic subgradient and present novel first-order methods that can use such objects to approximately solve convex optimization problems in relative scale. An important example where relatively inexact subgradients naturally arise is given by the Power or Lanczos algorithms for computing an approximate leading eigenvector of a symmetric positive semidefinite matrix. Using these algorithms as subroutines in our methods, we get new optimization schemes that can provably solve certain large-scale Semidefinite Programming problems with relative accuracy guarantees by using only matrix-vector products.

Keywords: Convex optimization; optimization in relative scale; gradient methods; randomization; convergence guarantees; eigenvalues; singular values; power method; Lanczos algorithm (search for similar items in EconPapers)
Pages: 34
Date: 2024-10-10
References: Add references at CitEc
Citations:

Downloads: (external link)
https://dial.uclouvain.be/pr/boreal/en/object/bore ... tastream/PDF_01/view (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:2024027

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().