acceptodds
Under review as a conference paper at ICLR 2027

Information Limits of Low-Rank Approximation Certification

Abstract

Low-rank approximation can require additional matrix–vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across \(W\) paths, a concentration bound exploiting shared residual energy yields a \(\log(W+1)\) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders \(N^1/3\) and \(N^2/3\) for validation and construction beyond the true target.

Primary area:
learning theory
Keywords:
randomized numerical linear algebra, low-rank approximation, query complexity, minimax lower bounds, error certification, adaptive stopping

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_BdMcOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies the query complexity of testing whether a low-rank matrix approximation is good using matrix-vector products. For a single approximation, the paper shows that Θ(g−2log⁡(1/δ))\Theta(g^{-2}\log(1/\delta)) queries are necessary and sufficient, even when queries are chosen adaptively. The paper also considers algorithms that gradually increase the approximation rank and repeatedly check whether the desired accuracy has been reached. The authors show that when the approximation sequence is constructed independently of the validation queries, O(g−2log⁡(1/δ))O(g^{-2}\log(1/\delta)) matrix-vector products suffice to make all required decisions correctly with probability at least 1−δ1-\delta. More generally, for WW such sequences, they prove a tight query bound of Θ((log⁡(W+1)+log⁡(1/δ))/g2)\Theta((\sqrt{\log(W+1)}+\log(1/\delta))/g^2). This improves the O((log⁡W+log⁡(1/δ))/g2)O((\log W+\log(1/\delta))/g^2) bound obtained by a naive union bound. Finally, the paper give numerical evaluation on synthetic data to support their theoretical results.

Critical strengths
  • The technical contribution of this paper is solid. For a single matrix, the paper gives tight query bounds, which also hold for adaptive queries. For multiple approximation matrices, the authors improve the query bound from a log⁡W\log W dependence to log⁡W\sqrt{\log W} and also prove a matching lower bound.
  • The paper also gives an empirical study for their theory analysis, which is also interesting to me.
Critical weaknesses
  • I feel like the presentation of this paper is hard to follow and can be improved significantly, especially in the abstract and introduction. For example, the "nested paths" and "W paths" are introduced without explaining what they mean, and the meanning of "exact dimension-uniform minimax query constant" is also unclear at a first look. I suggest the authors substantially revise the abstract and introduction to make the paper more accessible. In particular, they should clearly explain the different models considered in this paper and the corresponding result.
Questions for authors

See the above question.

3 comments
AuthorsOpenReview ↗

Improved Presentation and Clarification of Key Concepts

Thank you for this helpful suggestion. Revisions primarily addressing your comments are highlighted in blue. We have substantially rewritten the abstract, introduction, and Related Work, and checked and revised the presentation throughout the remaining sections.

The abstract and introduction now organize the paper around three questions: how to certify a single approximation, when validation can be reused across multiple candidates, and how certification affects stopping in iterative approximation. For each question, we introduce the setting before stating the corresponding result and its scope.

We have strengthened the explanations of the specific concepts raised in your review:

  • Nested paths: The introduction now explains that each candidate retains the existing approximation directions and adds new ones. This gives an operational interpretation of nesting before the formal treatment in Section 4.
  • “W paths” and path width: Section 4.2 defines width through a cover by ordered residual chains and illustrates it with a concrete workflow: KK preassigned randomized construction streams generate a family of width at most KK. This connects the abstract width parameter to the number of construction streams in an approximation algorithm.
  • “Exact dimension-uniform minimax query constant”: The introduction now states its meaning directly: for a fixed error target and separation gap, as the allowed failure probability tends to zero, the ratio of the Gaussian query count to the minimum required query count tends to one, with the worst case taken over matrices of all finite dimensions.

We also clarify the information model in Section 3.1, distinguishing additional validation queries in the upper bounds from all available operator observations in the lower bounds, and explicitly state the independence requirement for shared validation in Section 4.

Related Work has been rewritten to explain how the relevant ideas developed and where our contribution fits, rather than presenting separate summaries of individual papers. Across the remaining sections, we have supplemented previously abbreviated explanations, clarified assumptions and notation, and improved transitions between definitions, results, and their interpretation.

Thanks again for your time and valuable suggestion. We hope this revision can address your concern and make this paper more clear.

Thanks to the authors for the detailed response. I read the revised version and think the new abstract and introduction are much better now. I have raised my score to 3, and I think it would be great if the authors could further polish the presentation throughout the paper in the next version.

Dear Reviewer,

Thank you very much for your positive feedback, for re-evaluating our work, and for raising your score to 3. We are extremely glad that the revisions to our abstract and introduction met your expectations.

We highly appreciate your constructive suggestion to further polish the presentation. Thank you again for your invaluable guidance and support for our work.

Best regards,

The Authors

Reviewer_6EP9OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies how many forward matrix-vector products are needed to check whether a low-rank approximation meets a relative error target. Its three contributions connect checking one approximation, reusing validation during construction, and deciding when to stop.

First, Section 3 sharpens existing random-probe error estimation by finding the exact leading query constant as the allowed failure probability tends to zero, in the worst case over matrix dimensions. A matching lower bound covers methods that choose queries adaptively.

Second, Section 4 shows that one validation batch can check an entire nested sequence of approximation spaces without a query cost that grows with the number of checks. Across WW such paths, it proves an optimal log⁡(W+1)\sqrt{\log(W+1)} dependence for fixed interior error targets and sufficiently small error gaps. The complete candidate family must be constructed independently of validation. Beyond earlier work on reusing probes, the contribution is a matching upper and lower bound that exploits the shared structure of the approximation errors.

Third, Section 5 connects reliable certification to the extra construction performed while waiting to stop. It compares an energy-ratio rule with a block-sign rule, which checks whether groups of probes support acceptance. On a specified matrix family with energy spread across many directions, optimizing each rule's validation budget gives excess costs of order N2/3N^{2/3} and N1/3N^{1/3}, respectively, where NN is the number of remaining directions at the true target. This quantifies how two reliable rules can have different stopping costs; the comparison excludes construction before that target and is restricted to these two rules.

The paper is mainly theoretical. Synthetic experiments illustrate the confidence bound, the dependence on the number of paths, and the stopping-cost predictions. They also show that concentrating the matrix's energy can reverse which stopping rule performs better.

Critical strengths

The strongest contribution is the optimal query bound for shared validation. For candidate families constructed independently of validation, the query budget does not grow with the number of checks along a nested path. Across WW paths, the paper establishes an optimal log⁡(W+1)\sqrt{\log(W+1)} dependence in the stated regime. The shared-energy concentration argument and matching lower bound identify the cost of maintaining simultaneous reliability, going beyond probe reuse itself. This is the main theoretical result supporting a positive assessment.

The single-approximation result determines the exact leading query constant as the failure probability tends to zero, in the worst case over dimensions. Its lower bound covers adaptive forward queries and matches the Gaussian certificate asymptotically. This provides a precise benchmark for what any certification method can achieve under the stated information model and strengthens the paper beyond an analysis of one estimator.

Critical weaknesses

The stopping-cost comparison provides limited evidence of an advantage beyond the two selected Gaussian rules. On the diagonal family used in the analysis and experiments, Rademacher probes estimate the relevant quadratic forms exactly. A suitably calibrated Rademacher baseline is therefore particularly important. The experiments also exclude the initial construction cost and select validation budgets offline. These restrictions leave the practical significance of the stopping-cost separation unclear.

The information model limits the implications for certifying an already constructed approximation. The lower bounds charge for all operator observations, including construction responses, so they do not establish the same lower bound on additional validation queries when a construction transcript is available. Moreover, shared validation requires the complete candidate family to be independent of validation, excluding the use of validation residuals to construct new approximation directions. These limitations leave an important gap between the theoretical guarantees and their use within adaptive approximation algorithms.

Questions for authors

What motivates the choice of the two Gaussian rules compared in Section 5? On the diagonal family used there, Rademacher probes estimate the relevant quadratic forms exactly. Could a Rademacher certificate satisfying the same pathwise false-stopping guarantee achieve a smaller excess cost on this family? Resolving this would help assess whether the stopping-cost separation provides insight beyond the particular choice of baselines.

Note : EiE_i and TT appear before their meanings are introduced.

2 comments
AuthorsOpenReview ↗

Rademacher Certification, Stopping Costs, and Information Access

Thank you for your careful reading. Revisions primarily addressing your comments are highlighted in green. We address the overlapping concerns and question together below.

1. A uniformly calibrated Rademacher baseline

Yes, a Rademacher certificate can satisfy the same pathwise false-stopping requirement and achieve constant excess cost on this diagonal family.

For nonzero A∈Rm×nA\in\mathbb R^{m\times n} and an orthogonal projector PP, define the relative squared Frobenius error q(P)=∥(I−P)A∥F2/∥A∥F2q(P)=\|(I-P)A\|_F^2/\|A\|_F^2. Let 0<ρ<10<\rho<1 be the error target, 0<δ<10<\delta<1 the allowed probability of accepting any candidate with q(P)≥ρq(P)\ge\rho along the path, and ss the probe count. Draw independent vectors εi∈{−1,1}n\varepsilon_i\in\{-1,1\}^n with independent, equiprobable coordinates. Thus, εi\varepsilon_i denotes a random probe, not an accuracy parameter. Set

X_i(P)=\varepsilon_i^\top H(P)\varepsilon_i.$$ The statistics use cached responses $A\varepsilon_i$. Accept only when every $X_i(P)<0$. For $q(P)\ge\rho$, we have $\operatorname{tr}H(P)\ge0$. Appendix D.9 proves that the centered quadratic form $Q=\varepsilon^\top H\varepsilon-\operatorname{tr}H$ satisfies $\mathbb E Q^4\le15(\mathbb E Q^2)^2$. Hölder and Cauchy-Schwarz inequalities then give $\mathbb P(X_i(P)\ge0)\ge1/(4\cdot15)=1/60$. This bound is uniform in $\rho$. Each $X_i$ is nonincreasing along a nested path independent of the probes, reducing false stopping to the last unsafe candidate in each finite prefix. Probe independence and a limit over finite prefixes give $$\mathbb P(\text{false stopping anywhere on the path})\le(59/60)^s.$$ Hence a sufficient budget is $$s_{\mathrm{Rad}}=\left\lceil\frac{\log(1/\delta)}{\log(60/59)}\right\rceil.$$ This is a sufficient, unoptimized calibration. At $\delta=0.05$, this gives $s_{\mathrm{Rad}}=179$. On the diagonal family and coordinate path, each $X_i(P)$ equals $\operatorname{tr}H(P)$ exactly. At the first target-reaching rank $M$, it is zero; at $M+1$, it is negative. The strict acceptance condition therefore gives delay $1$. With unit query and direction costs, the excess cost is $179+1=180$, and is constant as matrix size grows at fixed confidence. **Changes:** Section 5 adds the rule; Appendix D.9 proves its pathwise safety and exact delay; Appendix E.4 adds the analytic cost to the comparison table. **2. Gaussian-rule motivation, initial cost, and offline selection** Both Gaussian rules can act on the same response cache, isolating the effect of the statistic and its calibration. Their optimized excess costs still have different orders on the same spectral family. This shows that equal reliability need not yield equally prompt stopping; the Rademacher result further demonstrates the role of probe choice. Our objective measures validation queries plus construction beyond the first target-reaching candidate. When the initial construction length $M$ is proportional to the number $N$ of remaining directions, including initial construction gives expected total cost $\Theta(N)$ at the Gaussian budgets minimizing excess cost. The budget experiment tests growth rates within the specified rule families. Budgets are selected offline from a fixed grid, then evaluated using 8192 fresh trials. Evaluation samples are not reused for selection. This is not an online budget-selection strategy. **Changes:** Section 5 clarifies the comparison and total-cost interpretation. Section 6 and Appendix E.4 specify the screening/evaluation protocol; the conclusion identifies online budget selection as future work. **3. Construction information and permitted adaptivity** A retained construction transcript may reduce fresh validation needs. Our independent-validation upper bound provides a sufficient additional-query budget; the lower bound charges all available responses, including construction responses. It does not establish the same fresh-query lower bound when a transcript is supplied for free. Shared validation permits data-dependent visits, path switches, and stopping within a candidate family specified independently of validation. Using validation residuals to generate new directions is outside the current guarantees. The added workflow retains construction queries, responses, and bases, and reuses responses $AG$ to one independent Gaussian probe batch $G$ while selecting which preassigned stream to extend. **Changes:** Sections 3.1 and 4.2 clarify these information requirements. The pseudocode in Appendix B.6 shows the complete workflow and separates construction from validation queries. The conclusion identifies validation-driven construction as future work. **4. Notation** We removed the premature use of $E_i$ and $T$ from Related Work. Total and residual energy matrices are now introduced in Sections 3 and 4 before their subsequent use. Thanks again for your time and valuable comments. We hope this revision can address your concern.

Thanks for getting back to me and for incorporating these changes. The Rademacher baseline answers my main question about the stopping comparison. I also find the revised paper easier to follow, particularly the explanation of how shared validation works with preassigned paths.

The optimal query bound for shared validation remains the strongest part of the paper for me. With my main concern resolved, I think the theoretical contribution merits clear acceptance. I am raising my rating to 4.

Reviewer_ehMhOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the matrix–vector query complexity of certifying the relative squared Frobenius error of a supplied low-rank approximation under a forward-only oracle. Certification distinguishes errors above a target from errors below that target by a prescribed separation gap.

For a single candidate, the paper determines the exact dimension-uniform minimax query constant as the permitted failure probability tends to zero. Its main contribution concerns simultaneous certification using a shared batch of Gaussian validation responses. For candidate families constructed independently of validation, a nested path can be checked without a query penalty depending on the number of checks. For families covered by WW ordered paths, the paper establishes the optimal complexity for fixed interior targets and sufficiently small gaps. The upper bound exploits a common positive-semidefinite energy envelope, and the lower bound applies to adaptive full-vector queries.

The paper also compares two uniformly valid stopping rules on a dispersed-spectrum family, obtaining optimized excess costs of orders N1/3N^{1/3} and N2/3N^{2/3} within the respective rule families. The results are supported by detailed proofs and synthetic experiments examining the predicted scaling laws.

Critical strengths

Theorem 4.1 and Proposition 4.2 are the strongest contributions. The matching lower bound, which applies even to adaptive forward queries returning full vectors, makes this an information-theoretic characterization. The reduction to boundary candidates also explains why repeated checks along one nested path need not increase the validation budget.

Critical weaknesses
  1. The paper would be more compelling with a concrete approximation workflow that produces multiple candidate paths independently of validation and explains what determines their width WW. The distinction between additional validation queries in the conditional upper bounds and all available operator observations in the lower bounds is stated correctly. However, its implications for an approximation algorithm that already has access to construction data deserve more discussion. Similarly, the stopping-cost separation is informative, but it concerns two specific certification rules on a particular spectral family. Although the paper acknowledges these restrictions, I find the broader algorithmic implications somewhat limited by the present analysis.

  2. Several earlier works study closely related questions in randomized error estimation, certification, and reuse of validation information. I am not suggesting that these works subsume the present results. However, a more detailed comparison is needed to explain how the problem settings and guarantees differ, which technical ingredients build on existing ideas, and which ingredients are new. This would help readers assess both the novelty and the significance of the contribution. In my view, a careful account of how the ideas developed through the literature is an essential part of presenting a theoretical contribution.

Questions for authors
  1. Can you describe a concrete approximation workflow producing several candidate paths independently of validation, explain what determines WW, and specify which construction observations the certifier possesses? This would clarify when the improved width dependence materially reduces additional certification work.

  2. How do the guarantees compare with the error-estimation and test-reuse results of Tropp et al. (2019) and Buhr–Smetana (2018), and with the finite-family query bounds of Amsel et al. (COLT 2026)? A concise comparison identifying the essential differences in oracle access and supplied candidate information would help establish the distinct contribution of Theorem 4.1.

3 comments
AuthorsOpenReview ↗

Concrete Workflow and Comparisons with Prior Work

Thank you for your careful reading and suggestions. Revisions primarily addressing your comments are highlighted in red. We address the weakness and the two questions together below.

1. Concrete workflow, path width, and construction information

A concrete workflow uses KK preassigned random probe streams for range construction, independently of validation. Each stream generates a nested path, so the family has width at most KK. We can therefore set W=KW=K when choosing the validation budget, without computing a minimum chain cover.

The certifier retains construction queries, responses, and bases to extend candidates, and computes an independent validation batch Y=AGY=AG once. Subsequent checks only project the cached YY. Validation may determine which preassigned path to extend and when to stop; directions within each path remain determined by its original stream.

For an algorithm with construction data, the independent-validation upper bound provides a usable additional-query budget; retained data may further reduce the fresh queries needed. The lower bound counts all available responses, so it does not lower-bound fresh validation after an arbitrary construction transcript is supplied for free.

Changes: Section 4.2 adds this workflow and explains what determines WW. Appendix B.6 provides pseudocode for candidate expansion, data retention, validation reuse, and stopping, with separate counts for construction and validation queries. Section 3.1 clarifies how retained construction data affect additional validation requirements.

2. Prior work and the contribution of Theorem 4.1

We explicitly identify independent error estimation, normalized estimation, and test-vector reuse as established ingredients, and add the following comparisons:

  • Tropp et al. (2019) maintain an independent Gaussian sketch ΘA\Theta A in a streaming model to estimate Frobenius residuals and normalized errors and guide rank selection. We characterize the query cost of threshold certification, establishing the exact single-candidate high-confidence constant and a matching information lower bound.
  • Buhr-Smetana (2018) reuse forward test responses and obtain operator-norm guarantees by allocating failure probability across iterations. We study simultaneous RSFE threshold certification and reduce an ordered path to at most two boundary decisions, removing the dependence of the validation budget on the number of checks.
  • Amsel et al. (COLT 2026) use queries to AA and A⊤A^\top to select a near-optimal candidate from a supplied finite family of explicit matrices. Our supplied objects are projectors PiP_i; the candidates PiAP_iA remain implicit. The task is simultaneous certification against prescribed error thresholds using only forward responses AvAv.

Building on the boundary reduction, Theorem 4.1 exploits the common energy envelope to obtain square-root logarithmic dependence on width, with a matching lower bound covering adaptive full-vector queries. The matching result holds for fixed interior error targets and sufficiently small separation gaps.

Changes: Section 2 now traces the progression from adaptive construction, through error estimation and query complexity, to shared validation and simultaneous guarantees. It includes these comparisons and concludes by distinguishing the established ingredients from our new theoretical results.

3. Algorithmic meaning of the stopping-cost comparison

The two rules use the same Gaussian observations and satisfy the same pathwise false-stopping guarantee, yet have different excess-cost orders on the same spectral family even after optimizing their budgets separately. Thus, equal reliability does not imply equally prompt stopping: the additional construction induced by certification also matters when choosing a rule.

The added Rademacher baseline satisfies the same pathwise false-stopping requirement. On this diagonal family, its delay is exactly 11 and its excess cost is constant for fixed confidence, demonstrating the role of the probe distribution. We also clarify that, when M≍NM\asymp N, including initial construction gives expected total cost Θ(N)\Theta(N) at the Gaussian budgets minimizing excess cost.

Changes: Section 5 clarifies the purpose of the comparison and distinguishes excess cost from total cost. Appendices D.9 and E.4 add the Rademacher safety proof and analytic baseline, whose cost is 180180 at δ=0.05\delta=0.05 with unit cost weights.

Thanks again and we hope this revision can address your concern.

Thank you for the clarifications. The workflow, and comparisons with prior work substantially address my concerns. But I still belive that the broader algorithmic implications remain somewhat limited, though to the best of my understanding Theorem 4.1 and its matching lower bound support a positive assessment. Consequently I will maintain my weak-accept recommendation.

Thank you for your follow-up and positive assessment. We will continue to develop applications of these theoretical results.

Best regards

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.