Low Precision Streaming PCA
Authors: Sanjoy Dasgupta
Syamantak Kumar
Shourya Pandey
Purnamrita Sarkar
Venue: NeurIPS 2025 poster ()
Keywords: Streaming PCA
Low-Precision Quantization
Oja’s Algorithm
Stochastic Quantization
Finite-Sample Convergence
Spectral Gap Assumption
Minimax Lower Bounds
Primary area: theory
TL;DR: Low-precision quantized variants of Oja’s algorithm can provably converge in streaming PCA under suitably fine discretization while drastically reducing memory and compute requirements.

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.

Low-Precision Streaming PCA
Sanjoy Dasgupta University of California San Diego sadasgupta@ucsd.eem
Syamantak Kumar University of Texas at Austin syamantak@utexas. edu
Shourya Pandey
Purnamrita Sarkar University of Texas at Austin purna. sarmaaaarkrruteee... edu
University of Texas at Austin shouryap@utexas.cm edu
Abstract
Low-precision Streaming PCA estimates the top principal component in stream- ing setting under limited precision. We establish an information-thoretti lower bound the quantization resolution required to achieve 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 stochas- tic 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 synthetic streams validate theoretical findings and demonstrate that our low-precision methods closely track the performance standard Oja's 's algorithm.
Introduction
Quantization (or discretization) is the mapping of continuous set of values 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 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 [Sti86]. In 1867, discretization was introduced for the approximate calculation of integrals [Ri667], and the effects of rounding errors integration were examined 1897 [Se97]] For an excellent survey and history of quantization, see [GKD + 22].
In the context of efficient model training, natural to ask the following: does training 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-bir bit accumulators) is standard GPUs and TPUs. yielding 1.5x to 3x speedups with negligible accuracy loss on large transformers and CNNs [MNA 18). Binary Neural Networks (BNNs), which constrain weights and activations to 1, achieve up 32x 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 low-prccision computation on optimization problems has received significant attention [LD19 17 SZORT5 SLZ* 18 LDX+ 17 ZLK* 117] Complementary
strategies leverage stochastic rounding to mitigate quantization bias during LLM training. Ozkara al. [OYP25] present theoretical analyses of implicit regularization and convergence properties of Adam when using BF16 with stochastic rounding, demonstrating up to 1.5x throughput gains and 30% memory reduction standard mixed precision (OY225)
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

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 [Ya109] uses linear quantization (LQ), where the quantization grid consists of points spaced uniformly at distance á (also denoted by quanta). [LDX + 17) analyze Stochastic Gradient Descent (SGD)-based optimization algorithms for IQQ, and S2 perform Learned Image Compression (LIC) under 8-bit fixed-pont point arithmetic. Nonlinear quantization (NLQ) grids with logarithmic spacing are also widely used [WWW
NTSW 22 XLY YTY21 ZMK22 23G+ 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 remain stuck the initial vector. Consider the update scheme w,- = W + 1g. followed by rounding each coordinate of Wt. Here 1j the learning rate and g: is the gradient evaluated at time t. Suppose max; (i) $ 1. Assume that Wo is quantized using the I.Q scheme and that < 8/2. For any coordinate i, we have [w) - wo( = 17 (i) & 1). Since 1) < 6/2, after rounding, w1(1) is mapped back to the original quantized value wo( i... Wi wo- As 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 [Pea0T] Zie03 is a dimension-reduction technique that extracts the directions of largest variance from the data. Suppose we observe n independent samples X, E Rd from a zero-mean distribution with covariance Σ. PCA seeks a unit vector V1 that maximizes variance, which is any eigenvector of Σ associated with its largest eigenvalue A1. Under mild tail conditions on the X,, the top eigenvector v of the sample covariance
>>= X,X! is a nearly
rate-optimal estimator of the true principal direction V1 [Wed72 JJK + 16 Ver10
Despite its statistical appeal, constructing the covariance matrix itself takes M(ndd) time and (dd))
space, which is prohibitive for large d and n. A popular remedy is Oja's 's algorithm [Oja82),
single-pass streaming algorithm inspired by Hebbian learning [Heb49]. Starting from a (random) unit vector Ug, for each incoming datum X; the algorithm performs the update
u - u + 7j X, (X, u,
u, - u |
(l)
Here, 77 0 is the learning rate which may vary across iterations. The batched version of Oja's method partitions the data into b batches Bi.... B,, of size n/b each and replaces the above update with the averages of the gradients within a batch:
u - u; jeB. X, (X]T,,1)
us /|sll
(2)
n/b
The entire procedure completes in O(nd) time and uses O(d) space. The scalability and simplicity of Oja's 's algorithm have motivated extensive analysis across statistics, optimization, and theoretical computer science [JJK 16 AZL.7 CYWZI8 (HWIN HWI9, MP22 Mon22 KS24b) KS24a |KL KPS25). These works establish precise convergence rates, error bounds under various noise models, and extensions to sparse or dependent-daie -ata settings. When operating with & bits, the overall complexity for streaming PCA (and that of the batched variant) grows polynomially with 3 (for fixed n, d); Table [ gives evidence towards this fact.
64 bits
16 bits
Runtime (s) 0.0274 i 0.00136 0.000398 + 0.0000235
Table 1: Benchmarking runtimes 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 inedene- dent 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 for the linear scheme and dimension independent (up to logarithmic factors) for the non-linear scheme.
'The experiments were conducted by representing the data and intermediate variables in double precision (64 bits) and half precision (16 bits) datatypes.
2

---

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 quantization is nearly dimension-free. We also provide a procedure to make the failure probability of the algorithm arbitrarily small.
Section introduces the problem setup and defines the linear and logarithmic quantization schemes. Section presents the main results, including lower and upper bounds for Oja 'ss algorithm with and without batching for both quantization schemes. Section provides proof sketches, Section 5 reports experimental results, and Section concludes the paper.
2 Problem Setup and Preliminaries
We use [n] to denote {i N | & n). Scalars are denoted by regular letters, while vectors and matrices are represented by boldface letters. I Rdxd represents the d-dimensional identity matrix. |l-Il denotes the lg euclidean norm for vectors and II-Ilop denotes the operator norm for matrices. For a, b E R, we write $ b if and only if there exists an absolute constant C' 0 such that & Cb. Ö, Q represent order notations that hide logarithmic factors. Sd-1 is the set of unit vectors in Rd.
We operate under the following assumption on the data distribution.
Assumption 1. (ii) are mean-zero iid vectors in Rd drawn from distribution 'D supported on the unit bull. Lei := EX_D [Xx [] denote the data covariance, with eigenvalues X > >2, Ad and corresponding eigenvectors vI, V2, Vdd We assume 3V. M >> O such that
XXx E1 and XX
-E
Σ12
.M almost surely for X D.
Assumption I enforces standard moment bounds used to analyze PCA in the stochastic setting.
Similar assumptions are also used in [HP14 [ROOS Shal6a [Sha 16 JJK + 16, AZL17 BDW Y16
XHDS 18) to derive pear-optimal sample complexity bounds for Oja's 's rule. We assume a bounded
range for ease of analysis, and can be generalized subgaussian data (see LSW21]KS44 [ia2l]
The misalignment between the estimated top eigenvector u and the true eigenvector u is measured using the principal angle between the vectors. The sin-squared error between any two non-zero
v) vectors u, v is defined as sin" (u. v) = - |u]?|v]2
2.1 Quantization Schemes and Rounding
Linear quantization: Let d > O, and let , > O the number of bits used by the low-precision model to represent numbers. A linear quantization scheme uniformly spaces the real line. Define
(r(6,)) - ... 8, 0, 6, 0(2,,, 1)}
We call 5 the quantization gap for the quantization grid Q1-
Logarithmic (non-linear) quantization: The error resulting from rounding an element æ in the
range [- 828-1, _5(22-1 - 1)] using the linear quantization scheme is an additive ó. Here, we present a well-known non-linear quantization scheme where the error scales with the quantized value.
The quantization grid QNz in the logarithunic quantization scheme with parameters and óg is defined as follows: Let Qo and g++1 (1+ () + 6, Vi N. Then,
2 8o, B) {-qN.- qN. - -1. Q1; qo, Q1, QN- 1N
where = 28-1 Henceforth, non- con-linear quantization refers to logarithmic quantization.
These two quantization schemes are widely used in practice [YTY21 D8L.2+18) LDS19 19 DMM 18) Our analysis of the logarithmic scheme lifts to floating-poin quantization commonly used in low- precision computing. The Floating Point Quantization (FPQ) is widely adopted variation on the Logarithmic quantization scheme, where adjacent values the quantization grid are multiplicatively close. FPQ and other logarithmic schemes used in most modern programming languages such as C++. Python, and MATLAB, and broadly standardized (IEEE 754 floating point standard (Kah66]).
Another quantization scheme for low-precision training is the power-of-two quantization [PSSS 22]. which rounds to the nearest power of two. All these schemes are similar principle to our scheme; Lemma A.9 in the appendix establishes relationship between the distance of a vector from its
3

---

quantization under NLQ. This Lemma applies to FPQ and to most other logarithmic quantization schemes. Our proofs can be modified work with any such scheme.
Stochastic Rounding, A natural quantization scheme is round any of the closest values in the quantization grid. We can randomize to ensure that the expectation of the quantized number is equal to x. For this, we stochastic rounding scheme. For any within the range of the quantization grid 2, suppose u and E are adjacent values in Q such that & < x < u. Define
(xr ② {eu
with probability 1 1 1-p(z) with probability p(x)
(5)
where p(z) (x 0)/(u f). This choice of probability ensures
I [QQr,, QNL) [x]] =
Q1,, QNL) - x & a e, Var(Q(z, @NL) & (u e)3/4.
(6)
3
Main Results
3.1 Lower Bounds
In this section, we establish worst-case lower bounds for the quantized PCA for both linear and logarithmic quantization schemes under the mild assumption that the quantized vectors under consid- eration have bounded norm. This assumption reasonable because (i) gradient-bar based algorithms and other typical algorithms for PCA are usually self eeffnnormalizigg ensuring that the norms of the iterates are controlled, and (ii) the quantized vectors are close the true vectors in norm.
Lemma 1. [Lower bound for linear quantization] Let d > 1 and 6 0 such that 8 & 0.5. Let VL denote the set of non-zero quantized vectors w E Rd using the linear quantization scheme 3 such that w|| [1/2, 2]. Then, supy,esu-1 inn, sin (w, V1) (2(82 d).
Lemma 2. [Lower bound for logarithmic quantization] Let d > 1 and do. <> such that Ç << 0.1 and ond < 0.5. Let VNL be the set of non-zero quantized vectors w E R² using the logarithmic scheme 4 such that ||w|| [1/2, 2]. Then, supviesá-1 infweVez sin" (w, vI) = Qi5² + dzd).
At first glance, the results of Lemmas and may appear similar. However, the parameter 8n substantially smaller than 8. In Section 3.4 we select optimal values for 6, 6g. and ( given fixed bit budget 3 for the low-precision model and show that 0 O(d4-2) while Ç² + 65 ((4-9) where the tilde hides a log" d factor. Hence, the lower bound for the logarithmic quantization scheme nearly independent of the dimension. The proofs of the lower bounds are deferred to Appendix
3.2 Quantized Batched Oja's Algorithm
In this section, present algorithm that uses stochastic quantization for the batch version of Oja's algorithm (see Eq We start by computing the quantized version w, of the normalized vector u:-1 from the last step. Then, quantize each X, XX, w:-1) and compute the average of the quantized gradient updates. This average gradient is quantized again and added to w,
Algorithm 1 Quantized Oja's Algorithm with Batches
Require: Data (ef) quantization grid Q, learning rate 7,, number of batches b 1: Initialize ug with a unit vector picked uniformly from Sd-1.
2: B, < {i -1) + 1, (i - 1) 2, ..., #53
3: for = 1 to do
4: w, - Q(u,11 Q)
E1. Q(u Q) u
z; - E, O(X, (X, Q.).Q)
5:
t- Eajs Q(X
X T w:): Q) - -X,(X, w;:
a/b
yi - Q(1 Eyen, Q ( w Q)
p- Ea,i := Σ Enji
6:
n/b
7:
u W: + yj
E2,1 := Q 2) y
8:
u,
- |
u.
9:
Quus, Q)
10: return w

---

The final vector that results from the batched Oja's ' rule (Eq without quantization is
(1+ DDDa) ... D2) + D
Dunquantized
[(T D)) .I. D2) DD)
I uD)
E where D; = j,,n x (n/b) b) is the empirical covariance matrix of the ith batch. Since X; are IID and the batches are disjoint, D, are also IID. The key observation for Algorithm iis that even with the quantization, the vector u, can be written
IT D, + 3 Up I + DD + u.)
Each E; a rank-one matrix resulting from the stochastic quantization. Conditioned on an appropriately chosen filtration oX1,.... Xi, uo,..., -;-1), E, is mean zero; Algorithm de- fines quantization variables Êi,i, Sa,i, and ε for all i E [b]. The rank one noise E; is E
(nS.. + E,, + (I+ (1) u Since the stochastic updates are conditionally unbiased (equa- tion 6
[ [D,,.... ..... Dj, Wo; wo....: W 0.
Similarly (D,,,. Di, Wo.... ... Wi-1] as it can be written as E[E[E,,/ DI...... D,, Wo. W.-il|Pi..... ...,,, Wo.... w;-1]] 0.
3.3 Guarantees for Low-Precision Oja's Algorithm
Before presenting main result, we present general result that apply to other noisy variants of Oja's rule and is of independent interest. The proof is deferred to Appendix Section Consider Oja's algorithm matrices A, Raxx,, such that A; nD; E, where D; are IID) random matrices with [[] Σ.
Let S; be the set of all random vectors in the first iterations of the algorithm and F,-. denote the a-algebra generated by the random ......, D; and S;-1- Define the operator E.I.J := [[- We assume the noise term is measurable with respect the filtration F,- and unbiased conditioned on Fi i.e., E, F- d Vo, 14 _M, K. and be non negatvett parameters such that
max (IEE(D,, D)
EI [E((D, E), Σ)1l
Vo.
(8)
D D 1,
D; DI & M, | &
|[ F 1 K1 a.s.
Theorem 1. Let d, n, b N and up N' (0, Ia). :e a loggn
6(11-22) be the learning rate where
is chosen to satisfy Lemma A.2 and suppose max by M² (d), bx log d) = O(1). Then, with probability least 0.9, the vector u, from equation 7 satisfies |ubl [1-K1, K1, K1] and
VVV logn
sin"(us, v1) S
2a +
22)² + max
K1 + u²2
b(A1
a lolog n
Remark 1 (Matching the Upper and Lower Bounds). In the LQ scheme with gap ö, each coordinate of the noise vector È is bounded by 8 almost surely. In particular, this implies k. = ( and K1 O(82 d) (see Appendix Section D and the resulting error due to quantization matches the lower bound in Lemmal) 1 In the NLQ scheme with parameters and do, the ith coordinate of the noise vectors bounded by Clu,] + do. where is the vector being quantized. Since the vectors in consideration are bounded in norm by this implies k = O 80v d) and Kg O 83d) (see Appendix Section D). The resulting error matches the lower bound in Lemma 2 as long the output vector has norm in the range [1/2,2].
relies the observation that accumulating the quantization error only b times in Algorithm leads to smaller sin? error. Moreover, choosing an appropriate batch size reduces the variance parameter Vo by a factor of n/b because of averaging.
Remark 2. Theorem 7
5

---

Remark 3 (Hyperparameters and eigengap). The choice of the learning rate 1
log n
is also
present in other works streaming PCA IHP14 SOR14 Shal6a Sba AZLI7 HNW7W20
UNNI9 BDF13j to derive the statistically optimal sample complexity (up to logarithmic factors). If
smaller learning rate is used (for example, by using an upper bound U on the eigengap X1 x2). then the first error term of Theorem [ will be larger, leading to a slightly larger sin-squared error. A similar argument applies to the choice of the batch size.
Remark 4 (Known n in the learning rate). The length of the stream n is an input in Theorem ! and the learning rate is constant over time. To handle variable learning rates using only constant-rate updates, a standard doubling trick (ACBFS95] can be used. Specifically, the time horizon is divided into blocks that double in size: the kth block has size 2 and Oja's 's algorithm run on that block uses a learning rate corresponding to that block's ' size. When the algorithm run on this block terminates, the older estimate of the top eigenvector run on the previous block is replaced by this new estimate. This scheme effectively simulates a decaying learning rate while keeping the analysis tractable.
3.4 Choosing the Optimal Quantization Parameters
To ensure a fair comparison between the linear and logarithmic quantization schemes, we fix budget 39 for the total number of bits used by the low-precision model. Moreover, our algorithms require that numbers in, say, (-2, 2) are representable by the quantization scheme. Therefore, we must ensure that the upper and lower limits of the scheme cover this range.
The largest number representable in the linear quantization scheme is 6(2 1) and the smallest negative number representable is - 28, We choose ó 22-3, which covers the range (-
To motivate the choice of ( and 6g. we note that the floating point scheme is a discretization of the logarithmic quantization scheme. The parameter dg in the logarithmic scheme represents the smallest representable positive real, which in the FPQ scheme is equal to 4 2 2-2 where 3e is the number of bits used to represent the exponent. The parameter ( represents multiplicative growth between adjacent quanta and is analogous to 2 fm in the FPQ scheme, where 3. is the number of bits to represent the mantissa, and 3 3. + 3e. Assuming Ç 2- and ōg 4- and Be are positive integers, the largest representable number is
2- 2-22-= where 8..
(1+ 2)= -1) d0 2 -1
42--1
To represent numbers in (-,, it suffices to ensure 9. 3. This allows some freedom to select 3m and Be such that the factor K1 (² + agd is minimized. We choose
B. flog2 (2/3 + loga (8dIn loga(8dIn 2))] and 8m = 3 Be
which is valid long B ' max(8, log, d) and Bm > 3. We justify this choice in appendix D.3 With this choice of Be and 8m. the parameters ( and 8u satisfy
2 and -² 423 log, (8d In 2))
(10)
48
With this setting, we present two immediate corollaries of Theorem with fixed budget f. The proofs are deferred to Appendix Section D. Theorem 2. [Oja's 's Algorithm with Batches]
1. Suppose Q = Qt and 8, b satisfy 8 - 22-3 - O A=-
and b satisfies
θ a² (nn)((n)
a login
(A1)
Then, with probability at least 0.9, the output wi of Algorithm
d a alog(n)
V
sin Wo. v1) & 22 + (Ai A2)
46
2. Suppose Q = QNL with S and 8o as in equation (1).. such that Ç + 80vd = a² log?(n)
d2 levalog(n) output Wa of Algorithm 7 ssatisfies
O
and butch size b = O
). Then, with probability at least 0.9, the
(A) (>a)>
a log(n)
(
82 + log (d)
sin (wb, v1) $ na
+ (Ai - )2)²
+
n
4
6

---

Theorem 3. [Oja's Algorithm]
1. Suppose Q Qr. and 6, b satisfy 6 = 22- O
0000mmm min
و ووو
Vodlog((n' van
and b
Then, with probability at least 0.9, the outpur wn of Algorithm satisfies
d
+ aVVlog())
dn
sin"(wns v1) &
+ 4 log(n)
naa n(1 X2)
2. Suppose Q = 2NL with < and d0 as in equation
(1)). such that Ç + 80vd < O min dnー [oddno van and batch size b n. Then, with probability au least 0.9, the outputt Wn of Algorithm satisfies
d a. aVlog(n)
(B² + +og d)n a log(n)
sin (wns v1)
na
n(11
X2)
Under linear quantization (LQ), the quantiza- tion error term scales as d/43, whereas under nonlinear/logarihhiic quantization (NLQ) it is only (332 + log² d)/49. Thus, NI.Q achieves nearly dimension- dimension-independen independent error resulting from quantization, making it especially advan- tageous in high-dimensional settings.
500, 2000
100
Mean sin Sainn-erre -error
10
10-2
The errors of Oja's algorithm with batching due to quantization are (d4-9) and ((4-9) in the two cases of linear and logarithmic quantiza- tion, which are an n factor larger than the cor- responding errors without batching. Theorem 2 show that batching significantly improves the performance under quantization. They fur- ther show that the NLQ scheme, when suitably optimized, gives nearly dimension-indess independent dependence on the quantization error. In com- resulting from quantization
rtandard
sundard
belched
10
batched
500
1000
1500
2000
Samples processed
Figure 1: We study the effect of different quantiza- tion strategies mean sin sin -erorr over 10 runs as the number of samples grows on the x axis. Stan- dard uses b n batches whereas Batched uses b 10 batches. Among the quantization algo- rithms, we see that in sin? error, Standard LQ Batched LQ and Standard NLQ > Batched NLQ.
parison, the in LQ suffers the most from higher dimensions. In Figure | we see that unquantized algorithms (standard and batched) have similar and best performance. See Section for detailed exper- imental evidence supporting the theory.
Remark 5. Theorems 2 and 3 are stated with a constant probability of success. In Section 3.5 provide a quantized probabiliy boosting algorithm (Algorithm) which boosts the probubility of success from constant to 1 for arbitrary 0 (0.
3.5 Boosting the Probability of Success
Quantized Oja's algorithm produces an estimate whose enror is within the target threshold with constant success probability. This section addresses this gap by presenting standard probability boosting framework to let the failure probability 0 be arbitrarily small.
Algorithm begins by partitioning m data (X, ]efm into r = Olog 1/0) disjoint batches of size n each and runs algorithm A on each batch. The output vectors [u:]eerr) are then aggregated using the boosting procedure SuccessBoost. This procedure looks for popular vector u, close to at least half of the other vectors and returns any such vector. general argument for SuccessBoost for arbitrary distance metrics can be found in [KL +23 KS24a].
7

---

Algorithm 2 Probability Boosted Oja's Algorithm
Require: Data (E(m) algorithm A. quantization grid Qr.(e), failure probability 0, error
1: - [20 log n [m/r]
2: for to do
3: B, - ((2 1)n, (i- 1)n 1, (2-
1)n + n}
4: u, - A ((
5: procedure p(x. y)
6: return (sin y), 21(c)
7: procedure SuccessBoost( (.
8: for i = to do
9:
C; []j [r] p(u, u,) < Se)l
10: if 0.5r then
11: return 1
return u,
SuccessBoost( (et)))))
13:
return
We quantized version ý proxy for the sin error in the SuccessBoost procedure, uses the linear quantization grid
- (,--- 1)e, -6, 0, c,...; (28-1 1)e},
(11)
where the gap e is set to the upper bound on the error guaranteed by Theorem depending on the algorithm A in use.
2 or Theorem
Standard arguments for SuccessBoost apply when the error is either computed exactly. The difference our setting is that we the error function ő is only approximately a metric and does not behave intended if the computed value is outside the quantization range. To highlight the second point, consider the unbounded quantization grid
(7.(c) = (ke k Z).
With this grid, fp(x. y) - sin (x. y) is bounded by O(e) almost surely. We extend the argument to show that Lemma holds even with the bounded grid Qz(c) (z,e, 8), which truncates values outside the range 2--1 c, (23-1 1)c] to its endpoints. This requires modest assumption that the number bits 3 > which is already assumed when optimizing the parameters in Section 3.4
(0, 1), and = |20 log(]/))], Let E Rd be unit vector and u1, U2,...., u, be independent random vectors such that (sin v) < 0.9. Let f be the function defined in Algorithm 2 with the quantization grid (E, Then, the vector = SuccessBoost (ussie(r)) p,c) satisfies
Lemma 3.
Let
3, > 4, E 00,0.75),
Pr (sin?(u, & 14c) > 1 1 0.
The proof of Lemma
Appendix
Algorithm|2 2 has a constant overhead in the error compared to algorithm A. The probability of success amplified from 0.9 to 1 O. The number of samples needed to achieve the same error (up to constant factors) as AA blows up only by a multiplicative factor Oloo 1/0). If algorithm A runs in ((dd) time and O(d) space, which is the case for Oja's algorithm and its batch variants, then Algorithm takes [og(logg1// d (1/8)) dlog2(1/8)) time and O(d (1/)) space.
Proof Techniques
Our proof of Theorem has three main parts. Let Z, = (I+ A,) where A, := 1,D; E as described in equation 7 First, note that the sin-squared error can be written as 1 (u, vi)
V V uz /|| 2. Using the one-step power method result shown Lemma 6 from -
JJK 16), for fixed 0 (0, 1), with probability atleast
3log (1/0) Tr [V1 ZZ V1)
- (u, v12²
(12)
82
ZoZ V1

---

This makes our strategy clear for the subsequent proof. We bound the numerator by bounding [[ Z,ZZz V.)] and applying Markov's inequality. For the denominator, we lower bound Z v by decomposing it as
v1ll vill > [ T vill I| (I+ (++)))") v1l > (1 nA11) (1+ 1Z, (I+ (I++))) (13)
and upper-bounding IZz (I+ nn)) $
For both the numerator and the denominator, we use the following intermediate bound, which controls the (p. nnorm for a random matrix X defined as [X]]| [_]] where |X represents the Schatten-p norm.
Proposition 1. Let the noise term 3, defined in 9 be bounded as = Assumption / for 7) (0, 1), have
x R almost surely. Under
7 ZZlll p.g & o² exp((Cbb)) ||
2, (1 + 17 , p. & (exp((C,bb) - 1) |z
where Zo I, o= (1 + m)))), y M x²), and Cp : p 1.
The proof of Proposition] [ ladats the arguments for matrix product concentration from [HNWTW20) which also include results for general sequence of matrices adapted a suitable filtration.
From Proposition | with
2. 2 + 2 log d, we get
E [ (I + , Z (I + 1) 1I,. & Verby (1 log (d)) (1 + n/)1))
This allows to control the lower bound via Markov's inequality, by substituting in equation [3]
To control the numerator, we show the following result (Lemma 4 Lemma 4. Let Assumption 7 hold and let y 2(17 M2 x²). If by (1 log (d)) 1, then
Vo + 5m
E[Tr(V] T Zg Z V1) & exp (2mpb1 + 7 (Vo + x))) exp (2mb (A1 - -x2)) 17 (A1 x2)
The proof of Lemma 4 follows Lemma 10 of [J] show, for B: E[Tr(V_ 1 Z, V 1)}.
Be & (1+ + 21/22 + n/ (Vo + xt)) f:-1 + (n + K1 E[ Z 1...
At this step, we deviate from their proof and appeal Proposition 1 for bounding Z[]| Setting = (1 + 32 7 = M² + x²²) and p = max(2, v log d/(())). get
F[
Z 11 Φe exp (xl()) Z | (1 n/11) 2d exp (2pby).
Unrolling the recursion and using this bound proves Lemma The proof of Theorem then follows from the one-step power method guarantee in equation 12 Detailed proofs are in Appendix
Experiments
bits 8, 100
10a
bits a n 5000
100
Findl enn -aner
10"
10
Frod
10
2010
1000
2000
3000
4000
200
300
[samplea)
(ddimenaion)
(a) Varying sample size n1, fixed 100, bits 8.
(b) Varying dimension fixed n 5000, bits 8.
(c) Varying bits B, fixed a 1000. 100.
Figure 2: Variation of - with (a) sample size, (b) dimension, and (c) quantization bits.

---

We generate samples from a dimensional distribution selected by choosing a random orthonormal matrix Q, setting := QAQ for A, i-2 and sampling datapoints i.i.d from .N (0, Σ). We compare six variants of Oja's algorithm for estimating vn, the leading eigenvector of E. The baseline the standard full precision update in Eq [T] (standard). standard _IQ and standard __tidd_iiQ use Algorithm D with b = n and Q(., 21) and Q( QNZ) respectively. The batched variant follows Eq with 5= 100 (for Figures 2a and 2b) and = 25 (for Figure 2c) equal-sized batches. Finally, we combine the batched schedule by running Algorithm| with Q Qz) (batched_ LQ) and with Q(, QNE) (batched (LQ)..__NNeee All experiments were done on a personal computer with a single CPU.
The low-precision methods rely on Eq 10 to choose quantization parameters for target number of bits 3 8. Given the dimension d, these routines compute a uniform quantization step duni- an exponential step Sexp, and multiplicative-grovei Each configuration is run for R 100 independent trials. In Experiment we fix d 100 and vary n {1000, 2000, 3000, 4000, 5000); in Experiment 2 we fix 5000 and vary d {100, 200, 300, 400, 500). Every trial begins from a random Gaussian vector normalized to unit Iu(n)
factor Goxp to cover fixed dynamic range.
Iu(n) length. We set the learning rate to a (Ai Aa) for the standard method and to rj 6 ((Ax--A2) for the batched methods. Upon completion we record the final excess eтror sin (w, v1) = 1- (w v1)² and report the mean. The first two use the log-log scale and the third uses the log scale for the y-axis.
As shown in Figure 2a all methods improve as the number of samples n grows except standard Q.Q and standard_Ni NI.Q. The errors of these two methods, as expected from Theorem 3 grow linearly with n. In contrast, the batched_La and batched Matched_NLL's s quantization errors do not depend linearly on and improve over the standard counterparts. Figure 2bb shows how the error varies with the data dimension d. Since V grows mildly with d, for our data distribution, all methods other than standard LQ and batched LQ do not grow with d. These two methods grow linearly with d. confirming our theoretical findings in the first results under Theorems 2 and 3 Finally, Figure 2c compares the eπгоrs with the bit budget B. As 3 increases from 4 to 12, linear and logarithmic quantization schemes steadily reduce their error and converge toward the full-precision result by 12. The batched quantizers require only 6-8 bits to achieve comparable performance to the full-precision batched error, whereas the standard__ _.Q and standard NL.Q need at least 10 bits to reach the same performance. The variability of the full precision methods arises from the randomness of initializations. Appendix F provides experiments on additional real-world and synthetic data.
6 Conclusion
We study the effect of linear (LQ) and logarithmic (NLQ) stochastic quantization on Oja's algorithm for streaming PCA. We obtain new lower bounds under both quantization settings and show that the batch variant of our quantized streaming algorithm achieves the lower bound up to logarithmic factors. The lower bound on the quantization error resulting from our logarithmic quantization dimension-free. In contrast, the quantization error under the LQ scheme depends linearly in d. which problematic in high dimensions. We also show a surprising phenomenon under quantization: the quantization error of standard Oja's 's algorithm scales with n under both NLQ and LQ schemes, while batch updates with a small batch size does not incur this dependence. These theoretical observations validated via experiments. A limitation of our analysis is that we estimate the first principal component only. Deflation based approaches (see c.g. [JKL XXL**2| 24 MMc08] (SSS99) provide an interesting future direction for extending this work for retrieving the top principal components.
A Acknowledgments and Disclosure of Funding
We gratefully acknowledge NSF grants 221 2217069, 2019844, and DMS 2109155.
10

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We prove theoretical results on the effect of quantization on streaming PCA. The abstract and introduction summarize the contributions and put them in the broader scope of low-precision computation.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In the conclusion, state that our work is about estimating the first principal component. Extending to principal components is part of future work.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex. system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
We provide complete proofs in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Our experimental section has all the parameters of the experiments for repro- ducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
12

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will submit the code with the supplementary material. We only provided synthetic experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cc)
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https /ttpsscccppbllcc//// htw.:/ddss/coeeeuuuiisiiiooooooo
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We specify the learning rate, data-generating distributions, and other parame- ters clearly in the experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
13

---

The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We provide error bars for the figures in the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments were done on our personal device with single CPU, which we mention in the experimental section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
14

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our work conforms with the NeurIPS code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction)
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is primarily theoretical and has no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is primarily theoretical, and do release data models.
Guidelines:
The answer NA means that the paper poses such risks.
15

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
We do not use any existing assets our contributions are primarily theoretical.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do release new assets our contributions are primarily theoretical.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
16

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our work is primarily theoretical we do not use crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our work primarily theoretical we do not use crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMSs if it is an important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is required.
Answer: [NA]
Justification:
We do use LLMs other than for writing or editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non non-standard components.
Please refer to our L.LM policy (https: http:p////aarrrepccc//ooeeeeeeee for what should or should not be described.
17

---

References
[ACBFS95] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pages 322-331. IEEF, 1995.
[AGL+ 17] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-effcienll SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1707-1718, 2017.
[AGO+ 13] Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Juan-Luis Reyes- Ortiz. public domain dataset for human activity recognition using smartphones. In Proceedings of the 21st European Symposium on Artificial Neural Networks, Computationall Intelligence and Machine Learning (ESANN), pages 437 337-442, 2013.
[A7L17] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pea: a global, gap-free, and near-optimal rate. In 20/7 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487-492. IEEE, 2017.
[BDF13] Akshay Balsubramani, Sanjoy Dasgupta, and Yoav Freund. The fast convergence of incremental pca. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 26, pages 3174-3182.
Curran Associates, Inc., 2013.
[BDWY16] Maria-Florie Florina Balcan, Simon Shaolei Du, Yining Wang. and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 284-309, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR.
[CYWZ18] Minshuo Chen, Lin Yang, Mengdi Wang, and Tuo Zhao. Dimensionality reduction for stationary time series via stochastic nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018
[DMM* 18] Dipankar Das. Naveen Mellempudi, Dheevatsa Mudigere, Dhiraj Kalamkar, Sasikanth Avancha, Kunal Banerjee, Srinivas Sridharan, Karthik Vaidyanathan, Bharat Kaul, Evangelos Georganas, et al. Mixed precision training of convolutional neural networks using integer operations. arXiv preprint arXiv: 1rXiv:/802.009330 2018.
[DPHZ23] Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms. arXiv preprint arXiv: 14314, 2023, https
serxiv.org// baarg//bs//uae 2305. 14314.
[DSLZ* 18] Christopher De Sa, Megan Leszczynski, Jian Zhang, Alana Marzoev, Christopher R Aberger, Kunle Olukotun, and Christopher Ré. High-accuracy low- ow-precision training. arXiv preprint 1833v:1803.0338. 2018
[GKD+22] 22] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. A survey of quantization methods for efficient neural network inference. In Low-power computer vision, pages 291-326. Chapman and Hall/CRC, 2022.
[HCS+ 16] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems, 2016.
[Heb49] Donald O. Hebb. The Organization of Behavior: A Neuropsychologcaa Theory. John Wiley & Sons, New York, 1949.
[HNWW200] De Huang, Jonathan Niles- Joel A. Tropp, and Rachel Ward. Matrix concentra- tion for products, 2020.
[HP14] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27, pages 2861-2869. Curran Associates, Inc., 2014.
18

---

[HW19] Amelia Henriksen and Rachel Ward. AdaOja: Adaptive Learning Rates for Streaming PCA. arXiv e-prints, page arXiv:1905. 12115, May 2019.
[JJK + 16] Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, and Aaron Sidford. Stream- ing pea: Matching matrix bernstein and near- near-optimal finite sample guarantees for oja's algorithm. In Proceedings of The 29th Conference on Learning Theory (COLT), June 2016.
[JKL*24] Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, and Kevin Tian. Black-box k-to- 1-pca reductions: Theory and applications. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory, volume 247 of Proceedings of Machine Learning Research, pages 2564-2607. PMLR, 30 Jun-03 Jul 2024.
[JL84] William B. Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into hilbert space. In Contemporary Mathematics, volume 26, page 189-206, 1984.
[JNN19] Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. SGD without Replace- ment: Sharper Rates for General Smooth Convex Functions. arXiv e-prints, page arXiv:1903.01663, March 2019.
[Kah96] William Kahan. Ieee standard 754 for binary floating-poin arithmetic. Lecture Notes on the Status of IEEE, 754(94720-1776))) 1996.
[3] Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference Learning Theory, pages 2352-2398. PMLR, 2023.
[KPS25] Syamantak Kumar, Shourya Pandey, and Purnamrita Sarkar. Beyond sin-squared error: linear time entrywise uncertainty quantification for streaming pca. In Proceedings of the Forty-First Conference on Uncertainty in Artificial Intelligence, UAI '25. JMLR.org, 2025.
[KS24a] Syamantak Kumar and Purnamrita Sarkar. Oja's algorithm for streaming sparse pea. In The eiihth- Annual Conference Neural Information Processing Systems, 2024.
[KS24b] Syamantak Kumar and Purnamrita Sarkar. Streaming pea for markovian data. Ad- vances in Neural Information Processing Systems, 36, 2024.
KWW* 17] Urs Köster, Tristan J. Webb, Xin Wang. Marcel Nassar, Arjun K. Bansal, William H. Constable, Oğuz H. Elibol, Scott Gray, Stewart Hall, Luke Hornof, Amir Khosrow- shahi, Carey Kloss, Ruby J. Pai, and Naveen Rao. Flexpoint: An adaptive numerical format for efficient training of deep neural networks. In Advances in Neural Informa tion Processing Systems, volume 30, pages 1742-1750, 2017.
[LBBH98] Yann LeCun, León Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied document recognition. Proceedings of the IEEE, 86(11):2278- 2324, 1998.
[LD19] Zheng Li and Christopher M. De Sa. Dimension bounds for low-precision training. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'Ach--Bucc E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32 (NeurIPS 2019), pages 11178-117733 1178, 2019.
[LDS19] Zheng Li and Christopher De Sa. frree bounds for low- cow-precision training. Advances in Neural Information Processing Systems, 2019.
[LDX+11] 17] Hao Li, Soham De, Zheng Xu, Christoph Studer, Hanan Samet, and Tom Goldstein. Training quantized nets: A deeper understanding. In Advances in Neural Information Processing Systems, pages 581 5813-5823, 2017.
[Lia21] Xin Liang. On the optimality of the oja's algorithm for online pca, 2021.
19

---

[LSW21] Robert Lunde, Purnamrita Sarkar, and Rachel Ward. Bootstrapping the enror of ssss algorithm. Advances Neural Information Processing Systems, 34:6240-622 62522 2021.
[Mac08]
Lester Mackey. Deflation methods for sparse pea. Advances in neural information processing systems, 21, 2008.
[MNA* + 18] Paulius Micikevicius. Sharan Narang, Gabriel Alben, Gregory Diamos, Erich Elsen, David Garcia, Dmitry Ginsburg, Michael Houston, Oleksii Kuchaiev, Sanjo Venkatesh, and Hao Wu. Mixed precision training. In International Conference on Learning Representations, 2018
[Mon22] Jean-Marie Monnez. Stochastic approximation of cigenvectors and eigenvalues of the q-symmetric expectation random matrix. Communications Statistics-Thent and Methods, pages 1-15, 2022.
[MP22] Nikos Mouzakis and Eric Price. Spectral guarantees for adversarial streaming pea. 2022.
INTSW*22) 22] Miloš Nikolić, Enrique Torres Sanchez, Jiahui Wang, Ali Hadi Zadeh, Mostafa Mah- moud, Ameer Abdelhadi, Kareem Ibrahim, and Andreas Moshovos. Schrödinger's s fp: Dynamic adaptation of floating-poil containers for deep learning training. arXiv preprint arXi:: 13666, 2022.
[Qja82] Erkki Oja. Simplified neuron model as principal component analyzer. Journal of mathematical biology, 15:267-273, 1982.
[OYP25] Kaan Ozkara, Tao Yu, and Youngsuk Park. Stochastic rounding for Ilm training: The- ory and practice. In Proceedings of the 28th International Conference on Artificial In- telligence and Statistics (AISTATS), 2025. https:/ /ttp///axiv..v/.. orggabs/////eeeoooeooooooee /202..252...0 20566
[Pea01] Karl Pearson. Liii on lines and planes of closest fit to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, 2(1 (1:51)5555775 572, 1901.
[PRSS+22] Dominika Przewlocka-Run Syed Shakib Sarwar, H Ekin Sumbul, Yuecheng Li, and Barbara De Salvo. Power-of-twe quantization for low bitwidth and hardware compliant neural networks. arXiv preprint arXiv:2203.05025 2022.
[Rie67] Bernhard Riemann. Ueber die Darstellbarkeit einer Function durch eine trigonometrische Reihe. Dieterich, 1867. German.
[SFD+ 14] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application Kata-parallel distributed training of speech dnns. In Interspeech, 2014.
[Sha16a] Ohad Shamir. Convergence of stochastic gradient descent for pea. In Proceedings of the 33rd International Conference on International Conference on Machine Learning Volume 48, ICML' 16, page 257-265. JMLR.org, 2016.
[Sha16b] Ohad Shamir. Fast stochastic algorithms for svd and pca: Convergence properties and convexity. In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Leurning, volume 48 of Proceedings of Machine Learning Research, pages 256, New York, New York, USA, 20-22 Jun 2016. PMLR.
[She97] William Fleetwood Sheppard. On the calculation of the most probable values of frequency-constane for data arranged according to equidistant division of a scale. Proceedings of the London Mathematical Society, 1(1):353-800 1897.
[SJS09] Reza Sameni, Christian Jutten, and Mohammad B Shamsollahi. A deflation procedure for subspace decomposition. IEEE Transactions on Signal Processing, 58(4):2363- 2374, 2009.
20

---

[SLZ* 18] Christopher De Sa, Megan Leszezynski, Jian Zhang, Alana Marzoev, Christopher R. Aberger, Kunle Olukotun, and Christopher Ré. High-accuracy low-precision training. arXiv preprint arXiv: 1oxXiv:8800:.. 1803.0338, 2018.
[SOR14] Christopher De Sa, Kunle Olukotun, and Christopher Ré. Global convergence of stochastic gradient descent for some nonconvex matrix problems. CoRR, abs/1411.1134, 2014.
[SRO15] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 2332- 2341, Lille, France, 07-09 Jul 2015. PMLR.
[Sti86] S. M. Stigler. The History of Statistics: The Measurement of Uncertainty before 1900. Harvard University Press, Cambridge, 1986.
[SYK21] Heming Sun, Lu Yu, and Jiro Katto. Learned image compression with fixed-point arithmetic. 2021 Picture Coding Symposium (PCS), pages 1-5, IEEE, 2021.
[SYKM17] Ananda Theertha Suresh, Felix X. Yu, Harsha Kumar, and H. Brendan McMa- han. Distributed mean estimation with limited communication. arXiv preprint arXiv:1611.00349, 2017.
[SZOR15] Christopher M. De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré. Taming the wild: A unified analysis of hogwild-style algorithms. In Advances in Neural Information Processing Systems, pages 2674-2682, 2015.
[Ver10] Roman Vershynin. Introduction to the non-asympiotic analysis of random matrices. arXiv preprint ar1 1.3027, 2010.
[Wed72] Per-Åke Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12:99-111, 1972.
[WXY+17] 17] Wei Wen, Chunpeng Xu, Felix Yan, Chunyi Wu, Yandan Wang, Yiran Chen, and Hai Li. Terggad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, 2017.
[XHDS+ 18] Peng Xu, Bryan He, Christopher De Sa, loannis Mitliagkas, and Chris Re. Accelerated stochastic power iteration. In International Conference on Artificial Intelligence and Statistics, pages 58 67-67. PMLR, 2018.
[4] Yongqi Xu, Yujian Lee, Gao Yi, Bosheng Liu, Yucong Chen, Peng Liu, Jigang Wu, Xiaoming Chen, and Yinhe Han. Bitq: Tailoring block floating point preci- sion for improved dnn efficiency on resource-comstrained devices. arXiv preprint urXiv:2409.17099 2024.
[MHH223] Lu Xia, Stefano Massei, Michiel E. Hochstenbach, and Barry Koren. On the influence stochastic roundoff errors and their bias on the convergence of the gradient descent method with low-precision floating-poin point computation, 2023.
[Yat09] Randy Yates. Fixed-point arithmetic: An introduction. (13)) 2009.
Digital Signal Labs,
[YGG+24] Tao Yu, Gaurav Gupta, Karthick Gopalswamy, Amith R. Mamidala, Hao Zhou, Jeffrey Huynh, Youngsuk Park, Ron Diamant, Anoop Deoras, and Luke Huan. Collage: Light- weight pow-preciioon strategy for 11m training. In Proceedings of the 41st International Conference on Machine Learning, 2024.
[YHW18] Puyudi Yang, Cho-Jui Hsieh, and Jane-Ling Wang. History pea: A new algorithm for streaming pea. arXiy preprint / /tti::/802.0.... 054705447, 2018.
[YIY21] Hisakatsu Yamaguchi, Makiko Ito, and Katsuhiro Yoda. Training deep neural networks in 8-bit fixed point with dynamic shared exponent management. Proceedings of the 2021 Design, Automation & Test in Europe Conference (DATE), 2021.
21

---

[Zie03] Eric R Ziegel. Principal component analysis. Technometrics, 45(3):276-21) 277, 2003.
[ZLK 17] Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and little bit of deep learning. In Proceedings of the 34th International Conference on Machine Learning, pages 4035-4043 2017.
[2MK22] Sai Qian Zhang, Bradley McDanel, and T. Kung. H. Fast: Dnn training under variable precision block floating point with stochastic rounding. In Proceedings of the 2022 IEEE International Symposium on Pirih-Perffomance Computer Architecture (HPCA), pages 846-860, 2022.
[ZWG+23] Jiajun Zhou, Jiajun Wu, Yizhao Gao, Yuhao Ding, Chaofan Tao, Boyu Li, Fengbin Tu, Kwang-Ting Cheng, Hayden Kwok-Hay So, and Ngai Wong. Dybit: Dynamic bit-precision numbers for efficient quantized neural network inference. arXiv preprint arXiv:2302.125100 12510, 2023.
22

---

The Appendix is organized as follows:
Section
provides utility results useful in subsequent proofs.
2. Section
provides the proof of the lower bound described in Section 3.1
3. Section proves helper lemmas for the results in Section
4. Section proves Theorems
and
5. Section proves the boosting result (Lemma 3 and end to end analysis of Algorithm T followed by the boosting algorithm 2
6. Section provides additional experiments.
7. Section provides more related work.
A Utlity Results
Lemma A.l. Let & x & u be reals, and define
Qax, ②) = {
with probability 1 p(xr) with probability p(x)
where p(x) = (x l)/(u f). Then,
(i) E [[Q(x, 2] x.
(ii) QQ(z, Q) x| & u su-l.
(iii) Var [ Q(z x [z] x (a-1)²
Proof. Throughout the proof, condition the fixed æ and treat all randomness coming from the independent choices made by the quantizer.
(i) Unbiasedness. We have
[[Q(2,
[]] p:(x))u p((x)))
(ii) Boundedness. By definition, after rounding. always round any [u, either I. Therefore, [Q, Q) x & u I.
Variance bound. Using the variance Bernoulli random variable, we have,
Var[Q(z, 2) x]]
(1(x p.(x)) (u (u=1)² 0)²
4 [u 1)2
1
since ((1-)) & 1/4 for all reals
Lemma A.2 (Choice learning rate). Let 17 : b(A1-12) Then, under Assumption 1 for e (0, 1),
a log(n)
satisfies
0.008
b(v22MM M2 x²) & log(d/0)' and 1) (0,
for a > b 250a² log2(n) log ( (A1 A22 and 2 0.004/ log (1)
Proof. For Lemma A.8 we require,
4b(12 M² + x²) (1 + 2 log (d)) & 1
(A.14)
For Theorem A.4 we require,
d
4c2b(17 x²) log
E
(A.15)
0
23

---

where 9 E (0, 1) represents the failure probability. It is not hard to see that A.15 implies A. 1.14)
Therefore it suffices ensure
byr2 M² + +x2)logg log d
0.008
Setting each term smaller than 0.004, it suffices to have
250a² log (n) log ($)
0.004 log ($)
b
x b²b <
A2)²
which completes the proof for the first condition.
The second condition on follows by setting 7) & 1 and solving for b. This yields
d / /A1 ) - 22)² a log (n) (A1 x2)
b > max 250a² log((n) log
Since 1, the first term is larger than the second one, which completes the proof. Lemma A.3. Let w and & be vectors in Re such that ||w]] = and w E * 0. Then,
|K
sin?(w, w + -) | + El1
Proof.
sin?(w w =E)==== =- w (w + +E)
2
(w + E)
(w + E)
(1 + w g)2
w + &
E
ET E)2 w + El2
|
2
| + El
Lemma A.4. Let x and y be unit vectors in Rd. Then,
2 min([Ix m yl1 ||x + y113) & sin (x, & min[[Ix -|l||xx-lll*' -y11",1x + y11)).
Proof. We express sin sin?(x, y) in terms of ||x - yl and ||x + y/.. Since 2x y 2000sxxxx y) and ||x + y1 2 cos(xx (x,
=||x12 11x1112
1
y1= |xx + y1 4 and sin iin((x,y) y) 1 cos (x,y)
|xx yl1² ||x yl1
The upper bound on sin? xx y) follows immediately from the above equations. For the lower bound, note that least one of ||x 2 and ||x + yl? is at least because their sum is equal to 4. If ||x + y/12 > then sin² yx. > |x- x /2. Otherwise, sin2 y) ||x + y11 /2.
Lemma A.5. Let x, and be non-zero vectors in Rd. Then,
sin sin" z) & ssin" (x.y) 2 syn"(y,z).
Proof. For unit vectors and in Rdd
uu vv
1|2- Tr (uu vV
Tr (uu) - (u T v)uv (v Tujuu + vvv
2 - 2(u v)2 = 2 sin su, v).
By parallelogram law,
2 xx
2z.' T
F x xx
yy T 11 + lyy zz
sin sin) & 2sin ( (x,,) 22si ().
24

---

B Lower Bounds
Proof of [emma[]
Proof. Let 11 E Rd be the unit vector with vi(1) 8/3 for i
[d 1] and vi(d) v (d-1)62
Consider any vector VL. and let w w/|[w/ Since Vı, w(i)
/w(i) > 6/2. In
particular, [vi(i) w(i) > 6/6 and |v (i) + (()) > 6/6 for all i E [d - 13. It follows that
[ w/
(vi(1) w()) (d - 6
(d - 1)
36
and [[v + w|| (d--1) similarly. The Lemma follows from A.4
Proof of Lemma
Proof. It suffices to construct two unit vectors Vi and va such that we sin?(w, v1) 22(?)
and wnfwe sin'(w, v2) ((6dd).
Let V1 be the vector in Rd with coordinates
1+c/2 VI+ (1+ (/2)²
(1) VI+ (1 2/2)2 (2
vi(1) 00i2 3.
For the sake of contradiction, suppose there exists W1 VNL such that sin 2 (W1, v1) 12/100.
Let W == w///will- By Lemma
A.4
w, w1ll lIv + will)) & 22sin((v1 W1) < 5²
min( [[v
50
Flipping the sign of w1 if necessary, we may assume [| w1l12 < 52/5 So.
(v) - w1 < </7 V E [d].
(A.16)
The bound Ç & 0.1 ensures (1( B 20/29 and v1 (2) v1 > 2/3, which also implies w w1(2)
w1(1) > 5/3 2C/7 = C/21 > 0. It follows that
(2 + 50/5 w1(1) + 8//C
wI(2) + 50/5 1/ |/
& (/7))+
w1(1)
50/5 1/ [|]
(/71)- 8//2
50/2( + - (1)) C/7)
+
2
+ 2/14-6/
1 +
v1(1) 5/7+50/7 50/2C
+ 2C/7
< 1 +
< <1+
2
2/3
and
(2 + 86/C
w. + 50/5 - 1/ [i]
- - 20
>
(1) + 6//C
(1( + 50/5 1/ |1]
v1(1) + C/7 200/5
<
200/5 - 1/70/11777111111 (12) (200/S + 5/7)
-1 +
+
2
vi </7 + 200/S
2 + (2/14+
1
+
2
(1(1)
+200/
(vi(1)/2 + +3/14 80
1+
1.
+/7)+5/7+ 200/C
25

---

Under the logarithmic quantization scheme, it can be inductively shown that
(k + óo/S = (dn/S) (1 +1++0 <)*
for all non-negative integers k such that qu E QNL- In particular, W: (2)+ power of contradicting
must be an integral
(1)+06/5
W1 + 60/5
1 < w1(1) 60/5
< x1+
Therefore, inf sin?(w1, v1) 3 52/100.
The other bound is similar to the linear case. let v2 be the vector with coordinates
do 3
v2(d) v (d ((d-1))) 1)08/9, vi(i)
vied d-
Any W2 E VNL satisfies (1) 0 or |w2(i) > 6p for all i E [d]. Since ||w [1/2, the normalized vector W2 W2/ W2 satisfies [2(1)] or (2(1)] 60/2 for all [d].
In particular (22(i) (2 6a/ and Vv2(t) + W2 (i)l 6a/6 for all E [d]. By Lemma A.4
sin (in, v2) x min || v21l || + v21l?)
1
og - 1)
72
C Proof of Results in Section 4
For ease of exposition, all results in this section are stated with generic number of data n. We apply these results with different choices of (e.g. number of batches b) for proving the main theorems (Theorem I 3 Consider Oja's Algorithm applied the matrices A, Raxds such that A; D, + E where Dj are independent with E[D.] = Σ. Let S be the set of all random vectors & resulting from the quantizations
the first iterations of the algorithm, and let F, denote the o-field generated by DI...., D, and - and denote E. == [[]]F; We assume the noise term
E, is conditionally unbiased, i.e., [.] Odxd-
F: : a ((D D.,S., ===((D D...
Recall the update rule
II, [I=,(I- A.)
(I (I+A, A,),wi
W
(A.17)
(I+ A,)uol
We bound the numerator and denominator in
separately.
For the numerator, we will show that i e [n]. and let (Zeoogign be defined
I (I + A.) - (I+ I| is small. Let Y, I+ A, for
Z = YZZ-11
Zo I.
(A.18)
Note that Z, is measurable w.r.t F._.
We are now ready state our first result. Note that
Zn = a A.).
where A, r7D; E, and D, are independent d x d random matrices with mean Σ.
26

---

& e which impliess C.1 Proof of Proposition 1
Proposition A.I. [Proposition 7 in main paper]Let the noise term E, defined in ②. be bounded as E & R almost surely. Under Assumption
[ for n E (0, 1) and b > O, we have
exp ||
Zn (I + 1) ,) "1 & ('(exp(C,(r)) - 1) Z lp
where Zo I, d= (1 + n))) 2 7
22 ) and Cp p 1. M
Proof. Recall the notation Y, I A, for all Then,
E[ = I + ح + ElE, [3,] 1 1/
Note that my = + n and
Y E In
- -)) E $ M.
The last line uses Eq Thus 0,
M++ Note that v & 2<n + k n² 1+
The same argument as in
Theorem 7.4 in HNW [20 gives the bound.
Lemma A.6. Under Assumption and with v) set according to Lemma A.2 with n,
P P( - + | > ( (1 + n)))") & e)
AlEE.
22222
where y M2 R²) and cxp(1) is the Napier's 's constant.
Proof. By Proposition A.1 for any positive real p.
E E|| Z, (I 11 1|
Zn (I (1+
P P( (I+ 1 + (1+ + n)))") n\)))))))
# (1+ + n/1)""
t0 (1 + m1/11)"
0² (exp(Cpp (Cpny) - -1)p/dd
& d ( (exp(C,mm) - 1)) n/2
1 (1 + ))11)p
where o = (1 + -= 7
2 x²), and Cp p-1. 1.
eny 2, then e. exexp
ž and the Lemma holds trivially. Otherwise, let ctn
20- Since t & e, Cyny pny
1²
1. Therefore, exp(Cyn1) -1 <cC,ny &
p/2 PP ( - (I+ + 1| > (1 + m))))) & 1-2 _))
12
dexp 22
e
Lemma A.7. Under Assumption 7 and with vi set according to Lemma A.2 with b n,
E ||,,11?
& exp (2v2nm max (2nc, log (d)) (1 + n
2n
where = 22 x²2). Moreover, 2n (1 + 2 (d) then
E Zn. EZ. 2 < 2 (1 log (d)) (1 + 2
Proof. Using Proposition
A.1
④ = (1 + )² and : 2(122 +22)
E||| ZZ. |1
Zm 12:2
(Ø Cp7)" " Zo 12-2 < (1 mn1)) 2n
exp (Cpny) | 12.2
Set p= max (2, 21og 70
Then,
Zz 1,22 = dt & exp
Therefore,
2
E[[|Z..|] & (1 + n 2m exp (2pm7) exp (2v 2ny max (2 log (d]) (1 27
27

---

For the second result, set p:= 2 (1 + log (d)). Then, Cpnyy & 1 by assumption and |Zoll, = dd/0 & Ve. By Proposition A.1
E Zm
& 12n - E [[Z,] 12.2 & (exp (Cpn7) 1) -) mjA1)" 1 [nn ]12]
< EpC (1 + m
26 n (1 2og (d)) (1 nd1)".
C.2 Proof of Lemma[4
Lemma A.8 (Lemma in main paper). Let Assumption hoold and 17 be set according to Lemma with b = Define
2(12M² + n²). 2n (1 2 log (d)) & 1, then
Tr [1 T Znn v1) < exp (2nmd) + 122n (Vo + x)))
d
5 (17 + K1)
exp (21ma (A1 -22)
" " X2)
Proof. Let 3e = := E V1 V.z.V.). for all 0 E & n. Then, for i [m].
B; Tr V (I+ A.) Z, 2T, (I AT) vi)]
E Tr V (1+ (I AT) V1) |F-
[ Tr [V] T (I+ (1.+ (I n/ V1) [o-
+ E E ( Z, Z. - |=-
The last line used E
0 and that Z,-1 is measurable with respect to F._. In other words,
8 = E Tr V T (I++)) Z, 2 (Y, V )} + E Tr Z E = V Vi [ (Z-1)) ):
For the first term, following the analysis of Lemma 10 of [6]
E E (v T (I+ [I+NY) Z Z, ( (I nY, nYY) V v < (1 2mdd + 17² (Vo + x;)) B + 72 [[ 2,12
$ (1 21122 + 1/2 (Vo xi)) B + Vo |
(A.19)
The second term can be bounded as
E Tr Z = T [1F.-Z--]
E Tr E
8. V.V.V
V J Z.-1ZT_1
E
[ Tr
[ V V
T= -..
12, Z,TT
K E
[|| 2Z 1|
(A.20)
Combining (A.19) and A.20). we obtain the recurrence
8, < (1 + Am + n?2 (Vo + x2) B + (n²2o + k1) Z7-
By Lemma A.7 we have for 7/ := 2(172M M2 2 + n²?),
B. < (1 + 2nd + 1 (Vo + x2)) 3: + (n²20- + k1) exp (2v 2ny (2/22m log d
(1 + 2(--1)
& exp (2m)2 7 (Vo + x?)) Bi + scxp (2m + 226 + 27))
28

---

where 8 = V k1) exp (2 logd). Unrolling the recursion,
2(n-11 1-
exp (2n + 1/² (Vo + xi))
3n < exp (2nnA1 + n (Vo A
exp (-2mm (A1 A2)) Bo -22)
exp (2m111 172 (Vo + x²))
r-0
< exp (2ynA1 + - n (Vo + )
exp (-2mm (A1 -22) 80 +
1 exp( 21 (A1 X2))
2.35s
exp (2 + n (Vo )
exp (-2m (A1 X2)) 90 +
21j (\1 X2)
5 + K1)
exp (2mnA1 n (Vo )
exp (-2mm (>1 X2)) d+
n) (A1 x2)
where the third inequality holds because I E 2.33(1 e =² for and the last inequality holds 2.35 exp 222 log d) 2.35 v2) < 5.
because Bo & d and
D Proofs of Theorems
and 3
D.1 Proof of Theorem
We are ready to present the proof of Theorem T which follows from the following Theorem A.4 and setting a constant failure probability for 0.
Theorem A.4. Fix 0 E 10. Then, for being the output of Algorithum under assumption
a lolo with is set as in Lemma A.2 learning rate lj b(1--1s) ->a)
R1 1/2, and
1
2e log (d/0) &
2
where 7 == 2 + x²). Then, with probability at least 1 30,
log (1/0)
d
5 (17 + K1)
sin?(w,vl
+ 8k1
83
cxp (2a log(n)
17 (>1 A2)
Proof.
Note that by Algorithm
1 and the definition of Z in (A.18).
Zgug Wb
7Z,uol ||
Since VIvI ViV1 Ida
V T Zguo
sin (ug. ==)== -1-
|| |Zb
By Lemma 6 from
JJK 16 with probability at least 1 - 0,
Tr V1 ZoZ,
sin (ub, v1) 2.5 log (1/0)
v ZoZZ, v1
By Lemma A.7 with and p- 2 (1 log (d)),
E ZZ - (I 1 Z [I イン p.2 & V bey (1 2 log (d)) (1 + 111)" (A.21)
For the numerator, we use Lemma A.8 and Markov's incquality to get
d exp (2mb (A1- -
5 ( + k1)
Tr V Z, exp (2nbd1 + 17b (Vo + +X))
7 - Ae)
(A.22)
with probability at least - 0.
29

---

The denominator can be bounded as
v1 - -Zo vi > (1+ (1+n - - Zo (I + ,
1 v1ll >
Using Lemma A.6 with probability atleast 0,
|Zovil| > (1 + 111) / 2/ee log (d/0) + n121)*
= (1+ n/11) (1 22ee2yy log (d/00)
3 exp (n11b 1 (1 v 2ee2ry log (d/0)
(A.23)
where the last line follows since (1 + x) 3 cxp (I x²) for all 2 3 From equa- tions (A.22). (A.33). and the assumption v by log (d/0) $ 1/2, it follows that with probability 1 30,
12 log (1/0)
d
3 ( + ki)
sin? 2 (ug, v1) &
(A.24)
A3
exp (2a log(n))
(>1 X2)
Since w Quu,, 2). by Lemma A.9 and using || & R. & 0.5,
|
||| ?
R²
sin 2 (w, up)
< 4k
(A.25)
[1, + E|
0.52
The result follows by using equations A.24)). A.25 and Lemmal A.5
D.2 Proofs of Theorems and
3
Next, we apply Theorem A.4 to analyze the quantized version of Oja's algorithm as described in Algorithm | The idea is to show that the error from the rounding operation be incorporated into the noise in the iterates of Oja's algorithm, which have mean zero. For this subsection, we will use:
X,XJ
D; = Σ
n/b
JEB,
where A; 7 (D: + E E2, (I D),
We first state and prove some intermediate results needed to prove Theorems 2 and Theorems 3 Theorem A.5. Let d, n. be N, and let (X,)sejn) be set of IID vectors in Rd satisfying assump- alo be the learning rate set as in Lemma A.2 Suppose the quantization grid =- b(1-Xa
tion
Q OL and / bbnn2 + d52 log (d/0) & 3. Then, with probability at least 0.9, the output w of Algorithm ssatisfies
24 log (1/0)
5 log (A1 X2)²
3065
sin?(w, (w.v1) v1)
log + 488
03
n2a
Proof. In order to apply Theorem we come up with valid choices of Vo. K, and K1.
Since each D, is symmetric and [ hie(m] are independent,
|[[[D, - E)(D, - -)
n/b | - -
&
6v
Vo.
(A.26)
n
Next,
E. uu S2,17_1 + (I DI
Also observe that
F[ 0,
[F 0,
ET F1.. 0,
(A.27)
30

---

By equation A.27
|| - -
+ +u 11 (T)(+++ "
68²
As for we have
| < 2(1 + noodd & 35v =:
We are now ready to obtain the sin-squared error. Note that M 2, since X; & 1 almost surely,
for all i E [n]. By Theorem A.4 with probability least 1 30,
24 24 (1/0)
d
5 (17 + k1)
sin ( v1)
&
+ 8.%1.
A3
exp (2a log(n))
(A1 X2)
long as 62 log (d/0)
1.4
Our parameter choices Vo n k 3 and K1 6ö2d.
24 (1/0)
50 log +
30652d
sin?(w,V) v1)
n2a +
aA1 x\2) logn + 4852d.
03
Lemma A.9. Let 11 (ww, QNL), where u E Rd and QNL is defined in equation
Then,
|| Q(w, @NL)l & 8ov |w|s
Proof. Let Q(w, 2NL) w. Say w, > Let be the unique integer such that w, [gk, [++1]. Equivalently for negative w,, say the bin is ++++ -ae- We have:
|E:l & Qk-1 dh 60 Cyu & |wals + 60
Thus have:
IIEll < dovd+ |w/ls.
Theorem A.6. Fix 0 E (0,1). Let the initial vector un N (). Let the number of batches b
and quantization scale 8 be such that b4n2 325 98(?) log (d/8) 1/2. Then, under
alogn assumption 7 with y set as b(} b())-X2)' where a is set as Lemma 4.2
8ov & 0.25, and Ç & 0.25,
with probability at least 36, the output wa of Algorithm gives:
24 log (1/8) sin? (w,v1) v1) &
d
5a logn n aAi A2)²
7()2
+ 8(48 2
03 na
log
Proof. In order apply Theorem we need to bound V, x and K1. We start with the first. For us, Dj is defined in E Let R, denote the random variables in the quantization up to and including the 7th update.
Our analysis analogous to the previous theorem. Note that the Vo parameter is as in Eq A.26
Now we will work out and since those are the only quantities that change for the nonlinear quantization. Recall that we have,
E. Era u E2,u,_ (I+ E..u
We have, | n' Lu
T
1. Euu nDD)(1 + t2.
31

---

Now we obtain the Frobenius norm of Ea,., É1, and & under the nonlinear quantization. We start with the norm of w,, a quantized version of a unit vector u,-1-
By Lemma
A.9
W:
dov Let
X wi). Then,
ss &
& 1 bov c. w;
Another application of Lemma A.9 gives:
| = [[Q(s,, QNL) sy & 50 v + (1 5. + 6 1.5Ç
which implies Ea,il & dov Next, we bound f1,- Q(u,,1, u1-1- By Lemma A.9
1Eis < dovdd u/|u 6ovd+
Finally we bound Ez, Recall that:
Yi = LEEB, Xx(X w:)
+ Ea.i
n/b
2, = Qy 0) -i
Since each | will < 1 + 8ov c.
ly./l < 1 8ovd c+ |E, < + 26 2.5Ç & 3.25.
By Lemma A.9
E & 6ovd+ C/yvll &
In all, it follows that
E & v.. + E2,ll + (1 e),ll & (ōov 1.5)) + (5ov + 3.25Ç) + 2(5bvd () & 48 7C =: K.
We are ready to obtain the sin-squared error. Note that M < 2, since |X:|| < almost surely, for all
i e [n]. By Theorem A.4 with probability at least 30,
24 (1/0)
d
5 (n + K1)
sin sin?(w, v1)
881.
exp (2a log(n))
17 (λ1 X2)
as long as by log (d/0) K1 (46ov d + 7 Therefore.
<
Our parameter choices are Vu
bV K
48 Vd + 7G. and
2"
24 log (1/0) sin?(w,v,) v1)
GaVlogn
5b 3b(4hov / / 72)2
+
+ 188000 +(466vVd+72)
03
n2a n (A1 - x2)² log
D.2.1 Finishing the Proofs of Theorems 2 and
Proof of Theorem For the linear quantization scheme, we apply Theorem A.5 with
1/30 and
a² log" a log Moreover, since 8 A
the condition
(Ar Az)²
b(4m) 982d) log (d/0) & holds. The Theorem follows by substituting these values into the bound of Theorem A.5
The proof of the logarithmic scheme follows analogously from Theorem A.6
Proof of Theorem We set 1/30. For the linear quantization scheme, we apply Theo- A.5 with b = n. Moreover, since 5 = 22-8 = O min A1ー
aavdlog(n) v the condition
rem
V 4b 4np2 982d) log (d/0) holds. The Theorem follows by substituting these values into the bound of Theorem A.5
For the non-linear scheme, the proof follows analogously from Theorem A.6
32

---

D.3 Optimal Choice of Parameters want to minimize the quantity
K1 := 6² 8gd,
where { 2- and dg 4 2-2% Here, 3m and B. are the number of bits used by the mantissa and the exponent, respectively, and satisfy the constraint
8m + Be = B.
Then.
2 = 2(8-)))) + 16d2 2 =: f(ee).
To find Be that minimizes f(3e) we differentiate with respect to Be and it to
(36) = 2 2(3 2(8-8a). Ba)
21 2 + 16d (2 (2-2th 1n (-2 In
2
8d2 8d2-2"
2 In 2 2 22
48
It is optimal to take Be such that
2- Sd 4 In
Equivalently, 8e + 2 23 logz (8d1n 2). This in particular implies
20 < 2,3 (8dg(88 29+11
so
23 + (8d (n 2) Be logg (23 + log (8d (8d In 2))
1ogg(8d
Therefore, choose
3 = [log2 (2g + log, (8d In 2))1 3 = B
This choice of 8 valid as long it does not make 8 non-positive. This true as long as 3 e max(8, log, (d)). With these values of 3 and 8%
2 log, (29 (Sd
2(2 (8d 2))
= 2 2
28
2
and
8 (4.2-207-1) = 2 2-2 & 16. (8dhh
2
4 2
E Proof of Boosting Lemma (Lemma 3
In this section, we present the proof of the boosting procedure. Our boosting procedure requires a modest assumption that the number of bits 3 4, which is already assumed in Section 3.4 while optimizing the parameters.
Proof of Lemma 3
Proof. For each [r], define the indicator random variable
X 1 (sin²(u;, v) $ <).
Then, by the guarantees of A, Pr(x: 1) > 1 p. where p 0.1. Let == (i [r] Xa 1), and define the event
m S|| 0.6r).
The Chernoff bound for the sum of independent Bernoulli random variables gives
8 [[|]]]
P ((S) < (1 0) [[[]]) & exp
A (0,1).
2
By linearity of expectation, E [[[]]] > (1 - p)r. Setting 0 = 1/3,
P (E*) & P (|S) & 0.6r) & e 20 $ 8.
33

---

It suffices to show that if the event & holds, then t is well-defined and has small sin- sin-squared error with v. Recall,
u, such that |(j [r] : (u, uj) 5e}] > 0.5r, Conditioned on E, any that belongs to the set S satisfies c; 0.6r. Indeed, Lemma A.5 gives for any i, E
sin (u; uz) & 2sin (u, v) 2sin (v. u,) & 4c,
which implies
(u; uy)l < sin
u, u₁) + t < 5e
because 4e within the range of the bounded grid (1(() : (e defined in 11 Therefore, the algorithm does not return 1 and is well-defined.
Now, (ū, ú, uy)l & 5c for at least 0.5r indices j ee [r] and |S| 3 0.6r. In particular, there exists an index 1 S for which (ă(ū, uy*)l & 5c. Since 5e is strictly inside the grid Qc(c), get sin [u, uy*) & 6e. We conclude
sin"(ū, v) & (u, uz) + 2sin"(u,, v) & 2(Ge) + 2e 14c.
Theorem A.7 puts everything together and applies Lemma to obtain the final high probability result.
Theorem A.7. Suppose A is the Oja's algorithm with the setting of Theorem 2 0or3 Let be the prob-
ability 0.9 error bound guaranteed by Theorem 2 [20 log 1/8)], and
Let (X.)ie(m) be
IID data drawn from distribution satisfying assumption / and uj A((X (1- Dnttsisjj for all j e [r]. Then, the output of algorithm satisfies
sin (u, v1) 14e
with probability at least 1 0.
Proof. The vectors up...., u, are mutually independent. By Theorem 0.1Vie [r]. Therefore, Lemma 3 applies and the theorem follows.
2 Pr (sin d (u;, v1) >
F Experimental Details
F.1
Additional Synthetic Experiments
Am 0.S, bits B, di 100
1- 0.5, bits - n- 5000
16a
A- 0.5, 1000, d= 100
10"
Idaed Lo
10"1
sutdted ALC
Aland LG saxiled
10
ai
10
1000
200
(a) Varying sample size n, fixed 100, bits 8.
(b) Varying dimension fixed 5000, bits
(c) Varying bits (3, fixed 1000.
d = 100.
Figure A.1: Variation of sin² with: (a) sample size, (b) dimension, and (c) quantization bits.
We generate synthetic datasets via the procedure described in [SW21] The generation process takes input the number of samples, n, the dimension d and eigenvalue decay parameter X. We defer the details of the generation process to the Appendix Section FF Given the sample size n, dimension d, and decay exponent in the eigenvalues, we first draw an n matrix with independent entries uniformly distributed on 33 v3] so that each coordinate has unit variance. We then build a kemnl matrix K e pddxd with entries Kij exp(-li ji and define variance profile o; 5
34

---

for = l....,d d. The population covariance is formed as Σ = Hadamard product. Computing the eigendecomposition of Σ yields its square root Σ and the observed data matrix taken as X (E We then extract the largest eigenvalues λ A2 of Σ and the associated top eigenvector on for evaluation. Figure A.1 shows the results for this dataset, which shows similar trends as the experiments described Figure
(aoT) K, where denotes the
F22 Real data experiments
This section presents experiments on two real-world datasets. For each dataset, we show sin" error with respect the true offline eigenvector. used as a proxy for the ground truth, varying with the number of bits. The results are plotted in Figure A.2
The goal this section determine whether real-world experiments reflect the behavior of batched vs. standard methods with linear and logarithmic quantization. Therefore, we use the eigengap computed offline as a proxy of the true eigengap. If we wanted to compute the eigengap an online manner, could split the dataset randomly into holdout set S and training set [n]] {S; run Oja" s algorithm with quantization on a range of eigengaps with outputs U1 Um, and select the one with the largest arg max, uf D, DjD J,, for held out set S.
100
7352, d = 561
10"
60000, 784
standard standard
standav_LL
standard_MLs NLO
hutiheed banchec.Lo
balched batched
Final sin sin-erro -error
batched
Final -arror
1
10-1
10
10
6
8
8
10
12
Bits
Bits
(a)
(b)
Figure A.2: Variation of sin -error with bits for (a) HAR dataset (b) MNIST dataset.
Time series missing data: The Human Activity Recognition (HAR) Dataset [AGO+
contains smartphone sensor readings from 30 subjects performing daily activities (walking, sitting, standing, etc.). Each data instance is 2.56-second window of inertial sensor signals represented as feature vector. Here, = 7352 and d = 561. For each datum, we also replace 10% of features randomly by zero to simulate missing data.
Image data: We use the MNIST dataset [LBBH98] of images of handwritten digits (0 through 9). Here, n = 60, 000, = 784, with each image normalized to a 28 x 28 pixel resolution.
These results collectively highlight that using the true offline eigengap (i) under stochastic rounding, batching provides a significant boost in performance since the quantization error does not depend linearly and (ii) the logarithmic quantization attains nearly dimension ffre quantization error in comparison to linear quantization across a wide range of number of bits.
G Related Work
In this section, we provide some more related work on low-precision optimization. (DPHZ23) duced QLoRA, which back-propagee propagates through frozen 4-bit quantized LLM into LoRA modules, enabling efficient finetuning of 65B- -ar-maraeteer models on single 48 GB GPU with full 16-bit performance retention. Earlier works [XMHK23] examined the impact of stochastic round-off errors and their bias on gradient descent convergence under low-precision arithmetic. (YGG+24) propose Collage, lightweight low- cow-precision scheme for LLM training in distributed settings, combining block-wise quantization with feedback error to stabilize large-scale pretraining. Fi- nally, communication-efficee distributed SGD techniques, such 1-bit SGD with error feedback
intro-
35

---

SFD 14] and randomized sketching primitives (e.g., Jownson Lindestn-s projections [L84 further underscore the broad efficacy of low-precision computation.
Low-Precision Optimization: Reducing the bit-width of model parameters and gradient updates has proven effective for alleviating communication and memory bottlenecks in large-scale learning. QSGD [AGL 17] uses randomized rounding to compress each coordinate to a few bits while pre- serving unbiasedness, incurring only an v/2) increase in gradient noise for 3 bits. [WXY+ 17 maps gradients to { 1- 0, +1} plus a shared scale and demonstrates negligible accuracy loss ImageNet and CIFAR benchmarks. [SYKMI7] achieve optimal communication-accuraa trade-offs randomized rotations and scalar quantization. More recently, "dimension-free analyses such as [LDS19] avoid scaling the required error rate with model dimension, instead depending on suitably defined smoothness parameter.
36


Reviews:
[{"review_id": "zpi3OWVrne", "reviewer": "Reviewer_4RCk", "summary": "The authors establish new lower bounds on linear and non-linear logarithmic quantized Oja's algorithm for streaming PCA. The bound is sharp (up to logarithmic factors) when batching is used. Error for log quantization is dimension-free, while linear quantization scaled with the dimension of the data points. The authors conduct empirical analysis over varying sample size, data dimension, and quantization bits, along with guidance for selecting optimal quantization hyperparameters when given a bit budget.", "questions": "1. What are the core challenges for extension to top-k? Namely, what prevents analysis over the deflated covariance matrix (once the previous component is found)? \n\n2. Is assumption 1 unreasonable? I'm not asking because I believe it's unreasonable, I just do not know if it's used in other similar results besides [1]. For example, streaming convergence for the power method with momentum in [2] does not seem to rely on assumptions regarding the distributions of entries in the X_i. \n\n[1] Kumar, S., & Sarkar, P. (2024). Oja's Algorithm for Streaming Sparse PCA. arXiv preprint arXiv:2402.07240.\n\n[2] Xu, P., He, B., De Sa, C., Mitliagkas, I., & Re, C. (2018, March). Accelerated stochastic power iteration. In International Conference on Artificial Intelligence and Statistics (pp. 58-67). PMLR.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n - A novel lower bound for a very classical algorithm (Oja + streaming PCA) with strong applications to machine learning. Indeed, it surprises me that such a result for quantized streaming PCA using Oja's rule had not already been established in literature. Bounds for both linear and logarithmic are provided, which enables flexibility on quantization procedure. \n\n - Very easy to read -- the review of streaming PCA, Oja's algorithm, and quantization + stochastic rounding will be comprehensible for those outside of numerical optimization. \n\n - The lower bound is sharp (up to algorithmic factors) when batching is used, demonstrating the utility of the bound. \n\n - Explicit determination of optimal quantization parameters under a fixed budget makes these bounds practically useful as well. \n\n - Reduction of linear dependence on dataset size to logarithmic dependence via batching is a nice result. \n\nWeaknesses\n\n - Results do not apply to extraction of top-k components. \n\n - I find the proof techniques in the manuscript do not necessarily reveal enough intuition for the core results. Deeper proof sketches of the core theorems would be helpful.", "was_revised": true, "final_justification": "I am maintaining my score. I find this bound interesting as this result seemingly doesn't already exist in literature for such a classical method (Oja's method). At least one reviewer has complained that some knowledge of the spectral gap is required but observe that is the case with similar literature [1,2]. Spectral-free knowledge which results in accelerated convergence seems notoriously difficult to acquire.\n\n[1] Xu, Peng, et al. \"Accelerated stochastic power iteration.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2018.\n\n[2] Rabbani, Tahseen, et al. \"Practical and fast momentum-based power methods.\" Mathematical and Scientific Machine Learning. PMLR, 2022.", "rebuttal": "Thank you for your valuable feedback on the readability of our paper and the novelty of our lower bounds. We agree that providing more intuition makes the core ideas more accessible, and we will expand the proof sketches in a revised version of the paper.\n\n## Regarding the top $k$ components\nWe believe our techniques can be extended to the top $k$ components via a deflation-based approaches (see [9,10]). Currently, our algorithm assumes the gapped setting where $\\lambda_1 > \\lambda_2$. Extending it to the top $k$ components may require the assumption and knowledge of all eigengaps $\\lambda_1 - \\lambda_2, \\lambda_2 - \\lambda_3, \\dots, \\lambda_{k}-\\lambda_{k+1}$.\n\nWe discuss what we believe is a barrier to extending our analysis to k-PCA with the deflation-based method, as requested by the reviewer, below. However, we want to point out that we believe that k-PCA methods that maintain $k$ vectors and perform QR decomposition at every step (see e.g. [5, 14]) would provide sharper bounds with less stringent assumptions. This is part of ongoing work. \n\n### **Deflation based methods** \nA standard deflation approach splits the data stream into $k$ chunks. For each chunk $C_i$, construct the projection matrix $P_{i-1}$ that removes the first $i-1$ estimated eigenvectors, and then estimate the leading eigenvector of $P_{i-1} \\left(\\sum_{j\\in C_i} X_j X_j^{\\top}\\right) P_{i-1}$. Because Oja’s updates use only matrix–vector products, the method remains fully streaming with $O(kd)$ memory. For quantized streaming PCA, one must also consider the accumulation of quantization errors from each eigenvector estimate. We expect that the martingale-based arguments should hold since the new datapoints become $P_{i-1}X_j$ for some fixed matrix $P_{i-1}$ (independent of $X_j$ in chunk $C_i$). However, the main barrier appears from the fact that one needs to make sure that the eigengap $\\lambda_i-\\lambda_{i+1}$ is larger than the errors accumulated up until now, which is $O(i\\Delta)$ where $\\Delta$ is the maximum $\\sin$ error over the $i$ chunks. \n\n## Regarding assumption 1\nAssumption 1 states standard moment bounds used to analyze PCA in the stochastic setting. These assumptions are also used in citations [1-7] to derive near-optimal sample complexity bounds for Oja’s rule. We note that while the current analysis assumes a bounded set, this is for ease of analysis, and it can be generalized to unbounded subgaussian data (see [11,12,13]). \n\nFor ease of exposition, we will provide an easy argument that changes the algorithm by considering \"truncated\" datapoints $Y_i := X_i 1 (||X||_{i}^{2} \\leq \\alpha_n)$, where the truncation parameter $\\alpha_n$  is set to be $c\\log(n)$. Thus we replace any datapoint whose squared norm exceeds the truncation parameter by zero. Standard truncation arguments can then show that the sin-squared error of the output of this algorithm w.r.t the original principal eigenvector has the same theoretical guarantee.\n\nEquation (1) in the Section titled “Stochastic PCA” in Accelerated stochastic power iteration (citation [8]) states their assumptions; **in fact, [8] uses a stronger assumption than ours.** The matrix $A$ in their paper is the covariance matrix $\\Sigma$, the matrices $\\tilde{A}_t = X_t X_t^{\\top}$, and the almost sure bound $r = \\mathcal{M}$. One difference is that the [8] use the bound $E[\\left\\lVert XX^{\\top} - \\Sigma \\right\\rVert ^2] \\le \\sigma^2$, while we use the weaker assumption $\\left\\lVert E[ (XX^{\\top} - \\Sigma)^2] \\right\\rVert \\le \\mathcal{V}$; note that $\\left\\lVert E[ (XX^{\\top} - \\Sigma)^2] \\right\\rVert \\le E[\\left\\lVert XX^{\\top} - \\Sigma \\right\\rVert ^2]$ by Jensen’s inequality.\n\n### **References**\n[1] Moritz Hardt and Eric Price. The noisy power method: a meta algorithm with applications. NeurIPS 2014.\n\n[2] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. ICML 2015.\n\n[3] Ohad Shamir. Convergence of stochastic gradient descent for PCA. ICML 2016. \n\n[4] Ohad Shamir. Fast stochastic algorithms for SVD and PCA: convergence properties and convexity. ICML 2016.\n\n[5] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-PCA: a global gap-free and near-optimal rate. FOCS, 2017.\n\n[6] Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming PCA: Matching matrix Bernstein and near-optimal finite sample guarantees for Oja’s algorithm. COLT, 2016.\n\n[7] Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. COLT, 2016\n\n[8] Xu, P., He, B., De Sa, C., Mitliagkas, I., & Re, C. (2018, March). Accelerated stochastic power iteration. In International Conference on Artificial Intelligence and Statistics (pp. 58-67). PMLR.\n\n[9] Jambulapati, Arun, et al. \"Black-box k-to-1-PCA reductions: Theory and applications.\" COLT 2024\n\n[10] Mackey, Lester. \"Deflation methods for sparse PCA.\" Advances in neural information processing systems 21 (2008).\n\n[11] Lunde, Robert, et al \"Bootstrapping the error of Oja's algorithm.\" NeurIPS 2022.\n\n[12] Kumar, S., & Sarkar, P. (2024). Oja's Algorithm for Streaming Sparse PCA. arXiv preprint arXiv:2402.07240.\n\n[13] Liang, Xin. \"On the optimality of the Oja’s algorithm for online PCA.\" Statistics and Computing 33.3 (2023): 62.\n\n[14] De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates. COLT, 2021."}, {"review_id": "1gwurzQsTv", "reviewer": "Reviewer_Bmfn", "summary": "The paper gives quantized version of Oja's algorithm for streaming PCA under both linear and logarithmic quantization schemes along with randomized rounding. They give lower bounds on quantization error for both quantization schemes. The batched versions of their algorithms almost match the lower bounds. The Non logarithmic quantization scheme can achieve errors which are independent of the dimension and hence very useful in high dimensions. The authors also give a way to boost the success probability of their algorithm. They validate their guarantees by experiments on synthetic data.", "questions": "See Weaknesses", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1) PCA is a very important problem in machine learning. Addressing the problem of finding out principal components in low precision scenario is an important and interesting problem.\n2)Lower bounds for quantization errors for linear and nonlinear quantization schemes and algorithms that almost matches the lower bounds.\n3) The algorithm is easy to understand and appears simple to implement too. \n4) I did not check the proofs in detail however the results appear correct and sound. \n\nWeaknesses and Suggestions:\n1) Overall, I did not like the writing of the paper. Better notational convention can be used. Also, there are typos. For e.g. I think there is a misplaced or additional bracket in eq. (3). Please correct me if I am wrong. In all equations involving product over terms, e.g. eq. (7) why is the lower limit of product $b$ and upper limit $1$. Again, it appears weird to me unless I missed something.\n2) Experiments are only performed on small set of synthetic data.", "was_revised": true, "final_justification": "I have modified my score base on rebuttal. But I would urge the authors to improve the presentation and explicitly explain the multiplications happening to remove confusions", "rebuttal": "Thank you for your valuable feedback. We will fix all typographical errors in the revision; in particular, the second value in the set of equation (3) should be $-\\delta \\cdot (2^{\\beta-1}-1)$ instead of $-\\delta \\cdot ((2^{\\beta-1}-1)+1)$.\n\n## Lower and upper limits in matrix product \n\nEach iteration of the Oja’s algorithm has a gradient update $u_{t+1}=(I+\\eta X_{t+1}X_{t+1}^T)u_{t}$ followed by normalization $u_{t+1} = u_{t+1}/\\left\\lVert u_{t+1} \\right\\rVert$. As a result, the final vector $u_T$ be unwound into the (normalized) product of n matrices successively left-multiplied to the initial vector $u_0$.\nThe crucial observation here is that the first term in the matrix from the left uses the _last_ data point, while the rightmost matrix corresponds to the _first_ data point. This is why the lower and upper limits go backward. We will clarify this notation in the revision.\n\n## Experiments\n\nWe conducted additional experiments on both synthetic and real-world datasets. For real-world datasets, we consider the top eigenvector of the sample covariance matrix of the data as the ground truth. All experiments below show the $\\sin^2$ error with respect to the ground truth eigenvector. For all three datasets, **we observe that the trends of these experiments are similar to those presented in our paper**. In particular, we observe that, in general,\n\n1) All quantized methods perform better as the bit budget increases. \n2) Batched methods outperform their analogues with per-iterate updates.\n3) NLQ outperforms LQ for a given bit budget.\n\n### **Additional Synthetic Data** \n\nOur first experiment considers covariance matrices generated using a random orthonormal basis $Q$, chosen by performing QR decomposition of $Z$ such that $Z_{i,j} \\sim N(0,1)$ with eigenvalues decaying as $\\lambda_{i} := i^{-2}$. We use $n=10,000$ and $d=100$.\n\n| Method             | 4 bits           | 6 bits           | 8 bits           | 10 bits          | 12 bits          |\n| ------------------ | ---------------- | ---------------- | ---------------- | ---------------- | ---------------- |\n| Standard Oja       | 0.004 ± 5.92e-17 | 0.004 ± 3.63e-17 | 0.004 ± 2.22e-17 | 0.004 ± 5.97e-17 | 0.004 ± 2.96e-17 |\n| Standard Oja + LQ  | 0.960 ± 0.017    | 0.454 ± 0.019    | 0.109 ± 0.005    | 0.016 ± 7.16e-04 | 0.005 ± 1.55e-04 |\n| Standard Oja + NLQ | 0.297 ± 0.010    | 0.117 ± 0.005    | 0.030 ± 0.001    | 0.010 ± 4.98e-04 | 0.006 ± 1.36e-04 |\n| Batched Oja        | 0.006 ± 0.004    | 0.002 ± 0.002    | 0.001 ± 6.13e-04 | 0 ± 1.99e-06     | 0 ± 7.21e-08     |\n| Batched Oja + LQ   | 0.572 ± 0.013    | 0.068 ± 0.002    | 0.005 ± 1.55e-04 | 0 ± 2.03e-05     | 0 ± 3.14e-06     |\n| Batched Oja + NLQ  | 0.033 ± 0.001    | 0.005 ± 2.41e-04 | 0.001 ± 3.47e-05 | 0 ± 1.58e-05     | 0 ± 5.01e-06     |\n\n### **Image data** \n\nWe use the **MNIST dataset**, which comprises grayscale images of handwritten digits (0 through 9). Here, n = 60,000, d = 784, with each image normalized to a 28 × 28 pixel resolution. \n\n| Method             | 4 bits           | 6 bits           | 8 bits           | 10 bits          | 12 bits          |\n| ------------------ | ---------------- | ---------------- | ---------------- | ---------------- | ---------------- |\n| Standard Oja       | 0.063 ± 1.22e-10 | 0.063 ± 2.13e-10 | 0.063 ± 1.94e-10 | 0.063 ± 1.90e-10 | 0.063 ± 2.66e-10 |\n| Standard Oja + LQ  | 0.997 ± 0.002    | 0.93 ± 0.009     | 0.421 ± 0.008    | 0.143 ± 0.002    | 0.07 ± 0.001     |\n| Standard Oja + NLQ | 0.511 ± 0.030    | 0.226 ± 0.008    | 0.110 ± 0.003    | 0.072 ± 9.98e-04 | 0.066 ± 5.31e-04 |\n| Batched Oja        | 0.372 ± 0.106    | 0.268 ± 0.081    | 0.270 ± 0.095    | 0.021 ± 0.026    | 0.020 ± 0.012    |\n| Batched Oja + LQ   | 0.887 ± 0.010    | 0.273 ± 0.007    | 0.050 ± 8.32e-04 | 0.030 ± 2.76e-04 | 0.030 ± 2.15e-04 |\n| Batched Oja + NLQ  | 0.067 ± 0.056    | 0.034 ± 5.57e-04 | 0.030 ± 2.62e-04 | 0.029 ± 1.49e-04 | 0.031 ± 2.11e-04 |\n\n### **Time series data** \n\nThe **Human Activity Recognition (HAR) dataset** contains smartphone sensor readings from 30 subjects performing daily activities (walking, sitting, standing, etc.). Each data instance is a 2.56-second window of inertial sensor signals represented as a feature vector. We have (n = 7,352, d = 561), and the data constitutes a time series. \n\n| Method             | 4 bits           | 6 bits           | 8 bits           | 10 bits          | 12 bits          |\n| ------------------ | ---------------- | ---------------- | ---------------- | ---------------- | ---------------- |\n| Standard Oja       | 0.013 ± 3.19e-10 | 0.013 ± 1.56e-09 | 0.013 ± 4.12e-10 | 0.013 ± 4.31e-10 | 0.013 ± 3.74e-10 |\n| Standard Oja + LQ  | 0.998 ± 2.33e-04 | 0.871 ± 0.016    | 0.305 ± 0.003    | 0.087 ± 0.002    | 0.028 ± 5.94e-04 |\n| Standard Oja + NLQ | 0.455 ± 0.014    | 0.157 ± 0.004    | 0.068 ± 0.001    | 0.033 ± 9.53e-04 | 0.020 ± 3.96e-04 |\n| Batched Oja        | 0.822 ± 0.025    | 0.670 ± 0.075    | 0.053 ± 0.053    | 0.063 ± 0.005    | 0.005 ± 0.010    |\n| Batched Oja + LQ   | 0.943 ± 0.005    | 0.405 ± 0.006    | 0.041 ± 0.001    | 0.009 ± 1.05e-04 | 0.006 ± 3.60e-05 |\n| Batched Oja + NLQ  | 0.047 ± 5.58e-04 | 0.013 ± 1.86e-04 | 0.007 ± 8.97e-05 | 0.007 ± 2.64e-05 | 0.006 ± 1.33e-05 |"}, {"review_id": "Ks6cxbVMjn", "reviewer": "Reviewer_3qrH", "summary": "This paper presents a rigorous study of low-precision algorithms for streaming principal component analysis (PCA). The motivation stems from the increasing need to perform high-dimensional data processing under severe memory and bandwidth constraints. The authors propose variants of Oja’s algorithms that apply quantization to either gradients or data, and they analyze their convergence properties under both linear and logarithmic stochastic quantizations. \n\n1. Quantized Oja's Algorithm: The authors generalize Oja's method to the setting where the data or gradients are low-precision representations, and rigorously analyze its convergence to the leading eigenvector of the data covariance matrix.\n3. Theoretical Guarantees: They provide non-asymptotic convergence bounds under various quantization models (e.g., unbiased stochastic quantizers and one-bit compression), and establish trade-offs between quantization level, convergence rate, and variance.\n4. Lower Bound: A matching lower bound is provided for the streaming PCA problem under quantization constraints, characterizing the inherent difficulty of the task.\n5. Empirical Validation: Experiments on synthetic and real-world datasets validate the theoretical findings, demonstrating that low-precision algorithms can achieve nearly the same accuracy as full-precision ones at a fraction of the communication cost .", "questions": "--\nWhy do you need to quantize every step of the algorithm? Why can’t you compute a final update and quantize that? In particular, I find what is the purpose of the quantization in Line~5, Algorithm~1?", "limitations": "--\nUse of excessive hyperparameters whose knowledge might not be known priori.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths: \nThis is a good algorithm for streaming PCA with low computational precision. The particular novelty lies in designing the algorithm (as in when to quantize). The probability boosting framework is standard and of course, it comes at the cost of additional space and memory.\nThe proofs follow a standard decomposition of the projection error and matrix product concentration.\n\nWeakness:\n\n-- \nSome theoretical results depend heavily on simplifying assumptions about data distributions or quantization noise, and may not fully reflect practical scenarios (e.g., non-iid or adversarial data). See for example, Robust Streaming PCA NeurIPS 2022, which considers one such practical model for this problem.\n\n--\nThe learning rate requires knowledge of spectral gap. This is unreasonable in practice.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback and for recognizing the novelty in our work. \n\n## Assumptions about data distribution, quantization noise, and non-IID/adversarial data\nBelow we sketch that the assumptions we use are widely adopted in streaming PCA and quantization literature. We also provide a discussion of how to adapt our techniques to non-IID settings.\n\n### **Assumptions about data distributions**\n\nAssumption 1 states standard moment bounds used to analyze PCA in the stochastic setting. These assumptions are also used in citations [5-12] to derive near-optimal sample complexity bounds for Oja’s rule.\n\n### **Quantization noise**\n\nThe quantization schemes we use have been widely used by other works [1,2,3,4]. As we discuss below, our analysis can be readily adapted to the following quantization schemes commonly used in low-precision computing.\n\nThe Floating Point Quantization (FPQ) is widely adopted and is a type of Logarithmic quantization scheme, where adjacent values in the quantization grid are multiplicatively close. Logarithmic schemes are of wide practical interest and are used in most modern programming languages such as C++, Python, and MATLAB, and are standardized for common use (such as the IEEE 754 floating point standard [19]). Another quantization scheme used for low-precision training is power-of-two quantization [16], where any value x is rounded down to the nearest power of two. This is yet another type of logarithmic quantization.\nLogarithmic quantization is similar in principle to the non-linear quantization (NLQ) scheme we use in our work. In particular, Lemma A.9 in the appendix establishes a relationship between the distance of a quantized vector and the original one under NLQ. This Lemma applies to FPQ and more generally, to most other logarithmic quantization schemes. We believe that **our proofs can be modified to work with any logarithmic scheme**. \n\n### **Non-IID or adversarial data** \n\nIn the streaming PCA literature, we are aware of the following extensions to non-IID data.\n\n**Independent but non-identically distributed data**: Robust Streaming PCA ([3]) handles data generated from covariance matrices that change over time (while being in the family of spiked models with $k$ spikes). Their analysis tracks the error accumulated from the mismatch of the varying covariance matrices with the last one in each batch. We believe that our rounding algorithm and analysis can be used to replace the part that considers matrix concentration.\n\n**Markovian datasets**: [18] analyzes Oja’s algorithm for Markovian datasets. We believe that our analysis, which incorporates martingale noise resulting from quantization, can be easily combined with their analysis to obtain results for Markovian data. \n\n**Adversarial or contaminated data**: The proof techniques here are vastly different ([13,14,17]) and would require substantially different tools. This presents an interesting direction for future work.\n\nWe believe that our work represents a **first step in exploring quantized streaming PCA** algorithms, which can be built upon to analyze various extensions.\n\n## Hyperparameters and learning rate\n\n**Only two hyperparameters**: Parameters such as $\\mathcal{V}$ and $\\mathcal{M}$, and quantization parameters $\\delta, \\alpha, \\delta_0$, are required for analysis only. **Hence, these are not hyperparameters.**\n\nThe only two hyperparameters required by Algorithm 1 are the batch size $b$ and the learning rate $\\eta$. The optimal choice for both is determined by the spectral gap $\\gamma = \\lambda_1 - \\lambda_2$.\n\n**Learning rate and eigengap**: The expression for the learning rate $\\eta = \\frac{\\alpha \\log n}{n (\\lambda_1 - \\lambda_2)}$ is also present in other works on streaming PCA [5-12] to derive the statistically optimal sample complexity (up to logarithmic factors). In particular, Theorem 1 (lines 165-166) in our paper shows that the error in the output vector is \n\n$d e^{-n\\eta (\\lambda_1-\\lambda_2)}+\\frac{\\eta \\mathcal{V}}{\\lambda_1-\\lambda_2}+\\max(\\frac{b}{\\alpha\\log n}, 1) \\kappa_1. $\n\nIf a smaller learning rate $\\eta$ is used (for example, from plugging in an upper bound $U$ on the eigengap $(\\lambda_1 - \\lambda_2)$ and using a crude upper bound $\\eta = \\frac{\\alpha \\log n}{n U}$ instead of $\\eta = \\frac{\\alpha \\log n}{n (\\lambda_1 -\\lambda_2)}$ will make the first term larger, leading to a slightly larger sin-squared error. A similar argument shows that the batch size is also robust to the choice of an upper bound on the eigengap. We will clarify this further in the revised manuscript.\n\n## Quantization at every step of the algorithm\n\nOur motivation for this study was to study the theoretical convergence guarantess of PCA in low-precision settings, which improves runtimes in practice. In the low-precision setting, intermediate values stored in memory have a limited number of bits, leading to quantization errors at every intermediate step [1-4]. We model this behavior by (i) quantizing at points where computed values are stored in memory, and (ii) fundamental arithmetic operations such as addition, multiplication, dot products, and matrix-vector products are quantized after being computed in high precision. In Line 5, Algorithm 1, the intermediate summands are quantized because they are stored in memory. We quantize again after summing the values. \n\nWhile in some settings, it may be reasonable to quantize at the final step, in this paper, we analyze streaming PCA in a low-precision setting, where intermediate values stored in memory have a limited number of bits. When the quantization is applied at the last step, the analysis is straightforward since the final error is equal to the sum of the error without quantization and the additional error $\\delta$ introduced by quantizing the final result.\n\n## References\n\n[1] Courbariaux, Matthieu, Yoshua Bengio, and Jean-Pierre David. \"Training deep neural networks with low precision multiplications, 2014.\"\n\n[2] Li, Zheng, and Christopher M. De Sa. \"Dimension-free bounds for low-precision training.\" NeurIPS 2019. \n\n[3] De Sa, Christopher, et al. \"High-accuracy low-precision training.\"\n\n[4] Das, Dipankar, et al. \"Mixed precision training of convolutional neural networks using integer operations.\" ICLR 2018. \n\n[5] Moritz Hardt and Eric Price. The noisy power method: a meta algorithm with applications. NeurIPS 2014.\n\n[6] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. ICML 2015.\n\n[7] Ohad Shamir. Convergence of stochastic gradient descent for PCA. ICML 2016. \n\n[8] Ohad Shamir. Fast stochastic algorithms for SVD and PCA: convergence properties and convexity. ICML 2016.\n\n[9] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-PCA: a global gap-free and near-optimal rate. FOCS, 2017.\n\n[10] De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k-PCA: Efficient guarantees for Oja’s algorithm, beyond rank-one updates. COLT, 2021. \n\n[11] Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming PCA: Matching matrix Bernstein and near-optimal finite sample guarantees for Oja’s algorithm. COLT, 2016.\n\n[12] Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. COLT, 2016\n\n[13] Diakonikolas, Ilias, et al. \"Nearly-linear time and streaming algorithms for outlier-robust PCA.\" ICML 2023.\n\n[14] Cheng, Yu, Ilias Diakonikolas, and Rong Ge. \"High-dimensional robust mean estimation in nearly-linear time.\" SODA 2019.\n\n[15] Bienstock, Daniel, et al. \"Robust streaming PCA.\" NeurIPS 2022.\n\n[16] Przewlocka-Rus, D., Sarwar, S.S., Sumbul, H.E., Li, Y. and De Salvo, B., 2022. Power-of-two quantization for low bitwidth and hardware compliant neural networks. arXiv preprint arXiv:2203.05025.\n\n[17] Price, E. and Xun, Z., 2024, October. Spectral guarantees for adversarial streaming PCA. FOCS 2024.\n\n[18] Kumar, S. and Sarkar, P.. Streaming PCA for Markovian data. NeurIPS 2023.\n\n[19] Kahan, William. \"IEEE standard 754 for binary floating-point arithmetic.\""}, {"review_id": "Yu4ZLvcXSP", "reviewer": "Reviewer_6QDR", "summary": "The authors proposed a low-precision version Oja's algorithm for streaming PCA, in which the iterates and the samples and the gradients are all quantized, and showed that its batched version achieves optimal estimation error rates, under either linear quantizer (LQ) and nonlinear quantizer (NLQ). The take-away lies on the advantage of NLQ in achieving nearly dimension-free estimation error.", "questions": "1. Can the authors further clarity the motivations/applications of their problem setting?  I am a bit confused about the \"quantization constraint\" -- specifically, what kind of quantization information one can use to estimate $v_1$ in the authors' setting. \n\nIn the algorithm, the authors quantize everything (samples, gradient, iterates) -- is this motivated by some practical regimes, or can we only quantize the samples?  Even only quantizing the samples, the problem distinguishes with some problems I know of where the samples should be quantized before running the algorithms (e.g., see \"Distributed gaussian mean estimation under communication constraints: Optimal rates and communication-efficient algorithms\"). \n\n2. The phenomenon that NLQ is statistically much better than LQ is new to me. I understand that this stems from the choice of the relevant parameters -- which nonetheless appears less straightforward to the readers. \n\nCan the authors provide some intuition that leads to such difference? Are there similar results appearing in other low-precision estimation problems?\n\n3. The authors studied two specific quantizers. Can the authors' method work other quantizers? Or can the authors explain why they specifically consider these two quantizers?", "limitations": "The limitation has been listed as questions above.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n\n1) The paper conveys rather clear messages - NLQ achieves faster nearly dimension-free rate - and batched version (or sample splitting) leads to much better performance. \n\n2) The results provide a clear understanding on the problem - the authors established lower bounds and matching upper bounds (by quantized batched Oja's). In view of Sec. 4, the proof techniques are nontrivial with some novelty. \n\n3) The experiments nicely back up the theory.\n\nWeaknesses:\n\n1) Some ambiguity in notation: P3 only defines $\\|.\\|_2,\\|.\\|_{op}$, while later $\\|.\\|$ is frequently used (e.g., Assumption 1, Eqs. 8-9)\n2) The weakness is that the motivation of such study should be made clearer.", "was_revised": true, "final_justification": "I maintain my current rating. The authors' responses address my main concerns and promote my understanding to their work. The setting differs from a standard estimation problem under quantization, in that everything is quantized throughout the computational procedure. The results are novel and interesting.", "rebuttal": "Thank you for your valuable feedback on the clarity of our paper and the novelty of our results. We will clarify the motivation of our work and make our notations consistent in a revision.\n\n## Motivation\nHardware accelerators—TPUs, for instance—derive much of their speed advantage from relying on low-precision arithmetic. In this paper, we analyze streaming PCA in a low-precision setting, where intermediate values stored in memory have a limited number of bits. This leads to quantization errors at every intermediate step [1-4].  We model this behavior as follows: (i) quantize at points where any computed values are stored in memory, and (ii) fundamental arithmetic operations such as addition, multiplication, dot products, and matrix-vector products are quantized after being computed in high precision. \nNote that this is different from only quantizing the samples, as the latter allows computed quantities to be stored in high precision.\nWhen operating with $\\beta$-bits, the overall complexity for streaming PCA (and that of the batched variant) is $O(nd\\beta)$. We performed a benchmarking experiment to illustrate this below. \n\n| Experiment | Runtime (seconds) |\n| ---------- | -------------------- |\n| 64 bits  | 0.0274 ± 0.00136  |\n| 32 bits  | 0.0260 ± 0.00225  |\n| 16 bits  | 0.000398 ± 0.0000235 |\n\n## NLQ is statistically much better than LQ\nNon-linear quantization (NLQ) is a type of logarithmic scheme where adjacent points in the quantization grid are multiplicatively close, that is, the error due to quantization in NLQ is proportional to the value itself. On the other hand, the linear quantization (LQ) scheme has an additive error, which can be (i) lossy when the value being quantized is small (see [2]), and (ii) needlessly accurate if the values are large.\n\nIn Oja’s algorithm with quantization, the learning rate is small, and the updates to the values are themselves small. If the error due to quantization is additive and of the same order as the value itself, then the direction of the gradient is significantly different compared to when the coordinates of the gradient directions are correct up to multiplicative factors. \n\n## Regarding Quantization Schemes \nThe quantization schemes we use have been widely used by other works [2-5]. As we discuss below, our analysis can be readily adapted to the following quantization schemes commonly used in low-precision computing.\n\nThe Floating Point Quantization (FPQ) is widely adopted and is a type of Logarithmic quantization scheme, where adjacent values in the quantization grid are multiplicatively close. Logarithmic schemes are of wide practical interest and are used in most modern programming languages such as C++, Python, and MATLAB, and are standardized for common use (such as the IEEE 754 floating point standard [6]). Another quantization scheme used for low-precision training is power-of-two quantization [1], where any value is rounded down to the nearest power of two. This is yet another type of logarithmic quantization.\nLogarithmic quantization is similar in principle to the non-linear quantization (NLQ) scheme we use in our work. In particular, Lemma A.9 in the appendix establishes a relationship between the distance of a quantized vector and the original one under NLQ. This Lemma applies to FPQ and more generally to most other logarithmic quantization schemes. We believe that **our proofs can be modified to work with any logarithmic scheme, including FPQ**. \n\n### **References**\n\n[1] Przewlocka-Rus, Dominika, et al. \"Power-of-two quantization for low bitwidth and hardware compliant neural networks.\" arXiv preprint arXiv:2203.05025 (2022).\n\n[2] Courbariaux, Matthieu, Yoshua Bengio, and Jean-Pierre David. \"Training deep neural networks with low precision multiplications, 2014.\"\n\n[3] Li, Zheng, and Christopher M. De Sa. \"Dimension-free bounds for low-precision training.\" NeurIPS 2019. \n\n[4] De Sa, Christopher, et al. \"High-accuracy low-precision training.\"\n\n[5] Das, Dipankar, et al. \"Mixed precision training of convolutional neural networks using integer operations.\" ICLR 2018.\n\n[6] Kahan, William. \"IEEE standard 754 for binary floating-point arithmetic.\""}, {"review_id": "9IEbyqXkn1", "reviewer": "Reviewer_nH8S", "summary": "Partially motivated by the advances of using limited precision arithmetic in neural networks, the authors study the effect of quantization on streaming PCA, restricted to finding the eigenvector with the largest eigenvalue. In particular, they analyze Oja's algorithm with two quantization schemes (linear and nonlinear), giving bounds on the \"difference\" of their approximated eigenvector and the optimal one. Additionally, the authors support their theoretical findings with a suite of experiments.", "questions": "Key points:\n\n- Is the length of the stream $n$ fixed beforehand or can $n$ grow over time?\n- Why there is no $\\beta$ dependence in Lemma 1 and Lemma 2?\n- What is meant by $\\prod_{i=b}^1$ applied to a vector? E.g., line 143 and (7).\n- In line 164, isn't everything on the l.h.s. constant and the assumption always holds? Or is $n$ increasing?\n- Theorem 1/2: What is $\\alpha$? \n\nFurther questions/remarks:\n\n1. Do the authors require a bounded input set?\n2. In line 59, is there no $n$ dependence for constructing and diagonalizing $\\hat \\Sigma$?\n3. Can the authors clarify in the beginning, what they mean by \"nearly dimension-free\"? From my understanding, the dimension enters the error only logarithmically; this should be made explicit.\n4. The norms in Assumption 1 are not made explicit: Is the expectation over the operator norm and the a.s. bound over the Frobenius norm?\n5. In line 99, is $\\beta \\in \\mathbb N_{>0}$? \n6. In (3), what is the -1+1 for?\n7. In the logarithmic scheme, line 107: Is it the same $\\beta$ introduced for linear quantization?\n8. In line 112, the authors state that they elaborate the stochastic rounding for linear quantization, but the equations concern $\\mathcal Q_{NL}$, i.e., nonlinear quantization?\n9. In line 113, can the authors make \"well within the range\" explicit?\n10. In line 114, do $l$ and $u$ have index $i$? Or what do the $i$-s in (5) refer to? \n11. In line 193, how explicitly were $\\beta_e$ and $\\beta_m$ chosen? \n12. From which dataset was Figure 1 created? How was $b=10$ chosen? According to Theorem 2, $b$ depends on $n,\\alpha$ and the eigengap $\\lambda_1-\\lambda_2$?\n13. Algorithm 2: Line 5 does not depend on $i$, can it be moved out of the loop?\n\nA few notes on typos/grammar:\n- In line 46, is $\\eta>0$ missing?\n- In line 68, space before the reference.\n- It could help to refer to the existence of the supplement in the outline (line 82-85).\n- In line 87, it seems that $0\\not \\in [n]$; this should be made explicit, e.g., by using $\\mathbb N_{>0}$ as $\\mathbb N$ is ambiguous.\n- Euclidean: Capitalize.\n- In line 122, use \"the norm of the estimated $\\mathbf u$\".\n- Sometimes the authors use \"Eq.\", sometimes \"equation\", e.g., line 143, 151, 165.\n- Line 156, $\\mathbb R^{d\\times d}$.\n- Can the authors write \"i.i.d.\" consistently?\n- In line 167, \"are bounded\" => \"is bounded\".\n- In line 168,  \"in/see\" duplicate.\n- In line 205, add comma to $\\min$. \n- In line 220, \"larger\" => \"smaller\"?\n- The bibliography is very inconsistent: Sometimes a venue has a number in words, other times in digits. Sometimes abbreviations are added, sometimes not. Some references have editors listed, others not. Names such as \"Bernstein\" should be capitalized. Similarly, abbreviations like \"LLM\", \"DCM\", \"PCA\".", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- While PCA has been studied extensively in the literature, incorporating quantization and studying its effect is an original and novel twist.\n- The lower bounds can be of independent interest, e.g., to compare future algorithms against.\n- While the article is generally well written, I think that the presentation can be improved. See below.\n### Weaknesses\n\n- Some notations are not well-defined, rendering the equations challenging/impossible to parse/comprehend. See the questions for details.\n- Similary, some abbreviations, e.g., BF16 in line 33 are not defined before they are used.\n- A few existing related works are enumerated (Line 35--) but their actual results are not put into perspective.\n- The practical relevancy, most prominently the impact on runtime, is not illustrated.\n- The contributions are not clearly articulated. E.g., what does the \"general theorem for streaming PCA\" tell? Which lower bound (the new one or an existing one) is being matched?", "was_revised": true, "final_justification": "Through consideration of the other reviewer's comments and the comprehensive rebuttal regarding my own review, I am bumping my score.", "rebuttal": "Thank you for your kind words regarding the originality, novelty, and the writing of the manuscript. We will fix all typographical errors pointed out by the reviewer in the revised manuscript and address key questions below:\n\n**Regarding bfloat16** : The bfloat16 (brain floating point) floating-point format uses 16 bits, designed for efficient deep learning training and inference. We will clarify this in the paper.\n\n**Regarding related work** : We provide more details on related work in Appendix G. However, most of the known guarantees are for stochastic gradient descent (SGD) with convex objectives, and we are not aware of existing analyses that apply to the streaming PCA setting off the shelf. \n\n**Regarding runtime comparisons** : When operating with $\\beta$-bits, the overall complexity for streaming PCA (and that of the batched variant) is $O(nd\\beta)$ and we performed a benchmarking experiment to illustrate this below. \n\n| Experiment | Runtime (seconds) |\n| ---------- | -------------------- |\n| 64 bits  | 0.0274 ± 0.00136  |\n| 32 bits  | 0.0260 ± 0.00225  |\n| 16 bits  | 0.000398 ± 0.0000235 |\n\n**Regarding contributions** : The general theorem refers to a result for streaming PCA with Oja’s algorithm that can handle martingale noise in the iterates, and is a generalization of known analysis with IID data. We are unaware of existing lower bounds for our problem setting and refer to the lower bounds proved in our work. We will clarify this.\n\n**Regarding length of the stream**: In the current manuscript, the length of the stream $n$ is an input and the learning rate is constant over time for ease of analysis. To handle variable learning rates using only constant-rate updates, we employ a standard \\emph{doubling trick}. Specifically, we divide the time horizon into blocks of exponentially increasing size, where each block $k$ has length $2^k$ and uses a constant learning rate $\\eta_k$ tailored to that block’s length. At the end of each block, the previous estimate is discarded and a new estimate is initialized. This scheme effectively simulates a decaying learning rate $\\eta_t$ while retaining the simplicity and analytical tractability of constant-rate updates.\n\n**Regarding $\\beta$ dependence in Lemma 1 and 2**: While the bounds in Lemma 1 and 2 are stated for a given $\\delta, d$, the optimal choice of these parameters given a fixed bit budget $\\beta$ does make the bounds dependent on \\beta (see lines 133-137).\n\n**$\\prod_{i=b}^{1}$ applied to a vector**: The product is a product of matrices in order $b$ to $1$, which is then multiplied by a vector. We will clarify this in the revised manuscript.\n \n**Regarding L.H.S of line 164**: The number of batches $b$ depends on $n$. The $O(1)$ factor here represents a constant w.r.t asymptotic behaviour of n. We will clarify this in the revised manuscript.\n\n**Regarding $\\alpha$ in Theorem 1 and 2**: $\\alpha$ is a constant which determines the learning rate, $\\eta$. Our results require $\\alpha \\geq 1$ (see Lemma A.2). We will refer to this lemma in the main paper.\n\n**Regarding bounded input set assumption**: We only require the variance and bounded assumptions in Assumption 1, which is popular in streaming PCA literature (see [1-7]). We note that while the current analysis assumes a bounded set, this is for ease of analysis and it can be generalized to unbounded subgaussian data (see [8, 9, 10]). \n\nFor space constraints and ease of exposition, we will provide an easy argument that changes the algorithm by considering \"truncated\" datapoints $Y_i = X_i \\mathbb{1}(||X_{i}||^{2} \\leq \\alpha_n)$, where the truncation parameter $\\alpha_n$  is set to be $c\\log(n)$. Thus, we replace any datapoint whose squared norm exceeds the truncation parameter by zero. Standard truncation arguments can then show that the sin-squared error of the output of this algorithm w.r.t the original principal eigenvector has the same theoretical guarantee. The crux of the argument is that the covariance matrix of the truncated data changes very little since the truncations happen with very small probability.\n\n**Regarding time and space complexity for diagonalizing $\\hat{\\Sigma}$** : Thank you for pointing this out - our intention was to say that the time and space dependencies of offline diagonalization are $\\Omega(d^2)$. We will clarify this.\n\n**Regarding “nearly dimension-free” bounds** : Yes, our dimension dependence is logarithmic in $d$, which we refer to as nearly dimension-free and we will make this explicit in the revised manuscript.\n\n **Regarding $||.||$ norm** : Both norms are the operator norm $||.||_2$. Throughout the paper, the norms $||.||$, $||.||_2$ and $||.||\\_{op}$ all refer to the 2-norm $||.||_2$ (which is the operator norm for matrices). We will clarify this in the notation section.\n\n**Regarding $\\beta$ being natural number** : Yes, $\\beta$ is the number of bits used by the model and is a natural number.\n\n**Regarding +1,-1 in (3)** : Yes, the second value in the quantization should be $-\\delta (2^{\\beta-1} - 1)$ instead of $-\\delta ((2^{\\beta-1}-1)+1).$ We will fix this typo. \n\n**Regarding stochastic rounding in Line 112**: Thank you for pointing that out. We will fix this typographical error.\n\n**Regarding “well within the range”**: Thank you for pointing it out. Here, we mean that the value being rounded is between the smallest and the largest numbers in the quantization grid. \n\n**Regarding $\\ell$ and $u$ in Line 114**: Thank you for pointing out the typographical error. The i's in (5) will be removed in the revised paper. \n\n**Regarding choice of $\\beta_e$ and $\\beta_m$**: The choice of the parameters $\\zeta$ and $\\delta_0$ is inspired from floating point computation, where the choice of the number of bits in the mantissa, $\\beta_m$, determines $\\zeta$ and the number of bits in the exponent, $\\beta_e$, determines the smallest representable number $\\delta_0$. The values $\\beta_e$ and $\\beta_m$ were chosen by minimizing the error $\\kappa_1 = \\zeta^2 + \\delta_0^2 d$ explicitly, that is, by taking a derivative with respect to $\\beta_e$ and setting the expression to zero. Note that the quantization errors $\\zeta$ and $\\delta_0$ depend on the bits and the choice is inspired from floating point computation.   \n\n**Regarding the dataset used in Figure 1**: The dataset is the same as used in Section 5, Experiments and is described in detail in Appendix F. Since the dataset is synthetically generated, we are able to explicitly calculate the eigengap. However, we would like to point out that the analysis is robust to upper bounds off by a multiplicative constant on the eigengap with a slight increase in the final sin-squared error.  \n\n**Regarding Algorithm 2, line 5**: Yes, we will move the definition of $\\rho$ outside the loop, making the algorithm more readable.\n\n### **References**\n[1] Moritz Hardt and Eric Price. The noisy power method: a meta algorithm with applications. NeurIPS 2014.\n\n[2] Christopher De Sa, Christopher Re, and Kunle Olukotun. Global convergence of stochastic gradient descent for some non-convex matrix problems. ICML 2015.\n\n[3] Ohad Shamir. Convergence of stochastic gradient descent for PCA. ICML 2016. \n\n[4] Ohad Shamir. Fast stochastic algorithms for SVD and PCA: convergence properties and convexity. ICML 2016.\n\n[5] Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-PCA: a global gap-free and near-optimal rate. FOCS, 2017.\n\n[6] Prateek Jain, Chi Jin, Sham M. Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming PCA: Matching matrix Bernstein and near-optimal finite sample guarantees for Oja’s algorithm. COLT, 2016.\n\n[7] Maria-Florina Balcan, Simon Shaolei Du, Yining Wang, and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. COLT, 2016\n\n[8] Lunde, R., Sarkar, P. and Ward, R., 2021. Bootstrapping the error of Oja's algorithm. Advances in neural information processing systems, 34, pp.6240-6252.\n\n[9] Liang, X., 2023. On the optimality of the Oja’s algorithm for online PCA. Statistics and Computing, 33(3), p.62.\n\n[10] Kumar, S. and Sarkar, P., 2024. Oja's algorithm for streaming sparse PCA. Advances in Neural Information Processing Systems, 37, pp.74528-74578."}]

Author rebuttal:

Meta-review: This work studies quantized Oja's algorithm for streaming PCA showing upper and matching lower bounds for linear quantization and logarithmic quantization.

All reviewers agree that the theoretical contributions of the paper are good. There were some concerns raised about the need to know the spectral gap for the algorithm. This has been somewhat addressed by the authors by pointing out that knowing the spectral gap is somewhat of a standard assumption in previous streaming PCA works. Further, some of the reviewers have expressed concerns about the quality of the empirical evaluation. The authors provide an extended empirical evaluation in the rebuttal which has addressed this concern. Several reviewers had issues with the presentation of the paper. I recommend that the authors include the extra experimental evaluation and implement the suggestions on improving the presentation of the paper.
Decision: Accept (poster)