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

The matrix completion problem seeks to recover a $d\times d$ ground truthmatrix of low rank $r\ll d$ from observations of its individual elements.Real-world matrix completion is often a huge-scale optimization problem, with$d$ so large that even the simplest full-dimension vector operations with$O(d)$ time complexity become prohibitively expensive. Stochastic gradientdescent (SGD) is one of the few algorithms capable of solving matrix completionon a huge scale, and can also naturally handle streaming data over an evolvingground truth. Unfortunately, SGD experiences a dramatic slow-down when theunderlying ground truth is ill-conditioned; it requires at least$O(\kappa\log(1/\epsilon))$ iterations to get $\epsilon$-close to ground truthmatrix with condition number $\kappa$. In this paper, we propose apreconditioned version of SGD that preserves all the favorable practicalqualities of SGD for huge-scale online optimization while also making itagnostic to $\kappa$. For a symmetric ground truth and the Root Mean SquareError (RMSE) loss, we prove that the preconditioned SGD converges to$\epsilon$-accuracy in $O(\log(1/\epsilon))$ iterations, with a rapid linearconvergence rate as if the ground truth were perfectly conditioned with$\kappa=1$. In our experiments, we observe a similar acceleration for item-itemcollaborative filtering on the MovieLens25M dataset via a pair-wise rankingloss, with 100 million training pairs and 10 million testing pairs. [Seesupporting code at https://github.com/Hong-Ming/ScaledSGD.]

Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion