Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Oja's streaming PCA admits per-coordinate confidence intervals at linear time and space.

desk verdict The first entrywise inference results for Oja's streaming PCA, with a clever median-of-means variance estimator; the main caveats are a stronger boundedness assumption and the need to know the eigengap, but the paper deserves serious refereeing. read the letter →

arxiv 2506.12655 v2 pith:5XDULTMF submitted 2025-06-14 math.ST cs.LGstat.MLstat.TH

Syamantak Kumar , Shourya Pandey , Purnamrita Sarkar This is my paper · ORCID
classification math.STcs.LGstat.MLstat.TH MSC 62H2562E2062F40
keywords streamingPCAOja'salgorithmentrywiseconfidenceintervalsuncertaintyquantificationmedian-of-meanssubsamplingcentrallimittheoremHoeffdingdecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that Oja's streaming PCA algorithm, usually analyzed only through its $\sin^2$ error, actually gives entrywise information: each coordinate of the output vector concentrates around the corresponding coordinate of the true top eigenvector at rate $\widetilde{O}(\sqrt{V_{kk}/n})$, where $V$ is a limiting covariance matrix. It also claims a central limit theorem for the coordinates with large limiting variance and provides a median-of-means subsampling estimator that recovers the diagonal entries $V_{kk}$ in $O(nd)$ time and $O(d\log(d/\delta))$ space. If these claims hold, a practitioner can attach honest confidence intervals to individual coordinates of a streaming PCA estimate, something the bootstrap does only at $b$ times the cost. The paper further shows that the entrywise bound implies the classical $\sin^2$ error rate up to log factors.

What carries the argument

The argument is carried by the Hoeffding decomposition of the random matrix product $B_n = \prod_{i=1}^n (I + \eta_n X_i X_i^\top)$, which splits $B_n$ into terms $T_{n,k}$; $T_{n,1}$ is the H\'ajek projection, the best approximation of $B_n$ by a sum of independent random matrices. The residual $r_{\mathrm{oja}}$ then decomposes as $\Psi_{n,1}+\Psi_{n,2}+\Psi_{n,3}+\Psi_{n,4}$, with $\Psi_{n,1}$ (the projected linear term) dominating: its covariance converges to $\eta_n(\lambda_1-\lambda_2)V$. Algorithm 1 estimates the resulting variances by splitting the stream into $m_1 \times m_2$ batches, running Oja on each small batch, squaring the residuals against a high-accuracy proxy $\tilde{v}$, and taking a median over $m_1$ groups.

What would settle it

Use the Gaussian covariance model of Section 5 (or any model where $V_{kk}$ can be computed in closed form from Lemma 1), run Oja's algorithm with $\eta_n$ set from the true gap, and check whether the empirical entrywise errors satisfy the claimed $\widetilde{O}(\sqrt{V_{kk}/n})$ bound for all coordinates and whether Algorithm 1's intervals attain the claimed coverage. Then rerun with the gap replaced by twice or half its true value: if coverage collapses, the known-gap assumption is the load-bearing premise.

Watch

Extended reading notes

Core claim

The paper's central claim is that for the Oja vector $v_{\mathrm{oja}}$, the residual $r_{\mathrm{oja}} := v_{\mathrm{oja}} - (v_1^\top v_{\mathrm{oja}})v_1$ satisfies, uniformly over coordinates, $|e_k^\top r_{\mathrm{oja}}| = \widetilde{O}(\sqrt{V_{kk}/n})$, where $V = (\lambda_1-\lambda_2)^{-1} V_\perp R_0 V_\perp^\top$ is a limiting covariance matrix built from the second-moment structure of the data. Theorem 2 asserts that Algorithm 1 estimates $V_{kk}$ up to additive error $O(V_{kk}/\sqrt{\log n})$ for every coordinate with large enough limiting variance, and Proposition 1 gives a Gaussian approximation for the distribution of the residual on any set of coordinates with $V_{jj} \geq b$, with convergence rate $n^{-1/6}+n^{-1/8}$ up to logarithmic factors. This converts streaming PCA from a point-estimation method into one with per-coordinate confidence intervals.

Load-bearing premise

The whole procedure assumes the true eigengap $\lambda_1-\lambda_2$ is known, because the learning rate $\eta_n = \alpha \log n/(n(\lambda_1-\lambda_2))$ and the final variance rescaling both depend on it; if the gap is misspecified, the confidence intervals have no stated guarantee.

Editorial extensions

If this is right

  • A user of Oja's algorithm can report coordinate-wise confidence intervals for the top eigenvector in one streaming pass, with no storage of the data matrix and no bootstrap replicas.
  • The uniform entrywise bound directly yields the optimal $\sin^2$ error rate $\widetilde{O}(V/((\lambda_1-\lambda_2)^2 n))$, matching offline PCA up to log factors.
  • For coordinates with large $V_{kk}$, the variance estimate is multiplicatively accurate to $O(1/\sqrt{\log n})$, which is enough to build honest intervals without knowing $V$.
  • The CLT for large-variance coordinates supports simultaneous hyperrectangle confidence sets, not only marginal intervals.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The paper's decomposition suggests that the same batch-median variance estimator could apply to any streaming estimator whose covariance is a known scalar times a fixed matrix; the conclusion gestures at this for SGD more broadly, but the authors do not prove it.
  • An obvious practical extension would estimate $\lambda_1-\lambda_2$ from the data (for instance from the Oja iterates) and feed it to Algorithm 1; the paper leaves this unanalyzed, so coverage under plug-in gaps is an open question.
  • Coordinate-adaptive confidence intervals could be used for post-hoc selection of reliably estimated eigenvector entries, e.g., for sparse or interpretable PCA, but the paper does not discuss downstream selection procedures.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper develops an entrywise uncertainty-quantification framework for Oja's streaming PCA. It decomposes the residual roja = voja − (v1^T voja)v1 via a Hoeffding decomposition, proves a Bernstein-type concentration bound for individual entries, states a CLT for a subset of entries whose limiting variance Vkk is bounded below, and introduces a median-of-means subsampling algorithm (Algorithm 1, OjaVarEst) that estimates Vkk in O(nd) time. The main theoretical outputs are Theorem 1 (entrywise concentration), Proposition 1 (entrywise CLT), and Theorem 2 (high-probability guarantees for the variance estimator). Experiments on synthetic data, HAR, and MNIST compare coverage and runtime against the multiplier bootstrap of Lunde et al. [2021].

Significance. If the results hold as stated, this is a useful advance: it moves streaming-PCA inference beyond sin-squared error to coordinate-wise confidence intervals, and it replaces the computationally heavy multiplier bootstrap with a linear-time subsampling estimator. The paper contains a substantial appendix with detailed proofs, including the Hoeffding decomposition, martingale-type norm bounds for the higher-order terms, Nazarov's inequality for the CLT step, and median-of-means aggregation. The explicit algorithm and reproducible experiments are assets, and the claim that the variance estimator gives O(1/√log n) multiplicative error for coordinates satisfying the stated conditions is concrete and falsifiable.

major comments (3)
  1. [§3.1, Algorithm 1 and Lemma 9] The end-to-end pipeline is not runnable from streaming data alone because Algorithm 1 requires the true eigengap λ1−λ2 as an input. Lemma 9 sets η_n = α log(n)/(n(λ1−λ2)), Algorithm 1 lists λ1−λ2 as an input on line 1, and line 15 rescales the median by η_B(λ1−λ2). The paper provides no procedure for estimating the gap, and Theorem 2's guarantees are proved only for this exact oracle choice. If the gap is misspecified, the Oja trajectory changes, the asymptotic-variance identity in Lemma 1 and the bias bound in Lemma 24 are no longer valid as stated, and the confidence-interval coverage is uncontrolled. This is load-bearing for the claimed linear-time UQ contribution; please either supply a pilot gap-estimation procedure (with an analysis of the resulting error), or explicitly reframe the contribution as conditional on known spectral parameters.
  2. [Abstract and §1, Eq. (2) versus Theorem 1] Equation (2) claims the uniform bound |e_k^T roja| = Otilde(√(Vkk/n)) for all k, but Theorem 1 in §3 proves the weaker statement |e_k^T roja|/√(η_n(λ1−λ2)) ≲ √(Vkk log d) + C b_k √(log n/n). Rescaling gives an additive term of order b_k log n/n, which is not Otilde(√(Vkk/n)) when Vkk is small relative to b_k^2 log^3 n/n, and which is nonzero even when Vkk = 0. Lemma 8, which derives the sin-squared-error bound from a coordinate-wise bound of the form in Eq. (2), also depends on the stronger statement. The abstract and introduction should either be revised to state the bound with the additive b_k term, or the paper should justify that the additive term is negligible under the maintained assumptions.
  3. [§3.1, Appendix B.2.6, Lemma 27 and Remark 3] There is a sample-dependency gap in the variance-estimation proof. The text says the n samples used for the B-batches 'need not be disjoint from the N samples' used to construct ˜v, and Remark 3 reports experiments with N = n and ˜v computed on the same data. However, Lemma 27 conditions on the high-probability event E for sin²(˜v,v1) and then treats the batch statistics βℓ as mutually independent and as independent of the Ψ_{B,0} term. If the batch samples overlap with the samples used to build ˜v, conditioning on E introduces dependence across batches and biases the conditional distribution of each batch, so the independence argument does not go through. If the intended protocol is a burn-in of N samples separate from the n samples used for variance estimation, Algorithm 1's input and the complexity statements should say so explicitly; if reuse of the same samples is intended, the proofs must account for the conditional dependence.
minor comments (5)
  1. [§1, Eq. (2)] The displayed formula for roja has a misplaced brace: it reads |e_k^T (voja − (v1^T voja)v1|{z}:=roja)|, which obscures the definition of roja. Please fix the typesetting.
  2. [§5.1, Table 1] The table headers say 'Dist. 1 (β = 1)' and 'Dist. 2 (β = 0.02)' in one pair of columns but 'Dist. 2 (β = 2)' in another, while the text says β ∈ {0.2, 1}. The constants should be made consistent between the text and the table.
  3. [§3.1, Algorithm 1] Algorithm 1's input includes the eigengap λ1−λ2 but not the batch learning rate η_B or the burn-in size N, both of which are needed to run the algorithm as stated. Please list η_B and N explicitly in the input, or define them in the algorithm description.
  4. [§5.1] The text says 'only two passes over the entire dataset suffice,' but the procedure requires one pass for the proxy ˜v and a second pass for the m1×m2 batch Oja runs, and if N is a separate burn-in the total cost is O((N+n)d). Please clarify the exact number of passes and the role of N in the empirical complexity claim.
  5. [§3, Proposition 1] The symbol b is used both as the variance threshold (Vjj ≥ b) and in the learning-rate condition M2^2 λ1 η_n/(λ1−λ2)^2 ≲ b. Though the two uses are related, reusing one letter for the threshold and the constant in the condition makes the statement harder to read; a distinct symbol for one of them would help.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the entrywise concentration, CLT, and variance estimator are derived from the Oja update via the Hoeffding decomposition and standard concentration arguments; the eigengap oracle is an assumption, not a self-referential input.

full rationale

The claimed derivations do not reduce to their inputs. The central entrywise bound (Lemma 30 and Theorem 1) is obtained by decomposing roja = Ψ_{n,1}+Ψ_{n,2}+Ψ_{n,3}+Ψ_{n,4} (Lemma 2), applying Bernstein's inequality to the independent summands of the Hájek projection Ψ_{n,1}, and separately bounding the lower-order terms (Lemmas 18-23). The limiting matrix V in Eq. (8) is defined from the population covariance Σ via fM = E[V⊥ᵀ(A1−Σ)v1v1ᵀ(A1−Σ)V⊥] and the eigenvalues, not fitted to the residuals, so the appearance of Vkk in Eq. (2) states a genuine asymptotic variance rather than a definitional identity. Algorithm 1's variance estimate is a subsampling/median-of-means estimator; Theorem 2 proves its concentration around Vkk, so the output is not a fitted parameter relabeled as a prediction. The gOja high-accuracy proxy in Eq. (10)/Definition 1 is an auxiliary construction (standard Oja runs aggregated geometrically) used only for the variance-estimation theorem; its stated sin² bound is an input/known convergence fact, not the source of the entrywise concentration claim. The paper's reliance on Lunde et al. for the Hoeffding decomposition and on Chernozhukov/Nazarov for Gaussian approximation is external standard mathematics. The self-citations to Kumar and Sarkar (geometric aggregation and a moment bound) are technical and auxiliary; even if omitted, the central derivation stands on the paper's own Lemmas 1, 2, 28-30. The requirement that Algorithm 1 receive λ1−λ2 as input is an oracle/practical assumption: the paper does not estimate the gap or define the gap in terms of its own output, so this affects applicability but is not circularity.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The central results rest on moment and scaling assumptions on the data, an almost sure boundedness condition for the main concentration theorem, a sub-Gaussian condition for the CLT, and an imported high-accuracy estimate v-tilde from the authors' prior work. No new particles, forces, dimensions, or conserved quantities are introduced. The limiting covariance matrix V is a derived population quantity, not a new entity.

free parameters (2)
  • learning rate eta_n = alpha log(n) / (n (lambda1 - lambda2)), alpha > 1
    Set in Lemma 9. The constant alpha and the eigengap are user inputs. The theory requires this particular scaling; the paper does not estimate alpha or the gap from data.
  • CLT variance threshold b = positive constant, not specified further
    Proposition 1 restricts to coordinates with Vjj >= b. The convergence rate depends on b, which is an arbitrary user-chosen threshold.
assumptions (7)
  • domain assumption Assumption 1: E[(Ai - Sigma)^2]_op <= V, E[||Ai - Sigma||_op^2]^(1/2) <= M2, E[||Ai - Sigma||_op^4]^(1/4) <= M4.
    Assumption 1 in Section 2; used throughout to control deviations of the random matrices Ai.
  • domain assumption Assumption 2: d = o(n^kappa) with kappa > 5 and a lower bound on n/log n involving M4 and the eigengap.
    Assumption 2 in Section 2; needed for the learning rate choice and dimension scaling.
  • domain assumption For Theorem 1, the iterates are almost surely bounded: ||Ai - Sigma||_op <= M.
    Introduced in Theorem 1 (Section 3). Needed for the Bernstein-type concentration. Not stated in the abstract or introduction.
  • domain assumption For the CLT, Xi is sub-Gaussian: E[exp(v^T X1)] <= exp(sigma^2 v^T Sigma v / 2).
    Stated in Proposition 1. Required to apply the high-dimensional Gaussian approximation of Chernozhukov et al.
  • domain assumption There exists a high-accuracy estimate v-tilde (Definition 1) from gOja satisfying sin^2(v-tilde, v1) <= C log(1/delta) log(N/log(1/delta)) M2^2 / (N (lambda1 - lambda2)^2) with high probability.
    Definition 1 in Appendix A. Imported from Kumar and Sarkar (2024b). Algorithm 1 and Theorem 2 depend on this estimate. This is a self-cited result not re-derived in the paper.
  • domain assumption The eigengap lambda1 - lambda2 is known and available as an algorithm input.
    Algorithm 1 line 1 and Lemma 9. Needed to set eta_n and to rescale the variance estimate. The paper does not estimate this quantity.
  • standard math Standard external results: Hoeffding decomposition of matrix products (Lunde et al. 2021), matrix concentration of Huang et al. 2022, Nazarov's inequality, and the Gaussian approximation theorem of Chernozhukov et al. 2017a.
    Used in proof sketches in Section 4 and in the appendix. These are external theorems, not proven in the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA." pith.science (2026). https://pith.science/paper/5XDULTMF

@misc{pith2026250612655,
  author       = {Pith},
  title        = {Pith review of: Beyond Sin-Squared Error: Linear-Time Entrywise Uncertainty Quantification for Streaming PCA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5XDULTMF}},
  note         = {Machine review of arXiv:2506.12655}
}
read the original abstract

We propose a novel statistical inference framework for streaming principal component analysis (PCA) using Oja's algorithm, enabling the construction of confidence intervals for individual entries of the estimated eigenvector. Most existing works on streaming PCA focus on providing sharp sin-squared error guarantees. Recently, there has been some interest in uncertainty quantification for the sin-squared error. However, uncertainty quantification or sharp error guarantees for entries of the estimated eigenvector in the streaming setting remains largely unexplored. We derive a sharp Bernstein-type concentration bound for elements of the estimated vector matching the optimal error rate up to logarithmic factors. We also establish a Central Limit Theorem for a suitably centered and scaled subset of the entries. To efficiently estimate the coordinate-wise variance, we introduce a provably consistent subsampling algorithm that leverages the median-of-means approach, empirically achieving similar accuracy to multiplier bootstrap methods while being significantly more computationally efficient. Numerical experiments demonstrate its effectiveness in providing reliable uncertainty estimates with a fraction of the computational cost of existing methods.

Figures

Figures reproduced from arXiv: 2506.12655 by the authors.

Figure 1
Figure 1. Time taken by the bootstrap methods and the OjaVarEst algorithm. Experiments verify [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Comparison of Median and Mean in Algorithm [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Uncertainty Estimation for HAR dataset ( [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Uncertainty Estimation for MNIST dataset. The [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Schematic picture of Algorithm 1 B.2.6 Total Variance Bound We now put together the results from Lemmas 14, 15, 19, 21, and 23 to provide a high probability bound on the error of the variance estimator Algorithm 1 [PITH_FULL_IMAGE:figures/full_fig_p040_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. The Phase Transition in Online PCA Depends on $n/d\log(d)$, not $n/d$

    math.ST 2026-07 conditional novelty 8.0 of 10

    Oja's algorithm undergoes a sharp phase transition at n ≈ d log d / [δ(2θ²−δ)]: below the threshold the overlap with the planted direction vanishes; above it, it tends to sqrt((θ²−δ/2)/(θ²(1+δ/2))), and exactly at thr...

Reference graph

Works this paper leans on

72 extracted references · 51 canonical work pages · cited by 1 Pith paper

  1. [1]

    Entrywise eigenvector analysis of random matrices with low expected rank

    Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank. Annals of Statistics, 48 0 (3): 0 1452--1474, 2020

    work page 2020

  2. [2]

    An _ p theory of PCA and spectral clustering

    Emmanuel Abbe, Jianqing Fan, and Kaizheng Wang. An _ p theory of PCA and spectral clustering . The Annals of Statistics, 50 0 (4): 0 2359 -- 2385, 2022. doi:10.1214/22-AOS2196. URL https://doi.org/10.1214/22-AOS2196

    doi:10.1214/22-aos2196 2022

  3. [3]

    First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate

    Zeyuan Allen-Zhu and Yuanzhi Li. First efficient convergence for streaming k-pca: a global, gap-free, and near-optimal rate. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 487--492. IEEE, 2017

    work page 2017

  4. [4]

    Asymptotic size and a problem with subsampling and with the m out of n bootstrap

    Donald WK Andrews and Patrik Guggenberger. Asymptotic size and a problem with subsampling and with the m out of n bootstrap. Econometric Theory, 26 0 (2): 0 426--468, 2010

    work page 2010

  5. [5]

    A public domain dataset for human activity recognition using smartphones

    Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Juan-Luis Reyes-Ortiz. A public domain dataset for human activity recognition using smartphones. In Proceedings of the 21st European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN), pages 437--442, 2013

    work page 2013

  6. [6]

    On the equivalence of oja’s algorithm and grouse

    Laura Balzano. On the equivalence of oja’s algorithm and grouse. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 7014--7030. PMLR, 28--30 Mar 2022. URL https://proceedings.mlr.pr...

    work page 2022

  7. [7]

    Online identification and tracking of subspaces from highly incomplete information

    Laura Balzano, Robert Nowak, and Benjamin Recht. Online identification and tracking of subspaces from highly incomplete information. In 2010 48th Annual allerton conference on communication, control, and computing, pages 704--711. IEEE, 2010

    work page 2010

  8. [8]

    J.A. Bather. Stochastic approximation: a generalisation of the robbins-monro procedure. In Proceedings of the Fourth Prague Symposium on Asymptotic Statistics (Prague, 1988), pages 13--27. Charles University, Prague, 1989

    work page 1988

Show all 72 references
  1. [9]

    On subsampling estimators with unknown rate of convergence

    Patrice Bertail, Dimitris N Politis, and Joseph P Romano. On subsampling estimators with unknown rate of convergence. Journal of the American Statistical Association, 94 0 (446): 0 569--579, 1999

    1999

  2. [10]

    On the choice of m in the m out of n bootstrap and confidence bounds for extrema

    Peter J Bickel and Anat Sakov. On the choice of m in the m out of n bootstrap and confidence bounds for extrema. Statistica Sinica, pages 967--985, 2008

    2008

  3. [11]

    Bickel, Friedrich G \"o tze, and Willem van Zwet

    Peter J. Bickel, Friedrich G \"o tze, and Willem van Zwet. Resampling fewer than n obersvations: Gains, losses, and remedies for losses. Statistica Sinica, pages 1--31, 1997

    1997

  4. [12]

    Joshua Cape, Minh Tang, and Carey E. Priebe. The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics . The Annals of Statistics, 47 0 (5): 0 2405 -- 2439, 2019 a . doi:10.1214/18-AOS1752. URL https://doi.org/10.1214/18-AOS1752

    2019 doi

  5. [13]

    Signal-plus-noise matrix models: eigenvector deviations and fluctuations

    Joshua Cape, Minh Tang, and Carey E Priebe. Signal-plus-noise matrix models: eigenvector deviations and fluctuations. Biometrika, 106 0 (1): 0 243--250, 2019 b

    2019

  6. [14]

    Statistical inference for online algorithms

    Selina Carter and Arun K Kuchibhotla. Statistical inference for online algorithms. arXiv preprint arXiv:2505.17300, 2025

    2025

  7. [15]

    On differentially private u statistics

    Kamalika Chaudhuri, Po-Ling Loh, Shourya Pandey, and Purnamrita Sarkar. On differentially private u statistics. In Advances in Neural Information Processing Systems, volume 37, 2024

    2024

  8. [16]

    plus/minus the learning rate

    Jerry Chee, Hwanwoo Kim, and Panos Toulis. “plus/minus the learning rate”: Easy and scalable statistical inference with sgd. In Francisco Ruiz, Jennifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and St...

    2023

  9. [17]

    Dimensionality reduction for stationary time series via stochastic nonconvex optimization

    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

    2018

  10. [18]

    Lee, Xin T

    Xi Chen, Jason D. Lee, Xin T. Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent. Ann. Statist., 48 0 (1): 0 251--273, 02 2020. doi:10.1214/18-AOS1801. URL https://doi.org/10.1214/18-AOS1801

    2020 doi

  11. [19]

    Central limit theorems and bootstrap in high dimensions

    Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Central limit theorems and bootstrap in high dimensions . The Annals of Probability, 45 0 (4): 0 2309 -- 2352, 2017 a . doi:10.1214/16-AOP1113. URL https://doi.org/10.1214/16-AOP1113

    2017 doi

  12. [20]

    Detailed proof of nazarov's inequality, 2017 b

    Victor Chernozhukov, Denis Chetverikov, and Kengo Kato. Detailed proof of nazarov's inequality, 2017 b . URL https://arxiv.org/abs/1711.10696

    2017 arXiv

  13. [21]

    Scalable dp-sgd: Shuffling vs

    Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, and Chiyuan Zhang. Scalable dp-sgd: Shuffling vs. poisson subsampling. Advances in Neural Information Processing Systems, 37: 0 70026--70047, 2024

    2024

  14. [22]

    Chandler Davis and William M. Kahan. The rotation of eigenvectors by a perturbation. III . SIAM Journal on Numerical Analysis, 7 0 (1): 0 1--46, 1970

    1970

  15. [23]

    B. Efron. Bootstrap Methods: Another Look at the Jackknife . The Annals of Statistics, 7 0 (1): 0 1 -- 26, 1979. doi:10.1214/aos/1176344552. URL https://doi.org/10.1214/aos/1176344552

    1979

  16. [24]

    Tibshirani

    Bradley Efron and Robert J. Tibshirani. An Introduction to the Bootstrap. Number 57 in Monographs on Statistics and Applied Probability. Chapman & Hall/CRC, Boca Raton, Florida, USA, 1993

    1993

  17. [25]

    Unperturbed: spectral analysis beyond davis-kahan

    Justin Eldridge, Mikhail Belkin, and Yusu Wang. Unperturbed: spectral analysis beyond davis-kahan. In Algorithmic learning theory, pages 321--358. PMLR, 2018

    2018

  18. [26]

    Online bootstrap confidence intervals for the stochastic gradient descent estimator

    Yixin Fang, Jinfeng Xu, and Lei Yang. Online bootstrap confidence intervals for the stochastic gradient descent estimator. Journal of Machine Learning Research, 19 0 (78): 0 1--21, 2018. URL http://jmlr.org/papers/v19/17-370.html

    2018

  19. [27]

    The Bootstrap and Edgeworth Expansion

    Peter Hall. The Bootstrap and Edgeworth Expansion. Springer, 1992

    1992

  20. [28]

    The organization of behavior: A neuropsychological theory

    Donald Olding Hebb. The organization of behavior: A neuropsychological theory. Psychology press, 2005

    2005

  21. [29]

    Adaoja: Adaptive learning rates for streaming pca, 2019

    Amelia Henriksen and Rachel Ward. Adaoja: Adaptive learning rates for streaming pca, 2019. URL https://arxiv.org/abs/1905.12115

    2019 arXiv

  22. [30]

    Streaming k-pca: Efficient guarantees for oja's algorithm, beyond rank-one updates

    De Huang, Jonathan Niles - Weed, and Rachel Ward. Streaming k-pca: Efficient guarantees for oja's algorithm, beyond rank-one updates. CoRR, abs/2102.03646, 2021. URL https://arxiv.org/abs/2102.03646

    2021 arXiv

  23. [31]

    Matrix concentration for products

    De Huang, Jonathan Niles-Weed, Joel A Tropp, and Rachel Ward. Matrix concentration for products. Foundations of Computational Mathematics, 22 0 (6): 0 1767--1799, 2022

    2022

  24. [32]

    Low-rank matrix completion using alternating minimization

    Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC '13, page 665–674, New York, NY, USA, 2013. Association for Computing Machinery...

    2013

  25. [33]

    Streaming PCA : Matching matrix bernstein and near-optimal finite sample guarantees for Oja's algorithm

    Prateek Jain, Chi Jin, Sham Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming PCA : Matching matrix bernstein and near-optimal finite sample guarantees for Oja's algorithm. In Proceedings of The 29th Conference on Learning Theory (COLT), June 2016

    2016

  26. [34]

    Black-box k-to-1-pca reductions: Theory and applications

    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 Proceeding...

    2024

  27. [35]

    On concentration inequalities for random matrix products

    Tarun Kathuria, Satyaki Mukherjee, and Nikhil Srivastava. On concentration inequalities for random matrix products. arXiv preprint arXiv:2003.06319, 2020

    2003 arXiv

  28. [36]

    Matrix completion from a few entries

    Raghunandan Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. Information Theory, IEEE Transactions on, 56: 0 2980 -- 2998, 07 2010. doi:10.1109/TIT.2010.2046205

    2010

  29. [37]

    Ariel Kleiner, Ameet Talwalkar, Purnamrita Sarkar, and Michael I. Jordan. A scalable bootstrap for massive data. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 76 0 (4): 0 795--816, 2014

    2014

  30. [38]

    Streaming pca for markovian data

    Syamantak Kumar and Purnamrita Sarkar. Streaming pca for markovian data. Advances in Neural Information Processing Systems, 36, 2024 a

    2024

  31. [39]

    Oja's algorithm for streaming sparse pca

    Syamantak Kumar and Purnamrita Sarkar. Oja's algorithm for streaming sparse pca. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024 b

    2024

  32. [40]

    Gradient-based learning applied to document recognition

    Yann LeCun, Le \'o n Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86 0 (11): 0 2278--2324, 1998. doi:10.1109/5.726791

    1998 doi

  33. [41]

    Fast and robust online inference with stochastic gradient descent via random scaling

    Sokbae Lee, Yuan Liao, Myung Hwan Seo, and Youngki Shin. Fast and robust online inference with stochastic gradient descent via random scaling. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 7381--7389, 2022

    2022

  34. [42]

    Subsampling scaling

    Anna Levina and Viola Priesemann. Subsampling scaling. Nature communications, 8 0 (1): 0 15140, 2017

    2017

  35. [43]

    Statistical inference using sgd

    Tianyang Li, Liu Liu, Anastasios Kyrillidis, and Constantine Caramanis. Statistical inference using sgd. In Sheila A. McIlraith and Kilian Q. Weinberger, editors, AAAI, pages 3571--3578. AAAI Press, 2018. URL http://dblp.uni-trier.de/db/conf/aaai/aaai2018.html#LiLKC18

    2018

  36. [44]

    Stochastic approximation and optimization of random systems

    Lennart Ljung, Georg Pflug, and Harro Walk. Stochastic approximation and optimization of random systems. Birkhauser Verlag, CHE, 1992. ISBN 3764327332

    1992

  37. [45]

    Bootstrapping the error of oja's algorithm

    Robert Lunde, Purnamrita Sarkar, and Rachel Ward. Bootstrapping the error of oja's algorithm. Advances in neural information processing systems, 34: 0 6240--6252, 2021

    2021

  38. [46]

    Estimating mixed memberships with sharp eigenvector deviations

    Xueyu Mao, Purnamrita Sarkar, and Deepayan Chakrabarti. Estimating mixed memberships with sharp eigenvector deviations. Journal of the American Statistical Association, 116 0 (536): 0 1928--1940, 2021. doi:10.1080/01621459.2020.1751645. URL https://doi.org/10.1080/01621459.202...

    1928

  39. [47]

    Stochastic approximation of eigenvectors and eigenvalues of the q-symmetric expectation of a random matrix

    Jean-Marie Monnez. Stochastic approximation of eigenvectors and eigenvalues of the q-symmetric expectation of a random matrix. Communications in Statistics-Theory and Methods, pages 1--15, 2022

    2022

  40. [48]

    On the maximal perimeter of a convex set in \( R ^n \) with respect to a gaussian measure

    Fedor Nazarov. On the maximal perimeter of a convex set in \( R ^n \) with respect to a gaussian measure. In Geometric Aspects of Functional Analysis (GAFA) 2001-2002, volume 1807 of Lecture Notes in Mathematics, pages 169--187. Springer, 2003

    2001

  41. [49]

    Problem complexity and method efficiency in optimization

    Arkadij Semenovi c Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983

    1983

  42. [50]

    Simplified neuron model as a principal component analyzer

    Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15: 0 267--273, 1982

    1982

  43. [51]

    On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix

    Erkki Oja and Juha Karhunen. On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix. Journal of mathematical analysis and applications, 106 0 (1): 0 69--84, 1985

    1985

  44. [52]

    Principal components analysis

    Karl Pearson. Principal components analysis. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 6 0 (2): 0 559, 1901

    1901

  45. [53]

    Scalable subsampling: computation, aggregation and inference

    Dimitris N Politis. Scalable subsampling: computation, aggregation and inference . Biometrika, 111 0 (1): 0 347--354, 03 2023. ISSN 1464-3510. doi:10.1093/biomet/asad021. URL https://doi.org/10.1093/biomet/asad021

    2023 doi

  46. [54]

    Politis, Joseph P

    Dimitris N. Politis, Joseph P. Romano, and Michael. Wolf. Subsampling / by Dimitris N. Politis, Joseph P. Romano, Michael Wolf. Springer Series in Statistics. Springer New York, New York, NY, 1st ed. 1999. edition, 1999. ISBN 1-4612-1554-4

    1999

  47. [55]

    B. T. Polyak and A. B. Juditsky. Acceleration of stochastic approximation by averaging. SIAM J. Control Optim., 30 0 (4): 0 838–855, July 1992. ISSN 0363-0129. doi:10.1137/0330046. URL https://doi.org/10.1137/0330046

    1992 doi

  48. [56]

    Spectral guarantees for adversarial streaming pca

    Eric Price and Zhiyang Xun. Spectral guarantees for adversarial streaming pca. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1768--1785, 2024. doi:10.1109/FOCS61266.2024.00108

    2024

  49. [57]

    Online bootstrap inference for policy evaluation in reinforcement learning

    Pratik Ramprasad, Yuantong Li, Zhuoran Yang, Zhaoran Wang, Will Wei Sun, and Guang Cheng. Online bootstrap inference for policy evaluation in reinforcement learning. Journal of the American Statistical Association, 118 0 (544): 0 2901--2914, 2023

    2023

  50. [58]

    Efficient estimations from a slowly convergent robbins-monro process

    David Ruppert. Efficient estimations from a slowly convergent robbins-monro process. Technical report, Cornell University Operations Research and Industrial Engineering, 1988

    1988

  51. [59]

    Using the m out of n bootstrap in hypothesis testing

    Anat Sakov. Using the m out of n bootstrap in hypothesis testing. University of California, Berkeley, 1998

    1998

  52. [60]

    G. W. Stewart and Ji-Guang Sun. Matrix Perturbation Theory. Academic Press, 1990

    1990

  53. [61]

    Su and Yuancheng Zhu

    Weijie J. Su and Yuancheng Zhu. Uncertainty quantification for online learning and stochastic approximation via hierarchical incremental gradient descent, 2018

    2018

  54. [62]

    Asymptotic statistics

    Aad van der Vaart . Asymptotic statistics. Cambridge University Press , 2000

    2000

  55. [63]

    Introduction to the non-asymptotic analysis of random matrices

    Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Yonina C. Eldar and GittaEditors Kutyniok, editors, Compressed Sensing: Theory and Practice, pages 210--268. Cambridge University Press, 2012. ISBN 9780511794308. doi:10.1017/CBO9780511794308.006

    2012 doi

  56. [64]

    High-dimensional probability: An introduction with applications in data science, volume 47

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018

    2018

  57. [65]

    High-dimensional statistics: A non-asymptotic viewpoint, volume 48

    Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019

    2019

  58. [66]

    Perturbation bounds in connection with singular value decomposition

    Per- ke Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12: 0 99--111, 1972

    1972

  59. [67]

    History pca: A new algorithm for streaming pca

    Puyudi Yang, Cho-Jui Hsieh, and Jane-Ling Wang. History pca: A new algorithm for streaming pca. arXiv preprint arXiv:1802.05447, 2018

    2018 arXiv

  60. [68]

    Lu Yu, Krishnakumar Balasubramanian, Stanislav Volgushev, and Murat A. Erdogdu. An analysis of constant step size sgd in the non-convex regime: asymptotic normality and bias. In Proceedings of the 35th International Conference on Neural Information Processing Systems, NIPS '21...

    2021

  61. [69]

    Online bootstrap inference with nonconvex stochastic gradient descent estimator

    Yanjie Zhong, Todd Kuffner, and Soumendra Lahiri. Online bootstrap inference with nonconvex stochastic gradient descent estimator. arXiv preprint arXiv:2306.02205, 2023

    2023 arXiv

  62. [70]

    Online covariance matrix estimation in stochastic gradient descent

    Wanrong Zhu, Xi Chen, and Wei Biao Wu. Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 118 0 (541): 0 393--404, 2023

    2023

  63. [71]

    High confidence level inference is almost free using parallel stochastic optimization

    Wanrong Zhu, Zhipeng Lou, Ziyang Wei, and Wei Biao Wu. High confidence level inference is almost free using parallel stochastic optimization. arXiv preprint arXiv:2401.09346, 2024

    2024

  64. [72]

    Principal component analysis

    Eric R Ziegel. Principal component analysis. Technometrics, 45 0 (3): 0 276--277, 2003

    2003

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.