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 propose $\textsf{ScaledGD($\lambda$)}$, a preconditioned gradient descentmethod to tackle the low-rank matrix sensing problem when the true rank isunknown, and when the matrix is possibly ill-conditioned. Usingoverparametrized factor representations, $\textsf{ScaledGD($\lambda$)}$ startsfrom a small random initialization, and proceeds by gradient descent with aspecific form of damped preconditioning to combat bad curvatures induced byoverparameterization and ill-conditioning. At the expense of lightcomputational overhead incurred by preconditioners,$\textsf{ScaledGD($\lambda$)}$ is remarkably robust to ill-conditioningcompared to vanilla gradient descent ($\textsf{GD}$) even withoverprameterization. Specifically, we show that, under the Gaussian design,$\textsf{ScaledGD($\lambda$)}$ converges to the true low-rank matrix at aconstant linear rate after a small number of iterations that scales onlylogarithmically with respect to the condition number and the problem dimension.This significantly improves over the convergence rate of vanilla $\textsf{GD}$which suffers from a polynomial dependency on the condition number. Our workprovides evidence on the power of preconditioning in accelerating theconvergence without hurting generalization in overparameterized learning.

The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing