Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML
differential privacy;large models;DP-SGD;matrix factorization
Yes
No ethics review needed.
- Could context be provided for how a "strategy" should be interpreted? Around l85 in the background.
- The "workload" $A$ is introduced around l150 but the context is also unclear to me here. What is the role of this object and why is it natural to view as a lower triangular matrix of ones?
- Could the authors provide a definition of Toeplitz strategies? One was not provided.
- Lastly, is there a typo on l85? $i \leq j + b$ looks the wrong-way-around to me.
The paper investigates practical scalability issues of a useful DP-ML algorithm and makes substantial performance improvements that increase the range of high-dimensional learning tasks that may be solved by DP-BandML.

The purpose and conclusions of the experiments are well-explained.

Overall, the paper is very clearly written and pleasant to read.
The paper studies a mechanism (DP-BandMF) for private machine learning that has advantages over the standard private mechanism (DP-SGD) in some regimes due to its use of optimized correlated noise. The algorithm is characterized by a strategy matrix that determines the correlational structure of the noise.

This work identifies the optimization of the stategy matrix is a computational bottleneck limiting the applicability of DP-BandMF. Prior work gives an $O(n^3)$ time and $O(n^2)$ space algorithm, which is impractical for large values of $n$. This work improves the running time to $O(bn^2)$ and the space to $O(bn)$ where the band size $b$ characterizes the level of correlation allowed between noise vectors. The authors go on to give a further improved $O(bn)$ time $O(n)$ space algorithm for a restricted class of strategies.

The authors conclude with a series of experiments that assess the scalability and solution quality of their algorithm, the optimal band-size, as well as the suitability of the RMSE measure optimized by their algorithm as a proxy for utility loss.
A small point not addressed in this work is efficient computation of the gradient of the RMSE objective. The authors defer to the Jax implementation. It is unclear whether there is an inherent limitation of this approach or if there is room for meaningful improvement in gradient computation efficiency.

A more significant weakness of this work is somewhat limited technical novelty in the results. The primary technical contribution appears to be Algorithm 3, which leverages sparsity and computes the objective in a streaming fashion.

The authors do extend their results in Proposition 3.1 to a new setting involving Toeplitz strategies. This result is nice but I found the following motivation not fully convincing: "This design decision was inspired by manual inspection of the optimal dense strategies, observing that they exhibit a near-Toeplitz structure." While this choice seems bolstered by by the result in Figure 1(a), a more careful theoretical justification would be welcome, if possible.
Yes
No ethics review needed.
1. Is there any insight on why adaptive estimator works worse than adaptive optimizer?

2. In practice, how do we manage the privacy budget for selecting number of bands?
1. This paper is well written and clearly addresses the contributions.
2. The empirical study is thorough with limitations sufficiently addressed.
The paper presents a improvement to the DP-BANDMF, a differentially private mechanism that adds correlated noise to DP-SGD, aiming to address its scalability limitations. Existing approach DP-BANDMF has struggled with computational and memory demands, especially in large-scale models. The authors introduce two methods  to optimize this mechanism for scenarios involving over 10^6 training iterations and up to 10^9 model parameters, making it feasible for use with modern, large-scale models. The empirical results demonstrate significant performance gains over existing mechanisms.
The only concern here is that this paper does not discuss too much privacy utility trade-off, which is not the focus of this paper.
Yes
No ethics review needed.
I have no questions.
1. The problem is well explained and motivated.
2. Extensive theoretical and empirical analysis to support the proposed mechanism.
3. The paper is well-written and easy to follow.
This paper proposes a differential privacy method that utilizes both random sampling and correlated noise via the use of b-banded strategy matrix. The number of bands b controls the proportion of privacy amplification from subsampling and correlated noise, which can be optimally selected with efficient computation cost using the banded Toeplitz strategy. Further distributed noise generation is used to save potential memory cost.
1. A discussion on the communication cost w.r.t the number of bands as a tradeoff in the distributed setting would be nice to have.
We propose new techniques to improve the scalability of the banded matrix factorization mechanism, which is the current state-of-the-art mechanism in the DP-MF family.
@inproceedings{
anonymous2024scaling,
title={Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private {ML}},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=69Fp4dcmJN},
note={under review}
}
Correlated noise mechanisms such as DP Matrix Factorization (DP-MF) have proven to be effective alternatives to DP-SGD in large-epsilon few-epoch training regimes.  Significant work has been done to find the best correlated noise strategies, and the current state-of-the-art approach is DP-BandMF , which optimally balances the benefits of privacy amplification and noise correlation.  Despite it's utility advantages, severe scalability limitations prevent this mechanism from handling large-scale training scenarios where the number of training iterations may be more than $10^4$ and the number of model parameters may exceed $10^7$.  In this work, we present techniques to scale up DP-BandMF along these two dimensions, significantly extending it's reach and enabling it to effectively handle settings with over $10^6$ training iterations and $10^9$ model parameters, with no utility degradation at smaller scales.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
differential privacy large models DP-SGD matrix factorization
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/bca97e3225106e0fc0153fb738793f788b730b56.pdf
alignment, fairness, safety, privacy, and societal considerations
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/e5db0d7d7f82a5818cb880d475fa9a6b859b098d.zip
Scaling up the Banded Matrix Factorization Mechanism for Large Scale Differentially Private ML
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission