acceptodds
Withdrawn from ICLR 2027

Decentralized Phase Retrieval over Networks

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We consider noiseless real Gaussian measurements and use the same mix–gradient–mix update at every iteration. We couple the network average to a population gradient trajectory and control the disagreement at each gradient evaluation. This gives a finite-accuracy recovery guarantee with explicit sample, iteration, and communication costs, including unequal batches and nodes with fewer than samples. The bound is conservative and polynomial in the dimension, initialization scale, and target accuracy. A separate local result gives exact convergence under additional regularity. Experiments show two-stage dynamics, recovery from individually underdetermined nodes, and a topology-dependent communication cost. To the best of our knowledge, this work provides the first systematic study jointly addressing statistical recovery, convergence, and communication complexity for decentralized phase retrieval over peer-to-peer networks from independent Gaussian node initializations.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Phase Retrieval

Reviews

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

This paper studies decentralized recovery of a real signal from random Gaussian projections at each node. Each node starts from an independent small Gaussian vector and runs a mix gradient and update.

Critical strengths
  1. The paper's main result provides a recovery bound from independent Gaussian starts.
Critical weaknesses
  1. For W=JW = J, the algorithm is exactly centralized GD from Gaussian starts. However, in this case, the bound in Theorem 1 (requiring (16), which is a very loose polynomial sample condition) is far worse than the bound given in (Chen et al. 2019).

  2. Proposition 4 gives linear convergence provided the algorithm has already entered a suitable regular neighborhood, but the global theorem does not provide a useful computable transition into this neighborhood.

  3. The proposed algorithm is not novel.

Questions for authors
  1. Decentralized phase retrieval is a traditional signal processing problem. Justify the relevance of this work to the ICLR and ML community in general. What are the potential ML applications?

  2. (Chen et al. 2019) proved global convergence of GD from random initialization with nearly minimal samples. Why does the theoretical result in this work require polynomial samples? What is the main bottleneck? A more detailed discussion should give insights into this issue.

  3. In many decentralized algorithms, nodes can use a common public random seed or a deterministic common initialization without violating data locality or peer-to-peer communication. Why do we need independent random initialization?

  4. The topology experiment counts edges. The complete graph with W=JW = J naturally costs more words. The claimed topology-dependent dependence of qq on the spectral gap is never plotted.

  5. The algorithm needs K,MK, M, and bound on ρ\rho. Aren't these global information?

  6. Experiments are synthetic and noiseless. This is a significant limitation because phase retrieval in practice is rarely noiseless. How does the method perform when there is noise and/or communication constraints?

2 comments

We thank Reviewer Ur72 for the constructive feedback. Our responses are below.

1. Response to W1 & Q2: Centralized comparison and the sample bound. When W=JW=J, the update reduces to centralized empirical GD from the average of the independent starts. The difference from Chen et al. (2019) lies in the initialization scale and empirical trajectory control.

Sections 4.1–4.2 and Appendix F identify two sources of the conservative bound. Full fourth-order tensor control in Frobenius norm contributes d4d^4, while worst-case trajectory amplification contributes Apop2TA_{\rm pop}^{2T}. Together they yield the sufficient scale M≳d4Apop2T/(ζε2)M\gtrsim d^4A_{\rm pop}^{2T}/(\zeta\varepsilon^2) at fixed calibration ratio. These factors arise in the population-tracking proof even under exact averaging. Chen et al. obtain sharper bounds through trajectory-specific leave-one-out control. Extending that approach here requires handling our smaller average initialization and propagating measurement-deletion effects through the coupled node trajectories. The revision gives these dependencies and polynomial exponents explicitly.

2. Response to W2: Global-to-local transition. Theorem 1 establishes prescribed finite-accuracy recovery from independent starts, while Proposition 4 establishes linear convergence within a regular neighborhood. Section 4.3 and Appendix G give the connection condition: VT≤bV_T\le b, with compatible continuation step and mixing parameters. We bound VT≤εr+ωDV_T\le\varepsilon r+\omega D for comparison with the local radius. Establishing this quantitative match at a fixed sample size remains open, since the global sample requirement grows as the target accuracy decreases.

3. Response to W3: Algorithmic novelty. The contribution is the recovery analysis for fixed Gaussian intensity data and independent nodewise starts. The proof couples population tracking, pooled empirical concentration, and network disagreement to control the gradient-evaluation points through the weak-signal phase and obtain one common sign at all nodes. Sections 1 and 3 and Appendix H clarify this contribution and the relation to multi-consensus methods and ATC.

4. Response to Q1: Relevance to ML. Section 1 now explains phase retrieval as quadratic regression and a tractable model for nonconvex statistical learning from partitioned data. It isolates how initialization, heterogeneous local updates, and communication jointly affect recovery. Distributed intensity sensing and computational imaging motivate this setting. The Gaussian model is a benchmark for these mechanisms, with structured sensing as a future extension.

5. Response to Q3: Independent initialization. Independent starts let us study whether nodes can align toward one signed solution without coordinating an initial direction. A public seed or deterministic common start is also compatible with data locality. Section 2.2 now clarifies this choice and quantifies its effect: averaging reduces the initialization scale by K−1/2K^{-1/2}, which enters the horizon and sample bound.

6. Response to Q4: Spectral-gap evidence. The added diagnostic plots rounds sufficient for fixed consensus attenuation against the reciprocal spectral gap. The required rounds increase as the gap shrinks, and accelerated gossip reduces this mixing budget. A separate fixed-step ablation shows that additional gossip substantially improves recovery and consensus on the slow-mixing cycle, while its effect is smaller on better-connected graphs. These experiments separate spectral mixing from edge-count costs and show the topology-dependent benefit of increasing qq. Please see Appendix I.6, “Accelerated consensus and spectral gap” and “Effect of mixing count across topologies,” for the plots and protocol.

7. Response to Q5: Global information. The public setup inputs are KK, MM, a certified spectral bound, and norm bounds. The factor K/MK/M scales the gradients, while the spectral bound configures mixing. Sections 2.2–3 and Appendix A distinguish setup inputs from local data and iterative neighbor exchanges. Appendix A also accounts for the additional metadata traffic when MM is obtained by flooding. The remaining inputs are supplied during setup.

8. Response to Q6: Noise and communication constraints. The added noise experiment shows reconstruction error increasing with noise, with Gossip-PR comparable to centralized GD and the decentralized comparators in the tested setting. Plain mixing leaves a disagreement floor, while gradient tracking maintains consensus. Under matched communication budgets, Gossip-PR can reach the target in fewer gradient updates, while tracking can use fewer transmitted words. Please see Section 5 and Appendix I.6, especially “Additive intensity noise,” for the protocol and figures. The noise results are empirical, and quantization, packet loss, and asynchrony remain directions for further study.

Thank you for the clarifcations, which confirm that tests on noisy channel conditions are not comprehensive. The optimality of the theoretical results also requires more work. I am keeping my score.

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

This paper investigates decentralized phase retrieval under noiseless real Gaussian measurements, where nodes maintain local datasets and start from independent Gaussian initializations. The authors propose a neighbor-based mix–gradient–mix algorithm and establish finite-accuracy recovery guarantees with explicit sample, iteration, and communication requirements, accommodating unequal data partitions and individually underdetermined nodes. A separate theoretical result establishes exact local linear convergence under additional regularity conditions. Numerical experiments demonstrate two-stage recovery dynamics, successful cooperation among nodes with insufficient local measurements, and the influence of network topology on communication costs.

Critical strengths
  1. The paper establishes finite-accuracy recovery guarantees for decentralized phase retrieval with independent Gaussian node initializations, allowing heterogeneous local sample sizes and individually underdetermined nodes. The common-sign recovery guarantee is particularly meaningful in decentralized settings.

  2. The theoretical analysis systematically connects population gradient dynamics, statistical estimation errors, and network disagreement, providing explicit sample, iteration, and communication complexity bounds.

Critical weaknesses
  1. The mix–gradient–mix update in Eq. (7) closely resembles the decentralized gradient scheme of Maros and Scutari (NeurIPS 2023[1], Eq. (3)). Moreover, defining Yt=WqXtY^t = W^q X^t yields Yt+1=W2q[Yt−ηG(Yt)]Y^{t+1} = W^{2q}\left[Y^t-\eta G(Y^t)\right], revealing its equivalence to an ATC-type update in the gradient-evaluation variables. Although Gaussian phase retrieval introduces distinct statistical challenges, the paper does not sufficiently establish what fundamentally new algorithmic mechanisms or theoretical techniques are introduced beyond adapting the existing framework.

  2. Theoretical guarantees do not cover a central experimental setting. The sufficient sample condition in Theorem 1 (Eqs. (12)–(16)) is extremely conservative and, under the stated parameter restrictions, implies M>KdM > Kd. Consequently, it cannot certify any configuration in which all nodes are locally underdetermined mi<d,∀im_i < d, \forall i, despite this being a central setting in Figures 3(b) and 4. This substantial gap between theory and experiments limits the explanatory value of the main recovery guarantee.

  3. Insufficiently communication-normalized experimental comparisons. Gossip-PR performs 2q2q gossip rounds per iteration, with q=16q=16 in the main recovery experiments (Section 5), whereas competing decentralized methods use different communication patterns (Appendix I.2). Although communication costs are reported across network topologies, Figures 3(b) and 4 do not provide systematic comparisons under matched communication budgets. Consequently, the reported results do not establish whether Gossip-PR offers advantages over competing methods at comparable communication costs.

[1] Maros M, Scutari G. Decentralized matrix sensing: statistical guarantees and fast convergence[J]. Advances in Neural Information Processing Systems, 2023, 36: 40154-40166.

Questions for authors
  1. The mix–gradient–mix update in Eq. (7) closely resembles the decentralized gradient scheme of Maros and Scutari (NeurIPS 2023, Eq. (3)). Moreover, a change of variables yields an equivalent ATC-type iteration for the gradient-evaluation points. Beyond the different measurement model, which specific theoretical challenges cannot be addressed using the existing analysis, and what genuinely new techniques are introduced to overcome them?

  2. The parameter conditions in Eqs. (12)–(16) appear to imply M>KdM > Kd, which excludes all configurations where every node is locally underdetermined mi<d,∀im_i < d, \forall i. Could the authors confirm this implication or identify where the reasoning fails? If it holds, what theoretical insight does Theorem 1 provide into the fully underdetermined recovery regime emphasized in Figures 3(b) and 4?

  3. Do the reported recovery advantages persist under matched total communication budgets, particularly in terms of transmitted scalar words? Could the authors provide recovery probability or target-reaching cost comparisons under such budgets while also accounting for gradient computation costs?

3 comments

We thank Reviewer PY4u for the constructive feedback. Our responses are below.

1. W1 & Q1: Relation to Maros and Scutari (2023) and technical contribution. The reviewer is correct. Our update uses the mix–gradient–mix architecture of their Eq. (3). With P=WqP=W^q and Yt=PXtY^t=PX^t,

Yt+1=P2[Yt−ηG(Yt)],Y0=PX0,Y^{t+1}=P^2[Y^t-\eta G(Y^t)],\qquad Y^0=PX^0,

which is a multi-consensus ATC iteration with a premixed initial state. They also discuss this transformation and analyze small independent starts and two-phase dynamics. We now credit these connections explicitly in Section 3 and Appendix H. We do not claim a new update mechanism.

The obstacle to importing their recovery analysis is the empirical sensing control. Gaussian intensity measurements obey E(a⊤Ha)2=2∥H∥F2+(tr⁡H)2\mathbb E(a^\top Ha)^2=2\|H\|_F^2+(\operatorname{tr}H)^2, and a sample-aligned rank-one direction contributes order d2/Md^2/M to the empirical quadratic form. Thus their in-network RIP result does not directly provide a near-linear guarantee here. Appendix D explains both distinctions.

Our analysis instead couples a pooled uniform fourth-moment event with population-tracking and disagreement recursions. Uniformity handles reuse of the fixed data. Simultaneous containment controls gradient-evaluation points from the first step, and the population sign transfers to all nodes. The component tools are established. Our contribution is their coupling into an explicit finite-accuracy common-sign guarantee at the native average initialization scale, with unequal local sample sizes. Section 4.2 and Appendices F and H now clarify this scope and its proof losses.

2. W2 & Q2: The sample condition excludes fully underdetermined local batches. We confirm the reviewer's implication. Under the stated restrictions, Appendix F now gives the explicit chain

>dA_{\rm pop}^{2T}>Kd.$$ If every $m_i<d$, then $M=\sum_i m_i<Kd$, so no such configuration is certified. Unequal partitions may contain underdetermined nodes, but other nodes must supply sufficiently many observations. We have corrected the abstract, scope discussion, and conclusion, and clarified this restriction in the empirical-control remark. Section 4.1 displays the expanded sample requirement. Appendix F gives the substitution and derivation. The theorem therefore provides no finite-sample recovery guarantee for the fully underdetermined experimental regime. Its population dynamics and error decomposition describe a possible recovery mechanism, while recovery in that regime is empirical evidence only. Full-tensor concentration and worst-case trajectory amplification cause the conservative bound. Sharper trajectory-specific concentration and stability remain open. **3. W3 & Q3: Comparisons at matched communication budgets.** The added comparisons show a computation–communication trade-off rather than uniform superiority. On the larger cycle network, Gossip-PR reaches the recovery target while gradient tracking remains short of it within the reported horizon. On better-connected graphs, tracking can use fewer transmitted words even though Gossip-PR uses fewer gradient evaluations. Increasing the spectral setup budget also improves recovery, at an additional preprocessing cost. The revised manuscript reports recovery probabilities at common word caps together with target-reaching communication and gradient costs, including spectral preprocessing and trials with unobserved target times. Please see Section 5, “Method comparisons at matched communication budgets,” and Appendix I.6, especially “Comparators and operation counts,” “Longer horizons and final errors,” and “Spectral preprocessing,” for the protocol, figures, and complete results.
  1. The analysis in W1 constitutes a key part of the distinction from prior work; it is recommended that the authors briefly discuss the relevant arguments in the main text.
  2. Carefully check whether the notation is consistently used throughout the paper; in the main text, LL denotes a Lipschitz upper bound, but in the appendix, it is used to denote a matrix.

Response to Comment 1. Thank you for this suggestion. We will add a brief discussion of the relevant arguments from W1 to the main text. Response to Comment 2. Thank you for the careful check. Scalars such as the Lipschitz upper bound are denoted by non-bold letters, while matrices are denoted by bold letters. We will check the notation throughout and ensure this convention is applied consistently.

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

This paper studies noiseless real Gaussian phase retrieval over a peer-to-peer network. Each node keeps its own intensity measurements. Each node also starts from its own small Gaussian vector. The proposed method is called GOSSIP-PR. In every iteration, the nodes first average with their neighbors for q rounds. Then each node takes one local gradient step, weighted by its sample size. Then the nodes average again for q rounds. With exact averaging, the method becomes centralized gradient descent.

The main theorem shows finite-accuracy recovery, with all nodes agreeing on one common sign. The proof follows a population gradient path with two stages. It controls the finite-sample error through one global fourth-moment event. It keeps the tracking error and the node disagreement inside an invariant region. A separate result gives local linear convergence under extra curvature assumptions. The experiments use synthetic data. They look at the two-stage dynamics, at recovery when every node has too few samples, and at how the network graph affects communication cost.

Critical strengths

Overall, the paper is well organized and clearly written. The problem setting is easy to understand, and the main ideas are easy to follow.

On the theory side, the analysis is built in a clean way. The authors handle the population dynamics, the finite-sample error and the network error one by one, so each part of the proof is easy to check. I also like that the authors are open about the limits of their results. For example, they say plainly that the sample condition is conservative and that the local result is not linked to the global one. This makes the claims in the paper easy to trust.

The experiments are also done well. The methods are compared on the same problem instances, tuning is kept apart from testing, and failed runs are kept in the results. The results show clearly that the method works and that cooperation helps. In particular, nodes can recover the signal by working together, even when no single node can do it alone.

Critical weaknesses

I will point out the weak or unclear parts of this work from three sides: novelty, theory and simulation.

In terms of novelty, the step forward seems small. Both the algorithm and its analysis mainly use known tools.

  • GOSSIP-PR is a form of multi-consensus decentralized gradient descent. It is close to the diffusion strategies in Sayed (2014), which the paper cites, and to methods that use several consensus steps per gradient step, such as NEAR-DGD (Berahas et al., IEEE TAC 2019). With exact averaging, it becomes centralized gradient descent.
  • The proof combines a population trajectory, uniform concentration and a perturbation argument. These are standard tools. It is hard to see a new technical idea beyond using them in this setting.

On the theory side, the main results do not seem strong enough to back the claims in the abstract.

  • The sample condition is polynomial, but its degree is very high. Even in the most favorable case, it is several dozen in d and more than a hundred in 1/ε. So the required sample size is far too large to be useful, even in small dimensions. The bound also grows with the number of nodes. Under a balanced split, every node still holds far more than d samples. The claim about nodes with fewer than d samples then only holds under extreme imbalance.
  • The communication result only gives a sufficient upper bound. There is no lower bound and no comparison with accelerated gossip. So the term "communication complexity" in the title says more than the paper shows.
  • The global result only reaches a finite accuracy, and the local result on exact convergence is not linked to it. So exact recovery from random starts is not shown.

As for the simulations, they are done with care, but they do not clearly show where the gain comes from.

  • A run counts as a success only if it reaches the target accuracy within a fixed budget of 1200 passes. However, the gradient-tracking baseline uses a step size at which the proposed method itself fails in a sizable share of runs within this budget. Its lower success rate may come from slower progress, not from a weaker method.
  • A natural baseline is missing, namely plain decentralized gradient descent with a single mixing step. Without it, it is not clear whether the mix–gradient–mix design is really needed.
  • The decentralized spectral baseline uses only four gossip rounds per power iteration. At large network sizes it falls well behind the centralized spectral start, so it may not be tuned well.
Questions for authors

Besides the comments above, I have several more concerns, as follows.

  • It would help if the authors could make clear what is new in the algorithm and the analysis, compared with existing multi-consensus decentralized gradient methods.
  • I suggest giving the exact order of the sample condition in the main text, in terms of d, K, ε and the calibration ratio. Right now, it is not clear whether the theorem is meaningful in any practical setting. It is also not clear whether it can cover a balanced split where every node has fewer than d samples.
  • The required number of gossip rounds may be far more than needed. A comparison with accelerated gossip would help here. So would an explanation of why the experiments depend so little on q.
  • The baseline comparison needs more support to be fair. For example, the step sizes could be tuned for each network size, and final errors or time to target could be reported without the fixed budget. A comparison with plain decentralized gradient descent with a single mixing step would also help judge whether the design is needed.
2 comments

We thank Reviewer AN2a for the constructive feedback. Our responses are below.

1. Contribution and relation to multi-consensus methods. Our contribution is the recovery analysis for independent small nodewise starts, fixed local Gaussian intensity data, and one common sign. The pooled empirical event and coupled invariant region control finite-data error and network disagreement through the weak-signal phase, including containment of the data-dependent gradient-evaluation points. We now distinguish this recovery analysis from the underlying multi-consensus architecture and cite NEAR-DGD (Berahas et al., 2019) alongside diffusion methods. Section 3 and Appendix H give the algebraic relation: with P=WqP=W^q and Yt=PXtY^t=PX^t, the update becomes Yt+1=P2[Yt−ηG(Yt)]Y^{t+1}=P^2[Y^t-\eta G(Y^t)], a multi-consensus ATC iteration initialized at Y0=PX0Y^0=PX^0.

2. Sample requirement and underdetermined nodes. Section 4.1 now displays the expanded sufficient condition. Let κ=r+/r−\kappa=r_+/r_- and η=c0/r+2\eta=c_0/r_+^2. Then

\left(\frac{16\kappa\sqrt{dK}}{\tau p\varepsilon}\right)^{\beta}, \qquad \beta=\frac{8\kappa^2}{c_0}\log(1+39c_0).$$ For $\kappa=1$ and $c_0=1/12$, $\beta\approx138.90$, giving the scale $d^{73.45}K^{69.45}\varepsilon^{-140.90}$ with fixed $\tau,p,\zeta$. These large exponents arise from full-tensor concentration and worst-case trajectory amplification. The condition implies $M>Kd$, permitting underdetermined nodes under unequal partitions while excluding configurations with **every** $m_i<d$. The revised discussion separates this sufficient theoretical regime from the fully locally underdetermined regime explored experimentally. Appendix F gives the derivation and identifies trajectory-specific concentration and stability as the route to sharper bounds. **3. Communication upper bounds, acceleration, and $q$.** The analysis provides sufficient budgets of $2qT$ rounds and $4|\mathcal E|dqT$ transmitted words for the prescribed recovery accuracy. The added experiments compare ordinary and accelerated consensus at matched word budgets. Accelerated consensus reduces communication in the tested configurations, with the benefit depending on topology. The fixed-step $q$ ablation also shows why the effect of additional mixing varies: it is small when disagreement is already well controlled and substantial on the slow-mixing cycle. Please see Appendix I.6, “Accelerated consensus and spectral gap” and “Effect of mixing count across topologies,” for the settings and results. The acceleration results are empirical, while the recovery theorem assumes nonnegative mixing weights. **4. Random starts and exact convergence.** Theorem 1 establishes finite-accuracy recovery from independent random starts. Proposition 4 gives linear convergence once the weighted basin-entry condition and local step/mixing requirements hold. Section 4.3 and Appendix G now specify the connection through $V_T\le\varepsilon r+\omega D$ and the required comparison with the local radius. Matching these conditions at a fixed sample size remains open because the global sample requirement depends on the target accuracy. Chen et al. (2019) provide a relevant leave-one-out approach for sharper empirical trajectory control. Adapting it here requires handling the average initialization scale $\tau r_-/\sqrt K$ and the heterogeneous gradient-evaluation points introduced by finite gossip. Appendix F explains the required measurement-deletion stability estimates through the weak-signal phase. **5. Fair tuning, longer budgets, and single-mixing baselines.** We expanded the evaluation with separate pilot tuning for each network configuration, longer horizons, final-error reporting, and single-mixing DGD and ATC baselines. The longer horizon increases gradient tracking's target-reaching rate, and the single-mixing methods recover in several configurations. The comparisons reveal a computation–communication trade-off: Gossip-PR can reach the target in fewer gradient updates, while tracking can require fewer transmitted words. We report common word budgets together with method-dependent per-update mixing costs. Please see Section 5, “Method comparisons at matched communication budgets,” and Appendix I.6, “Longer horizons and final errors,” for the protocol and results. **6. Decentralized spectral initialization.** The expanded study varies the spectral setup budget and separately tunes the subsequent refinement. Increasing setup communication substantially improves recovery on the slow-mixing cycle and closes the observed success-rate gap from the centralized spectral reference. This improvement comes with additional preprocessing traffic, showing how spectral accuracy and communication jointly affect recovery. We include the full setup cost in the comparisons. Please see Appendix I.6, “Spectral preprocessing,” for the setup scan, refinement tuning, and figure.

Dear Reviewer AN2a, As the discussion period is coming to an end, we would appreciate your feedback on whether our rebuttal has addressed your concerns. We would be happy to clarify any remaining questions. Thank you for your time and consideration.

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

Related papers

Discussion (0)

Sign in to comment.