- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies how to certify the linear-quadratic decision error induced by a low-rank representation when both the prediction matrix and the actuation matrix are estimated from data. Its central contribution is an expansion of the first-order Gaussian error around the fixed true optimal controller, together with a policy ball constructed from observable low-dimensional moments that is simultaneously valid for any fitted linear controller. It also provides a gap lower bound for spectral direction selection and an analysis of sampling error for new tasks. The novelty should be attributed primarily to finite-sample certification, rather than to weighted PCA or low-rank compression itself.
Critical strengths
-
The central certification result has clear technical substance. Theorem 2 on p. 3 and Sections A.5–A.6 on pp. 16–17 separate the first-order Gaussian term, products of noise terms, and Gram deviations, avoiding the direct use of full-matrix error from irrelevant outputs as a measure of decision difficulty. Expanding around the fixed true controller also avoids treating data-dependent coefficients as fixed quantities in the Gaussian analysis.
-
The claims align with the experimental scope, and limitations are adequately disclosed. Table 1 on p. 5 compares certificates for the same fitted models: as p increases from 4 to 1024, the stationarity ratio rises from 73.9 to 1229.0, whereas the policy-ball ratio rises from 13.0 to 21.7. The paper explicitly retains the pb² bias term and does not claim complete dimension independence. It also reports on p. 7 that the new certificate performs worse at small sample sizes and that compression quality deteriorates when too few task samples are available.
Critical weaknesses
-
The scope of applicability and algorithmic novelty are limited. Equation (6) on p. 3 and the limitations paragraph on p. 9 require a correctly specified linear model, known feature second moments, independent isotropic Gaussian OLS errors, and a known noise scale. Correlations in practical trajectories, unknown noise, and closed-loop stability are not certified; the neural-network experiment also does not satisfy the assumptions of the main theorem. The optimum in Corollary 3 remains ordinary Plug-in, and the task representation on p. 4 is equivalent to weighted policy-bank PCA. The authors explicitly acknowledge these facts. The contribution should therefore be assessed as improved statistical certification, rather than credited with broad improvements to general representation-learning algorithms.
-
The practical utility of the certificates is not yet sufficiently established. The certificates on p. 5 remain 13–21.7 times the true cost. Under one condition on p. 6, the excess bound is approximately 0.02, while the actual excess is approximately 10⁻⁵. The task diagnostic bound on p. 7 is approximately 1.23, compared with a measured excess of 3.20×10⁻⁴. These results clearly establish improvements over the previous bounds, but do not sufficiently demonstrate which ranks the certificates can certify at practical tolerances. All experiments are synthetic, and a direct assessment relating certification success rates, tolerances, and data requirements is missing.
Questions for authors
- For representative systems and a tolerance τ, what are the smallest rank accepted by the certificate, the failure rate, and the actual error? Do these results yield useful choices of sample size and compression budget?
- Do the benefits of the policy ball persist relative to split-and-certify or tighter decision-error certification methods under the same data budget?
3 comments
Response to Reviewer sM6G (2/3): certified rank, failure rate and sample size (Q1)
Q1. Conservatism means a higher rank or abstention (certifying no rank). An unsafe rank occurs with probability at most .
Because the certificate holds for every linear controller on one event of probability at least , the rank can be chosen from the same data. On that event the certified rank is never below the oracle rank (the smallest rank that meets with the true model), and the deployed controller's true cost is at most (Sec. 3, Appendix A.14).
The new experiment (Sec. 5, Appendix E.2) pads the systems of Tables 2 and 3 with pure-noise outputs up to . It uses from 256 to 65536 and tolerances of , and times , the excess cost of not acting, for 10,240 fits in all. None of the three certificates (ours, the stationarity bound and the simpler moment bound of Eq. (18)) was violated, and PB+ was violated once, consistent with (Appendix E.6). The table gives medians for our certificate at (Table 8), where a dash means that no fit certified any rank. "Diagonal" is the diagonal system of Table 2, and "orientation" means the 16 randomly oriented systems of Table 3.
| System | Oracle rank | Certified rank | Fits certifying nothing | True cost over | Certificate over true cost | ||
|---|---|---|---|---|---|---|---|
| diagonal | 1024 | 0.1 | 2 | 4 | 0% | 0.05 | 18.9 |
| diagonal | 1024 | 0.01, 0.001 | 4, 5 | – | 100% | – | – |
| diagonal | 65536 | 0.1 | 2 | 2 | 0% | 0.614 | 1.13 |
| diagonal | 65536 | 0.01 | 4 | 4 | 0% | 0.14 | 1.95 |
| diagonal | 65536 | 0.001 | 5 | 5 | 0% | 0.13 | 4.83 |
| orientation | 1024 | all | 2–3 | – | 100% | – | – |
| orientation | 65536 | 0.1 | 2 | 2 | 0% | 0.21 | 1.41 |
| orientation | 65536 | 0.01 | 3 | 3 | 0% | 0.0025 | 22.6 |
| orientation | 65536 | 0.001 | 3 | 3 | 0% | 0.025 | 22.6 |
- At the certified rank equals the oracle rank in 6,095 of 6,144 pairs of fit and tolerance and is one higher in the rest. The deployed controller's median true cost is at most .
- Abstention is the main weakness. Our certificate certifies nothing in 70 of the 180 combinations of system family, , and , all with or . The stationarity bound abstains in 114 of them, Eq. (18) in 93 and PB+ in 65.
- With many outputs and few samples, simpler bounds can be far lower. For the orientation systems at , and rank 2, ours is 284, the stationarity bound 31 and Eq. (18) 5.2, against a true cost of 0.31 (Table 10). Even without padding, Table 3 gives ours 2.80 against 1.97 for the stationarity bound at .
Sample size (Appendix E.3). In the dimension study of Table 1, our certificate certified on 90% of fits once was 4–16 times the sample size at which the median true cost first reaches . In five settings the median true cost was already at most at the smallest tested, so there the factor is only a lower bound. The stationarity bound needed 4–8 times more data than ours at , and at it needed 64–128 times more or did not certify within samples. PB+ needs half as many samples in 5 of the 18 settings and never more. Recomputing the radius from a preliminary fit at predicted the required on every fit of the dimension study on the factor-two grid, as a planning heuristic rather than a guarantee.
To your last question, the results give usable choices at large but often none with or tight tolerances.
The two other numbers you quote are diagnostics of other bounds. The excess bound of about 0.02 in Sec. 6 (mean 0.025, against an actual excess of about ) is a moment-based eigengap diagnostic. Substituting the true gap lowers it only to 0.018, so most of the looseness comes from the calibration terms rather than the unknown gap. Certifying a rank at a tolerance needs no eigengap. The 1.23 in Sec. 7 is a diagnostic in which task sampling makes up 99.7% of the radius term. The measured excess it bounds is , not as submitted.
Response to Reviewer sM6G (3/3): split-and-certify and other methods (Q2)
Q2. Certifying on all the data beat splitting in every setting we ran, although not always with our policy ball.
Theorem 2 holds uniformly over linear controllers, so it needs no held-out data. Split-and-certify (SC) instead fits on half the data and certifies the frozen controller on the other half (Appendix A.7). The table gives median certificates at rank 2 with equal halves, with the median ratio to the true cost in parentheses (Appendix E.4, Table 12). "Dimension" is the Table 1 system at , and "orientation" refers to the unpadded systems of Table 3. These are fresh fits, so the values differ slightly from Table 1 and from the means in Table 3.
| Method | Dimension, | Dimension, | Orientation, | Orientation, |
|---|---|---|---|---|
| Ours, all data | 5.5e-4 (13.4) | 1.45e-3 (20.5) | 2.72 (30.6) | 0.507 (6.5) |
| Stationarity, all data | 3.1e-3 (76) | 0.082 (1163) | 1.90 (21.4) | 0.668 (8.6) |
| Eq. (18), all data | 3.2e-3 (79) | 4.1e-3 (58) | 2.82 (31.6) | 0.905 (11.8) |
| SC with ours | 2.2e-3 (29) | 6.35e-3 (32) | 9.64 (89) | 1.11 (13.8) |
| SC with Eq. (18) | 8.9e-3 (112) | 0.0105 (53) | 6.24 (56) | 1.68 (20.9) |
Across Appendix E.4, SC with our certificate gave values 1.1–5.5 times larger than ours on all the data. In the dimension study, the controller fitted on half the data also had 1.9 times () and 2.8 times () the true cost of the full-data controller (Table 12).
We also ran ten padded small-sample settings at ranks 1–6 (Appendix E.7, Table 16), including 8 of the 11 settings of Appendix E.2 where a simpler bound is below ours.
- In 4 of the 10 settings at rank 2, SC with Eq. (18) was below our policy ball. The worst case is the orientation systems at and , where ours is 284 and SC with Eq. (18) is 10.9.
- Even there, Eq. (18) on all the data gives 5.2. At every rank in all ten settings at least one full-data certificate was lower than every split-and-certify variant. The split controller also had a higher true cost, 0.635 against 0.311.
- Combining bounds helps more than splitting the data. Computed at the failure probability that PB+ assigns to each tail event, Eq. (18) uses ten events that PB+ already contains. The minimum of the two, PB+M, therefore holds with probability at least at no extra cost (Appendix A.15). In the worst cell it gives 5.6, slightly above the 5.2 that Eq. (18) gives with its own split of . By construction it never exceeds PB+. In the ten settings of Appendix E.7 it was never more than 10% above Eq. (18), so it is the bound we would use in practice.
- A bound specialized to one frozen controller could be tighter, but we do not derive one.
Other methods. Learn-then-Test and conformal risk control work with observed per-sample losses, and conformal risk control also needs them bounded and monotone in a tuning parameter. Our excess over an unknown optimum has no observable per-sample loss, is unbounded, and need not be monotone in the rank (Eq. 4).
Response to Reviewer sM6G (1/3): scope, novelty and conservatism
Thank you for a careful and accurate review. Parts 2 and 3 answer Q1 and Q2, and the end of Part 2 explains the 0.02 and 1.23 figures.
W1: scope and novelty. We agree. The revised abstract and contributions present the work as finite-sample certification of decision error rather than a new compressor. Our certificate-minimizing rank-r controller is plug-in compression (Corollary 3), and the sampled-task encoder is principal component analysis of a weighted policy bank (Sec. 4.2). Sec. 1 now credits Wagenmaker et al. (2021), whose task-Hessian-weighted risk is the antecedent of our first-order term. Their bounds hold after a burn-in and depend on the unknown system, whereas ours is computed from the data at finite n.
The linear model with a known feature second moment Exx⊤=I gives the exact cost formula, Eq. (3). The Gaussian error model, Eq. (6), makes the first-order term exactly Gaussian and gives its second moment (8), its covariance bound (19) and the remainder bound (21), while the known noise scales set every radius. Dependent trajectories, unknown noise scales and feedback control are outside the guarantees (Sec. 9). In new stress tests (Appendix E.9), heavy-tailed noise and a random design caused no violations, but ignored process noise did. The neural experiment (Sec. 8) carries no certificate, and in one cell with few action probes and small nuisance amplitude the weighting does not help (Table 4, now in Appendix C).
W2: practical utility. We agree that the certificate remains conservative, and the revision makes it tighter, explains the remaining gap and gives a floor for any certificate. All experiments remain synthetic because checking a certificate requires the true cost. The new multi-step benchmark is simulated from a physical model (Sec. 5).