- 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
- 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.
- 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
- 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?
- 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?
- What is the main theoretical novelty of Theorems 4.1 and 4.2?
- Why not consider a realistic coordination or distributed optimization problem with a real-world dataset or learning problem?
- 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?
- 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
Thank you to the authors for their detailed responses and clarifications. I maintain my original rating.
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, L=8, and Gi=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=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=8, improved solver-error guarantees allow certification of all 200 quadratic and 200 log-cosh instances within 512 rounds.