acceptodds
Withdrawn from ICLR 2027

Observable Clocks for Sequential Recovery in Tensor PCA

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Online stochastic gradient descent on multi-spiked tensor PCA recovers the planted spikes one at a time. Long plateaus, during which an overlap grows from its random-initialization scale, are followed by rapid recovery. These stages are defined through overlaps with the unknown spikes, so they cannot be observed directly. We show that they can nevertheless be read off online from a quantity SGD already computes. For each estimator column, the contraction of the fresh sample with the current iterate—a rescaled per-sample loss term—tracks the overlap-defined column signal uniformly over polynomially many steps. A windowed threshold on this signal gives an observable stopping rule. From initializations at the random scale with separated greedy weights, it reports the columns in the latent greedy recovery order, and each report falls within a vanishing fraction of its stage of the corresponding certified recovery time. The proof combines a reconstruction of the known sequential-recovery dynamics with new two-sided bounds on stage durations and threshold margins. We further show that the lower bulk of the transverse Riemannian Hessian carries the same signal as a spectral shift, uniformly along the trajectory under non-Gaussian noise. This spectral readout is consistent, but it is a noisier readout of the same quantity rather than an improvement. Simulations illustrate both monitors at finite size.

Primary area:
learning theory
Keywords:
tensor PCA, stochastic gradient descent, sequential recovery, observable stopping rules, Hessian spectra, high-dimensional statistics

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_DLaeOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors address the problem of automatically reporting the recovery of individual latent spikes in a multi-spiked tensor PCA model, as they are achieved along the run of an SGD algorithm. This is done by exploiting statistics computed from a sequence of tensor observations containing the same signal but with distinct and independent noise realizations. The first statistic is a contraction of the observations with the current iterates, while the second one relies on the spectrum of the so-called traverse Riemannian Hessian.

While the paper seems novel and the subject is definitely interesting for researchers working in high-dimensional inference, in particular involving tensor models, it needs in my view a substantial revision combined with a great pedagogical effort in order to improve its readability.

Critical strengths
  1. The subject is timely.

  2. The results seem to have important implications for practitioners who rely on tensor spectral methods.

Critical weaknesses
  1. In its current form, this Reviewer finds that the paper is unfortunately extremely hard to read, which obscures the main messages and makes it difficult to assess its soundness and its contributions. This difficulty is due to several reasons:
  • Many expressions and sentences have an unclear (or yet undefined) meaning in their surrounding context. Examples are: "overlap-defined column signal", "windowed threshold" and "latent greedy recovery order" (Abstract); "initialization with separated greedy weights", "transverse column-j Hessian", "transverse Hessian" and "stage certification" (Introduction); "Haar-probability claim", "Hessian compression", "quadratic-form compression", "lower-bulk theorem", "null-replicate eigensolver errors", "full-law noise simulator" (Section 2). And the list goes on.
  • Many math symbols are used before they are defined, such as SNS_N in line 83, ν\nu in line 109, σ\sigma in line 134, Cact\mathcal{C}^\text{act} and Cgr\mathcal{C}^\text{gr} in line 161, ζ^\hat{\zeta} in line 253, BNcalB_N^\text{cal} in line 269. Furthermore, SS is reused (SNS_N and Sj,tS_{j,t} seem to mean quite different things), as well as QQ (QNQ_N and QXQ_X).
  • The presentation is highly technical and far from pedagogical, which is in my view an issue for a conference aimed at a quite broad audience. A plethora of different symbols and definitions is given throughout the paper, but often without an accessible description of the overall/high-level reasoning being followed. It is thus quite difficult to keep track of its contents and main messages.
  • The meaning of certain concepts is not sufficiently explained. For instance: What exactly are the certified regions of lines 160-161? What exactly are the quantities plotted in Figure 1 (are they those defined in (35))?
  1. Model (1) assumes that a sequence of tensor-valued observations is given as an input to the algorithm. However, it is not clear that this model is relevant for applications, in particular the ones given in the Introduction as motivation. In the case of moment tensors, one could in principle partition the observations in order to compute a sequence of independent estimators of the target tensor, but this would increase the noise variance. Furthermore, the condition QN/SN→∞Q_N/S_N \to \infty in (12) seems to imply that a large number of observed tensors would be required. This issue is not discussed in the paper.

  2. The discussion on related work and on relevant properties of the tensor PCA model is insufficient. In particular, the paper does not mention the fact that, in the regime N→∞N \to \infty, there is an algorithmic threshold that each spike weight λi\lambda_i must attain for its associated spike to be recoverable by the considered algorithm. Hence, the assertion that individual overlaps will grow, as discussed in the Introduction, hinges upon all spikes being in this (weakly) recoverable regime, but this assumption is not discussed.

Questions for authors
  1. Shouldn't the given statements include a condition that spike strengths (the λi\lambda_i of your model) are beyond the algorithm threshold (which scales as N(p−2)/2N^{(p-2)/2} for randomly initialized local search algorithms, or as N(p−2)/4N^{(p-2)/4} if, say, a spectral initialization is used)?
Reviewer_wf1SOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies observable monitoring of sequential recovery in multi-spiked tensor PCA. Building on prior analyses of online SGD, the authors show that thresholding rescaled per-column sample losses reports recovering columns in the correct order and approximates their stage times under the stated assumptions. They also establish a Hessian-based readout of the same signal and illustrate the results through synthetic experiments. However, this paper is poorly written and hard to follow.

Critical strengths
  1. The paper connects observable monitoring with latent recovery dynamics, providing guarantees for reporting order and relative timing accuracy.
  2. The loss-based monitor is simple and uses quantities already computed by SGD, requiring little additional computation.
  3. The Hessian analysis provides a spectral interpretation of the recovery signal under sub-Gaussian noise.
Critical weaknesses
  1. Readability is a concern throughout the paper. The structure and the writing of this paper should be improved. Notations appeared in the paper are not clearly explained or organized.
  2. The theoretical results provided in the paper appears incremental relative to Ben Arous et al. (2026). The paper should justify clearly its contributions over prior work.
  3. The experiment part should be improved. There are no experiments on real world datasets.

[1] Ben Arous G, Gerbelot C, Piccolo V. Stochastic Gradient Descent in High Dimensions for Multi-Spiked Tensor PCA[J]. Communications on Pure and Applied Mathematics, 2026.

Questions for authors
  1. What are the practical necessities of the proposed observer? What are the contributions of this paper?
  2. Please justify the novelty of this paper over existing work .
  3. What additional insight or practical benefit does the Hessian-based readout provide over the simpler loss-based monitor?
Reviewer_4dMVOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The submission provides the analysis of a per-sample contraction observable in online SGD on Stiefeld manifold for Tensor PCA. The aim of the study is to show that such observable can be used as a "clock" that informs when the algorithm is finding ground truth signal.

Critical strengths
  • This result bridges theoretical predictions on tensor PCA with the practical viewpoint of using algorithms without access to the ground truth.
  • The mathematical arguments seem sound and non trivial to me.
  • Numerical experiments nicely complement the arguments.
Critical weaknesses
  • The observable considered is very standard for spiked data structures, hence there is little contribution in selecting this observable, but rather the scientific contribution is mostly to prove that the per-sample contraction observable works.

  • The scope of the novelty in this work is limited by the fact that, as discussed in the introduction to the manuscript, there already are predictive theories for SGD dynamics in tensor PCA. This mean that the full contribution only lies in providing an observable clock for a problem that already had precise asymptotic descriptions. In my opinion this is a critical consideration, that should be addressed together with the related question below.

  • The presentation is very technical and hard to follow at times.

Questions for authors
  • Can the authors explain what are the technical novelties in their proofs, comparing with the arguments in the already available tensor PCA analyses.

  • Can the authors comment if more naive stopping criteria such as "counting r plateaus" in sample averaged loss would also work.

  • Can the authors explain what is gained from a practical point of view by using the observable clock compared to just trusting the theoretical timescales predicted by existing results? Is it due to the imprecision of the multiplicative constants in the existing SGD predictions?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.