acceptodds
Under review as a conference paper at ICLR 2027

Multi-Round SPEAR++: Exact Data Reconstruction from Model Updates across communication rounds in Federated Learning

Abstract

Federated learning trains a model over multiple communication rounds by sharing model updates instead of the clients' training data. For models with a fully connected first layer followed by ReLU, SPEAR++ can exactly reconstruct training inputs from a model update observed in a single communication round. However, whether an honest-but-curious attacker can exploit the same client's model updates across rounds to exactly reconstruct more inputs remains unexplored. In this paper, we formulate these multiple model updates as a single reconstruction problem and derive Multi-Round SPEAR++ from this formulation. Our formulation normalizes and concatenates first-layer weight updates from observed rounds that use the same inputs, yielding a reconstruction problem structurally similar to that of SPEAR++. Multi-Round SPEAR++ then adapts the -based reconstruction procedure used by SPEAR++ to the resulting formulation. On CIFAR-10 with inputs per client, 1000 neurons per hidden layer, and one local update per round, Multi-Round SPEAR++ reconstructs all inputs for approximately % of evaluated clients using rounds, whereas SPEAR++ using the first round almost never does. To further analyze these results, we theoretically characterize the strict local minimizers of the -minimization problem used by both methods and use this characterization to empirically analyze reconstruction failures. These results show that evaluating reconstruction risk using only a model update observed in a single communication round can underestimate the risk.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Federated Learning, Data Reconstruction Attack, Gradient Inversion Attack

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 2 reviews, above 27% of the others.
Reviewer_v5SCOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes Multi-Round SPEAR++, an exact input-reconstruction attack in federated learning. Building on SPEAR++, the method exploits the sparsity of gradients induced by ReLU activations in fully connected layers to recover training inputs through a low-rank factorization of model updates. The main extension consists of jointly exploiting updates from multiple communication rounds to improve reconstruction success on image datasets.

Critical strengths
  1. The paper demonstrates how an honest-but-curious attacker can extend the SPEAR++ framework to exploit model updates across multiple communication rounds, improving reconstruction success.

  2. The paper focuses on the FedAvg setting, including multiple local optimization steps, going beyond the simplified single-step FedSGD setting commonly considered in gradient inversion literature.

  3. Proposition 1 provides a novel theoretical characterization of the strict local minimizers of the optimization problem in Equation 11, offering insights into the conditions under which input reconstruction can succeed.

Critical weaknesses
  1. The paper builds heavily on SPEAR and SPEAR++, reusing essentially the same procedure for candidate selection and recovery of the matrix QQ. The main algorithmic contribution consists of normalizing and stacking model updates from multiple communication rounds into a single matrix, with minor adaptations to the candidate-filtering procedure. This increases the number of available constraints and helps satisfy the rank condition. Consequently, as shown in Figure 3, a major benefit of Multi-Round SPEAR++ is the reduction of rank-related failures F1. Overall, the algorithmic novelty compared to SPEAR++ appears limited.

  2. The proposed method does not overcome several important limitations of SPEAR and SPEAR++. In particular, it requires the input matrix to have full column rank, which implies that the input dimension must be at least as large as the number of reconstructed samples BB. This restricts its applicability to low-dimensional data, such as tabular datasets, when BB exceeds the input dimension. Moreover, the approach relies on the exact sparsity induced by ReLU activations, and its effectiveness with smooth activation functions, such as GELU or SiLU, and more complex models that do not have a first FC layer remains unexplored. Similarly, the paper does not evaluate robustness to noisy or differentially private model updates.

  3. The experimental results do not provide a sufficiently comprehensive picture of the advantages of Multi-Round SPEAR++ over SPEAR++. While the experiments on CIFAR-10 demonstrate some improvements in reconstruction success, the results on MNIST reported in the Appendix are less consistent, with SPEAR++ outperforming the proposed method in some settings. Furthermore, the paper does not provide a detailed analysis of the additional computational cost introduced by jointly processing multiple communication rounds. Consequently, it remains unclear under which conditions the increased computational burden is justified by improvements in reconstruction performance. This concern is particularly relevant for higher-resolution image datasets, such as ImageNet, where stacking and factorizing multiple large gradient matrices could introduce substantial computational and memory overhead.

  4. The experimental evaluation does not fully isolate the benefits of the proposed joint multi-round reconstruction approach. Although jointly combining updates is a contribution of the paper, nothing prevents an attacker from applying SPEAR++ independently to each observed round and then combining the resulting reconstructions. Such a baseline would ensure that both attacks have access to the same information and would provide a fairer comparison, allowing the authors to quantify the benefits of jointly processing multiple rounds rather than simply observing additional model updates. Furthermore, this comparison would help assess the computational efficiency of Multi-Round SPEAR++ relative to running SPEAR++ independently across multiple rounds, clarifying whether the proposed approach offers advantages in terms of both reconstruction performance and computational cost

Questions for authors
  1. Could the authors elaborate on why Multi-Round SPEAR++ does not consistently benefit from additional communication rounds on MNIST, particularly for smaller local dataset sizes? Intuitively, observing additional rounds should provide more constraints on the shared input factorization that the underlying dictionary-learning problem aims to recover, potentially facilitating the reconstruction. It would be helpful to include an analysis similar to Figure 3 for MNIST, distinguishing the different types of reconstruction failures to better understand the reasons behind this behavior.

  2. Could the authors provide a more detailed analysis of the computational cost of the attack, particularly how runtime and memory requirements scale with the input dimension, number of neurons, and the number of observed communication rounds?

  3. Could the authors evaluate Multi-Round SPEAR++ against a baseline that independently applies SPEAR++ to the same number of observed communication rounds and then combines the resulting reconstructions? This would help isolate the benefits of the proposed joint reconstruction strategy and provide a clearer comparison of reconstruction performance and computational efficiency.

5 comments

We thank the reviewer for the thoughtful feedback, which helped us substantially strengthen the paper. Our central contribution is a formulation that enables joint exact reconstruction from model updates across multiple communication rounds. We complement this formulation with an algorithm derived from it, a novel theoretical characterization of reconstruction conditions, and additional experiments that isolate the benefits of joint reconstruction. We hope these revisions address your concerns and welcome further discussion.


Novelty and Effectiveness of Joint Reconstruction (W1, W4, Q3)

We would like to clarify that our main contributions are a new multi-round reconstruction formulation and an algorithm derived from it, a novel theoretical characterization of reconstruction conditions, and substantial improvements in exact reconstruction, as summarized in the Introduction.

Our formulation enables joint reconstruction of a common input matrix from model updates observed across multiple rounds. We derive Multi-Round SPEAR++ by adapting SPEAR++ with per-round normalization, block-wise sparsity filtering, and ReLU consistency checks across rounds. To further validate the benefit of our joint reconstruction formulation, as suggested in W4 and Q3, we added a comparison with independently applying SPEAR++ to each observed round and combining the reconstructed inputs. Figure 3 in Section 5.2 of the revised manuscript shows that Multi-Round SPEAR++ outperforms this baseline, demonstrating the effectiveness of our joint reconstruction formulation beyond simply observing multiple rounds.

Furthermore, Proposition 1 provides necessary and sufficient conditions for strict local minimizers of the ℓ1\ell_1 objective used by both methods. Figure 4 shows different dual-margin failure rates between concatenating rounds and increasing the number of first-layer neurons, even with the same number of rows. These results demonstrate that the benefits of multi-round reconstruction cannot be explained solely by reducing rank-condition failures.


Clarification of the Full-Column-Rank Assumptions on the Input and Gradient Matrices (W2)

We agree that our method inherits the full-column-rank assumption on the input matrix XX from SPEAR++, requiring n≥Bn\geq B. Consequently, our method remains limited for low-dimensional data when the number of reconstructed inputs exceeds the input dimension.

However, Multi-Round SPEAR++ relaxes the corresponding rank assumption on the backpropagated-gradient matrix by exploiting multiple communication rounds. As established in Section 3.1, the concatenated gradient matrix can have full column rank even when the gradient matrices from individual rounds are rank deficient. Thus, our formulation relaxes the gradient-side rank requirement while retaining the input-side limitation.


Clarification of Applicability to Other Architectures and Activation Functions (W2)

Thank you for the suggestion. We confirmed that Multi-Round SPEAR++ can reconstruct intermediate features in CNN-based models with a frozen backbone, as shown in Table 3 of Appendix F.2. Using a frozen ResNet-18 backbone and a fully connected ReLU head, Multi-Round SPEAR++ achieves nearly perfect cosine similarity between reconstructed and original features, substantially outperforming SPEAR++. The frozen backbone preserves intermediate features across rounds, allowing our common-input formulation to apply. The recovered intermediate features could be used to approximately reconstruct the original input images through feature inversion, as demonstrated in the original SPEAR paper.

Direct application to convolutional first layers remains challenging because their weight updates factorize over spatial patches rather than individual input images. For GELU and SiLU, the multi-round factorization remains valid for fully connected layers under SGD. However, our reconstruction algorithm cannot be directly applied because these activations do not generally induce the exact sparsity required for reconstruction. Extending the reconstruction algorithm to these activations remains a promising future direction.


Robustness to Clipping and Gaussian Noise (W2)

Thank you for the suggestion. We conducted additional experiments with full-batch DP-GD using per-sample gradient clipping and Gaussian noise, as shown in Figure 14 of Appendix F.2. This result shows that clipping alone does not prevent full reconstruction, and Multi-Round SPEAR++ substantially outperforms SPEAR++ under very small Gaussian noise. In contrast, neither method achieves full recovery when the noise is calibrated to provide a meaningful DP guarantee. Table 4 reports the corresponding privacy budgets.


Analysis of Why Multi-Round SPEAR++ Can Underperform SPEAR++ on MNIST (W3, Q1)

Thank you for the suggestion. We conducted an additional failure analysis on MNIST to identify why Multi-Round SPEAR++ does not consistently outperform SPEAR++, as shown in Figure 6 of Appendix F.2. Figure 6 shows that the reduced reconstruction performance in the evaluated setting is primarily associated with completeness failures, followed by candidate-search and dual-margin failures, rather than failures of the rank condition.

These results demonstrate that satisfying the rank condition does not guarantee full reconstruction, which also requires successful candidate search, selection of the complete set of true column directions, and recovery of their signed scales. This explains why additional communication rounds can improve the rank condition without necessarily improving the full recovery rate on MNIST.


Analysis of Computational Overhead and Scalability (W3, Q2)

Thank you for the suggestion. We additionally evaluated reconstruction time and peak GPU memory across different numbers of observed rounds, local data sizes, first-layer widths, and input dimensions, as shown in Table 5 of Appendix F.2. Peak GPU memory increases approximately linearly with mm, ∣T∣|\mathcal T|, and nn, while remaining nearly constant with BB. Reconstruction time for successful runs generally increases with BB and mm but does not exhibit a consistent scaling trend with ∣T∣|\mathcal T| or nn. These results clarify the trade-off between computational cost and reconstruction capability, showing that Multi-Round SPEAR++ incurs additional overhead but achieves full recovery in settings where SPEAR++ fails.


Comparison with Independent Reconstruction Across Multiple Rounds (W4, Q3)

Thank you for the suggestion. We confirmed that our joint multi-round reconstruction formulation outperforms independently reconstructing and combining inputs across the same communication rounds, as shown in the newly added Figure 3 in Section 5.2 of the revised manuscript. We applied SPEAR++ independently to each of the first 10 rounds and combined the reconstructed inputs for each client, ensuring that both methods use the same observed updates. These results demonstrate the effectiveness of our joint reconstruction formulation beyond simply observing multiple communication rounds. The computational overhead of Multi-Round SPEAR++ is reported separately in Table 5 of Appendix F.2.

Thank you again for your review. As less than 36 hours remain before the discussion ends, we would appreciate it if you could clarify whether our responses have addressed your concerns and, if not, which concerns remain.

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

This paper proposes Multi-Round SPEAR++, an exact data reconstruction attack that jointly exploits model updates from multiple federated learning rounds. By normalizing and concatenating first-layer updates that share the same inputs, the method extends SPEAR++ to leverage cross-round information while preserving the ReLU-induced sparsity structure. The paper also characterizes the strict local minimizers of the underlying l_1 objective and uses this analysis to explain reconstruction failures. Experiments on CIFAR-10 show that multi-round updates can substantially improve exact reconstruction over single-round SPEAR++, highlighting that single-round evaluations may underestimate privacy risk.

Critical strengths
  1. The paper introduces a multi-round formulation that jointly exploits updates across communication rounds, extending SPEAR++ beyond the single-round setting while preserving the exact-reconstruction structure.
  2. The work combines theoretical analysis with empirical validation, providing strict-local-minimizer conditions for the l_1 objective and showing substantial reconstruction gains over single-round SPEAR++ on CIFAR-10.
Critical weaknesses
  1. The attack relies on a restrictive common-input assumption across rounds, and it does not directly apply when data augmentation changes the inputs between communication rounds.
  2. The method has limited practical generality, since it depends on a fully connected ReLU first layer and the exact ΔW = GX^⊤ factorization induced by minibatch SGD, leaving adaptive optimizers and broader architectures largely unaddressed.
Questions for authors
  1. How robust is Multi-Round SPEAR++ when the sets of inputs only partially overlap across communication rounds, rather than being exactly the same up to permutation? Since the current formulation relies on a common input matrix across rounds, it would be helpful to clarify whether the method can be extended to realistic client sampling or data-augmentation settings.
  2. How sensitive is the attack to the number and choice of observed communication rounds? In particular, can the authors explain why adding more rounds does not always monotonically improve reconstruction, and provide guidance on how an attacker should select informative rounds?
  3. What is the computational cost of Multi-Round SPEAR++ in practice? The experiments use 2×10^5 random initializations for the l_1-minimization, so runtime and scalability with respect to B, m, and the number of rounds would be important for assessing practical feasibility.
  4. How general is the proposed approach beyond fully connected ReLU networks and minibatch SGD? Since the exact factorization ΔW = GX^⊤ is central to the method, additional discussion or experiments on CNNs, alternative activations, or adaptive local optimizers would substantially strengthen the practical relevance of the paper.
2 comments

We thank the reviewer for the positive assessment and constructive suggestions, which helped us substantially strengthen the paper. We have added extensive experiments addressing the common-input assumption, applicability to other architectures and optimizers, and computational cost. We hope these results address your concerns.


Evaluation with Partially Overlapping Inputs Across Rounds (W1, Q1)

Thank you for the suggestion. We confirmed that Multi-Round SPEAR++ can reconstruct inputs even when the input sets partially overlap across communication rounds, as shown in Figure 11 of Appendix F2. As discussed in Appendix D, the model updates can still be factorized over the union of inputs while preserving ReLU-induced sparsity, allowing our method to exploit these properties for reconstruction. Figure 11 in Appendix F.2 shows that the full recovery rate remains high with substantial overlap but decreases as the overlap becomes smaller. These results demonstrate that joint reconstruction remains effective with partially overlapping inputs, although performance depends on the degree of overlap. In contrast, independently augmented inputs generally violate Assumption 1, so our current formulation does not directly apply.


Analysis of When Additional Rounds Improve Reconstruction (Q2)

Thank you for the question. Figure 8 in Appendix F.2 shows that increasing the number of observed rounds substantially improves full recovery rates, particularly for larger local datasets, although the improvement is not necessarily monotonic.

Additional rounds can improve the rank condition but do not necessarily improve the dual margin or guarantee successful candidate search. While the attacker can evaluate the rank of observed updates, rank alone does not determine reconstruction success. These results clarify why additional observations can improve reconstruction without guaranteeing monotonic gains. Developing a reliable criterion for selecting informative rounds remains an interesting direction for future work.


Clarification of Applicability to Other Architectures and Activation Functions (W2, Q4)

Thank you for the suggestion. We confirmed that Multi-Round SPEAR++ can reconstruct intermediate features in CNN-based models with a frozen backbone, as shown in Table 3 of Appendix F.2. Using a frozen ResNet-18 backbone and a fully connected ReLU head, Multi-Round SPEAR++ achieves nearly perfect cosine similarity between reconstructed and original features, substantially outperforming SPEAR++. The frozen backbone preserves intermediate features across rounds, allowing our common-input formulation to apply. The recovered intermediate features could be used to approximately reconstruct the original input images through feature inversion, as demonstrated in the original SPEAR paper.

Direct application to convolutional first layers remains challenging because their weight updates factorize over spatial patches rather than individual input images. For GELU and SiLU, the multi-round factorization remains valid for fully connected layers under SGD. However, our reconstruction algorithm cannot be directly applied because these activations do not generally induce the exact sparsity required for reconstruction. Extending the reconstruction algorithm to these activations remains a promising future direction.


Clarification of Applicability to Momentum and Adaptive Local Optimizers (W2, Q4)

Thank you for the suggestion. We demonstrated that Multi-Round SPEAR++ remains applicable to momentum SGD and maintains its advantage over SPEAR++, as shown in Figure 12 of Appendix F2. When the momentum state is reset at the beginning of each communication round, momentum SGD preserves the required factorization and ReLU-induced sparsity. Figure 12 in Appendix F.2 confirms that our reconstruction approach is not limited to plain SGD. In contrast, adaptive optimizers such as Adam and AMSGrad generally break the required factorization through parameter-wise scaling, as discussed in Appendix A.


Analysis of Computational Overhead and Scalability (Q3)

Thank you for the suggestion. As shown in Table 5 in Appendix F2, we additionally evaluated reconstruction time and peak GPU memory across different numbers of observed rounds, local data sizes, first-layer widths. Peak GPU memory increases approximately linearly with mm and ∣T∣|\mathcal T|, while remaining nearly constant with BB. Reconstruction time for successful runs generally increases with BB and mm but varies non-monotonically with ∣T∣|\mathcal T|. These results clarify the trade-off between computational cost and reconstruction capability, showing that Multi-Round SPEAR++ incurs additional overhead but achieves full recovery in settings where SPEAR++ fails.

Thanks for your reply. I will maintain my score.

Comments on the paper

6 comments

We thank the reviewer for the constructive feedback, which helped us substantially strengthen the paper. We have added extensive experiments addressing the applicability, robustness, and computational cost of Multi-Round SPEAR++. We hope these results address your concerns and would appreciate reconsideration of the overall rating. If concerns remain, we welcome further discussion of the key unresolved issues.


Evaluation with Partially Overlapping Inputs Across Rounds (W1, Q3)

Thank you for the suggestion. We confirmed that Multi-Round SPEAR++ can reconstruct inputs even when the input sets partially overlap across communication rounds, as shown in Figure 11 of Appendix F.2. As discussed in Appendix D, the model updates can still be factorized over the union of inputs while preserving ReLU-induced sparsity, allowing our method to exploit these properties for reconstruction. Figure 11 in Appendix F.2 shows that the full recovery rate remains high with substantial overlap but decreases as the overlap becomes smaller. These results demonstrate that joint reconstruction remains effective with partially overlapping inputs, although performance depends on the degree of overlap. In contrast, independently augmented inputs generally violate Assumption 1, so our current formulation does not directly apply.


Clarification of Applicability to Other Architectures and Activation Functions (W2, W3, Q6)

Thank you for the suggestion. We confirmed that Multi-Round SPEAR++ can reconstruct intermediate features in CNN-based models with a frozen backbone, as shown in Table 3 of Appendix F.2. Using a frozen ResNet-18 backbone and a fully connected ReLU head, Multi-Round SPEAR++ achieves nearly perfect cosine similarity between reconstructed and original features, substantially outperforming SPEAR++. The frozen backbone preserves intermediate features across rounds, allowing our common-input formulation to apply. The recovered intermediate features could be used to approximately reconstruct the original input images through feature inversion, as demonstrated in the original SPEAR paper.

Direct application to convolutional first layers remains challenging because their weight updates factorize over spatial patches rather than individual input images. For GELU and SiLU, the multi-round factorization remains valid for fully connected layers under SGD. However, our reconstruction algorithm cannot be directly applied because these activations do not generally induce the exact sparsity required for reconstruction. For Transformers, extending the low-rank gradient structures exploited by DAGER and TIGER to multi-round reconstruction remains a promising future direction.


Clarification of Applicability to Other Data Modalities (W3)

Thank you for the suggestion. We additionally demonstrated the applicability of Multi-Round SPEAR++ to physiological signals using the PTB-XL ECG dataset, as shown in Figure 13 of Appendix F.2. Multi-Round SPEAR++ substantially outperforms SPEAR++ at larger local data sizes. These results demonstrate that exploiting multiple rounds also improves exact reconstruction beyond image inputs.


Clarification of Applicability to Momentum and Adaptive Local Optimizers (W2, Q5)

Thank you for the suggestion. We demonstrated that Multi-Round SPEAR++ remains applicable to momentum SGD and maintains its advantage over SPEAR++, as shown in Figure 12 of Appendix F.2. When the momentum state is reset at the beginning of each communication round, momentum SGD preserves the required factorization and ReLU-induced sparsity. Figure 12 in Appendix F.2 confirms that our reconstruction approach is not limited to plain SGD. In contrast, adaptive optimizers such as Adam and AMSGrad generally break the required factorization through parameter-wise scaling, as discussed in Appendix A.


Robustness to Clipping and Gaussian Noise (W2, Q5)

Thank you for the suggestion. We conducted additional experiments with full-batch DP-GD using per-sample gradient clipping and Gaussian noise, as shown in Figure 14 of Appendix F.2. The result shows that clipping alone does not prevent full reconstruction, and Multi-Round SPEAR++ substantially outperforms SPEAR++ under very small Gaussian noise. In contrast, neither method achieves full recovery when the noise is calibrated to provide a meaningful DP guarantee. Table 4 reports the corresponding privacy budgets.


Analysis of the Effects of Non-IID Data on Reconstruction Conditions (W4)

Thank you for the suggestion. We confirmed that Multi-Round SPEAR++ remains effective under non-IID data distributions, as shown in Figure 10 of Appendix F.2. Although non-IID data can affect the rank conditions and sparsity patterns, the common-input factorization and ReLU-induced sparsity remain valid when each client's inputs are fixed across rounds.

Figure 10 in Appendix F.2 shows that non-IID data reduces reconstruction performance in some settings, particularly with multiple local update steps, but Multi-Round SPEAR++ maintains a substantial improvement over SPEAR++. These results demonstrate that joint reconstruction remains effective under Non-IID data distribution.


Analysis of When Additional Rounds Improve Reconstruction (W5, Q1)

Thank you for the question. Figure 8 in Appendix F.2 shows that increasing the number of observed rounds substantially improves full recovery rates, particularly for larger local datasets, although the improvement is not necessarily monotonic.

As discussed in Sections 4 and 5.3, additional rounds can improve the rank condition but do not necessarily improve the dual margin or guarantee successful candidate search. Thus, exploiting more rounds does not necessarily lead to higher full recovery rates.


Clarification of the Choice of Frobenius Normalization (W5, Q2)

Thank you for the suggestion. We confirmed that Frobenius normalization improves reconstruction performance and performs comparably to per-row L2L_2 normalization, as shown in Figure 9 of Appendix F.2. Among the suggested alternatives, we evaluated per-row L2L_2 normalization because it preserves the factorization and ReLU-induced sparsity. Both methods substantially outperform no normalization, while per-row normalization provides no consistent improvement over Frobenius normalization. We did not adopt whitening because it generally mixes neuron coordinates and breaks the sparsity required for reconstruction.


Analysis of Computational Overhead and Scalability (Q4)

Thank you for the suggestion. As shown in Table 5 in Appendix F2, we additionally evaluated reconstruction time and peak GPU memory across different numbers of observed rounds, local data sizes, first-layer widths, and input dimensions. Peak GPU memory increases approximately linearly with mm and ∣T∣|\mathcal T|, while remaining nearly constant with BB. Reconstruction time for successful runs generally increases with BB and mm but varies non-monotonically with ∣T∣|\mathcal T|. These results clarify the trade-off between computational cost and reconstruction capability, showing that Multi-Round SPEAR++ incurs additional overhead but achieves full recovery in settings where SPEAR++ fails.

We also varied the number of random initializations NinitN_{\mathrm{init}}, as shown in Table 2 of Appendix F.2. Table 2 shows that increasing the candidate-search budget improves the full recovery rate, consistent with the search failures shown in Figure 4 and discussed in Section 5.3.


Clarification of the Theoretical Contributions Beyond Existing Sparse Recovery Theory (Q7)

Thank you for the question. Classical dual-certificate conditions in sparse recovery typically concern convex ℓ1\ell_1 minimization under linear constraints. In contrast, Proposition 1 provides necessary and sufficient conditions for strict local minima of our nonconvex, sphere-constrained ℓ1\ell_1 objective. It characterizes individual true column directions through both a rank condition and a strict dual-margin condition, as established in Section 4 and Appendix E.

Concatenating rounds adds both zero and nonzero rows. Additional zero rows can help satisfy the rank condition, whereas nonzero rows also change the dual-certificate condition. Consequently, additional rounds do not necessarily improve the dual margin. Figure 4 shows different dual-margin failure rates between multi-round concatenation and increasing the number of first-layer neurons, even with the same number of rows. Thus, the reconstruction gains from multiple rounds cannot be explained solely by improvements in the rank condition.

AuthorsOpenReview ↗

Summary of Updates

We thank all reviewers and the area chair involved in the review of our paper. We are glad that the reviewers recognized the substantial improvements in exact reconstruction over SPEAR++ (Reviewers v5SC, KrFj, and H8SP) and the evaluation in a more realistic FedAvg setting with multiple local update steps, beyond the commonly studied single-step FedSGD setting (Reviewer v5SC).

On the other hand, the reviewers raised several concerns about the original submission, particularly regarding (a) the novelty and effectiveness of joint reconstruction, (b) the scope of applicability and robustness to defenses, and (c) reconstruction conditions and computational cost. We hope that the following updates, highlighted in red in the revised paper, have successfully addressed their concerns.

(a) Novelty and effectiveness of joint reconstruction

  • Joint reconstruction (Figure 3). At B=128B=128 with 1,000 first-layer neurons, Multi-Round SPEAR++ achieves 82% full recovery using 10 rounds, versus 0% when SPEAR++ is applied independently to the same rounds and the reconstructed inputs are combined.

(b) Scope of applicability and robustness to defenses

We confirmed the applicability of our method under the following settings raised by the reviewers.

  • Non-IID data (Figure 10). At B=96B=96, our method achieves 53.1% full recovery, compared with 1.0% for SPEAR++, demonstrating its effectiveness under heterogeneous client data.
  • Partial input overlap (Figure 11). Our method achieves 92.7% full recovery with 96 of 128 inputs sampled per round, demonstrating that complete input overlap is unnecessary.
  • Momentum SGD (Figure 12). At B=128B=128 with momentum coefficient μ=0.9\mu=0.9, our method achieves approximately 77% full recovery, compared with 0% for SPEAR++.
  • CNN-based models (Table 3). At B=96B=96, our method achieves a median cosine similarity of 1.000, compared with 0.360 for SPEAR++, resulting in exact reconstruction of intermediate features from a frozen CNN backbone.
  • ECG data (Figure 13). At B=96B=96, our method achieves 46.9% full recovery, compared with 2.1% for SPEAR++, extending exact reconstruction beyond image data.
  • Gaussian noise (Figure 14). At B=64B=64 with σ=10−6\sigma=10^{-6}, our method achieves 94.8% full recovery, compared with 4.2% for SPEAR++, demonstrating its advantage under very small Gaussian noise.

We also clarified the scope of our method in response to the reviewers’ questions.

  • Applicability scope (Appendix A). We clarified why Multi-Round SPEAR++ does not directly extend to the additional settings raised by the reviewers, including non-ReLU activations, convolutional first layers, and Transformer architectures, beyond the previously discussed limitations on data augmentation and adaptive optimizers.

(c) Reconstruction conditions and computational cost

  • MNIST failure analysis (Figure 6). At B=64B=64, we identified reconstruction completeness as the main cause of failure, followed by candidate-search and dual-margin failures.
  • Candidate search (Table 2). At B=128B=128, increasing random initializations from 50,000 to 800,000 improves the full recovery rate from 46.9% to 81.2%.
  • Computational cost (Table 5). At B=128B=128 with 1,000 first-layer neurons and 10 rounds, our method requires a median of 47 seconds for successful reconstruction and 1.55 GiB of peak GPU memory.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.