- 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
- The paper's main result provides a recovery bound from independent Gaussian starts.
Critical weaknesses
-
For , 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).
-
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.
-
The proposed algorithm is not novel.
Questions for authors
-
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?
-
(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.
-
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?
-
The topology experiment counts edges. The complete graph with naturally costs more words. The claimed topology-dependent dependence of on the spectral gap is never plotted.
-
The algorithm needs , and bound on . Aren't these global information?
-
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
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.
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=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 d4, while worst-case trajectory amplification contributes Apop2T. Together they yield the sufficient scale M≳d4Apop2T/(ζε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≤b, with compatible continuation step and mixing parameters. We bound VT≤εr+ω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/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 q. 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 K, M, a certified spectral bound, and norm bounds. The factor K/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 M 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.