Low-Precision Streaming PCA

Sanjoy Dasgupta, Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar · 2025

Read Low-Precision Streaming PCA by Sanjoy Dasgupta, Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22440.txt.

Introduction

Sanjoy Dasgupta and three co-authors study principal component analysis when data arrive as a stream and numbers must be stored at low precision. The task is to track the top direction of variation while rounding values coarsely. They first prove a lower bound on how fine the rounding must be to reach a chosen accuracy for that leading direction.

They then study a classic streaming method under two rounding schemes, using random rounding that stays unbiased. A batched version meets the lower bound apart from small logarithmic factors. Tests on synthetic streams confirm the theory, with low precision runs tracking the standard method closely.

Catalog record

CREATORSanjoy Dasgupta, Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE97 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22440

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Low-Precision Streaming PCA Sanjoy Dasgupta, Syamantak Kumar, Shourya Pandey, Purnamrita Sarkar Abstract Low-precision Streaming PCA estimates the top principal component in a streaming setting under limited precision. We establish an information-theoretic lower bound on the quantization resolution required to achieve a target accuracy for the leading eigenvector. We study Oja’s algorithm for streaming PCA under linear and nonlinear stochastic quantization. The quantized variants use unbiased stochastic quantization of the weight vector and the updates. Under mild moment and spectral-gap assumptions on the data distribution, we show that a batched version achieves the lower bound up to logarithmic factors under both schemes. This leads to a nearly dimension-free quantization error in the nonlinear quantization setting. Empirical evaluations on synthetic streams validate our theoretical findings and demonstrate that our low-precision methods closely track the performance of standard Oja’s algorithm. 1 Introduction Quantization (or discretization) is the mapping of a continuous set of values to a small, finite set of outputs close to the original values; standard methods for quantization include rounding and truncation. The current popularity of training large-scale Machine Learning models has brought a renewed focus on quantization, though its origins go back to the 1800s. Some early examples include least-squares methods applied to large-scale data analysis in the early nineteenth century Sti 86 . In 1867, discretization was introduced for the approximate calculation of integrals Rie 67 , and the effects of rounding errors in integration were examined in 1897 She 97 . For an excellent survey and history of quantization, see GKD+ 22 . In the context of efficient model training, it is natural to ask the following: does training a model require the full precision of 32- or 64-bit representation, or is it possible to achieve comparable performance using significantly fewer bits? Mixed-precision training (using 16 -bit floats with 32 -bit accumulators) is now standard on GPUs and TPUs, yielding 1.5\times to 3\times speedups with negligible accuracy loss on large transformers and CNNs MNA+ 18 . Binary Neural Networks (BNNs), which constrain weights and activations to \pm 1 , can achieve up to 32\times memory compression and replace multiplications with bitwise operations. This has been shown to approach nearly full-precision ImageNet accuracy with careful training HCS+ 16 . Theoretical analysis of the effect of low-precision computation on optimization problems has received significant attention LD 19 ; AGL+ 17 ; SZOR 15 ; SLZ+ 18 ; LDX+ 17 ; ZLK+ 17 . Complementary strategies leverage stochastic rounding to mitigate quantization bias during LLM training. Ozkara et al. OYP 25 present theoretical analyses of implicit regularization and convergence properties of Adam when using BF16 with stochastic rounding, demonstrating up to 1.5\times throughput gains and 30% memory reduction over standard mixed precision OYP 25 . Consider the set of values that can be exactly represented in the quantization scheme, which we call the quantization grid . For example, fixed-point arithmetic Yat 09 uses linear quantization (LQ), where the quantization grid consists of points spaced uniformly at a distance \delta (also denoted by quanta ). LDX+ 17 analyze Stochastic Gradient Descent (SGD)-based optimization algorithms for LQ, and SYK 21 perform Learned Image Compression (LIC) under 8 -bit fixed-point arithmetic. Nonlinear quantization (NLQ) grids with logarithmic spacing are also widely used KWW+ 17 ; NTSW+ 22 ; XLY+ 24 ; YIY 21 ; ZMK 22 ; ZWG+ 23 in low-precision training. To illustrate the importance of the quantization scheme, consider the example of rounding, where each input is mapped to the value in the quantization grid closest to it. The following toy iterative optimization algorithm demonstrates that rounding can cause the solution to remain stuck at the initial vector. Consider the update scheme \mathbf{w}_{t}=\mathbf{w}_{t-1}+\eta\mathbf{g}_{t} , followed by rounding each coordinate of \mathbf{w}_{t} . Here \eta is the learning rate and \mathbf{g}_{t} is the gradient evaluated at time t . Suppose \max_{i}\|\mathbf{g}_{t}(i)\|\leq 1 . Assume that \mathbf{w}_{0} is quantized using the LQ scheme and that \eta<\delta/2 . For any coordinate i , we have \left|\mathbf{w}_{1}(i)-\mathbf{w}_{0}(i)\right|=\eta\cdot\left|\mathbf{g}_{t}(i)\right|\leq\eta . Since \eta<\delta/2 , after rounding, \mathbf{w}_{1}(i) is mapped back to the original quantized value \mathbf{w}_{0}(i) , i.e., \mathbf{w}_{1}=\mathbf{w}_{0} . As a result, the algorithm fails to make progress. We address this issue by using stochastic rounding . In this approach, each value is randomly mapped to one of the closest two quanta with the probabilities chosen such that the quantized value is unbiased. Principal Component Analysis. PCA Pea 01 ; Zie 03 is a dimension-reduction technique that extracts the directions of largest variance from the data. Suppose we observe n independent samples \mathbf{X}_{i}\in\mathbb{R}^{d} from a zero-mean distribution with covariance \mathbf{\Sigma} . PCA seeks a unit vector \mathbf{v}_{1} that maximizes variance, which is any eigenvector of \mathbf{\Sigma} associated with its largest eigenvalue \lambda_{1} . Under mild tail conditions on the \mathbf{X}_{i} , the top eigenvector \hat{\mathbf{v}} of the sample covariance \frac{1}{n}\sum_{i=1}^{n}\mathbf{X}_{i}\mathbf{X}_{i}^{\top} is a nearly rate-optimal estimator of the true principal direction \mathbf{v}_{1} Wed 72 ; JJK+ 16 ; Ver 10 . Despite its statistical appeal, constructing the covariance matrix itself takes \Omega(nd^{2}) time and \Omega(d^{2}) space, which is prohibitive for large d and n . A popular remedy is Oja’s algorithm Oja 82 , a single-pass streaming algorithm inspired by Hebbian learning Heb 49 . Starting from a (random) unit vector \mathbf{u}_{0} , for each incoming datum \mathbf{X}_{i} the algorithm performs the update \displaystyle\mathbf{u}_{i}\leftarrow\mathbf{u}_{i-1}+\eta\,\mathbf{X}_{i}\bigl(\mathbf{X}_{i}^{\top}\mathbf{u}_{i-1}\bigr),\qquad\mathbf{u}_{i}\leftarrow\mathbf{u}_{i}/\|\mathbf{u}_{i}\|. (1) Here, \eta>0 is the learning rate which may vary across iterations. The batched version of Oja’s method partitions the data into b batches B_{1},\dots B_{b} of size n/b each and replaces the above update with the averages of the gradients within a batch: \displaystyle\mathbf{u}_{i}\leftarrow\mathbf{u}_{i-1}+\eta\frac{\sum_{j\in B_{i}}\,\mathbf{X}_{j}\bigl(\mathbf{X}_{j}^{\top}\mathbf{u}_{i-1}\bigr)}{n/b},\qquad\mathbf{u}_{i}\leftarrow\mathbf{u}_{i}/\|\mathbf{u}_{i}\|. (2) The entire procedure completes in O(nd) time and uses O(d) space. The scalability and simplicity of Oja’s algorithm have motivated extensive analysis across statistics, optimization, and theoretical computer science ( JJK+ 16 ; AZL 17 ; CYWZ 18 ; YHW 18 ; HW 19 ; MP 22 ; Mon 22 ; KS24b ; KS24a ; JKL+ 24 ; KPS 25 ) . These works establish precise convergence rates, error bounds under various noise models, and extensions to sparse or dependent-data settings. When operating with \beta bits, the overall complexity for streaming PCA (and that of the batched variant) grows polynomially with \beta (for fixed n,d ); Table 1 gives evidence towards this fact. 64 bits 16 bits Runtime (s) 0.0274\pm 0.00136 0.000398\pm 0.0000235 Table 1 : Benchmarking runtimes 2 2 2 The experiments were conducted by representing the data and intermediate variables in \mathsf{double} precision (64 bits) and \mathsf{half} precision (16 bits) datatypes. for the experiment described in Appendix F.1 Our Contributions. 1. We present a general theorem for streaming PCA with iterates that are composed of independent data (as in standard Oja’s algorithm) and a noise vector that is mean zero, conditioned on the filtration up until now, which may be of independent interest . 2. We obtain new lower bounds for estimating the principal eigenvector under both quantization schemes. The quantization error depends linearly in the dimension d for the linear scheme and dimension-independent (up to logarithmic factors) for the non-linear scheme. 3. Our batched version of Oja’s algorithm matches the lower bounds under both quantization schemes. The quantization error of the batched version with logarithmic

Read the complete text