Timezone: »

Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing
Jikai Jin · Zhiyuan Li · Kaifeng Lyu · Simon Du · Jason Lee

Tue Jul 25 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #332

It is believed that Gradient Descent (GD) induces an implicit bias towards good generalization in training machine learning models. This paper provides a fine-grained analysis of the dynamics of GD for the matrix sensing problem, whose goal is to recover a low-rank ground-truth matrix from near-isotropic linear measurements. It is shown that GD with small initialization behaves similarly to the greedy low-rank learning heuristics and follows an incremental learning procedure: GD sequentially learns solutions with increasing ranks until it recovers the ground truth matrix. Compared to existing works which only analyze the first learning phase for rank-1 solutions, our result provides characterizations for the whole learning process. Moreover, besides the over-parameterized regime that many prior works focused on, our analysis of the incremental learning procedure also applies to the under-parameterized regime. Finally, we conduct numerical experiments to confirm our theoretical findings.

Author Information

Jikai Jin (Peking University)
Zhiyuan Li (Computer Science Department, Stanford University)
Kaifeng Lyu (Princeton University)
Simon Du (University of Washington)
Jason Lee (Princeton University)

More from the Same Authors