On the Optimal Tradeoff Between Computational Efficiency and Generalizability of Oja’s Algorithm

Abstract

The Oja's algorithm is widely applied for computing principal eigenvectors in real problems, and it is practically useful to understand the theoretical relationships between the learning rate, convergence rate, and generalization error of this algorithm for noisy samples. In this paper, we show that under mild assumptions of sampling noise, both the generalization error and the convergence rate reveal linear relationships with the learning rate in the large sample size and small learning rate regime. In addition, when the algorithm nearly converges, we provide a refined characterization of the generalization error, which suggests the optimal design for the learning rate for data with noise. Moreover, we investigate the minibatch variation of Oja's algorithm and demonstrate that the learning rate of minibatch training is decayed by a factor characterized by the batch size, which provides theoretical insights and guidance for designing the learning rate in minibatch training algorithms. Finally, our theoretical results are validated by experiments on both synthesized data and the MNIST dataset.

Keywords

• Computational efficiency
• generalizability
• learning rate
• minibatch training
• Oja’s algorithm
• principal component analysis