Research map / Learning theory and algorithms / Sample complexity
Low Precision Streaming PCA
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies Oja's streaming PCA under linear and logarithmic stochastic quantization, proving lower bounds on quantization error and showing a batched quantized Oja's variant nearly matches them, with near dimension-free error for logarithmic quantization.
Problem
Streaming estimation of the top principal component when the iterates and updates must be represented with a limited number of bits (low precision).
Approach
Uses unbiased stochastic rounding on the weight vector and the gradient updates inside Oja's algorithm, with a batched variant that accumulates quantization error only b times; a general noisy-Oja theorem bounds the error, and matching lower bounds are derived for linear and logarithmic grids.
Key results
- Batched NLQ matches full-precision batched Oja's error with about 6-8 bits, while standard LQ and NLQ need at least 10 bits (synthetic experiments, d=100, n=1000).
- Theory: linear-quantization error scales as d/4^beta while logarithmic quantization error scales as (beta^2 + log^2 d)/4^beta for the batched algorithm.
- Standard (unbatched) quantized Oja's error grows linearly with n under both schemes, whereas batching removes this dependence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use batched updates instead of standard single-sample updates (ablation) | Oja's algorithm with linear quantization · Synthetic streaming PCA | sin²-error | Helped |
| Use batched updates instead of standard single-sample updates (ablation) | Oja's algorithm with logarithmic quantization · Synthetic streaming PCA | sin²-error | Helped |
| Use logarithmic quantization instead of linear quantization (ablation) | Batched Oja's algorithm · Synthetic streaming PCA, varying dimension | sin²-error | Helped |
| Use logarithmic quantization instead of linear quantization (ablation) | Standard Oja's algorithm · Synthetic streaming PCA, varying dimension | sin²-error | Helped |
| Use standard updates with linear quantization instead of batching (ablation) | Oja's algorithm · Synthetic streaming PCA, varying sample size | sin²-error | Hurt |
| Use standard updates with logarithmic quantization instead of batching (ablation) | Oja's algorithm · Synthetic streaming PCA, varying sample size | sin²-error | Hurt |
| Increase the quantization bit budget from 4 to 12 (ablation) | Linear and logarithmic quantized Oja's algorithm · Synthetic streaming PCA, varying bits | sin²-error: 4 to 12 | Helped |
| Use batched quantization rather than standard quantization (ablation) | Quantized Oja's algorithm · Synthetic streaming PCA, varying bits | bits needed for comparable full-precision performance: 6–8 bits; at least 10 bits | Helped |
| Use 16-bit half precision instead of 64-bit double precision | Oja's algorithm · Runtime benchmark | runtime (s): 0.0274 \pm 0.00136 -> 0.000398 \pm 0.0000235 | Helped |
Surprising findings
- Unbatched quantized Oja's error grows linearly with sample size n under both quantization schemes.
Limitations
- Estimates only the top principal component; extension to top-k needs deflation.
- Analysis assumes bounded data and bounded iterate norms; sub-Gaussian extension only mentioned.
Experimental setup
Datasets: synthetic Gaussian data with covariance eigenvalues i^-2
Benchmarks: synthetic Gaussian streams
Metrics: sin^2 error runtime
Baselines: standard Oja's algorithm (full precision) standard_LQ standard_NLQ
Builds on: Oja's algorithm stochastic rounding matrix product concentration (Jain et al. style streaming PCA analysis)
Closest papers by meaning
- Robust Streaming PCA (NeurIPS 2022 · similarity 0.91)
- Streaming PCA for Markovian Data (NeurIPS 2023 · similarity 0.90)
- Streaming Principal Component Analysis in Noisy Setting (ICML 2018 · similarity 0.89)
- Oja's Algorithm for Streaming Sparse PCA (NeurIPS 2024 · similarity 0.89)
- Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA (ICML 2023 · similarity 0.88)
- Approximating the Top Eigenvector in Random Order Streams (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.