acceptodds
Under review as a conference paper at ICLR 2027

Constrained Polynomial Probabilistic Zonotopes: When Can One Compressed Model Serve Many Tasks?

Abstract

When can one compressed probability model meet several prediction requirements simultaneously? We introduce Constrained Polynomial Probabilistic Zonotopes (CPPZs), which combine polynomial constraint geometry, prescribed intrinsic probability laws, and explicit observation semantics. We study shared finite-coordinate continuous representations for declared tasks under worst-case squared prediction risk. For a class of elliptic task families of common order with scalar principal symbols, task-mixture constraints exactly characterize the jointly attainable leading-order risk region, without a common eigenbasis. For the stated nonlinear CPPZ family with smooth, strictly convex geometry, requiring one shared reconstruction with its prescribed intrinsic law preserves the optimal leading-order risk region attainable by unrestricted task-specific decoders of shared codes. This holds for each fixed finite task family differing only in context distribution and every fixed source radius strictly inside the geometric validity domain; each target admits a shared code. The construction separates coarse geometry from residual information and compiles recovery into a valid polynomial probability object. Within the same family, one geometry-dependent measurement update preserves the leading performance of deterministic adaptive linear acquisition, with sublinear additional queries. For two compact linear tasks on a real Hilbert source ball, continuous, linear, and deterministic adaptive-linear encoding have identical attainable risk regions at every coordinate budget, without ellipticity assumptions. Yet complete pairwise information does not determine collective feasibility: two CPPZ task triples with a common finite-context detector can have identical pairwise risk regions at every budget while differing on whether one code meets all three tasks' requirements at the same budget.

Primary area:
learning theory
Keywords:
representation learning theory, probabilistic representations, multi-task representation learning, minimax risk, nonlinear approximation, constrained polynomial probabilistic zonotopes

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

This paper introduces the CPPZ framework and explores how a single compressed probabilistic representation can be leveraged to simultaneously satisfy the requirements of multiple prediction tasks. It further demonstrates that, under specific conditions, this approach can maintain optimal prediction risk. Additionally, the authors find that even when tasks are pairwise compatible, it does not necessarily follow that a single representation can simultaneously satisfy the requirements of all these tasks.

Critical strengths
  1. The problem explored in this paper holds some value: while maintaining multi-task prediction capabilities, is it possible to restore a consistent probability object through shared compression, even though the problem is not new.

  2. Their research ensures both the prediction accuracy of each task and that they all originate from the same probabilistic object.

Critical weaknesses
  1. I find this paper hard to read. The motivation for this work is not clear enough.

  2. My primary concerns are whether the assumptions and the setting of this work are practically meaningful, and whether the (highly complex) tools used are actually necessary.

Questions for authors

I suggest that the author further elaborate on their motivations and the necessity of the tools employed.

2 comments
AuthorsOpenReview ↗

Response to Reviewer 6dnJ (1/2): summary

Thank you for stating your concerns directly. Each led to a change in the revised PDF. Brief answers follow, under your own sentences; the comment under this one gives the details.

"The motivation for this work is not clear enough."

One compressed code is often read by several tasks. If every task has its own decoder, the predictions need not agree with any single probability model. The paper asks what it costs to require one valid model, and how many coordinates a shared code needs. The introduction now opens with a concrete example, and the redrawn Figure 1 shows both options.

"... whether the assumptions and the setting of this work are practically meaningful"

  • Setting. The bounds bind real codes on image data. PCA misses all 2,304 boundary requests, while the shared construction meets 2,303 (Appendix F.2). In 192 task families, four standard projection codes need a median 1.47 to 2.19 times as many coordinates, and none ever needs fewer (Appendix F.4). On 45 targets that the bound excludes, every neural encoder we trained violates the requests. Sizing a code by checking tasks in pairs fails in 38 of 192 families (Section 6.2), and in 36 of 192 new ones. These exclusions, failures and width comparisons are certified in ball arithmetic.
  • Assumptions. They make the exact constants computable, and the conclusion persists when they are changed: with four other detectors, three other probability laws and mixed strata, one CPPZ stays within 0.8%, 2.3% and 0.7% of the bound for every continuous code at budgets 4 to 31 (certified, Appendix F.1). The image results above use none of these assumptions.

"... whether the (highly complex) tools used are actually necessary"

Where a simpler argument suffices, the paper uses it (Proposition A.6). The heavier tools are needed because the main claim is about constants, which rate arguments cannot see: in a simple pair of tasks, one model keeps the rate but at least doubles the constant (Appendix C.3). The details say what each tool does.

"I find this paper hard to read."

The introduction now starts from a concrete example. Section 3 has a notation table, and each quantity has its own symbol. Figure 1 is redrawn as one path from input to predictions, with fewer words and larger labels. The wording of the main text was also edited throughout for readability.

AuthorsOpenReview ↗

Response to Reviewer 6dnJ (2/2): details

1. Motivation, and whether the setting is practically meaningful

One probability model, instead of a decoder per task, is needed when the predictions must be mutually consistent, or when the model itself is sampled or propagated, as probabilistic zonotopes are in reachability analysis (Althoff et al., 2009; Modares et al., 2026), which CPPZs contain as degree-one cases (Appendix A.2). But one model is a restriction. The decoder must output a valid object, so it may need more coordinates, or accept higher risk, than separate decoders. The paper asks how large this price is and what the code has to measure.

A concrete case: the unknown object is a smooth convex surface sampled by area. Each task uses the same detector, looking from directions drawn from its own distribution, and predicts how often it fires. Under area sampling, the distribution of surface normals is fixed by the shape. Separate task decoders can therefore output firing rates that no single surface produces. Requiring one surface with its area law rules this out.

What we found:

  • In this family the restriction costs nothing to leading order: the rates and constants are the same (Theorem 4.1).
  • Measurement design matters. Three geometry-adapted queries meet a request that every fixed three-query scheme misses (Proposition 5.2).
  • Checking tasks in pairs can underestimate the joint budget. In a six-task MNIST family every pair fits in 34 coordinates, but the six tasks together need 36 (Section 6.2). Pairwise sizing fails in 38 of 192 image-derived families and in 36 of 192 new ones, all certified. The worst-case analogue of grouping by pairwise affinities (Standley et al., 2020; Fifty et al., 2021) therefore accepts groups that no shared code serves (Appendix F.4).
  • The bounds bind practical codes. On image-derived tasks the shared construction meets 2,303 of 2,304 boundary requests, while PCA misses all of them, by a median 46% (Appendix F.2); in 192 task families, request-weighted PCA needs a median 1.47 times its coordinates (Appendix F.4). On 45 image targets that the collective bound excludes, every trained neural encoder we tried violates the requests, yet a random-start Adam search reports 66 of 120 such networks as compliant (Appendix F.4).

The nonlinear family's assumptions make the exact leading constants computable. At finite budgets the conclusion persists, certified, when the detector, the law or the strata are changed (Appendix F.1). The last two findings do not depend on these assumptions: they use linear tasks built from image statistics, and Theorem 5.3 holds for any two compact linear tasks on a Hilbert ball.

2. Are the tools necessary?

Where a simpler argument suffices, the paper uses it: for one task and a fixed message, classical closure of area laws shows a legal output costs nothing (Proposition A.6), but builds no shared code. The tools below serve one code and one object for all tasks, with exact constants:

  • Polynomial constraints let a polynomial model carry a law on a surface: by Proposition A.3, no finite mixture of polynomial maps of a source with a density carries the sphere's uniform law, but one constraint equation does.
  • A prescribed law is the consistency requirement itself: the law must be the one the reconstructed geometry determines, not a separately fitted density.
  • Observation semantics define what a task asks of the object, so one object answers every task by the same rule.
  • Elliptic and Weyl asymptotics: "no extra cost" is a statement about constants, not only rates, and rate arguments cannot see a constant-factor penalty. In a task pair where one task predicts a vector and the other only its length, one object keeps the rate but at least doubles the constant (Appendix C.3). Because the tasks need not share an eigenbasis, Theorem 4.2 needs a joint construction rather than a diagonal one.
  • Coarse geometry first: linearising at one fixed shape leaves a relative error proportional to the radius δ\delta that does not shrink with the budget; sending coarse geometry first makes it vanish at fixed δ\delta.

3. Novelty

As far as we know, the closest work (Spantini et al., 2017; Zhang et al., 2021; Hu et al., 2023; Guo et al., 2025; Section 2) does not characterise the joint worst-case risk region, with its constants, when one valid probability object must serve all tasks. We also know of no earlier statement of three results: in the nonlinear family, one object costs nothing at leading order (Theorem 4.1); for two compact linear tasks, continuous, linear and adaptive-linear codes have the same exact risk region at every budget (Theorem 5.3); and complete pairwise information does not determine the joint budget (Proposition D.6). If you have a specific reference in mind, we would gladly discuss it.

We hope this addresses your concerns, and we would be glad to clarify any remaining point.

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

This paper studies whether a single compressed representation can meet the prediction requirements of multiple tasks. The authors introduce CPPZ, which combines geometric constraints, probability distributions, and observation rules. Under the specified model and task assumptions, Theorem 4.1 shows that, as the encoding dimension increases, requiring recovery of a single valid probability model does not increase the leading-order optimal risk or its constants. The paper also examines adaptive queries and whether pairwise task feasibility implies joint feasibility for all tasks. Experiments use finite-dimensional geometric models and image-derived linear reconstruction tasks.

Critical strengths
  1. The paper investigates whether recovering a common probability model incurs additional encoding costs. Theorem 4.1 compares two approaches using shared encoding: separate task decoders and recovery of a common model followed by prediction. Under the stated assumptions, both approaches have the same optimal asymptotic risk region, providing a theoretical basis for understanding the cost of preserving geometric and probabilistic constraints.

  2. The paper provides concrete constructions showing that pairwise feasibility does not imply joint feasibility at the same encoding budget. In the six-task MNIST linear reconstruction example in Section 6.2, every pair can be served using 34 coordinates, whereas satisfying all tasks requires 36 coordinates. This demonstrates that allocating an encoding budget based only on pairwise requirements may underestimate the joint requirement.

  3. Some encoding-dimension results are supported by both lower bounds and feasible constructions. For the fixed task model above, the authors use exact integer arithmetic to exclude 35-dimensional continuous encodings and verify a 36-dimensional projection satisfying all task requirements. The minimum-dimension conclusion therefore has explicit verification support, rather than relying solely on a solution found through numerical optimization.

Critical weaknesses
  1. In Section 6.3 (page 9), the three adaptive queries use 13, 13, and 10 bits, while the four fixed queries use 11, 11, 2, and 2 bits. The main text reports these configurations, but the reasons for assigning different precision levels to different queries could be explained more clearly.

  2. Page 43 reports different outcomes across image tasks: some tasks are feasible in pairs but infeasible jointly, whereas this behavior is not observed for other tasks. The reasons for this difference could be discussed more clearly.

  3. Page 62 reports higher encoding and decoding times for the two-batch method than for the fixed method, but the main sources of the additional cost could be clarified. Separating the time spent on query selection, encoding, and model recovery would help readers assess the computational trade-off associated with reducing the number of queries.

  4. Pages 3–5 introduce many symbols, and r has different meanings in different places, which can be confusing. A notation table and distinct symbols for different quantities would improve readability.

  5. The text and arrows in Figure 1 (page 2) are crowded, making the relationships between components difficult to follow. Reducing the text and enlarging the labels would make the overall flow clearer.

Questions for authors
  1. How were the bit allocations of 13, 13, 10 and 11, 11, 2, 2 in Section 6.3 (page 9) selected? Why are only 2 bits sufficient for each of the last two fixed queries? Could the authors briefly explain this in relation to the role of each query?

  2. On page 43, the region-weighted tasks exhibit pairwise feasibility but joint infeasibility, whereas this behavior is not observed for tasks involving blurring and detail extraction. Could the authors briefly explain which differences between these task groups might account for this result?

  3. For the timing experiment on page 62, could the authors separately report the time spent on query selection, encoding, and model recovery? Which steps can be performed in advance, and which must be repeated for each input?

  4. Could the authors add a notation table defining the main symbols? In particular, could distinct symbols be used for the regularity parameter and the risk requirements currently denoted by rr on pages 3–5?

  5. Could the authors simplify the text and enlarge the labels in Figure 1 (page 2), while making the sequence from input to encoding, common model, and task predictions clearer?

2 comments
AuthorsOpenReview ↗

Response to Reviewer nQqU (1/2): Weaknesses 1–2 and Questions 1–2

Thank you for the careful and accurate reading. Weaknesses 1–5 and Questions 1–5 raise the same five points, so we answer each pair together. All five led to changes in the paper, and Q2 to a new result.

W1/Q1. How were (13,13,10)(13,13,10) and (11,11,2,2)(11,11,2,2) chosen, and why do 2 bits suffice for the last two fixed queries?

Both were found by search: each is the smallest allocation our rational upper bound certifies on a grid (Table 8, Appendix F.6).

Two-batch, three queries. At each radius we evaluated the bound on a full grid: 8–18 bits for each coarse answer and 6–18 for the third, 858 allocations up to symmetry. We kept the smallest total certifying the request 1.04ρ01.04\rho_0. At δ=300\delta=300, the radius of Section 6.3, the unique minimum is 36 bits, (13,13,10)(13,13,10). At smaller radii it is 36 bits at δ=250\delta=250, 35 at δ=150,200\delta=150,200 and 34, (13,12,9)(13,12,9), at δ=50,100\delta=50,100.

Fixed, four queries. Again a full grid: 6–16 bits for each coarse answer and 1–8 for each fine one, 2,376 allocations up to symmetry. The unique minimum is 26 bits, (11,11,2,2)(11,11,2,2). No allocation with a 1-bit fine answer certifies, and with both coarse answers at 10 bits none does.

The roles of the queries explain the numbers. In both schemes, the first two answers are the coarse (degree-two) coordinates fixing the background geometry; the others concern degree-five coordinates, which the forecast map smooths strongly. In the bound, the forecast is about 630 times more sensitive to a coarse coordinate than to a fine one (coefficients Eb≈872.5E_b\approx872.5 and Ox≈1.38O_x\approx1.38, Appendix F.6). That factor is about 9 bits, the gap between 11 and 2. With (11,11,2,2)(11,11,2,2) the two rounding terms are comparable: about 0.38ρ00.38\rho_0 from the coarse answers and 0.49ρ00.49\rho_0 from the fine ones, in total 0.873ρ00.873\rho_0.

The fixed scheme can afford 2-bit answers because four queries measure every coordinate of the four-mode model, so rounding is the only error and may use the whole request. Three queries leave one degree-five direction unmeasured, so even with exact answers the three-query bound is 1.0011ρ01.0011\rho_0 (1.0020ρ01.0020\rho_0 at 16 bits, Table 8). All rounding must therefore fit in the remaining 3.9%.

A second, smaller reason: the three-query bound projects the reconstruction radially into the source ball, so an error in the third answer can also shrink the expensive coarse coordinates. The fixed control keeps the coarse pair (Appendix F.6). Section 6.3 now explains this.

W2/Q2. Why do region tasks show pairwise feasibility with joint infeasibility, while blur/detail tasks do not?

The F.2 operator triples are nearly ordered, in the sense of the bound below; many region targets are not. Write Gi=Ai/riG_i=A_i/r_i for the request-scaled Grams. With qi=piri/(p⋅r)q_i=p_ir_i/(p\cdot r) the mixture bound is 12λm+1(∑iqiGi)\tfrac12\lambda_{m+1}(\sum_iq_iG_i) on the simplex. Moving the weight of task ii onto task jj lowers it by at most 12dij\tfrac12d_{ij}, where dij=λmax⁡(Gi−Gj)+d_{ij}=\lambda_{\max}(G_i-G_j)_+ (Weyl). For three tasks, the collective bound therefore exceeds the pairwise threshold by a factor of at most 1+Ξ1+\Xi, with Ξ=min⁡i≠jdij/max⁡kλm+1(Gk),\Xi=\min_{i\ne j}d_{ij}\Big/\max_k\lambda_{m+1}(G_k), and recursively for more tasks. If one task is dominated by another, Ξ=0\Xi=0 and no pairwise-feasible target can be excluded.

We computed Ξ\Xi on every target of Appendices F.2–F.3 and of new controls (F.2's protocol):

FamilyTargetsΞ≤2\Xi\le2Excluded
regions, tenfold weight (F.3)2,6881,790200
quadrants, threefold weight (F.3)3843137
quadrants, thirtyfold weight (F.3)384112111
image/blur/edges, blur/detail/edges (F.2)2562490
nested disks (control)1281210
three quadrants (control)128756
differences and blur (control)128883
band-pass triples (control)2,0481,72636
F.2 triples, scrambled frequencies (control)7687310

All 363 exclusions found by the search have Ξ>2\Xi>2; none of the 5,205 targets with Ξ≤2\Xi\le2 is excluded, and an independent dense lattice finds no exclusion among the 2,402 with 0<Ξ≤20<\Xi\le2. We read this threshold off the controls; it held on the 2,688 tenfold F.3 targets, not used for it. Above 2 the excluded share grows with Ξ\Xi, from 7% for 2<Ξ≤102<\Xi\le10 to 39% beyond. With images, budgets, directions and weights matched, three nested disks (Ξ=0\Xi=0 at 111 of 128 targets) give no exclusion and three separated quadrants (Ξ=0\Xi=0 at 42) give 6. Operators can exclude too (band-pass, difference/blur).

Three other explanations are not borne out. Near-commutation: diagonal triples exclude in 48–82 of 96 families per setting (Appendix F.3). A shared frequency ordering: scrambling the edge task's frequencies still leaves no exclusion. The complementarity of blur and detail: band-pass triples with a complementary pair still exclude, at 6 of 384 targets. Appendix F.2 now adds the bound and these controls.

AuthorsOpenReview ↗

Response to Reviewer nQqU (2/2): Weaknesses 3–5 and Questions 3–5

W3/Q3. Where does the two-batch time go, and what can be done in advance?

The page-62 run timed encoding and decoding as whole calls. Following your suggestion, we re-ran it on the same machine (RTX 5090) with every step timed on its own. Times are medians per warm batch of 64 objects, over 18 backgrounds, 3 task counts and 3 budgets:

StepBalanced fixedTwo-batch
Encode0.07 ms1.62 ms
… of which choosing the second-batch directions–1.27 ms
Decode0.09 ms1.66 ms
… of which choosing the second-batch directions–1.27 ms
Compile the supports0.03 ms0.03 ms
Normalise and predict, all tasks0.75 ms0.75 ms

For a fixed rule and budget, the medians for 2, 4 and 8 tasks differ by at most 3.1% in every row, since every task reads the same normalisation and forecast field.

On each side, the two-batch rule takes about 1.55 ms longer than the fixed rule. About four-fifths of that (81–82%) is the one step the fixed rule does not have: choosing the second-batch directions at the received coarse background. Batched over the 64 objects, this step evaluates the Jacobian at that background (0.37 ms), forms a 27×2727\times27 task-weighted matrix (0.22 ms) and computes its eigendecomposition (0.65 ms). The decoder repeats it from the received words, because no side information is sent. The remaining 0.3 ms per side is spread over the other small steps.

In your three categories, for the two-batch rule: query selection is the direction choice, 1.27 ms in the encoder and again in the decoder; encoding proper (answering, rounding, forming the coarse background and packing) takes 0.19 ms; model recovery (unpacking, the coarse background, reconstruction and projection) takes 0.27 ms, plus 0.03 ms to compile the supports. Timed one by one, the steps sum to 1.46 ms (encode) and 1.54 ms (decode); the whole calls in the table take slightly longer. Adapting the second batch therefore costs about 3.1 ms per batch of 64 objects, encoder and decoder together.

The re-run times 25 calls after 3 warm-up calls in each configuration, on the same machine after a GPU driver update. Its times are 1.4–2.3 times lower than on page 62. The payload bytes are identical to those of the page-62 run, and the revised Appendix F.8 reports both runs.

Which steps run when:

WhenSteps
Once per modelThe public model: 2.4 KB of compressed parameters (support basis, background and context axes), from which the code rebuilds the quadrature and the detector matrix in 0.4 s
Once per declared task family, budget and requestThe fixed query matrices, the five coarse queries, and the task-weighted form used to choose the second batch. These take 2.4 ms to compute. The strong fixed rule additionally takes a median 2.8 s of offline optimisation (page-62 run). For one family and budget, the plans of all five query rules together take 210–227 KB compressed.
Once per inputAnswering and rounding the queries; for two-batch, the direction choice in the encoder and again in the decoder; reconstruction and projection into the source ball; compiling the support; one normalisation and one forecast field that every task reads

The direction choice could also move offline. The second-batch directions can be tabulated over a finite catalogue of coarse backgrounds, as in the proof of Theorem 5.1 and the catalogue heuristic of Appendix F.9. This trades the per-input eigendecomposition for public storage. The revised Section 6 reports the split above and these three categories.

W4/Q4. Notation table and the two uses of rr.

Yes, we agree on both points. The revised PDF adds a notation table that lists each symbol, its meaning and where it is defined. The smoothing order in Er=(I+Δ)−r/2E_r=(I+\Delta)^{-r/2} and μ=r+β−2\mu=r+\beta-2 now has its own symbol, ς\varsigma, so it no longer shares the letter rr with the risk requests rτr_\tau.

W5/Q5. Figure 1.

We redrew Figure 1 along the sequence you describe, as one left-to-right path: input surface → shared code (mm numbers) → one CPPZ with its area law → task forecasts. Separate task decoders appear as a dashed alternative leaving the code. Most text inside the figure moved to the caption, and the remaining labels are at least caption size.

On the strengths you list. Two additions bear on them. The pairwise-versus-joint result was replicated on 192 new task families: pairwise sizing fails in 36 (18.8%, against 19.8% originally). And all three decisions of Figure 3 are now certified, as is every decision of the 192-family study behind Section 6.2 (Appendices F.1 and F.4).

Thank you again. Your questions made Sections 3 and 6, Figure 1 and Appendix F clearer, and Q2 added a lemma to the paper. We hope the answers resolve them, and we would be glad to clarify any remaining point.

Reviewer_gJv8OpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper reads like AI-generated.

So I am using AI to generate a summary:

This paper investigates whether a single compressed probabilistic representation can simultaneously satisfy multiple prediction tasks without incurring an additional asymptotic risk penalty from requiring a consistent underlying probability model.

The authors introduce Constrained Polynomial Probabilistic Zonotopes (CPPZs), a framework combining polynomial constraint geometry, prescribed intrinsic probability distributions, and explicit observation semantics.

The principal contribution is Theorem 4.1, which establishes that, for a specified nonlinear family of smooth, strictly convex geometric models, recovering one valid CPPZ preserves the optimal leading-order risk region achievable using unrestricted task-specific decoders of a shared continuous code. The result applies to finite task families at fixed source radii within the geometric validity domain.

The paper also develops a joint capacity characterization for elliptic linear tasks without requiring a common eigenbasis (Theorem 4.2), proves an exact equivalence between continuous, linear, and deterministic adaptive-linear encoding for two compact linear tasks (Theorem 5.3), and demonstrates that geometry-dependent measurement selection can improve acquisition efficiency (Theorem 5.1).

Additionally, the authors show that pairwise task feasibility does not imply collective feasibility, constructing examples where all task pairs have identical attainable risk regions but the full task families require different compression budgets.

The theoretical results are supported by extensive mathematical arguments, synthetic geometric experiments, image-derived reconstruction tasks, and selected exact rational certificates. For instance, one six-task MNIST-derived reconstruction problem requires 36 coordinates jointly, despite every task pair being feasible with 34 coordinates.

Overall, the paper provides a comprehensive theoretical treatment of shared representation capacity, consistency of probability laws, and multi-task compatibility.

Critical strengths

Strength 1: A substantial theoretical result connecting shared prediction and consistent probabilistic recovery.

The main contribution establishes that enforcing recovery of one geometrically valid probability object does not impose an additional leading-order risk penalty in the studied nonlinear setting. The result preserves both asymptotic rates and leading constants.

This is consequential because existing shared-representation approaches often concentrate on prediction performance without requiring consistency among the probability distributions implied by different tasks.

The proof construction is also more substantial than a lower-bound argument, since it provides a shared encoder and a valid probability-object decoder attaining the characterized risk region.

Strength 2: Sharp distinctions between two-task, multi-task, and adaptive information settings.

The exact two-task equivalence theorem and the higher-order collective-feasibility counterexamples are particularly compelling.

They establish that conclusions valid for two tasks need not extend to larger task collections, even when complete pairwise risk information is available. This has potentially important implications for task grouping and shared representation design.

The combination of exact mathematical results and carefully scoped finite-dimensional certificates strengthens this contribution.

Critical weaknesses

Weakness 1: The principal capacity theorem applies to a highly specialized subclass of the proposed representation framework.

Although CPPZs are introduced as a general framework encompassing polynomial constraints, probability laws, and observation semantics, the strongest nonlinear capacity theorem is established only for a particular family of smooth, strictly convex geometric models with prescribed surface-area laws and Bessel-based observation operators.

Furthermore, the native tasks differ through their context distributions rather than arbitrary prediction mechanisms.

These assumptions are mathematically important, but they substantially restrict the generality of the main conclusion. It remains unclear whether the zero-leading-order-penalty phenomenon is characteristic of CPPZs more broadly or depends on special properties of this geometric and observational construction.

This limits how broadly the headline contribution can be interpreted.

Weakness 2: Limited connection between the optimal theoretical constructions and practically efficient compression.

The principal asymptotic characterization measures compression through real-valued coordinate budgets. Polynomial degree, model-description complexity, and computational requirements are treated separately.

Although finite-precision guarantees are provided, they do not establish bit-optimality, and the asymptotically optimal encoder construction is not shown to be computationally efficient.

Moreover, the theoretical guarantees allow encoders to depend on the declared task family and risk requirements. The finite experiments demonstrate interesting separations, but they do not establish an efficient general implementation of the optimal multi-task construction.

As a result, the paper provides stronger theoretical insight than practical evidence that CPPZ-based compression would outperform existing approaches in realistic applications.

This is a meaningful limitation given the paper's motivation in shared compressed representations.

Questions for authors

Question 1 — Generality of the common-law capacity theorem

To what extent does the asymptotic equivalence in Theorem 4.1 depend on the particular surface-area probability law and the common Bessel observation model?

Could the authors clarify which assumptions are essential for obtaining no additional leading-order penalty from common-law recovery? In particular, is there a simple CPPZ example involving different observation mechanisms, mixed strata, or more general constrained carriers where this equivalence fails?

A clearer delineation would materially affect my assessment of the result's general significance.

Question 2 — Finite-budget implications and operational complexity

Can the authors provide a more explicit account of the resources required by the asymptotically optimal common-allocation construction, including polynomial degree, public model storage, and encoding/decoding complexity?

The manuscript carefully notes that asymptotic onset is not uniform and that practical optimization is unresolved. Nevertheless, even a conservative quantitative example relating coordinate budget, risk tolerance, and computational cost would help determine whether the theoretical guarantee can be meaningful at attainable budgets.

This would strengthen the connection between the main capacity theorem and the numerical experiments.

3 comments
AuthorsOpenReview ↗

Response to Reviewer gJv8 (1/3): summary

Thank you for the review and the two questions; both led to additions to the paper. We answer Weakness 1 with Question 1 and Weakness 2 with Question 2. Brief answers follow; the two comments under this one give the details.

W1/Q1. Which assumptions are essential, and can the equivalence fail?

It can fail, and the revised PDF now says where.

  • The proof uses four properties: (a) all tasks observe one object through one detector and differ only in context weights; (b) an elliptic derivative of the same order for every task; (c) a relative tail estimate; (d) a legal reconstruction with an exact compiler.
  • With a different observation mechanism the conclusion can fail. The simplest case: the source is a disc of radius δ\delta and the code is one real number. Task 1 predicts the point zz, and task 2 predicts only its distance ∥z∥\|z\| from the centre. Separate decoders send the distance: task 2 is exact, and task 1 guesses the centre, which is optimal for one continuous number. One object must itself lie at the right distance. For any continuous code, two opposite points on the boundary receive the same number (Borsuk–Ulam), so their common object also lies on the boundary, and task 1's worst squared error at least doubles. On a Hilbert ball, for a compact TT with polynomially decaying singular values, such as the linearisation of a native task, the same argument gives at least a factor of two in task 1's leading constant.
  • The disc example and its analogues at every budget mm are themselves CPPZ task pairs. With the convex supports, area laws and finite-context Bernoulli detector of Proposition D.6, task 1 predicts the firing probabilities and task 2 only the norm of their deviation from one half. Separate decoders are optimal for task 1 and exact for task 2, while one CPPZ at least doubles task 1's risk, at every budget mm with m+1m+1 contexts (Appendix C.3; checked by quadrature on these supports).
  • The Bessel detector itself is not what the equality needs. The task pairs of Proposition D.6 use that Bernoulli detector and differ only in context weights, and there one CPPZ attains the whole continuous-code region at every budget. In the native family at finite budgets, a heat kernel or an unsmoothed band limit in place of the Bessel smoothing leaves one compiled CPPZ within 0.8% of the lower bound for every continuous code at every budget from 4 to 31 (certified).
  • Mixed strata and more general carriers are within the CPPZ framework (Definition A.1, Proposition A.2), while the theorem is stated for the native family. At finite budgets, other prescribed laws and a CPPZ whose two strata mix the area law with the mean-curvature law of the same support keep the certified equality (gaps below 2.3% and 0.7% from budget 4 on). A paragraph after Theorem 4.1 now states this scope and gives the example.

W2/Q2. What resources are needed, and is there a quantitative example?

  • For the asymptotic construction we give the number of bits (O(mlog⁡m)O(m\log m)), the Lipschitz constants and a sufficient polynomial degree; for the parameters of our finite models, support degree 2m2m suffices.
  • At small budgets we measure the risk and the cost of explicit codes. With 8, 12 and 16 coordinates, each of 15 requests set 2% above the tangent boundary is met by its own code with one compiled CPPZ, within 0.15% of the lower bound that holds for every continuous code. Ball arithmetic now certifies these bounds, and over all budgets from 4 to 31 the certified gap stays below 0.7%. At budget 16, each of these codes sends 46 bytes, uses a 4 KiB query matrix and 14 MB of shared arrays, and takes a median 16 ms per input on a CPU from encoding to prediction. With the same query matrices, requests 1%, 2%, 5% and 25% above the tangent boundary need at most 18, 17, 15 and 13 bits per answer at budget 16 (36, 34, 30 and 26 bytes).
  • Against existing codes: across 192 image-derived task families, request-weighted PCA needs a median 1.47 times as many coordinates as the shared code for the same requests, and none of four standard projection codes needs fewer in any family (certified, Appendix F.4).

Readability. The revised introduction starts from a concrete example, a convex surface that several tasks view through one detector. A notation table is added, and Figure 1 is redrawn as one path from input to predictions. The main text was also reworded for readability.

Soundness. Every theorem has a complete proof in Appendices A–E, and the three finite decisions of Figure 3 are certified: Section 6.1 in ball arithmetic, the 36-versus-35 coordinate result of Section 6.2 in exact integer arithmetic, and Section 6.3 by rational intervals. Ball arithmetic also certifies all 192 families of the Section 6.2 width study. If a particular statement or step is in doubt, we would be glad to answer it specifically.

We hope these answers address your questions, and we would be glad to clarify any remaining point.

AuthorsOpenReview ↗

Response to Reviewer gJv8 (2/3): details for Q1, which assumptions Theorem 4.1 uses

W1/Q1. Which assumptions are essential, and where can the equivalence fail?

The proof (Appendix C.1) has three steps.

  1. Lower bound. At each coarse background bb, Borsuk–Ulam gives two inputs b±abwb\pm a_bw with the same code. This bounds every decoder, separate task decoders and one CPPZ alike. It needs Weyl asymptotics for the task derivatives at bb, and a forecast that stays close to its linearisation relative to the prediction error (Lemma A.8: ηJ→0\eta_J\to0 at fixed δ\delta).
  2. One object attains the bound. The code reconstructs one source z^=b+f+∑iQs,ixi\hat z=b+f+\sum_iQ_{s,i}x_i with ∥z^∥≤∥z∥\|\hat z\|\le\|z\|, and the decoder outputs the CPPZ of z^\hat z. One object can serve all tasks because the tasks observe the same object through the same detector and differ only in context weights ωτ\omega_\tau, so every task forecast is a weighting of one forecast field. Separate decoders gain nothing at leading order because the lower bound comes from antipodal pairs b±abwb\pm a_bw, whose best common guess is their midpoint in every task norm at once, and the common allocation of Theorem 4.2 attains these constraints for all tasks with one code.
  3. Legality. Since ∥z^∥≤∥z∥≤δ<δgeom\|\hat z\|\le\|z\|\le\delta<\delta_{\rm geom}, z^\hat z is a positive, strictly convex support with a well-defined area law. The compiler turns it into a polynomial CPPZ with lower-order error (Lemmas A.4–A.5).

The surface-area law and the Bessel detector enter in three places:

  • Strict convexity makes the curvature cofactor positive definite, so the derivative of the area law is a second-order elliptic operator, and KβK_\beta and EςE_\varsigma add elliptic smoothing. Together they give every task the same order −μ-\mu and a scalar principal symbol ωτtb2\omega_\tau t_b^2, which the Weyl constants and the common decomposition of Theorem 4.2 require.
  • The regularity condition ς>s+2+k/2\varsigma>s+2+k/2 on the smoothing order (written rr in the submission) gives Lemma A.8 at a fixed radius.
  • The area law is closed under mixing: a mixture of area laws of smooth strictly convex bodies is again an area law (Minkowski's theorem). Hence legal decoding costs nothing for one task at a fixed message (Proposition A.6).

So the proof uses four properties:

  • (a) one object seen through one detector, with tasks differing only in context weights;
  • (b) an elliptic reference-to-decision derivative of common order with scalar principal symbol;
  • (c) a relative tail estimate at the working radius;
  • (d) a reconstructed source that is legal, together with an exact compiler.

These are the properties the proof uses; the theorem itself is stated for the native family.

A different observation mechanism can break the equivalence at leading order. On a Hilbert ball (as in Theorem 5.3), task 1 predicts TzTz for a compact TT whose singular values decay polynomially, and task 2 only the score ∥Tz∥\|Tz\|; TT can be a native task linearised at a background, whose singular values decay polynomially by Weyl's law. Separate decoders spend one of the mm coordinates on the score, so task 2 is exact and task 1 loses nothing at leading order. One object must reproduce the score. By Borsuk–Ulam, any continuous mm-coordinate code gives one object to some pair ±z0\pm z_0 in the top m+1m+1 singular directions. Both have the same score, so the object cannot sit at their midpoint, and the parallelogram law gives r1≥1+(1−r2)+2r_1\ge1+(1-\sqrt{r_2})_+^2 in units of task 1's separate-decoder constant. The penalty does not need an exact score: r2≤1/4r_2\le1/4 still forces r1≥5/4r_1\ge5/4. With an exact score, task 1 therefore needs at least twice its separate risk (four times is attainable): a penalty in the leading constant. What fails is step 2, which uses property (a): the score does not read the shared forecast field with a context weight, so the midpoint no longer serves every task. The score's derivative also has rank one, so (b) fails too.

Other detectors, laws and strata at finite budgets. Mixed strata and more general carriers are within the CPPZ framework (Definition A.1, Proposition A.2). Over 31 budgets and 65 request ratios each, ball arithmetic certifies how far the requests one compiled CPPZ meets lie above those excluded for every continuous code, from budget 4 on: below 0.7% in the paper's model; at most 0.8% with the Bessel smoothing replaced by (1+λℓ)−1/2(1+\lambda_\ell)^{-1/2}, (1+λℓ)−5/2(1+\lambda_\ell)^{-5/2}, a heat kernel or an unsmoothed band limit (the last two of no finite elliptic order); 0.5%, 1.2% and 2.3% for the laws 1+trH+αdet⁡H1+\mathrm{tr}H+\alpha\det H with α=1/2,2,4\alpha=1/2,2,4; and at most 0.7% for two strata mixing the area law with the mean-curvature law.

The revised paper lists (a)–(d) after Theorem 4.1 and gives the example, proved and realised by CPPZs in Appendix C.3.

AuthorsOpenReview ↗

Response to Reviewer gJv8 (3/3): details for Q2, resources and a quantitative example

W2/Q2. What resources does the asymptotic construction need?

The theorem charges real coordinates. Section 3 treats public descriptions, polynomial degree and computation as separate resources. From the proofs:

  • Bits. ⌈(μ/k+2)log⁡2(m+1)⌉\lceil(\mu/k+2)\log_2(m+1)\rceil bits per coordinate preserve the leading risks, so O(mlog⁡m)O(m\log m) bits in total (Section 4.3).
  • Stability. Encoding and recovery are Lipschitz with constants Cmlog⁡(e+m)Cm\log(e+m) and Cmlog⁡2(e+m)Cm\log^2(e+m) (Section 4.3). As Section 4.3 states, these bounds give neither bit-optimality nor efficient decoding; at small budgets we measure the cost directly (below).
  • Polynomial degree. One support degree 2L(m)2L(m) serves every message, where L(m)−(ς−t)=o(m−μ/k)L(m)^{-(\varsigma-t)}=o(m^{-\mu/k}) for some t∈(2+k/2,ς)t\in(2+k/2,\varsigma) (Lemma A.5), and the density has degree at most 2kL(m)+22kL(m)+2 (Lemma A.4). For the parameters (ς,β,k)=(8,3,2)(\varsigma,\beta,k)=(8,3,2) of our finite models, μ/k=4.5\mu/k=4.5, so any t∈(3,3.5)t\in(3,3.5) allows L(m)=mL(m)=m: support degree 2m2m and density degree at most 4m+24m+2.
  • Public description. Each decomposition, margin and selector is fixed before its spectral budget limit and then refined along one slow sequence (Section 4.3, Appendix C.1); the table below gives measured sizes at budget 16.

One code with its risk and its cost (Section 6.1, Appendix F.1)

In the native model with 32 harmonic coordinates, take budget 16 and the request with risk ratio 1/2, set 2% above the tangent boundary; both task constraints bind there. The request selects a projection, and its 23-bit answers are compiled into one CPPZ.

QuantityValue
Request, tasks 1 and 2 (half-Brier, 10−1510^{-15})10.999, 5.4995
Whole-ball nonlinear upper bounds (certified)10.787, 5.394
Upper bound over the lower bound for every continuous code, along the request1.0004
Payload16 answers, 368 bits (46 bytes)
Query matrix, once per request4 KiB
Support degree / density degree5 / at most 12
Geometry and bound arrays in memory, once per model14.0 MB, built in 0.2 s
Choosing the projection and evaluating the bounds, once per request8.1 ms
Encoding, recovery, compilation and prediction, per input on a CPU (median of 16, after warm-up)16.0 ms, of which compilation 15.5 ms

Ball arithmetic certifies these bounds for the stored model and query matrices (revised Appendix F.1). All 15 requests at budgets 8, 12 and 16 are met, within 0.15% of that lower bound, at per-input medians of 15.8–16.1 ms. The coordinatewise minimum of two opposing budget-16 requests is excluded at budget 16 and met at budget 17, with 391 answer bits (49 bytes).

Other finite examples

  • Linear, six tasks (Section 6.2). In an MNIST family, 36 coordinates meet all six requests and 35 cannot, with exact integer arithmetic on both sides.
  • Bits (Section 6.3). At radius 300, 36 bits over three adaptive queries, or 26 bits over four fixed ones, meet the request under a rational upper bound.
  • Up to eight tasks, batched on a GPU (Appendix F.8). On 18 nonspherical backgrounds, payloads are 20, 40 and 60 bytes at budgets 8, 16 and 24; the stored public model takes 2.4 KB compressed, from which the code rebuilds quadrature and detector in 0.4 s; and a batch of 64 objects takes 0.07–1.66 ms to encode or decode (medians; per-step times in our reply to Reviewer nQqU, Q3).

Section 6.1 and Appendices F.1 and F.8 of the revision report these costs.

Dependence on declared tasks and requests

The comparison fixes the class of codes and changes only the decoder. Request-dependent codes are therefore the fair setting for asking what one object costs. A request-independent encoder is a stronger requirement and a different question, closer to universal coding (Zhang et al., 2021). Within our results, part of the dependence on the task family disappears: codes built for eight tasks serve 64 new convex mixtures of them with unchanged bytes and law. This holds because the risk under a mixed context is the same mixture of the task risks (Appendix F.8).

Practical comparisons

The paper's claims concern capacity: what it costs, in coordinates and risk, to require one valid probability object. Where the bounds meet practical codes, they bind. On image-derived tasks the shared construction meets 2,303 of 2,304 boundary requests, while PCA misses all of them, by a median 46% (Appendix F.2). In the 192-family width study, request-weighted PCA needs a median 1.47 times as many coordinates as the shared code to meet the same requests, and mean-Gram PCA 1.58 times, and none of the four standard codes compared needs fewer in any family (Appendix F.4). The bounds also bind learned codes: on 45 image targets that the collective bound excludes (certified), every trained neural encoder we tried violates the requests (Appendix F.4).

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response: summary of the paper, the reviews and the revision

We thank the three reviewers for their time. Reviewers gJv8 and nQqU count the main theorem, the separation between pairwise and collective feasibility, and the exact certificates among the paper's strengths.

What the paper asks. A shared compressed code can be decoded separately for each task, or into one valid probability model from which every task's prediction is computed. The paper asks what the second option costs. In the nonlinear family we study, it costs nothing at leading order (Theorem 4.1). For any two compact linear tasks, continuous, linear and adaptive-linear codes have the same exact risk region at every budget, attained by one common projection (Theorem 5.3). Complete pairwise information does not determine the collective budget: two task triples can have identical pairwise risk regions at every budget yet need 3M3M versus 4M4M coordinates, for any M≥2M\ge2 (Proposition D.6), and in a six-task MNIST family every pair fits in 34 coordinates while all six need 36 (Section 6.2). Measurement design matters as well (Proposition 5.2).

What the reviews ask. The concerns are motivation (6dnJ), readability (all three reviewers), the scope of Theorem 4.1 and the resources it needs (gJv8), and five points of clarification (nQqU). As far as we can see, none of them points to an error in a statement, proof or certificate; if a reviewer doubts a specific step, we will gladly answer it.

What changed. Prompted by the reviews, the revised PDF makes the changes below; the individual replies give the details.

  • Scope of Theorem 4.1 (gJv8). A paragraph after the theorem lists the four properties its proof uses: one object and one detector; an elliptic derivative of common order; a relative tail estimate; and legal reconstruction with an exact compiler. It shows that the equality is not automatic: in a task pair where one task predicts a vector and the other only its length, one object can cost a constant factor at leading order, and Appendix C.3 realises such pairs by CPPZs at every budget. With other detectors (two of them of no finite elliptic order), other prescribed laws and mixed strata, the certified finite-budget equality persists (Appendix F.1).
  • Resources (gJv8, nQqU). Section 6 reports the cost of the codes that meet the budget-16 requests (46-byte payloads, a median 16 ms per input on a CPU), the resource counts and per-step timings of the GPU study, and which steps are precomputed and which run once per input.
  • Certified finite decisions (all reviewers). Ball arithmetic now certifies the uniform bounds of Section 6.1 (all 15 requests, the 16-versus-17-query decision, and a rerun of the threshold map over 31 budgets and 65 request ratios) and every saved decision of the 192-family width study of Section 6.2. On the 432 fresh nonspherical backgrounds of Section 6.1, applying the paper's cross-term bound to every screened request raises the requests with sufficient uniform bounds from 1,232 to 1,440, and ball arithmetic certifies all 1,440. Across the threshold map from budget 4 on, the requests one compiled CPPZ meets are certified within 0.7% of those excluded for every continuous code, and in the tightest cell a worst-case search through the decoder reaches 99.99% of the certified upper bound. Together with the exact integer certificate of Section 6.2 and the rational intervals of Section 6.3, all three decisions of Figure 3 are certified. A replication on 192 new families from the same generator finds pairwise sizing insufficient in 36 (18.8%, against 19.8% originally, all certified), as predicted before the run.
  • Standard codes (6dnJ, gJv8). Appendix F.4 compares the shared code with four standard projection codes on all 192 families: to meet the same requests, request-weighted PCA needs a median 1.47 times as many coordinates and mean-Gram PCA 1.58 times, and none needs fewer in any family.
  • Precision choices (nQqU). Section 6.3 explains how the bit allocations (13,13,10)(13,13,10) and (11,11,2,2)(11,11,2,2) were found, and why the coarse answers need more bits than the fine ones.
  • Image tasks (nQqU). Appendix F.2 adds a bound on the collective excess in terms of how far the tasks are from being ordered, evaluated on 6,912 targets, and control experiments. The image-operator triples lie almost entirely in the range where none of these 6,912 targets is excluded.
  • Motivation and readability (all reviewers). The introduction starts from a concrete example. Section 3 has a notation table, and the smoothing order and the risk requests no longer share the letter rr. Figure 1 is redrawn with one path from input to predictions and with larger labels. The wording of the main text was also edited for readability, and one sentence of the abstract now names the two decodings being compared; these edits change no result or number. All changes are marked in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.