acceptodds
Under review as a conference paper at ICLR 2027

Certified Primal-Dual State Reuse for Sequential Robust Tensor Sampling

Abstract

Tensor sampling often arises as a sequence of related tasks in which sensing factors and uncertainty change while earlier optimization states remain informative. Existing samplers typically solve each task independently, whereas heuristic warm starts provide no test of whether a stored state remains valid after the task changes. We propose Variation-Aware Primal-Dual Memory Robust Frank-Wolfe (VPM-RFW), a projection-free algorithm that stores outer sampling designs and inner primal-dual states and validates their reuse through transfer bounds across tasks. These bounds control changes in the robust value, KKT state, and Frank-Wolfe gap. They allow the method to return a stored point that meets the current stationarity tolerance, continue from a reusable state, or fall back to a cold start. Under verified regularity and provided that no fallback occurs, the continuous output satisfies FW stationarity at tolerance with a weighted solver oracle bound. Feasible binary rounding has a separate bound on the objective value. On the tested synthetic sequences and KSC data, reusing states required less measured solver work than cold starts.

Primary area:
optimization
Keywords:
Sequential Tensor Sampling, Robust Optimization, Frank–Wolfe, Certified Primal-Dual Memory

Reviews

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

The paper deals with tensor sampling that deals with a sequence of related sampling tasks. In these settings, sensing factors and scenario uncertainties vary gradually across tasks, while historical optimization states remain informative. Standard tensor samplers solve each task independently from a cold start, whereas heuristic warm starts lack formal validity checks when task parameters shift

The solution offered by the authors is a Variation-Aware Primal-Dual Memory Robust Frank-Wolfe (VPM-RFW), a projection-free memory framework that returns:

  1. Stationarity Screen (Direct Return): Returns a stored historical point immediately if its transferred FW gap already satisfies the current stationarity tolerance $\epsilon$1more_horiz.

  2. Warm-Start Continuation: Initializes the outer FW method and inner primal-dual solver from the historical candidate with the lowest predicted solver oracle cost1more_horiz.

  3. Fallback (Cold Start): Reverts to an independent certified cold start if historical certificates fail or exceed predicted cold solver costs1more_horiz.Under Robinson constraint qualification and verified loca

The quesstion of course is how to choose which option to return and the theoretical part of the paper suggests how to evaluate candidate historical states using explicit transfer bounds that control changes in the robust value, the inner KKT state and the Frank-Wolfe stationarity gap.

Mixed results on several datasets are reported.

Critical strengths

The main contribution of the paper, in my view, is a principled formulation for sequential tensor sampling that is mathematically grounded in explicit validate certificats.

Critical weaknesses

The main weakness, is that the algorithm does not seem to be very useful in practice. It improves over heuristics such as prev-RFW and TD-RFW but not by much (see figure 1). The improvement start to appear only towards the end of the graph. This is a synthetic experiment so I don't know how realistic it is. On real dataset (table 1), prev-RFW performs on par with VPM-RFW.

Questions for authors

Can the authors identify real world scenarios where their method outperform existing heuristics?

Reviewer_zTQjOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes an approach that certifies the validity of past states in a sequential robust tensor sampling setting. This method stores outer solutions and primal dual states, and reuses them if they pass a validation for subsequent related tasks, by choosing between returning them, using them as a warm start, or starting cold. They provide theoretical guarantees for their approach and evaluate on synthetic sequences and a KSC hyperspectral dataset.

Critical strengths

The motivation of the paper is sound. Being able to estimate and certify whether the past states can be reused for future tasks, rather than starting from scratch or reuse blindly, seems valuable.

Critical weaknesses

Empirical analysis is thin. There is only one real world dataset (table 1, Kennedy Space Center (KSC) hyperspectral cube), and unlike synthetic data, the proposed method has identical results to the baseline (Prev-RFW) on all metrics. This makes it hard to evaluate the empirical performance of the approach.

The experiments do not verify the conditions of the theory. For example, Table 3 confirms that no verified constants or chart cover were established, no guard logs covering the full trajectory were reported, and no reference bound were verified. The authors acknowledge this but it makes the relevance of the theory hard to evaluate. Moreoever, it is hard to estimate how loose the certificate bounds are, thus whether they are relevant in practice.

Questions for authors

Could you provide insights on why VPM-RFW ties Prev-RFW on KSC, and provide real worlds settings where the paper's proposed method shows improvement over baselines? The small number of bands per window seems to suggest that the same option was chosen by both methods, it could be useful to see if longer horizon protocols, without reset, could distinguish the two methods.

Could you provide the numerical values of the transfer certificates on the experiments? How often is screening triggered?

Reviewer_6fqhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes VPM-RFW, a projection-free method for sequential robust tensor sampling. It stores outer and primal-dual states across tasks. Transfer bounds on the robust value, KKT state, and FW gap decide whether to return a stored point, warm-start from it, or use a cold start. Experiments on synthetic sequences and KSC report reduced solver work.

Critical strengths

The paper turns three questions into a decision problem with explicit criteria: whether a stored state can be reused directly, which stored state to reuse, and when to fall back to a cold start. The value, KKT state, and FW gap transfer bounds each serve a distinct purpose. The authors also clearly separate the certified execution from the practical numerical implementation.

Critical weaknesses

There may be a clear gap between the theoretical guarantees and the experiments. A preliminary reproduction suggests that the certificates may be too loose on the tested instances to guide state reuse. The selection rule used in the experiments also does not appear to be the certificate described in the paper. Therefore, the reported savings in solver work may not come from the proposed certified transfer mechanism.

Questions for authors
  1. The experiments do not verify the assumptions required by the theory, and the selection rule used is not the certificate from the paper. Given this, do the results show that the proposed certified state reuse is effective? Or do they only show that ordinary warm starts are effective?
  2. If VPM-RFW in the experiments re-evaluates each stored state on the current task, how is it different from trying several initializations and picking the best one? Why is this evaluation overhead excluded from the solver oracle metric?
  3. On KSC, VPM-RFW and Prev-RFW give identical results. Does VPM-RFW simply select the previous band every time? What advantage of the selection mechanism does this experiment show?
  4. The reported mean NMSE on KSC is positive in dB. This means the reconstruction error energy exceeds the signal energy. At this level of reconstruction quality, is the comparison between sampling methods still meaningful?
  5. Cold-RFW and the warm-start methods solve the same objective. Why do their reconstruction errors differ so much (1.059 vs. 0.636 dB)? Does this only reflect that the solver has not converged under the iteration caps?
  6. Sampling rows that are more diagnostic for scenario j reduces the allowed adversarial mass on that scenario. No observation is available before sampling. What physical or statistical basis supports this design-dependent uncertainty?
  7. FP-based samplers already run in milliseconds. Such a complex certification framework is introduced to save a small number of oracle calls. What is its practical value?
Reviewer_7fbdOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Given sequential tensor data, this work discusses how we should decide which indices need to be observed to estimate the entire of the tensor at each time step or task within a limited sampling budget. In line with the literature in this area, the method optimizes FP rather than the reconstruction error. More specifically, it uses certificate bounds obtained from previous time steps or tasks to determine whether the previous sampling design x, which specifies which entries to sample, can be reused. This approach reduces the computational cost while retaining theoretical guarantees. Numerical experiments are conducted to evaluate the usefulness of the proposed method.

Critical strengths

The source code has been submitted, which is good for reproducibility.

The mechanism that guarantees whether a previous sampling design can be reused for the current FP optimization is novel.

Critical weaknesses
  1. [Too hard to read] This article seems to be written for experts in signal processing rather than machine learning, and it does not clearly describe what a cold start is, why FP needs to be optimized, or what kind of practical application it considers. Thus, it was quite hard for me to follow the introduction, and I could not easily catch the motivation, even though I am an expert in tensors. The current setting looks very artificial. I believe their writing can be significantly better. For example, I recommend that they write that sampling design means deciding which modes in the tensor to sample. I spent a lot of time understanding what the "task" means in the introduction. In the machine learning context, the naive approach in their setting could be more Bayesian, and I could not see why the proposed methods are required instead of naive Bayesian methods. I believe the motivation for using a tensor is to discuss interactions spanning multiple modes in data; however, at the end of the day, the experiments seem to recover the tensor by reconstructing each matrix in the tensor, which I do not see as matching their motivation. From Section 3 to 5, the technical topics last; I recommend that they emphasize what the core is, what the essential gap is, and what the non-trivial methodological contribution is. The lengthy appendices are difficult to navigate, as the main text does not clearly indicate which parts should be consulted or provide sufficient context for the referenced material. As a result, the current manuscript is not well written for human readers; thus, I downgrade the Presentation score.

  2. I could not find an experimental design with one real dataset that follows their motivation. Although the proposed method appears to reduce the sampling burden compared with the cold-start approach, it does not appear to outperform the warm-start approach.​‌ The experimental results do not indicate how many sampling-design optimization steps were avoided by reusing x_i​ based on the certificate. Therefore, the effectiveness of the proposed method does not appear to have been sufficiently validated.

Questions for authors

[Q1] The KSC experiment models every spectral band as a rank-20 matrix. How was rank 20 selected?

[Q2] Could you clarify how the experimental results empirically support Theorems 1 - 4?

[Q3] The current evaluation is based on PSNR and SSIM. However, should the paper not also provide an empirical analysis of how the optimized FP values differ among the warm-start, cold-start, and proposed frameworks?

Suggestion

[S1] The conceptual novelty of the paper is currently difficult to identify. I suggest adding a conceptual figure that illustrates how the method constructs a sampling design and then uses the derived bounds and certificates to decide whether a historical state should be reused or rejected. If necessary, some of the algorithmic details could be moved to the appendix to secure the space.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.