Gradient Methods for Stochastic Optimization in Relative Scale

Nesterov, Yurii;Rodomanov, Anton
(2024) , 34 pages

Files

CORE_DP_2024-27.pdf
  • Open Access
  • Adobe PDF
  • 959.48 KB
Download

Details

Authors
  • Nesterov, YuriiUCLouvain
    Author
  • Rodomanov, AntonUCLouvain
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Nesterov, Y., & Rodomanov, A. (2024). Gradient Methods for Stochastic Optimization in Relative Scale (LIDAM Discussion Paper CORE 2024/27). https://hdl.handle.net/2078.5/233885