A Comprehensively Tight Analysis of Gradient Descent for PCA
Dec 6, 2021
Speakers
Zhiqiang Xu
Speaker · 0 followers
About
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(1/Δlog1/ϵ) that holds for any real symmetric matrix. More importantly, when the gap Δ is significantly smaller than the target accuracy ϵ 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(1/ϵlog1/ϵ). The two analyses naturally roll out a comprehensively tight convergence rate at O(1/max{Δ,ϵ}-.3emlog1/ϵ). 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.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(1/Δlog1/ϵ) that holds for any real symmetric matrix. More importantly, when the gap Δ is significantly smaller than the target accuracy ϵ on the objective sub-optimality of the final…
Organizer
NeurIPS 2021
Account · 1.9k followers
About NeurIPS 2021
Neural Information Processing Systems (NeurIPS) is a multi-track machine learning and computational neuroscience conference that includes invited talks, demonstrations, symposia and oral and poster presentations of refereed papers. Following the conference, there are workshops which provide a less formal setting.
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Stateful ODE-Nets using Basis Function Expansions
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Using Random Effects to Account for High-Cardinality Categorical Features and Repeated Measures in Deep Neural Networks
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Regulating algorithmic filtering on social media
Watch later
Sarah H. Cen, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Online Learning via Linear Programming
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Text Ranking and Classification using Data Compression
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Online false discovery rate control for anomaly detection in time series
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%