acceptodds
Under review as a conference paper at ICLR 2027

Cube Rounding for Matrix Sketching: Complete-Path Risk and Efficient Gram-Aware Updates

Abstract

Cube sampling preserves prescribed inclusion probabilities, yet minimizing the variance of individual rounding steps need not minimize the error of the final matrix sketch. We study this gap through the complete flight-and-landing process and develop an efficient implementation of a Gram-aware sampling rule. For a specified class of legal actions and landing procedures, we show how residual balance infeasibility forces terminal mutual exclusion, yielding policy-invariant covariance structure and conditions for exact optimality and quantitative near-optimality. Conversely, an explicit six-unit construction exhibits a unique locally optimal update with strictly positive complete-path regret, revealing the role of subsequent branching and landing. For rank-one positive semidefinite contributions, the resulting risk analysis connects Gram approximation to PCA reconstruction and subspace error. We then introduce Incremental Gram-Cube (IGC), which combines cross-step Gram reuse, an endpoint nullspace basis, and direct two-dimensional direction evaluation to accelerate a directional-energy surrogate on four-unit buffers. Under matched tie conventions, the implementation preserves the sampling rule in exact arithmetic. On 24 development cases spanning synthetic populations, real-data subsets, and larger synthetic inputs, IGC reduces end-to-end sampling-and-estimation time by 7.30–12.20% across the three groups relative to an already cached implementation of the same rule. All 9,216 paired evaluation draws produce identical selected indices and Frobenius errors. These results characterize when local Cube decisions suffice and demonstrate how matrix-aware updates can be computed with less overhead.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
balanced sampling, Cube method, matrix sketching, randomized numerical linear algebra, variance reduction, principal component analysis

Reviews

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

I think it has something to do with matrix sub-sampling (see equation (2)), and an application to low-rank approximation via PCA is mentioned (see Corollary 7). Cube rounding seems to be the sampling technique that is analyzed in the paper, but I'm not really sure what it is exactly.

Critical strengths

None.

Critical weaknesses

The paper is entirely incoherent. The introduction refers to numerous undefined concepts and terms, and the following theory sections are also filled with imprecise and undefined notation. I have no idea what is going on in the paper, despite the fact that I actually consider myself an expert in matrix sketching and sub-sampling.

Questions for authors

None.

1 comment
AuthorsOpenReview ↗

Response to Reviewer NWxo: A clearer explanation of the problem and contributions

Thank you for taking the time to read our paper. We are sorry that the original presentation did not make the problem and contributions clear. It introduced too many terms and theorems before explaining the sampling problem. Your feedback prompted a substantial revision.

We have rewritten the abstract and introduction, defined terms before the results, clarified notation, and moved detailed implementation derivations to Appendix C. Figure 1 connects sampled rows, matrix error, and principal component analysis (PCA) bounds. The main idea is as follows.

1. The starting point: keeping a small set of actual rows.

Suppose a data matrix contains many observations, and we want to retain a smaller set of real rows. By weighting the selected rows appropriately, we can estimate the full matrix's Gram matrix, which summarizes second moments and cross-products between features. This supports PCA and covariance analysis. Our task-specific extensions also examine classification, correlation estimation, clustering, and tail-frequency estimation. The experiments include activity recognition, handwritten-digit data, and financial time series.

Cube is an existing balanced-sampling method. It starts with each row's desired selection probability and randomly adjusts several probabilities together while preserving chosen totals. Zero means discard the row; one means keep it. This is flight. When balanced moves can no longer continue, randomized landing rounds the remaining probabilities. Each row keeps its prescribed selection chance, although landing may relax auxiliary balance. We study how to choose the moves within this process.

2. The question: which rows should be selected together?

Consider four rows: two copies of (1,0) and two copies of (0,1), with two rows to be selected. Selecting one of each type preserves both directions and, after reweighting, the Gram matrix exactly. Selecting a duplicate pair loses one direction in each sample. Both designs can give every row the same selection probability of one half. The difference is which rows appear together.

Cube makes these joint-selection decisions through a sequence of random moves. A rule that chooses the move with the smallest immediate variance may leave a poor choice later. We therefore study the expected squared error of the final matrix estimate, including the last rounding step. This is what we mean by complete-path risk.

3. What the theory and algorithms contribute.

First, we identify when balance constraints themselves limit how much these choices can matter. Some rows cannot be selected during flight because doing so would make the remaining balance impossible. Under the stated pairwise landing rule, at most one of these rows can enter the final sample. This fixes part of the joint-selection structure for every admissible policy. If that part accounts for all the error, every policy has the same risk; if the remaining contribution is small, we obtain a quantitative near-optimality bound.

Second, an exact six-row example shows the complementary case: the uniquely best immediate move leads to a worse final estimate because of subsequent branches and landing. These two results explain when local decisions are sufficient and when looking ahead matters. For row outer products, the analysis becomes a Gram-error analysis and supplies PCA error bounds (Secs. 3-6).

The computational contributions follow two distinct routes. Incremental Gram-Cube (IGC) computes the same specified direction rule with fewer local calculations. Task-specific coupling instead changes which rows enter together, using contributions relevant to the task. Sections 7-9 now distinguish these routes explicitly.

4. The measured outcomes and supporting evidence.

IGC reduces complete-draw time by 7.30-12.20% relative to the cached implementation of the same rule, with 9,216 identical paired outputs.

The separate task-specific designs show downstream gains under matched information and row budgets. With identical groups and 128 selected rows, classification accuracy improves by 0.382 and 1.179 percentage points on HAR and ISOLET, at 5.6% and 6.5% additional complete cost (Table 3). This demonstrates a concrete use of controlling joint selection, with its computational cost measured alongside quality.

The results above come from executed experiments and exact computations. The anonymous supplement provides code, saved inputs, seeds, per-draw measurements, and commands to regenerate the tables. It retains all 46,560 observations from the new task studies, including unfavorable outcomes. Exact constructions have independent rational-arithmetic checks. Historical archive coverage is stated in the README.

We would be grateful if you could revisit the revised introduction, Figure 1, and Sections 3-6, which now explain the sampling problem and central mechanism before the formal results.

Reviewer_ZqJSOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the gap between immediate-variance minimization and complete-path risk minimization in Cube sampling. The authors derive terminal mutual-exclusion structure from residual balance infeasibility, establishing conditions for exact and approximate optimality. A six-unit counterexample demonstrates how subsequent branching and landing costs can make a myopic policy suboptimal. The paper further connects the risk analysis to Gram sketching and PCA, and introduces IGC, which accelerates a specified Gram-aware rule through an endpoint basis and direct two-dimensional direction evaluation.

Critical strengths
  1. The complete-path analysis accounts for both flight and landing and clarifies why root-action optimality alone does not guarantee policy optimality. This provides a clear framework for understanding the limitations of local variance criteria.

  2. The six-unit counterexample has a unique myopic root action and uses exact rational arithmetic to distinguish the effects of branching and landing. The argument therefore does not rely solely on action ties or floating-point simulations.

  3. The connection between residual feasibility, terminal mutual exclusion, and covariance invariance offers useful structural insight. The authors also transparently report inconclusive downstream results, computational costs, and implementation limitations, without conflating risk improvements and runtime savings obtained under different policies.

Critical weaknesses
  1. The martingale decomposition, Bellman recursion, normal-cone characterization, and PCA perturbation bounds build on standard tools, so the theoretical contribution rests primarily on the terminal correlation structure. The success regime in Theorem 2 makes all legal policies equally risky, while Theorem 3 bounds the entire policy class. These results therefore mainly explain when policy choice has limited impact; they provide less insight into the quality of the myopic rule when policies differ substantially. Moreover, the strict-open certificate for general matrix contributions does not directly extend to the rank-one PSD geometry used in the application.

  2. Across the 180 real-data windows in Appendix G, no skips were certified under the 1.02 near-optimality criterion, and the median ratio of the energy bound to the exact regret was 32.08. The fixed mapping also satisfies ∣F∣≤1|F|\le1, limiting the evaluation of nontrivial protected blocks. These observations do not undermine the theorems, but suggest that the certificates currently serve more as explanatory tools than effective computational decision rules. Evidence is still needed on whether the centered certificate in Appendix K improves their usefulness on the existing real-data cases.

  3. Table 1 reports exact-risk reductions of 0.23%–3.35% for H3H_3, but the offline policy-evaluation work proxies for H2H_2 and H3H_3 are approximately 34–35 and 41–42 times that of the myopic policy, respectively. These proxies do not directly quantify actual runtime costs, while most downstream intervals cross zero under both the original and corrected tie-handling implementations. The results support improvements in conditional expected Gram risk, but do not yet establish whether their practical benefits justify the associated costs.

  4. IGC minimizes directional energy while omitting the direction-dependent maximal-step factor in the actual conditional variance. It therefore differs from the all-triple myopic policy analyzed in the theory and does not inherit its optimality guarantees. The timing results establish constant-factor improvements within the same rule, but use previously exposed development cases on a single host; IGC also remains slower than the public Cube implementation. A clearer risk–runtime comparison is needed to establish when the additional cost of this matrix-aware rule is worthwhile.

Questions for authors
  1. What is the key structural advance of Theorems 2–3 over existing complete Cube variance analyses? Do these results primarily explain terminal correlations, or can they provide informative decisions when policies differ substantially? Which conclusions apply to rank-one PSD contributions?

  2. On the existing real-data windows in Appendix G, does applying the centered certificate from Appendix K improve bound tightness, the fraction of cases with a positive lower bound, or the number of certified skips?

  3. Could the authors provide a small set of actual runtime and peak-memory measurements on the existing six-row blocks or windows to clarify the cost–benefit trade-off of lookahead? Please also clarify whether the PCA metrics use the window Gram or the full-training Gram as their reference, and how this choice corresponds to Eqs. (4)–(5).

  4. On the existing four-unit states, how large is the gap between directional-energy minimization and actual conditional-variance minimization? Could the authors use the existing comparisons to clarify IGC’s risk–runtime trade-off relative to public Cube and the approximate rules?

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

I understand the paper to analyze the complete flight-plus-landing risk of Cube sampling for unbiased matrix sketches. It shows that "residual balance infeasibility" can force terminal mutual exclusion on a protected set, making covariance (thus risk) policy-invariant and giving exact or near-optimality of local variance minimization under a registered action/landing class. They explicitly construct an example that shows myopic updates can have strictly positive complete-path regret (corresponds to branch-dependent continuations and landing costs). The same risk specializes to rank-one PSD Gram sketches and yields PCA reconstruction/subspace bounds. Separately, “Incremental Gram-Cube” does accelerate the evaluation of a directional-energy surrogate on four-unit buffers (Gram reuse, endpoint nullspace, closed-form 2 x 2 direction) with exact-arithmetic equivalence under matching ties and 7-12% end-to-end speedups versus an already-cached baseline of the same rule.

Their validation consists of (1) exact dynamic programming and energy bounds for the theory, (2) experiments on 4 datasets showing small but consistent exact Gram-risk reductions for 2 and 3-step lookahead versus myopic (0.23-3.35% relative), with most sampled PCA/ridge intervals crossing zero, and (3) timing on 24 development cases where they confirm identical outputs and the stated speedups.

Critical strengths
  1. The residual-feasibility argument that forces the terminal mutual exclusion (and policy-invariant covariance) along with the explicit six-unit counterexample that isolates the branch-and-landing regret clearly separate when the local Cube decisions are complete-path optimal from when they are not. The geometric and dynamic-programming reasoning is clear and the scope is stated honestly. This is a real technical contribution.

  2. Overall, the paper is very sound, is clear about the theoretical limits and experimental results, and does a good job of separating its claims. The repetition in distinguishing the later energy-surrogate rule from the theoretical policies, things like the note that the certificates do not transfer, the honesty in stating that most downstream intervals cross zero (thus inapplicable), and keeping the risk theory and the implementation contributions distinct is all good. The theoretical work is sound, credible, and well-explained.

Critical weaknesses
  1. My main reservation is that this will have borderline significance for the ICLR audience. Exact Gram-risk reductions are small, most PCA and ridge intervals are unresolved, and the computational gains are relative only to an already cached implementation of the identical surrogate (and admittedly remain slower than public Cube). The theory is carefully scoped to a registered Cube interface. Broader prevalence or impact on practical sketching/PCA is not established.

  2. I feel that the two contributions remain unlinked because the experiments do not evaluate a controller that combines the complete-path reasoning with the efficient Gram-aware implementation. The paper presents a real scoped theoretical characterization plus a modest implementation note rather than a unified advance whose practical value is demonstrated. That would be a clearer cause for acceptance.

Questions for authors

I am sure that there must have already been some attempt, but if you could find a realistic regime of feature matrices and inclusion probabilities in which the protected set is nontrivial, the near-optimality ratio is close to 1, and the exact-risk improvement appears in downstream PCA or classification metrics, that would greatly improve the paper. What if any regimes have you investigated, or do you believe that a natural, non-contrived direct application of the theory you prove is just not realistic? (Request)

I wonder whether any fraction of the H2/H3 Gram-risk reduction survives when the action class is restricted to the four-unit buffers used by IGC, or when a shallow lookahead is paired with the directional-energy surrogate. Given your acknowledgement in section 9 that these heavy lookahead policies require orders of magnitude more offline evaluation work and are treated strictly as "mechanism probes", how do you envision the complete-path risk theory can guide future work when lighter-weight rules like of IGC cannot inherit those lookahead gains? Perhaps there is a feasible intermediate surrogate that captures a meaningful fraction of the H2/H3 regret reduction without incurring the prohibitive offline cost. (Suggestion for future work)

1 comment
Reviewer_t1vnOpenReview ↗

Updates to review and rating, informed by the discussion

After considerable review, I have decided to decrease my score to weakly recommend rejection. After reading the other reviews and author responses, diving back into the current paper, rereading the theory and experimentation more carefully, and discussing the shortcomings, which the authors to their credit do acknowledge---the paper is simply too dense, too burdensome on the reader, and has a specific fatal incoherence.

On the paper’s density, use of uncommon terms and phrases, and artificially difficult word choice (synonyms of common terms and phrasings that are awkward because they are not common in this technical field). The abstract and rest of the first six pages repeatedly introduce and rely on specialized survey sampling vocabulary (“flight”, “landing”, “protected set”, “residual balance infeasibility”, “terminal mutual exclusion”, “complete-path risk”, “directional energy surrogate”). Although core terms such as flight, landing, complete-path risk, and the protected set F receive definitions in Sec 1, 3, and 4, the exposition still requires the reader to reconstruct the precise meaning of the registered action class, the pairwise landing rule, the FIFO four-unit buffer, and the distinction between the true one-step variance and the directional energy surrogate that IGC actually optimizes, relative to the randomized numerical linear algebra or matrix sketching literature that an ICLR reader could be expected to be familiar with.

On the burden it places on the reader, reviewer NWxo refused to engage with the paper but pointed out that it is difficult to follow, calling it “entirely incoherent”. Although NWxo does not elaborate much, it is certainly the case that the paper is not self-contained. Although many concepts referenced throughout the paper are cited or reasonably traceable to the literature mentioned, they may not reach the standard of being readily identifiable, even by researchers with publications in closely adjacent topics, as evidenced by the experiences of NWxo and this reviewer. See the contextually seemingly unmotivated appearance of the six-unit instance (Thm 5), whose forced-root regret and related quantities are presented in exact rational arithmetic, the energy bounds L_E and U_E​ whose practical tightness on the 180 reconstructed windows is reported via additive bound-to-regret ratios of 43.637 (uncentered) and 33.522 (translation-centered) in the current revision, and the repeated need to consult Appendices A, C, K, L and M simply to learn what the main theorems actually assert about the objects used in the experiments.

I understand that these inclusions/exclusions are made in weighing page space and to resolve weaknesses identified in the reviewing process. Regardless, it is the case that the current paper suffers from an unnatural flow and language problem.

Most importantly, after considerable review, and as the authors note in Sec 10 that “a native IGC-plus-lookahead controller with stable downstream gains and low total cost remains open.” Put simply, the main body of motivating theory, and the core theoretical novelty does not apply to the experimental method developed and tested. Thm. 2, Thm. 3, and Cor. 4 establish the policy-invariant covariance (and therefore exact or near-optimality of every admissible policy) only when residual infeasibility forces terminal mutual exclusion on protected set F under the stated exact-mass pairwise landing rule. The six-unit counter-example (Thm 5) proves that a unique myopic root action can still have strictly positive complete-path regret. Still, neither result actually governs IGC.

Sec. 7 and Prop. 8 show that IGC evaluates a fixed continuous directional energy rule on a four-unit FIFO buffer by Gram reuse and a closed-form null-space eigenproblem. It deliberately omits the direction-dependent factor that appears in the true one-step variance. Separately, four-row H2/H3 (Sec. 9.1) do operate on a FIFO buffer and report Gram-risk reductions of 0.179-2.366% (Table 1), but these are finite triple-action lookahead policies, not a combination with IGC’s continuous directional energy rule. The Sec. 9.1 and author discussion therefore correctly separate the two contributions. The four-row lookahead lowers Gram risk without resolved downstream PCA or classification intervals on the tested data, while IGC’s 7.30-12.20% end-to-end speed up (Table 2) is measured only against the already cached implementation of the identical surrogate and remains slower than the public Cube adapter. The task specific coupling designs in Sec. 8 and Table 3 do show improvements over grouped baselines on several endpoints, yet these remain distinct from the IGC rule and the complete-path risk theory. Also, the experiment methodology does not make a meaningful improvement over baseline in the setting that most directly connects the theory to the efficient implementation, though this lack of excitement alone is not cause for rejection.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.