acceptodds
Under review as a conference paper at ICLR 2027

Certifying Shared Gumbel Couplings: Geometry, Query Complexity, and Marginal Error

30 views

Abstract

Correct categorical marginals do not determine a sampler's coupling across inputs. We study certification of the shared Gumbel coupling through categorical queries to reusable hidden seeds. Certificates must be valid for every sampler satisfying a marginal promise, while being efficient under the Gumbel reference. For full-support targets on labels, we characterize exactly when a fixed finite input family permits inverse-accuracy certification: the ordered ratios must satisfy . At most three inputs then suffice. Otherwise, every fixed finite family has inverse-square complexity, but accuracy-dependent queries are faster. For fixed and distinct targets bounded away from zero, the uniform optimal order is , where . The order simultaneously characterizes reference expected seeds, reference expected calls, and an all-sampler deterministic call budget; lower bounds allow adaptation and stopping. We also characterize the marginal-tolerance transition for each fixed pair with . Exact finite-law experiments expose both the advantage of affine certificates at the reference and their conservatism under auxiliary misspecification. Deterministic quadrature verifies the local variance mechanism, without claiming an end-to-end implementation of the general minimax construction.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Gumbel coupling, sampler certification, query complexity, shared randomness, marginal robustness

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_KKWgOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies how to certify that a sampler implements the shared Gumbel coupling, assuming known or approximately correct marginals. It characterizes when a fixed set of auxiliary inputs suffices for efficient certification and establishes query-complexity bounds.

Critical strengths

The distinction between correct marginals and a correct joint coupling motivates a meaningful verification problem. The characterization of finite input families and matching complexity bounds under exact marginals are the main theoretical strengths.

Critical weaknesses

I have major concerns about the presentation of this paper.

First, the manuscript does not adequately introduce the concepts needed to interpret its main contributions. The abstract states several results before defining their parameters or explaining the quantities being bounded. For example, ρ\rho and δ\delta appear in the complexity bound without their meanings being specified in the abstract, although they are defined in the introduction. More seriously, the final sentence announces an ϵ−11/7\epsilon^{-11/7} “score-energy lower bound” without explaining either ϵ\epsilon or score energy. The wordings “structured critical-tolerance family,” “weighted orbit arguments,” and “sharp critical law” are also unexplained. The problem setup and main result are unclear from the abstract. As a comparison, the cited recent work [Daliri et al., 2025] clearly defined the coupling problem by an Alice and Bob example in the abstract and explained the topic-specific terminology in words.

The introduction does not sufficiently resolve this problem. It introduces “maximum anchor,” “reference predictor with fresh audits,” and “common-seed change of measure” largely as names of ingredients, without providing enough explanation of their roles. Moreover, the related-work discussion identifies several relevant areas and attributes the maximum-anchor to previous work, but provides little concrete comparison of their problems, assumptions, and guarantees with those studied here. The introduction should explain more explicitly which certification questions are new, what the closest existing results establish, and what obstacle requires the proposed techniques. Naming the classification and complexity bounds as new does not adequately explain their conceptual advance. In addition, the paper's motivation and application are not properly discussed. As a summary, the introduction lacks a complete and consistent presentation of the problem setup, the main theoretical results, the comparison with previous work, and the implications and practical relevance of the results.

The issue of unclear definition persists in the main technical presentation. In Section 5.2, the definition of K∗(ϵ)K_*(\epsilon) requires scores satisfying “target nullity,” but that condition is defined only in Appendix C.1. The subsequent discussion invokes orbits, occupied strips, and a weighted error estimate without first describing the orbit construction or explaining why it addresses the certification problem. The significance of the arithmetic assumption and the particular condition τ=ρ/3\tau=\rho/3 is similarly underdeveloped.

The paper contains potentially interesting theoretical results, but the current write-up makes it impossible to evaluate its contribution and to verify the technical soundness. I strongly suggest that the authors thoroughly polish the paper.

Questions for authors

N/A

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

This paper studies the certification of shared Gumbel couplings using categorical queries with reusable hidden seeds and known marginal guarantees. The authors characterize when fixed finite query families permit inverse-accuracy certification, establish matching optimal query-complexity bounds with accuracy-dependent queries, and extend the analysis to marginal uncertainty. Theoretical contributions are supported by detailed proofs and numerical experiments.

Critical strengths
  1. Sharp theoretical characterization of finite-query certification. Theorems 3.1–3.2 provide an exact characterization of when a fixed finite query family permits inverse-accuracy certification. The Gumbel-specific geometric characterization, together with an explicit construction using at most three inputs, constitutes a nontrivial theoretical contribution.

  2. Matching complexity bounds under a general adaptive query model. Theorem 4.1 establishes matching upper and lower bounds for certification complexity, accounting for adaptive queries, sequential stopping, and actual sampler calls. The extension to marginal uncertainty in Theorem 5.1 further strengthens the theoretical analysis.

Critical weaknesses

Limited motivation and applicability of the certification framework. The proposed setting relies on strong assumptions, particularly reusable hidden-seed access and known marginals at every input. The paper does not sufficiently motivate when these assumptions are realistic or what practical value certifying the target shared Gumbel coupling would provide. This makes the broader significance of the theoretical results difficult to assess.

Questions for authors

Q1. Motivation and practical implications of the setting.

I tried to understand this work in the context of existing shared-Gumbel and counterfactual modeling literature (e.g., Oberst and Sontag, 2019), but I struggled to see the direct motivation for the certification problem studied here. In particular, the introduction and problem setup are rather abstract, and the assumptions of reusable hidden-seed access and known marginals at every input are not sufficiently motivated. Could the authors provide a concrete application where these assumptions are justified and explain what certification would achieve in that setting?

Q2. Interpretation and implications of the main theoretical results.

Could the authors provide more intuition for the key quantities and the implications of Theorems 3.2 and 4.1? For instance, the introduction defines ρ\rho as the desired TV accuracy, δ\delta as the failure probability, and DD as the "span of the interior log-ratios," but offers little explanation of their roles in the framework. While I can follow the general conclusions, the geometric meaning of DD, why it determines the complexity regimes, and what these results imply for the choice and usefulness of auxiliary queries remain difficult to interpret. A concrete example connecting these quantities to the theoretical results would help clarify their significance.

Q3. Computational feasibility and evidence for the main theoretical claims.

The main results establish optimal sampler-call complexity, while preprocessing, numerical precision, and computational costs are excluded from the analysis. Moreover, the experiments appear to evaluate selected finite query plans rather than the full theoretical constructions. Could the authors clarify how computationally feasible the proposed certification procedures are as the desired accuracy increases, and to what extent the current experiments support the main complexity claims?


Reference: Oberst, M., and Sontag, D. (2019). Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Models. Proceedings of the 36th International Conference on Machine Learning (ICML)

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

Two samplers can produce the same output distribution at every input and still behave differently when the same random seed is reused across inputs. The paper asks how many queries are needed to check that a black-box sampler matches the shared Gumbel coupling at a given pair of inputs. It identifies when this can be done quickly with a fixed set of queries, gives the optimal query cost when the queries may be adapted to the desired accuracy, and partly extends the analysis to samplers whose output distributions are only approximately correct. Simulations on prototype examples in the appendix illustrate the certificates.

Critical strengths

The question appears natural: it concerns how a sampler couples its outputs across inputs, not just its output distributions. It is related to distribution testing with richer query access.

The theory appears careful, and the main rates come with matching lower bounds; only one special case is left open.

Critical weaknesses

The only experiments are small simulations on toy examples in the appendix, and in several of them a simple direct estimate does as well or better. Without experiments on real samplers and real data, it is unclear whether the method is useful in practice.

The paper names application areas, such as counterfactual models and coupled sampling, but does not explain which concrete system would need this check. The general results also assume a fixed number of labels and probabilities bounded away from zero, which excludes settings with large vocabularies and many small probabilities.

The main text uses only six of the nine allowed pages and is very dense, with brief proof sketches and the full proofs in a long technical appendix. The extra space could be used to explain the ideas and the motivation or present and discuss corresponding experiments.

Questions for authors

see above

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.