acceptodds
Under review as a conference paper at ICLR 2027

Private-Response Coordination: Information Limits and Feasible Decisions

Abstract

A coordinator can query each party's allocation at a price without observing its objective. We study when these responses suffice to produce and certify a feasible joint decision. We construct coupled strongly convex objectives with different optima that admit the same error-bounded vector response at every price. Their two-world minimax regret equals the conditional-error budget, even with arbitrary adaptive queries and unlimited memory. A comparison family separately gives sharp query, state, and ambiguity bounds. We then certify feasible candidates from response positions, public smoothness, and local error bounds without fitting their objectives. On identical transcripts and recovered averages, the position certificate verifies target accuracy after a mean of and high-fidelity calls for quadratic and log-cosh objectives. Neither recovery-based certificate does so within calls. Coupled nonlinear studies show how response fitting and validation complement each other. The results distinguish irreducible response ambiguity from avoidable certificate conservatism.

Primary area:
optimization
Keywords:
private-response coordination, constraint-coupled optimization, query complexity, persistent state, response fidelity

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_6ggkOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies a coordination problem where multiple parties retain private local objective functions, and a coordinator can query their responses to publicly specified prices. A method for certifying the quality of feasible decisions without reconstructing the private objectives. The theoretical results show a regret lower bound when distinct strongly convex objectives produce indistinguishable approximate responses. A response-position certificate is developed to certify the regret of a feasible candidate. Simulation results compare the proposed certificate with recovery-based alternative and investigate how candidate generation and publicly available solver information affect certification performance.

Critical strengths

This paper presents detailed mathematical formulations and theoretical results. It develops several results, including regret lower bounds, query-state-ambiguity trade-offs, and a response-position certificate.

Critical weaknesses
  1. The writing seems poor. The paper is difficult to follow due to the lack of a clear and well-motivated problem formulation. The introduction provides only a brief application example before moving directly to abstract concepts, mathematical formulations, and the claimed contributions. It does not adequately explain why the studied problem is important, what specific limitations exist in established coordination and optimization methods, or why these limitations motivate the proposed framework.

The presentation also lacks sufficient intuition behind the main theoretical results and the proposed response-position certificate. The related work section provides a relatively brief overview of existing approaches without clearly identifying their limitations or explaining the fundamental differences between them and the proposed method.

More importantly, the significance of the theoretical contributions remains unclear. The indistinguishability-based regret lower bound and the query-state-ambiguity trade-off are established under specifically constructed models, but their broader implications are not convincingly explained. The paper does not demonstrate whether these results provide new insights beyond existing theories of related optimization papers.

It is difficult to assess the novelty and significance of the proposed contributions in this paper.

  1. Experiments are conducted on small-scale synthetic optimization problems with quadratic and log-cosh objectives. These results are limited. The author should conduct experiments on real-world datasets, general optimization and machine learning problems.
Questions for authors
  1. What is the limitation of existing coordination or optimization certification methods that motivates the proposed framework? Could the authors provide a concrete example illustrating why existing approaches are insufficient and how the proposed method addresses this limitation?
  2. Can the authors provide a more detailed explanation of Figure 1? How can different objective functions produce indistinguishable responses, and how does the proposed certificate achieve tighter bounds using the same response information?
  3. What is the main theoretical novelty of Theorems 4.1 and 4.2?
  4. Why not consider a realistic coordination or distributed optimization problem with a real-world dataset or learning problem?
  5. The proposed certificate is based on several assumptions, such as smoothness constants, gradient bounds, and local conditional error bounds. Are these assumptions too strict? Are they commonly used in the related optimization studies? How can these parameters be determined in practical problems where the local objective functions are private?
  6. In Table 1, all methods achieve the target accuracy with (J = 4), but none of them can be certified by the proposed position certificate within 512 response calls. Why does the proposed certificate fail in this setting? What are the main factors determining whether an accurate candidate can be successfully certified?
2 comments

Q1: In edge computing, IoT energy management, and wireless networks, parties must coordinate shared resources without disclosing objectives that encode proprietary costs, operating strategies, or sensitive usage patterns. The coordinator therefore queries local decisions through prices rather than accessing these objectives. Classical decomposition methods provide convergence and recovery guarantees, but their error bounds can remain inconclusive even for an accurate feasible candidate. Proposition 5.1 instead certifies such a candidate directly from response positions and public bounds, independently of how it was generated. We have strengthened this motivation and the comparison with existing methods in the Introduction and Related Work.

Q2: Figure 1(a) shows how two different optimization problems can produce indistinguishable approximate responses. Although their true optimal solutions differ, a common response function can satisfy the allowed solver-error bound for both problems at every price. Thus, the coordinator can receive exactly the same responses regardless of which problem is present, and additional price queries cannot resolve this ambiguity. Figure 1(b) shows why different certificates can give different conclusions about the same solution. Recovery-based certificates rely on convergence and error bounds of the optimization procedure, which may be too conservative to confirm that a feasible solution meets the target accuracy. Our position certificate instead uses the distance between the candidate and the observed local responses, together with public bounds, to evaluate its quality directly. As a result, the same candidate can be certified by our method even when the recovery-based bounds remain inconclusive.

Q3: As discussed in our response to Reviewer sNpR (W1), the two theorems address complementary information limits. Theorem 4.1 goes beyond analyzing how inexact responses affect algorithmic convergence. It establishes an exact worst-case regret floor for coupled strongly convex problems, showing that fixed response-error bounds can make different problems indistinguishable at every price, even with unlimited adaptive queries and memory. Theorem 4.2 builds on comparison-search and finite-memory ideas, but jointly characterizes query depth, retained state, and response ambiguity in a scalar optimization setting. Its contribution is to establish sharp bounds on the resulting decision regret, explicitly quantifying the effects of these three factors.

Q4: Controlled quadratic and log-cosh problems let us compute the true optimum and compare certificates on identical candidates and response histories. This separates inaccurate candidates from conservative certification bounds. Real-world applications, such as edge computing, IoT energy management, and wireless resource allocation, introduce additional challenges. Evaluating our framework in these settings requires modeling private local objectives, implementing price-based response interfaces, and establishing reliable error bounds for local solvers. A real-world dataset alone would not necessarily provide these components or the ground-truth optimum needed for controlled certificate comparisons. We additionally evaluated candidate generation on seven coupled quadratic configurations, up to 32 parties and 64 variables per party (200 instances each). These tests extend the scale studied; real-world coordination or learning-task validation remains future work.

Q5: The certificate requires valid smoothness, gradient, and conditional-error bounds, but does not require access to the realized private objective parameters. Such bounds can follow from a declared problem class and solver guarantees. Appendix I.3 derives μ=0.5\mu=0.5, L=8L=8, and Gi=8G_i=8 from public parameter ranges. Eq. (25) bounds conditional error using midpoint initialization and projected-gradient convergence. A local stopping certificate is also usable if it gives a valid conditional-suboptimality upper bound. A heuristic residual without that guarantee is insufficient. Table 2 shows why tightness matters: the valid midpoint bound raises dense-fit certification from 0% to 100% across four structural settings, with unchanged candidates and responses.

Q6: At J=4J=4, candidates meet the target accuracy under the true objectives, but four local iterations leave a loose conditional-error bound. The resulting position-certificate upper bound exceeds the target, even for accurate candidates. More response rounds need not fix this when solver fidelity is unchanged. Certification also depends on candidate–response distances and public bound tightness. At J=8J=8, improved solver-error guarantees allow certification of all 200 quadratic and 200 log-cosh instances within 512 rounds.

Thank you to the authors for their detailed responses and clarifications. I maintain my original rating.

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

This paper studies when price-query responses suffice to produce and certify a feasible joint decision without observing local objectives. It establishes an indistinguishability lower bound under fixed response-error caps and a separate query--state--ambiguity tradeoff for a scalar comparison family. It then develops a response-position certificate using complete local responses and public bounds, and compares its performance with recovery-based certificates on identical candidates and response histories.

Critical strengths

The paper clearly distinguishes response ambiguity from certificate conservatism and isolates improvements in certification through controlled comparisons on identical candidates and response histories.

Critical weaknesses
  1. The connection between the theoretical results could be clearer. The exact query--state tradeoff in Theorem 4.2 applies to a scalar comparison family, whereas Theorem 4.1 concerns coupled vector responses and Section 5 uses complete local responses for certification. Although the restricted scope is acknowledged, it remains unclear what quantitative guidance the comparison result provides for the vector-response setting used in the experiments.

  2. The practical requirements of the certificate deserve further justification. Section 3 normally returns interface responses, while Section 5 requires complete local decisions and public smoothness, coordinate-gradient, and conditional-error bounds. The paper should explain how these bounds can be obtained when objectives remain private and what additional communication or disclosure is required. A direct comparison of the information required by the closest certification methods would also clarify the contribution.

  3. The experiments provide limited evidence about robustness and scalability. Table 1 reports no certification at J=4J=4 despite attainment of the offline target, while Table 2 shows that tightening the public error bound changes dense-fit acceptance from zero to 100%. Moreover, the main experiments use only four parties. Sensitivity studies for the public bounds and scaling experiments reporting computation and communication costs would better establish the practical benefits.

Questions for authors

Q1. Equation (2) uses ymy_m for interface responses, whereas Section 5.1 uses yy for complete local decisions. Could distinct notation be used to make the change of space easier to follow?

Q2. Please clarify whether calls'' and depth'' in the abstract and Table 1 refer to calls per party, consistently with Figure 2 and the distinction between QQ rounds and MQMQ responses in Section 3.

2 comments

W1: The three results address two related questions: what information can be obtained from local responses, and how effectively can it be used? Theorems 4.1 and 4.2 study the first question from different perspectives. Theorem 4.1 shows that different optimization problems can admit identical approximate responses at every price under fixed conditional-error caps, making some uncertainty unavoidable regardless of the number of queries. Theorem 4.2 further examines how query depth, memory, and response ambiguity affect decision accuracy in a scalar comparison setting. Proposition 5.1 addresses the second question. It shows that when sufficient response information is available, we can certify the quality of a feasible decision directly from response positions and public bounds, without reconstructing private objectives. Together, these results distinguish limitations of the response information itself from limitations in how that information is used. We have clarified these connections in the Introduction and between Sections 4 and 5.

W2: The position certificate requires complete local responses rather than only their interface images, but does not require access to private objective values, gradients, or realized parameters. This introduces additional communication: if party mm has nmn_m local variables and the interface dimension is pp, transmitting complete responses requires ∑mnm\sum_m n_m scalars per round, compared with MpMp for interface-only responses. Appendix H.3 provides a local-certificate alternative in which parties retain complete responses and communicate scalar certificate bounds, trading central disclosure for additional local computation and storage. The required public bounds can be derived from declared problem structures and solver guarantees without revealing private objectives. For example, Appendix I.3 establishes μ=0.5\mu=0.5, L=8L=8, and Gi=8G_i=8 from public parameter ranges, while Eq. (25) derives a conditional-error bound from the known initialization and projected-gradient convergence guarantee. Compared with recovery-based certificates, which use algorithm-specific recovery analysis and associated error terms, our position certificate directly evaluates an already feasible candidate using response positions and public bounds, independently of how the candidate was generated. We have clarified these information requirements and the differences from existing certification approaches in Section 5.

W3: We conducted additional candidate-generation scalability experiments on coupled quadratic problems, covering seven configurations with up to 32 parties and 64 local variables per party, using 200 instances per configuration. At J=64J=64, increasing the number of parties from 4 to 16 reduces mean normalized feasible regret from 1.35×10−41.35\times10^{-4} to 6.63×10−66.63\times10^{-6}. Increasing the local dimension from 8 to 64 (with four parties) yields comparable regret (1.35×10−41.35\times10^{-4} to 1.79×10−41.79\times10^{-4}). At 32 parties, performance deteriorates under the unchanged fixed-step solver, suggesting that solver configuration becomes important at larger scales. Regarding sensitivity, Table 2 shows that replacing the diameter-based solver-error bound with the tighter midpoint bound increases certification acceptance from 0% to 100% across all four structural settings, without changing the candidates or responses. Furthermore, at J=8J=8, the position certificate successfully certifies all 200 quadratic and 200 log-cosh instances within 512 rounds. At J=4J=4, accurate candidates are not certified by the position certificate, illustrating the importance of sufficiently tight solver-error guarantees. Finally, Appendix J.4 reports the computational cost of the certificate: the midpoint-grid implementation requires a median of 18 microseconds per instance, compared with 109 microseconds for expanded search. We have incorporated the supplementary scalability results and clarified these findings in the revised manuscript.

Q1-Q2: We have clarified the distinction between complete local responses Rm(λ)R_m(\lambda) and interface responses ym(λ)=AmRm(λ)y_m(\lambda)=A_mR_m(\lambda) in Sections 3 and 5. We have also clarified in the abstract and Table 1 that QQ denotes response rounds (calls per party), with MQMQ total local response calls.

Thank you for addressing my concerns. While the evidence is still limited to controlled settings, the additional experiments and clarifications strengthen the paper. I will increase my score by one point.

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

This paper studies what a coordinator can infer from price-based local optimization responses and how it can certify the quality of a feasible joint decision. The authors construct strongly convex problems with different optima that admit identical approximate responses at every price, establishing an irreducible regret floor under fixed error budgets. They also analyze query–state–ambiguity trade-offs in a comparison model and propose a position certificate based on complete responses, public smoothness, and error bounds. Synthetic experiments show earlier certification than two recovery-based bounds on identical responses and candidates.

Critical strengths

1.The paper distinguishes insufficient response information, poor candidate quality, and conservative certification. This is useful because failure to certify does not necessarily imply an inaccurate decision. 2.Theorem 4.1 establishes an exact two-world minimax bound despite adaptive queries, randomization, and unlimited memory. It demonstrates that additional price queries cannot eliminate all uncertainty under fixed conditional-error budgets. 3.The main comparison keeps response histories and candidate decisions fixed while changing only the certificate, effectively isolating certification quality. Query counts, local solver work, fitting, and certification costs are also accounted for separately.

Critical weaknesses

The all-price lower bound permits any oracle satisfying the fixed error cap, while the comparison model allows adversarial choices within ambiguity regions. These are meaningful worst-case results, but do not directly establish the same obstruction for a particular numerical solver. The paper acknowledges this distinction, yet the connection between the hard constructions and practical solver behavior remains limited. The experiments focus on small synthetic quadratic and log-cosh problems with public box and balance constraints. The structural study uses four parties with eight variables each, leaving scalability and more complex local constraints insufficiently tested. Certification is also highly sensitive to the declared solver-error bound: replacing the diameter bound with the tighter midpoint bound substantially changes acceptance. Practical usefulness therefore depends on obtaining reliable and sufficiently tight error guarantees.

Questions for authors

1.Could you evaluate the interface-response-plus-local-certificate scheme and report its additional communication, storage, and local computation costs? 2.Can you construct instances approaching the Theorem 4.1 floor for a fixed solver, initialization, and stopping rule? Which additional solver properties can break the indistinguishability? 3.How much tighter could certification become by jointly enforcing smoothness, convexity, or strong-convexity consistency across responses, and at what computational cost? 4.How would the method apply when parties cannot provide tight global smoothness, strong-convexity, or solver-error bounds? Can verifiable local stopping criteria be used instead? 5.Could you scale the experiments to more parties, higher local dimensions, and more complex coupling constraints? Also, can actively choosing a better validation price improve acceptance without changing the candidate?

1 comment

Q1: Appendix H.3 provides a local-certificate scheme that avoids transmitting complete local decisions to the coordinator. For QQ rounds, the central approach communicates Q∑mnmQ\sum_m n_m response scalars, whereas the local scheme requires QMpQMp interface scalars, up to MQMQ combination-weight scalars, and MM certificate scalars per validation, where nmn_m and pp denote the local and interface dimensions. In exchange, parties retain Q∑mnmQ\sum_m n_m response scalars locally and perform the certificate calculations themselves. Thus, the scheme reduces central information disclosure at the cost of additional local storage, computation, and messages. We have clarified these trade-offs in Section 5 and Appendix H.3.

Q2: Theorem 4.1 establishes an oracle-level worst-case bound over responses satisfying fixed conditional-error caps, rather than a lower bound for every numerical solver. Its construction guarantees identical admissible responses at every price, independently of the coordinator's adaptive query strategy. A fixed solver may break this indistinguishability if its initialization, update rule, or stopping behavior produces distinguishable responses across the two problems. In particular, sufficiently accurate responses can expose differences hidden by the fixed error cap. We have made this distinction more explicit in Section 4.1.

Q3: The current certificate uses the near-optimality and position information of a response at a given price. Section 5.2 also permits historical reuse, taking the minimum of valid position bounds computed from retained responses without additional oracle calls. Jointly enforcing smoothness, convexity, or strong-convexity consistency across responses could further restrict the set of compatible objectives and potentially tighten certification. Unlike historical reuse, this would require solving a larger optimization problem with constraints across multiple queries, involving additional computation and retained information. We have clarified this distinction in Section 5.2.

Q4: The certificate requires valid public smoothness, gradient, and conditional-error bounds, but not the realized private objective parameters. For example, Appendix I.3 derives μ=0.5\mu=0.5, L=8L=8, and Gi=8G_i=8 from declared parameter ranges. Eq. (25) obtains a conditional-error bound from the known midpoint initialization and projected-gradient convergence guarantee. Alternatively, a locally computed stopping certificate can be used if it provides a valid upper bound on conditional suboptimality. A heuristic stopping residual alone is insufficient without such a guarantee. The importance of bound tightness is demonstrated in Table 2: replacing the diameter-based bound with the valid midpoint bound increases dense-fit certification from 0% to 100% across all four structural settings, without changing candidates or responses.

Q5: We conducted additional candidate-generation scalability experiments on seven coupled quadratic configurations, with up to 32 parties and 64 local variables per party (200 instances per configuration). At J=64J=64, increasing the number of parties from 4 to 16 reduces mean normalized feasible regret from 1.35×10−41.35\times10^{-4} to 6.63×10−66.63\times10^{-6}. Increasing the local dimension from 8 to 64 with four parties yields comparable regret. At 32 parties, performance deteriorates under the unchanged fixed-step solver, highlighting the importance of solver configuration for larger problems. For validation prices, Section 5.2 allows the same candidate to be checked against retained responses at different historical prices, taking the smallest valid bound without additional response calls. Actively selecting a new validation price could further improve acceptance, at the cost of additional oracle calls. Extending the certificate to more general local constraints would also require adapting its computation beyond the current box-constrained setting. We have incorporated the supplementary scalability results and clarified these considerations in the revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.