Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA

Chun-Liang Li, Hsuan-Tien Lin, Chi-Jen Lu

Abstract

We study the problem of recovering the subspace spanned by the first $k$ principal components of $d$-dimensional data under the streaming setting, with a memory bound of $O(kd)$. Two families of algorithms are known for this problem. The first family is based on the framework of stochastic gradient descent. Nevertheless, the convergence rate of the family can be seriously affected by the learning rate of the descent steps and deserves more serious study. The second family is based on the power method over blocks of data, but setting the block size for its existing algorithms is not an easy task. In this paper, we analyze the convergence rate of a representative algorithm with decayed learning rate (Oja and Karhunen, 1985) in the first family for the general $k>1$ case. Moreover, we propose a novel algorithm for the second family that sets the block sizes automatically and dynamically with faster convergence rate. We then conduct empirical studies that fairly compare the two families on real-world data. The studies reveal the advantages and disadvantages of these two families.

Introduction

Principal Component Analysis (PCA) is a cornerstone of high-dimensional data analysis. However, in modern streaming scenarios where data arrives continuously and dimensions $d$ can exceed 100,000, traditional $O(d^2)$ memory requirements for storing covariance matrices are prohibitive. This paper investigates the performance of two algorithmic families restricted to $O(kd)$ memory: Stochastic Gradient Descent (SGD) based methods and Block-wise Power Methods.

Methodology

The research improves upon both competing families to provide a more robust streaming PCA framework:

1. Stochastic PCA (SPCA) with Decaying Learning Rate

While fixed-learning-rate algorithms like Alecton are common, they often reach an error floor and fail to converge further. The authors analyze a version of Oja’s rule using a decaying learning rate ($\gamma_n = c/n$), providing a rigorous convergence analysis for the general $k > 1$ case. This approach allows for continued refinement of the principal component estimates as more data is processed, avoiding the plateaus seen in fixed-rate methods.

2. Dynamic Block Power Method (DBPCA)

The primary innovation is DBPCA, which addresses the "block size" selection problem in standard block methods. DBPCA starts with small blocks to quickly obtain initial estimates and then exponentially increases the block size. This dynamic scaling allows the algorithm to tolerate high noise early on and achieve high precision later without manual tuning of block sizes.

Experimental Evaluation

Algorithms were evaluated on two massive text datasets: NYTimes ($d \approx 102,000$) and PubMed ($d \approx 141,000$). The primary metric was spectral error, defined as $\sin(U, Q_n)^2$, measuring the distance between the estimated subspace $Q_n$ and the true subspace $U$.

Key Results and Discussion

The empirical studies highlight a clear rivalry between the two families. DBPCA demonstrated superior convergence and stability in 6 out of 8 experimental scenarios.

Hyperparameter sensitivity for $k=4$ on the NYTimes dataset. DBPCA (d) maintains stable performance across different growth ratios ($r^2$), whereas SPCA (b) is highly sensitive to the choice of constant $c$.

As illustrated in Figure 1, DBPCA is significantly more robust to hyperparameter selection than SGD-based methods. While SPCA's error rates fluctuate wildly depending on the learning rate constant $c$, DBPCA's dynamic block sizing ensures consistent convergence.

Comparative performance on the PubMed dataset for $k=10$ (left) and $k=4$ (right). DBPCA (d) achieves faster and deeper convergence compared to BPCA (c) and SGD-based methods (a, b).

Figure 2 shows that on the PubMed dataset, DBPCA reaches near-zero spectral error much faster than competing methods. The study reveals a fundamental trade-off: SGD methods offer immediate updates after every data point, while block methods like DBPCA provide more stable, long-term convergence at the cost of less frequent updates as block sizes grow.

Conclusion

DBPCA offers a powerful alternative for memory-restricted streaming PCA, combining the stability of block methods with a dynamic scheduling approach that removes the need for manual block-size tuning. Future research will focus on hybrid models to bridge the gap between the high update frequency of SGD and the robust convergence of dynamic block methods.

Summary updated

Abstract

We study the problem of recovering the subspace spanned by the first $k$ principal components of $d$-dimensional data under the streaming setting, with a memory bound of $O(kd)$. Two families of algorithms are known for this problem. The first family is based on the framework of stochastic gradient descent. Nevertheless, the convergence rate of the family can be seriously affected by the learning rate of the descent steps and deserves more serious study. The second family is based on the power method over blocks of data, but setting the block size for its existing algorithms is not an easy task. In this paper, we analyze the convergence rate of a representative algorithm with decayed learning rate (Oja and Karhunen, 1985) in the first family for the general $k>1$ case. Moreover, we propose a novel algorithm for the second family that sets the block sizes automatically and dynamically with faster convergence rate. We then conduct empirical studies that fairly compare the two families on real-world data. The studies reveal the advantages and disadvantages of these two families.
BibTeX
@inproceedings{li2016rivalry,
  author = {Chun-Liang Li and Hsuan-Tien Lin and Chi-Jen Lu},
  title = {{Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=BpfZwvRAUx5},
}
Figure