On the Optimality of the Oja's Algorithm for Online PCA

• URL: http://arxiv.org/abs/2104.00512v1
• Date: Wed, 31 Mar 2021 15:02:54 GMT
• Title: On the Optimality of the Oja's Algorithm for Online PCA
• Authors: Xin Liang
• Abstract summary: It is proved that with high probability it performs an efficient, gap-free, global convergence rate to approximate an principal component subspace for any sub-Gaussian distribution. It is the first time to show that the convergence rate, namely the upper bound of the approximation, exactly matches the lower bound of an approximation obtained by the offline/classical PCA up to a constant factor.
• Score: 1.3934770330948278
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we analyze the behavior of the Oja's algorithm for online/streaming principal component subspace estimation. It is proved that with high probability it performs an efficient, gap-free, global convergence rate to approximate an principal component subspace for any sub-Gaussian distribution. Moreover, it is the first time to show that the convergence rate, namely the upper bound of the approximation, exactly matches the lower bound of an approximation obtained by the offline/classical PCA up to a constant factor.

Related papers

• The role of gaps in digitized counterdiabatic QAOA for fully-connected spin models [0.0]
  CD corrections to the quantum approximate optimization algorithm (QAOA) have been proposed, yielding faster convergence within the desired accuracy than standard QAOA. We show that the performances of the algorithm are related to the spectral properties of the instances analyzed.
  arXiv  Detail & Related papers  (2024-09-05T13:17:56Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  We study differentially private (DP) optimization problems under sparsity of individual gradients. Building on this, we obtain pure- and approximate-DP algorithms with almost optimal rates for convex optimization with sparse gradients.
  arXiv  Detail & Related papers  (2024-04-16T20:01:10Z)
• On Linear Convergence of PI Consensus Algorithm under the Restricted Secant Inequality [5.35599092568615]
  This paper considers solving distributed optimization problems in peer-to-peer multi-agent networks. By using the proportional-integral (PI) control strategy, various algorithms with fixed stepsize have been developed.
  arXiv  Detail & Related papers  (2023-09-30T15:54:52Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Orthogonal Polynomials Approximation Algorithm (OPAA):a functional analytic approach to estimating probability densities [0.0]
  We present the new Orthogonal Polynomials Approximation Algorithm (OPAA) OPAA estimates probability distributions using functional analytic approach. It can be applied to estimating the normalizing weight of the posterior.
  arXiv  Detail & Related papers  (2022-11-16T00:51:00Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Gradient Descent Averaging and Primal-dual Averaging for Strongly Convex Optimization [15.731908248435348]
  We develop gradient descent averaging and primal-dual averaging algorithms for strongly convex cases. We prove that primal-dual averaging yields the optimal convergence rate in terms of output averaging, while SC-PDA derives the optimal individual convergence. Several experiments on SVMs and deep learning models validate the correctness of theoretical analysis and effectiveness of algorithms.
  arXiv  Detail & Related papers  (2020-12-29T01:40:30Z)
• Distributed Variational Bayesian Algorithms Over Sensor Networks [6.572330981878818]
  We propose two novel distributed VB algorithms for general Bayesian inference problem. The proposed algorithms have excellent performance, which are almost as good as the corresponding centralized VB algorithm relying on all data available in a fusion center.
  arXiv  Detail & Related papers  (2020-11-27T08:12:18Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions. We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
  arXiv  Detail & Related papers  (2020-10-23T09:12:47Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  We introduce a framework for designing primal methods under the decentralized optimization setting where local functions are smooth and strongly convex. Our approach consists of approximately solving a sequence of sub-problems induced by the accelerated augmented Lagrangian method. When coupled with accelerated gradient descent, our framework yields a novel primal algorithm whose convergence rate is optimal and matched by recently derived lower bounds.
  arXiv  Detail & Related papers  (2020-06-11T18:49:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.