- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper develops a new analysis of Oja's algorithm for top-one streaming PCA with i.i.d., arbitrary-rank matrix updates, a positive-semidefinite population mean, and only a matrix second-moment bound. Without assuming a leading eigengap, it obtains a cPCA sample complexity of at constant confidence, together with a lower bound matching the leading statistical term. A shared-sketch aggregation procedure improves the confidence dependence. A refined multiscale analysis also establishes the ePCA rate . Finally, these tools yield gap-free private PCA guarantees for mean-zero sub-Gaussian data with public scale parameters. In the Gaussian setting with known , the private ePCA bound becomes .
Critical strengths
-
A substantive theoretical gap is addressed. Theorem 1 permits general, potentially nonsymmetric updates under Model 1. Theorem 4 supports the optimality of the leading dependence on and , up to logarithmic factors.
-
The proof techniques are useful beyond a single rate statement. Trace control of the stochastic matrix products and shared-sketch aggregation address difficulties that arise when several top directions are equally valid. The ePCA analysis retains spectral information across thresholds and improves on the lossy black-box cPCA-to-ePCA conversion.
-
The private application gives the general-update theory a concrete use. The coupling between the clipped private iteration and Gaussian matrix perturbations produces a meaningful gap-free result. The manuscript states the public-scale assumptions and separates distribution-free privacy from model-dependent utility.
Critical weaknesses
-
The regime interpretation following Equation (6) is not supported by the displayed rates. The relative size of the privacy term decreases as or decreases, with other parameters fixed. This affects the explanation of the claimed advantage over AnalyzeGauss, although it does not by itself invalidate the sample-complexity theorems.
-
The practical cost and implementation of the private experiments need clarification. The full-batch design is acknowledged, but the paper gives little information about implementing it at and up to . Sample complexity alone does not establish a computational advantage.
-
The empirical settings are only loosely connected to the guarantees. The choices , , and the grid-searched step sizes are not accompanied by sensitivity results or a sufficiently explicit tuning protocol. Figure 2 includes uncertainty intervals, but its 20-trial results establish neither uniform superiority nor uniformly high success probability. The experiments also do not directly illustrate exact top-eigenvalue multiplicity.
Questions for authors
- Interpretation of the comparison in Equation (6). In Section 4.2, lines 421--423, smaller are described as favoring the improvement over AnalyzeGauss. However, the ratio of its privacy term to the shared statistical term is
We thank the reviewer for the detailed comments and for recognizing the theoretical contributions of our work, particularly the general-update analysis, the nearly matching lower bound, and the multiscale ePCA guarantee. We address the questions below. We hope that our response clarifies your concerns, and elevates your opinion of our paper.
1. Interpretation of Equation (6): Please see our general comment.
2. Computational cost and implementation: We thank the reviewer for suggesting a more explicit computational comparison. We note that all code for our experiments is provided in the supplementary material. Algorithm 2 requires O(ndR2T) arithmetic operations and O(dR2) auxiliary memory, where Theorem 2 chooses
T=O\left(\frac{\log(dR/\Delta)}{\gamma}\right).$$ The $R$ runs can be processed jointly in $T$ dataset passes. Thus, for constant accuracy and failure probability parameters, the arithmetic complexity is $\widetilde O(nd)$, compared with $O(nd^2)$ for explicitly constructing the empirical covariance in AnalyzeGauss. Our algorithm also avoids storing the full $dxd$ covariance matrix. We additionally benchmarked both methods at $d=5000, R = 3$, and $T = 500$ on an AMD EPYC CPU with one BLAS thread. At $n=10000$, Algorithm 2 took $63.96$ seconds with $1074$ MiB peak process memory, compared with $8.79$ seconds and $1464$ MiB for AnalyzeGauss. These smaller-sample measurements illustrate the computational tradeoff associated with multiple full-batch iterations and an improved convergence rate. The implementation computes the adaptive clipped queries directly from the observations, including both clipping operations and Gaussian perturbations, as specified in Algorithm 2. We will include the computational bounds and benchmarking details in the revision. **3. Experimental parameters and privacy calibration**: For Figure 2, we use $R=3, T=500$, and $$\eta_t=\frac{32}{100+t}, \qquad \tau=\frac18\sqrt{\frac{\Delta}{R}}.$$ We picked $R=3$ since it gives a majority for aggregation without huge private queries. As for $T$, we sweep over ${100,250,500,1000}$, and we found $500$ gives the most success for Oja’s method. The clipping thresholds $R_1, R_2$ are chosen according to Equation (32), with $\nu = \lambda_1 = 1$ and $\zeta = 0.1$. The Gaussian noise is calibrated according to Lemma 13, $$\sigma^2= \frac{12RT R_1R_2}{n^2\varepsilon^2} \log\frac1\delta,$$ which guarantees $(\varepsilon, \delta)$-DP. The smaller $\delta_*$ in Equation (33) is used in the utility analysis to control adaptive clipping events and is not required for the privacy guarantee itself. The experimental parameters were selected independently of the sufficient parameter choices used in the proof of Theorem 2. We will clarify this distinction and the noise calibration in the revised manuscript. **4. Hyperparameter tuning and experimental evaluation**: The learning rates were selected using independent synthetic pilot trials and fixed before the reported evaluations. In particular, Figure 2 uses the same learning-rate schedule across all sample sizes and both values of $\gamma$. The known population covariance was used to evaluate cPCA error in the synthetic experiments, and tuning did not use the private evaluation samples. We will clarify this in the revision. The experiments are intended to illustrate our theoretical guarantees. Figure 2 reports mean errors and empirical success rates with confidence intervals, rather than claiming uniform superiority across all parameter settings. **5. Exact leading-eigenvalue multiplicity**: We thank the reviewer for this helpful suggestion. We have conducted an additional controlled experiment with exactly repeated leading eigenvalues, $\lambda_1=\lambda_2=\lambda_3=1$, and the remaining eigenvalues drawn from $\operatorname{Unif}(0,0.95)$. We use the same setup as in Section 4.1. Over 100 independent trials at $d = 50$, $\Delta$ decreases from approximately $0.126$ at $n=200$ to $0.0031$ at $n=8000$. This directly illustrates gap-free convergence in the presence of exact leading-eigenvalue multiplicity. We will include this experiment in the revision. **6. Public covariance scale and scope of the results**: Please see our general comment.