Timezone: »
Poster
A Comprehensively Tight Analysis of Gradient Descent for PCA
Zhiqiang Xu · Ping Li
We study the Riemannian gradient method for PCA on which a crucial fact is that despite the simplicity of the considered setting, i.e., deterministic version of Krasulina's method, the convergence rate has not been well-understood yet. In this work, we provide a general tight analysis for the gap-dependent rate at $O(\frac{1}{\Delta}\log\frac{1}{\epsilon})$ that holds for any real symmetric matrix. More importantly, when the gap $\Delta$ is significantly smaller than the target accuracy $\epsilon$ on the objective sub-optimality of the final solution, the rate of this type is actually not tight any more, which calls for a worst-case rate. We further give the first worst-case analysis that achieves a rate of convergence at $O(\frac{1}{\epsilon}\log\frac{1}{\epsilon})$. The two analyses naturally roll out a comprehensively tight convergence rate at $O(\frac{1}{\max\{\Delta,\epsilon\}}\hskip-.3em\log\frac{1}{\epsilon})$. Particularly, our gap-dependent analysis suggests a new promising learning rate for stochastic variance reduced PCA algorithms. Experiments are conducted to confirm our findings as well.
Author Information
Zhiqiang Xu (Baidu Inc.)
Ping Li (Baidu Research USA)
More from the Same Authors
-
2021 Poster: Backdoor Attack with Imperceptible Input and Latent Modification »
Khoa Doan · Yingjie Lao · Ping Li -
2021 Poster: A Note on Sparse Generalized Eigenvalue Problem »
Yunfeng Cai · Guanhua Fang · Ping Li -
2021 Poster: Mitigating Forgetting in Online Continual Learning with Neuron Calibration »
Haiyan Yin · peng yang · Ping Li -
2021 Poster: Rate-Optimal Subspace Estimation on Random Graphs »
Zhixin Zhou · Fan Zhou · Ping Li · Cun-Hui Zhang -
2021 Poster: Learning Generative Vision Transformer with Energy-Based Latent Space for Saliency Prediction »
Jing Zhang · Jianwen Xie · Nick Barnes · Ping Li -
2020 Poster: Towards Better Generalization of Adaptive Gradient Methods »
Yingxue Zhou · Belhal Karimi · Jinxing Yu · Zhiqiang Xu · Ping Li -
2019 Poster: Towards Practical Alternating Least-Squares for CCA »
Zhiqiang Xu · Ping Li -
2018 Poster: Gradient Descent Meets Shift-and-Invert Preconditioning for Eigenvector Computation »
Zhiqiang Xu