Scholarlink

<p>Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in developing efficient methods for <i>smooth</i> problems that avoid computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced.</p><p>In this paper we consider a standard convex relaxation: minimizing a convex nonsmooth objective function over the spectrahedron (set of real positive-semidefinite matrices with unit trace), under a plausible strict complementarity (SC) condition. Following an observation that, even arbitrarily close to a low-rank optimal solution which satisfies SC, the standard projected subgradient descent method may fail to produce low-rank iterates, we focus on nonsmooth objectives that can be written as a maximum of smooth functions and consider the corresponding saddle-point formulation. Mainly, we prove that (approximated) variants of two popular <i>mirror-prox</i> methods: the Euclidean extragradient method and mirror-prox with matrix exponentiated gradient updates, when initialized with a “warm-start”, converge to an optimal solution with the standard <i>O</i>(1/<i>t</i>) ergodic rate, while requiring only two <i>low-rank</i> SVDs per iteration. For the Euclidean method we also consider relaxed versions of SC which yield a trade-off between the rank of SVDs and the radius of the ball in which we need to initialize. We support our theoretical findings with empirical experiments on several tasks, demonstrating both the plausibility of the SC assumption, and the efficient convergence of our proposed mirror-prox variants.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Low-rank mirror-prox methods for nonsmooth and low-rank matrix optimization problems

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年9月4日

查看全文
  • Dan Garber,
  • Atara Kaplan

摘要

Low-rank and nonsmooth matrix optimization problems capture many fundamental tasks in statistics and machine learning. While significant progress has been made in developing efficient methods for smooth problems that avoid computing expensive high-rank SVDs, advances for nonsmooth problems have been slow paced.

In this paper we consider a standard convex relaxation: minimizing a convex nonsmooth objective function over the spectrahedron (set of real positive-semidefinite matrices with unit trace), under a plausible strict complementarity (SC) condition. Following an observation that, even arbitrarily close to a low-rank optimal solution which satisfies SC, the standard projected subgradient descent method may fail to produce low-rank iterates, we focus on nonsmooth objectives that can be written as a maximum of smooth functions and consider the corresponding saddle-point formulation. Mainly, we prove that (approximated) variants of two popular mirror-prox methods: the Euclidean extragradient method and mirror-prox with matrix exponentiated gradient updates, when initialized with a “warm-start”, converge to an optimal solution with the standard O(1/t) ergodic rate, while requiring only two low-rank SVDs per iteration. For the Euclidean method we also consider relaxed versions of SC which yield a trade-off between the rank of SVDs and the radius of the ball in which we need to initialize. We support our theoretical findings with empirical experiments on several tasks, demonstrating both the plausibility of the SC assumption, and the efficient convergence of our proposed mirror-prox variants.