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

This paper rigorously shows how over-parameterization changes the convergencebehaviors of gradient descent (GD) for the matrix sensing problem, where thegoal is to recover an unknown low-rank ground-truth matrix from near-isotropiclinear measurements. First, we consider the symmetric setting with thesymmetric parameterization where $M^* \in \mathbb{R}^{n \times n}$ is apositive semi-definite unknown matrix of rank $r \ll n$, and one uses asymmetric parameterization $XX^\top$ to learn $M^*$. Here $X \in \mathbb{R}^{n\times k}$ with $k > r$ is the factor matrix. We give a novel $\Omega (1/T^2)$lower bound of randomly initialized GD for the over-parameterized case ($k >r$)where $T$ is the number of iterations. This is in stark contrast to theexact-parameterization scenario ($k=r$) where the convergence rate is $\exp(-\Omega (T))$. Next, we study asymmetric setting where $M^* \in\mathbb{R}^{n_1 \times n_2}$ is the unknown matrix of rank $r \ll\min\{n_1,n_2\}$, and one uses an asymmetric parameterization $FG^\top$ tolearn $M^*$ where $F \in \mathbb{R}^{n_1 \times k}$ and $G \in \mathbb{R}^{n_2\times k}$. Building on prior work, we give a global exact convergence resultof randomly initialized GD for the exact-parameterization case ($k=r$) with an$\exp (-\Omega(T))$ rate. Furthermore, we give the first global exactconvergence result for the over-parameterization case ($k>r$) with an$\exp(-\Omega(\alpha^2 T))$ rate where $\alpha$ is the initialization scale.This linear convergence result in the over-parameterization case is especiallysignificant because one can apply the asymmetric parameterization to thesymmetric setting to speed up from $\Omega (1/T^2)$ to linear convergence. Onthe other hand, we propose a novel method that only modifies one step of GD andobtains a convergence rate independent of $\alpha$, recovering the rate in theexact-parameterization case.

How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization