English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We revisit the use of Stochastic Gradient Descent (SGD) for solving convexoptimization problems that serve as highly popular convex relaxations for manyimportant low-rank matrix recovery problems such as \textit{matrix completion},\textit{phase retrieval}, and more. The computational limitation of applyingSGD to solving these relaxations in large-scale is the need to compute apotentially high-rank singular value decomposition (SVD) on each iteration inorder to enforce the low-rank-promoting constraint. We begin by considering asimple and natural sufficient condition so that these relaxations indeed admitlow-rank solutions. This condition is also necessary for a certain notion oflow-rank-robustness to hold. Our main result shows that under this conditionwhich involves the eigenvalues of the gradient vector at optimal points, SGDwith mini-batches, when initialized with a "warm-start" point, producesiterates that are low-rank with high probability, and hence only a low-rank SVDcomputation is required on each iteration. This suggests that SGD may indeed bepractically applicable to solving large-scale convex relaxations of low-rankmatrix recovery problems. Our theoretical results are accompanied withsupporting preliminary empirical evidence. As a side benefit, our analysis isquite simple and short.

On the Convergence of Stochastic Gradient Descent with Low-Rank Projections for Convex Low-Rank Matrix Problems