{"id":"efe19e07-dc17-42a1-8a78-0b6f0291b0b7","arxiv_id":"1908.03080","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A distributed cutting-plane algorithm that uses alternating projections and secure multiparty summation to solve nonconvex resource allocation problems without revealing agents' private constraints or profiles.","lead":"This paper designs a privacy-preserving method for a central operator to allocate shared resources among many agents whose individual constraints stay private, while minimizing a possibly nonconvex cost. It combines alternating projections, cutting planes, and secure multiparty computation, and demonstrates the approach on a microgrid with 256 consumers.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Halving ε_cvg can accept an invalid Hoffman cut before the hypotheses of Prop. 3.8 hold, so the constructive guarantee of Algorithm 3.4 is not established.","rationale":"The paper's core construction is plausible and mostly well-supported: Theorem 3.3 is the key structural result, and the privacy analysis via permutation invariance is reasonable. The reader identified the unknown constants ν and ρ as the weakest assumption, and that is indeed the main soft spot. However, the more precise and more damaging issue is that the proposed halving loop can terminate with an invalid cut before the hypotheses of Proposition 3.8 are satisfied. The paper explicitly states in the text following Algorithm 3.3 that 'in practice it is easier and more efficient to proceed in an iterative manner' and that Proposition 3.8 ensures finite termination; this is a limitation statement that deserves flagging. A wrong cut accepted early breaks the correctness of Algorithm 3.4, not just its complexity. This justifies a CONDITIONAL rather than ACCEPT verdict: the theoretical framework is valuable, but the constructive guarantee needs either a proof that the halving test cannot accept an invalid cut, or a practically computable bound on ν, or a modification of the algorithm that verifies cut validity before acceptance. I do not see grounds for REJECT, since the exact-constant version of the algorithm is correct and the numerical experiments are suggestive, though not fully reproducible. The concrete test I propose would settle whether the halving heuristic is genuinely unsound or merely unproven.","tokens_in":30906,"tokens_out":6283,"duration_ms":72124,"concrete_test":"Search over small instances with T = 4, N = 3 and rational bounds, fixing an infeasible target p. For each instance, compute ρ and ν exactly (e.g., by semidefinite or exact-arithmetic methods), then run Algorithm 3.3 with B and ε_cvg deliberately violating the hypotheses of Proposition 3.8 (e.g., 2B ε_cvg > ν). Whenever the algorithm returns a cut, check whether the inequality Σ_{t∈T} p_t ≤ AT(x^(k)) is valid for all p ∈ PD by enumerating all Hoffman inequalities (2.5) or all vertices of PD. If any returned cut is violated by a feasible p ∈ PD, the halving heuristic is unsound. Repeat for random instances and report the first counterexample.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The finite-time cut-generation step (Propositions 3.8 and 3.9) is only valid under hypotheses B > 1/(1−ρ) and 2B ε_cvg < ν, where ρ and ν depend on the private data and are unknown a priori. Theorem 3.20 gives a computable upper bound for ρ, so B can be chosen conservatively, but ν remains unknown. The paper's practical remedy (Algorithm 3.3, lines 16–22) is to halve ε_cvg until a violated cut is found. This heuristic is not proven sound: if the test AT − Σ_{t∈T} p_t < 0 passes for a set T ≠ T∞, Algorithm 3.3 returns the cut Σ_{t∈T} p_t ≤ AT(x^(k)), which may not be a valid Hoffman inequality for PD. Adding such an invalid cut can remove feasible aggregate allocations and make Algorithm 3.4 converge to a suboptimal or infeasible solution. The claim that 'Proposition 3.8 ensures this loop terminates in finite time' only shows that eventually, if no earlier termination occurs, the correct cut is found; it does not rule out an earlier false positive. Proposition 3.13 therefore holds only if ν (and effectively ρ) are known, contradicting the constructive nature of the algorithm. This is load-bearing because the central guarantee that Algorithm 3.4 computes an optimal allocation depends on every added cut being valid.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a privacy-preserving cutting-plane method for a resource allocation problem in which a central operator minimizes a possibly nonconvex cost over an aggregate allocation p while each agent n must realize an individual profile x_n in a private feasible set X_n, and the profiles must sum to p. The authors assume first that each X_n is a transportation polytope (a demand constraint plus componentwise bounds) and later discuss a general polyhedral extension. The central idea is to solve a sequence of master problems with increasingly constrained feasible sets P^(s), and to use the Alternate Projections Method (APM) to test whether the current aggregate allocation is disaggregable. If the disaggregation is infeasible, the limit cycle of APM is used to construct a violated Hoffman inequality, which is added as a cut; secure multiparty computation (SMC) is used to compute the needed aggregates without revealing individual profiles. The paper states a finite-time version of the cut-generation procedure (Propositions 3.8 and 3.9), termination after at most 2^T - 2 cuts (Proposition 3.12), a correctness statement (Proposition 3.13), an explicit APM convergence-rate bound in the transportation case (Theorem 3.20), and numerical experiments on a nonconvex microgrid problem.","tokens_in":31246,"tokens_out":12521,"duration_ms":127997,"significance":"If the advertised guarantees held, this would be a valuable contribution to distributed, privacy-aware optimization: it applies to nonconvex master problems, it has a finite cut bound that is independent of the number of agents in the transportation case, and its use of SMC to protect individual constraints and iterates is a useful design. The core cut-validity argument (Theorem 3.3 and the supporting Proposition 3.4) is a self-contained and interesting piece of polyhedral analysis, and the explicit APM rate is a worthwhile attempt to quantify the linear dependence on N. However, the finite-time exactness claims depend on unverifiable data-dependent constants, the practical halving heuristic is not proven sound, and the stopping criteria of the non-intrusive algorithm are not fully specified in a privacy-preserving way. These issues are load-bearing for the central correctness theorem, so the paper needs substantial revision before the main claims can be accepted.","major_comments":[{"comment":"The acceptance test on line 18 of Algorithm 3.3 only checks whether the candidate cut is violated by the current p. It does not verify that the set T computed on line 16 coincides with T∞. If APM has stopped with a coarse ε_cvg, the hypotheses of Proposition 3.8 may not hold, so T can differ from T∞; then Proposition 3.9 does not apply, and the returned value AT may not equal AT(x∞). The inequality sum_{t∈T} p_t ≤ AT added in Algorithm 3.4 may therefore be invalid for some feasible disaggregations, and adding it can remove true optimal allocations. The halving loop proves only that if no earlier cut is accepted, a sufficiently small ε_cvg is eventually reached; it does not exclude a false positive at an earlier, coarser precision. Proposition 3.13 is therefore not established for the algorithm as stated. The authors should either prove that passing the line-18 test implies T = T∞, or modify the algorithm so that a cut is added only after its validity is certified, for example by computing the true Hoffman right-hand side for the candidate T via SMC and adding the cut only when that valid inequality is violated.","section":"§3.2, Algorithm 3.3, lines 16–22; Props. 3.8 and 3.9"},{"comment":"Proposition 3.13 is conditional on constants B and ε_cvg satisfying B > 1/(1−ρ) and 2B ε_cvg < ν, where ρ is the APM contraction rate and ν := min{|ν∞_t| > 0} is the smallest nonzero component of the limit multiplier. Neither ρ nor ν is known a priori, and ν depends on the private data of all agents. The paper explicitly notes that a conservative lower bound on ν could be obtained by Diophantine arguments in a rational-input model, but no such bound is stated. The suggested practical procedure—halve ε_cvg until a violated cut is found—is the same heuristic whose soundness is questioned above. The sentence 'Proposition 3.8 ensures that this loop terminates in finite time' only guarantees that the loop would eventually find the correct set if it did not return an invalid cut earlier. The constructive claim that Algorithm 3.4 computes the optimal allocation therefore needs either a certified parameter-selection procedure or a more modest statement of what is guaranteed when ν is unknown.","section":"§3.2, paragraph after Algorithm 3.3; Prop. 3.13"},{"comment":"The stopping conditions in Algorithm 3.3 require the values ||x^(k) − x^(k−1)|| and ||x^(k) − y^(k)||. The operator only receives the aggregate profiles S^(k) from the SMC summation protocol and cannot compute these norms from S^(k) alone, because the individual iterates x^(k)_n are private. The pseudocode does not specify a privacy-preserving procedure for evaluating these norms, and the information set I_op defined in §3.3 omits them. As written, either the algorithm is not implementable without revealing profile-level information to the operator, or the privacy analysis is incomplete. This can be repaired by having each agent send shares of its local squared norm through the same SMC mechanism, but that step must be written explicitly and its effect on the privacy guarantees must be analyzed.","section":"§3.2, Algorithm 3.3, lines 11–12; §3.3"},{"comment":"The proof of Theorem 3.20 relies on Lemma 3.21 to pass from the known subspace APM rate to the polyhedral sets X and Y. The lemma is quoted from [33] as an 'intuitive generalization', but no proof is given here and no precise theorem number in [33] is cited. Since the explicit convergence rate is one of the paper's main results, the authors should either prove Lemma 3.21 or provide an exact reference that establishes it. Without one, Theorem 3.20 is not fully established. This issue does not affect the cut-validity result of Theorem 3.3, but it undercuts the claimed convergence-rate contribution and, through ρ, the practical interpretability of Proposition 3.8.","section":"§3.4, Lemma 3.21 and Theorem 3.20"}],"minor_comments":[{"comment":"There are numerous typos and minor grammatical issues, e.g. 'adress' in the abstract and the '⊿' symbols in Algorithm 3.3 that appear to be intended as comments or bullets. A careful proofreading pass is needed.","section":"Abstract and throughout"},{"comment":"The statement contains a double comma in 'p(s)∈P , , ∀n∈[N]'. Additionally, the notation ‖∑_n x*_n − p(s)‖ is used without specifying which norm is meant; the algorithm uses a norm chosen by the operator, so the correctness statement should make the norm dependency explicit.","section":"Proposition 3.13"},{"comment":"The displayed chain in the proof ends with an inequality '≤' followed by 'which equals AT(x∞)'. The intended relation is an equality: by Lemma 3.10 the two expressions are identical. The inequality should be replaced by an equality to avoid confusion.","section":"Proof of Proposition 3.9"},{"comment":"The paper acknowledges in the conclusion that termination of Algorithm 4.1 is not proved in the general polyhedral case. This limitation should be stated in Section 4 itself, directly after Algorithm 4.1, rather than only in the conclusion, and the algorithm should be labeled as heuristic when the polyhedral structure is arbitrary.","section":"§4, Algorithm 4.1 and Conclusion"},{"comment":"The numerical table reports only means over 100 instances. Reporting standard deviations or quartiles would strengthen the claim that the number of master iterations remains 'almost constant' and that the projection count grows sublinearly, given that the displayed means are not monotone in N.","section":"§5.2, Table 5.1"},{"comment":"The phrase 'cannot infer ... with probability 1' is informal. The proof only establishes permutation-invariance of the operator's information. This is a meaningful structural property, but the privacy claim should be stated more carefully, e.g. as indistinguishability of the operator's transcript under agent permutations, and the residual information leaks illustrated in Remark 3.18 should be acknowledged in the abstract or introduction if the term 'privacy-preserving' is used prominently.","section":"§3.3, Corollary 3.17"}],"recommendation":"major_revision","confidential_remarks":"The core cut-validity argument is sound and the paper contains a useful algorithmic idea, but the current statement of Proposition 3.13 is not proven for the algorithm as implemented, because the finite-time cut-selection step can return an invalid cut before the hypotheses of Proposition 3.8 are met. The missing privacy-preserving evaluation of the stopping criteria is also a genuine gap in the claimed privacy guarantees. I am not recommending rejection because the gaps appear fixable: adding an SMC-based validation of the candidate cut, or proving that the line-18 test implies T = T∞, together with a certified or honestly stated parameter-selection procedure, would restore the main correctness claim. The authors should also strengthen the proof of Lemma 3.21 if Theorem 3.20 is to remain a main result."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a real algorithm with a real gap in one of its advertised guarantees. The core idea is good, the paper deserves refereeing, but the finite-time termination argument needs work.\n\nWhat is genuinely new: the cut-generation lemma (Thm 3.3) that turns a two-point limit cycle of APM into a violated Hoffman inequality is self-contained and elegant. The explicit geometric convergence rate for transportation polytopes (Thm 3.20) is a useful addition, and the SMC-based implementation is a practical way to keep projections private. Unlike most Lagrangian schemes, the master problem can be nonconvex, which matters for the microgrid application. The numerical experiments are reasonable, though not fully reproducible.\n\nThe soft spots. The main one is the finite-time cut identification. Propositions 3.8 and 3.9 require B and eps_cvg to satisfy B > 1/(1-rho) and 2B eps_cvg < nu, where rho and nu are data-dependent and unknown. The paper's practical remedy, halving eps_cvg until a violated cut is found, is not proven sound: nothing rules out accepting a set T which is not T_infty; the inequality may not be a valid Hoffman cut, and adding it could cut off feasible allocations and make the algorithm converge to the wrong answer. That makes the guarantee in Prop 3.13 non-constructive as stated. This is load-bearing because correctness of Algorithm 3.4 depends on every added cut being valid. It is probably fixable, e.g. by adding a verifiable certificate, but as written it's a real hole.\n\nAlso, the convergence-rate proof borrows an 'intuitive' lemma (Lemma 3.21) from [33] without proof. That's a lesser issue, but the lemma is doing real work. The polyhedral generalization in Section 4 explicitly lacks a termination proof; the authors admit it in the conclusion. Minor: no code or data are shipped, so the numerical claims aren't checkable.\n\nWho it's for: anyone working on distributed resource allocation with privacy, especially demand response. The paper is a serious piece of work, but I'd want the termination gap addressed before relying on the main theorem.","headline":"A solid, useful algorithm with a genuine gap in the finite-time termination guarantee; worth refereeing but needs a fix.","tokens_in":31756,"tokens_out":3428,"would_cite":true,"duration_ms":36519,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C26","90B10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A privacy-preserving algorithm computes optimal aggregate allocations without any agent revealing her constraints or profile.","keywords":["privacy-preserving optimization","distributed resource allocation","alternating projections","secure multiparty computation","cutting planes","transportation polytope","nonconvex optimization","disaggregation"],"falsifier":"Take a small transportation instance with rational bounds, set the APM tolerance $\\varepsilon_{\\mathrm{cvg}}$ above $\\nu/(2B)$ while keeping $B>1/(1-\\rho)$, and run Algorithm 3.3 to see whether it returns a genuinely violated cut or, on the tolerance-halving path, ever stops with a nonviolated cut. A single such instance with a wrong cut would refute the practical claim that exact cut recovery follows from the finite-time condition.","tokens_in":30717,"feed_emoji":"🔒","tokens_out":7778,"duration_ms":86607,"temperature":0.7,"pith_summary":"The paper asks whether a central operator can minimize a global cost over an aggregate allocation while each agent's feasibility set and consumption profile remain private. It claims yes: an iterative cutting-plane algorithm, in which each agent runs local alternating projections and only masked aggregate sums leave the group, computes an optimal aggregate allocation together with feasible individual profiles. The method tolerates nonconvex costs, unlike Lagrangian decomposition approaches, and in the transportation-polytope case it terminates after at most $2^T-2$ master iterations with a certified near-feasible disaggregation. A sympathetic reader would care because this makes demand-response and similar resource-sharing applications compatible with confidentiality.","feed_headline":"Private optimization reaches the optimum without exposing constraints","feed_subtitle":"A cutting-plane scheme turns alternating projections into private feasibility cuts, even for nonconvex costs.","key_machinery":"The load-bearing machinery is alternating projections (APM) applied to the private product polyhedron $X$ and the aggregate affine subspace $Y_p$. Its convergence to a pair of points, one in each set, converts the feasibility question into an optimization problem whose stationary conditions yield exact multipliers; those multipliers identify the subset of resources that is oversupplied, and the corresponding flow-feasibility inequality becomes a violated cut on the aggregate allocation $p$. A second piece is secure multiparty summation, which computes sums of agent profiles and cut constants while each agent sends only random shares, so the operator sees only aggregates. The third piece is a spectral-graph bound on the APM contraction rate in the transportation case, giving the explicit geometric rate $\\left(1-\\frac{4}{N(T+1)^2(T-1)}\\right)^k$; this makes the finite-time tolerance argument quantitative.","core_discovery":"At the core is a disaggregation oracle that learns nothing but aggregate information. Given a candidate allocation $p$, the disaggregation problem asks whether private profiles $x_n\\in X_n$ sum to $p$; the paper represents this as the intersection of $X=\\prod_n X_n$ with the affine subspace $Y_p$ of profiles aggregating to $p$. The discovery is that when $X\\cap Y_p$ is empty, the limit of alternating projections between $X$ and $Y_p$ is not wasted information: the two limit points $x^\\infty$ and $y^\\infty$ encode, through which coordinates exceed their bounds, an exact feasibility inequality that $p$ violates. The paper proves this, shows that finite-time iterates can recover the exact cut constants provided tolerances are small relative to the smallest nonzero dual gap, and wraps the procedure in a secure multiparty summation so that only aggregate sums and cut data reach the operator. In the transportation case the scheme terminates after at most $2^T-2$ master iterations, and the alternating-projection subproblem has an explicit geometric rate with a $1/N$ dependence, both confirmed in numerical experiments.","pith_inferences":["Editorial inference: the finite-time recovery guarantee depends on two constants, the APM contraction rate $\\rho$ and the smallest nonzero dual gap $\\nu$, that the operator cannot know without the private data; the paper's tolerance-halving fallback is plausible but unproven, so a stress test on adversarially scaled data would be valuable.","Editorial inference: the privacy guarantee is permutation-level symmetry, not differential privacy; profile-level information can still leak through the sequence of cuts, so a differential-privacy version would need calibrated noise or secure aggregation with formal leakage bounds.","Editorial inference: the per-iteration communication cost of the secure summation is $O(N)$ messages per agent; a natural extension, noted in the paper via $k$-splitting, is to trade privacy against collusion for communication cost in very large populations.","Editorial inference: the same 'read the violated inequality from the projection limit' mechanism should transfer to other feasibility problems with a finite description of aggregate feasibility, such as polymatroid or network-flow constraints, where an analogue of the flow-feasibility inequalities exists."],"forward_implications":["An energy operator can optimize flexible consumption against a nonconvex generation cost while households reveal neither their appliance constraints nor their consumption profiles.","The number of master iterations is at most $2^T-2$ in the transportation case, independent of the number of agents $N$, so large populations do not inflate the outer loop.","Each alternating-projection step decomposes into independent local projections, so the per-iteration work parallelizes across agents, and the proved rate degrades only linearly with $N$.","When agent constraints are arbitrary polyhedra, the same projection limit yields decomposition-style cuts, though termination is proved only in the transportation case.","Privacy holds against a malicious operator and against collusion of fewer than $N-1$ agents, at the level of permutation symmetry of the aggregate information."],"supporting_citations":[{"why":"Supplies the alternating-projections convergence theorem giving the limit points on which the cut-generation result rests.","marker":"[20]"},{"why":"Supplies the flow-feasibility cut characterization used to certify disaggregation infeasibility.","marker":"[22]"},{"why":"Establishes geometric convergence of cyclic projections on polyhedra, supporting the finite-time tolerance condition.","marker":"[12]"},{"why":"Provides the explicit convergence-rate technique via angles and spectral graph theory that the transportation-case bound adapts.","marker":"[33]"},{"why":"Introduces secure multiparty computation, grounding the privacy-preserving summation protocol.","marker":"[42]"},{"why":"Provides the random-share split protocol used in Algorithm 3.2 to compute aggregates without revealing profiles.","marker":"[4]"},{"why":"Supplies the secure summation variant that Algorithm 3.2 builds on for the aggregate profile and cut constants.","marker":"[38]"}],"fun_headline_variants":["Alternating projections yield private cuts for optimal allocation","Privacy-preserving cuts from alternating projections","Exact cuts from private projections: optimal without leaks","Reach true optimum while keeping constraints private","Neither operator nor third party sees your constraints"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the algorithm's guarantee to hold, the operator must know, or guess safely, two numbers that depend on the agents' private data: how fast the projection iterates contract and the size of the smallest nonzero gap between the two limit points.","fun_headline_variants_meta":{"raw":{"variants":["Alternating projections yield private cuts for optimal allocation","Privacy-preserving cuts from alternating projections","Exact cuts from private projections: optimal without leaks","Reach true optimum while keeping constraints private","Neither operator nor third party sees your constraints"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000484,"raw_usage":{"total_tokens":2410,"prompt_tokens":987,"completion_tokens":1423,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":603,"completion_tokens_details":{"reasoning_tokens":1355}},"tokens_in":603,"tokens_out":1423,"duration_ms":11319,"temperature":1.0,"reasoning_tokens":1355,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:43:49.445145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small transportation instance with rational bounds, set the APM tolerance $\\varepsilon_{\\mathrm{cvg}}$ above $\\nu/(2B)$ while keeping $B>1/(1-\\rho)$, and run Algorithm 3.3 to see whether it returns a genuinely violated cut or, on the tolerance-halving path, ever stops with a nonviolated cut. A single such instance with a wrong cut would refute the practical claim that exact cut recovery follows from the finite-time condition.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the alternating-projections convergence theorem giving the limit points on which the cut-generation result rests."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the flow-feasibility cut characterization used to certify disaggregation infeasibility."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes geometric convergence of cyclic projections on polyhedra, supporting the finite-time tolerance condition."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the explicit convergence-rate technique via angles and spectral graph theory that the transportation-case bound adapts."},{"cited_title":"Seong, M","cited_arxiv_id":null,"evidence_quote":"Introduces secure multiparty computation, grounding the privacy-preserving summation protocol."},{"cited_title":"In this section, we extend our results to a more general framework where for eachn∈ [N],Xn is an arbitrary polyhedron, instead of having the particular structure given in (2.2)","cited_arxiv_id":null,"evidence_quote":"Provides the random-share split protocol used in Algorithm 3.2 to compute aggregates without revealing profiles."},{"cited_title":"Nishihara, S","cited_arxiv_id":null,"evidence_quote":"Supplies the secure summation variant that Algorithm 3.2 builds on for the aggregate profile and cut constants."}],"review_version":1}