Federated Binary Matrix Factorization using Proximal Optimization

Dear reviewer d72F,

Thank you for the kind words, for pointing-out the strength of our work, and for the constructive feedback and extensive list of interesting questions. We address the remaining open points in the following.

W1) Significant Contribution

While we draw upon the work of Dalleiger et al. in Boolean matrix factorization, our enhancements are substantial. Firstly, we introduce a novel regularization scheme that surpasses the effectiveness of Dalleiger et al.'s methodology. Secondly, our methodologies represent the inaugural and sole truly federated Boolean matrix factorization algorithm, bridging a crucial research gap and meeting practical demands. Thirdly, we furnish comprehensive guarantees on convergence.

W2) Aggregation complexity

We acknowledge that our proximal aggregation increases the work required from our server. However, the proximal operator is not inherently costly to compute. In fact it can be implemented as a single element-wise matrix operation as a GPU kernel. Computational complexity speaking, it is therefore cheaper than matrix multiplication, and will not raise the computational complexity class neither of our server nor of our clients .

Additionally, aggregation does not occur after every update. Given that the proximal operator is applied to the aggregate, the associated increase in complexity remains independent of the number of clients. Consequently, our approach demonstrates scalability with the number of clients, as illustrated in Figures 3 and 4 of the manuscript.

W3) convergence rate

The convergence rate trivially follows from our proof of Proposition 1, which will yield a rate of $\mathcal{O}\left(\frac1{\lambda_T}\right)$. That is, setting $\lambda_t = t$ yields a linear convergence rate of $\mathcal{O}\left(T^{-1}\right)$. Note that, by choosing a large lambda (such as $t^2$) we can yield faster convergence, but in practice might lead to a reduction in the relative reconstruction loss.

We thank the reviewer for the interest in this aspect of our algorithm. We will clarify the implications in the final version of our manuscript.

W4) assumptions regarding loss

We make use of the standard squared error as loss function and furthermore only make the standard assumption that gradients are bounded. Could you please point out which assumption you deem strong?

W5) writing, proximal operator intuition

To improve our presentation and raise the accessibility of our work, we will include more intuitive descriptions in the main body of our paper, regarding—for example—the interplay of gradient descent, proximal operator, regularization, and aggregation.

W6) self-contained

To make our paper self-contained, we will expand the details and a complete derivation of our proximal algorithms in the appendix.

Q1) Eq. (2)

We deemed this to be more readable, but will revisit the notation.

Q2) After Eq. (3)

$m$ and $n$ are meant to be the parameter-dependent row- or column-counts of the input matrix of $R$. To address confusion, we will adapt our notation.

Q3) Eq. (4): $x$

$x$ is a single real-valued matrix cell from one of the factor matrices. For example $x = U_{ij}$.

Q4) Can the server learn I from A and V=?

Our point is that the server cannot trivially estimate specific attributes about users (i.e., learn $U$ from $A$ and $V$, since factorizations are not unique (nonnegative factorization are not unique, even in case of infinitesimal rigidity [1], and Boolean factorizations can be shown to be not unique by a simple application of the pigeonhole principle, see [2] for further details). We apologize for the imprecision. As stated in Sec. 4.2, we are well aware that a curious server could in principle obtain information about local data from V - one could imagine approaches similar to gradient leakage or membership inference attacks. This is the whole motivation for the differential privacy mechanism in Sec. 4.2 and our empirical evaluation of it in Sec. 5.1.3.

Q5) Proposition 1: the symbol R should be replaced by some other symbol, as it has been used to denote the regularizer.

Indeed, this is a mistake. We will replace it with another symbol. Thank you!

Q6) typo

Good catch!

Q7) Loss function and gradient

It is correct that the loss function does not necessarily converge to $0$. Indeed, it is rather unlikely that it does, since it would imply a perfect factorization. Proposition 1 does not assume this. The assumption of a bounded gradient is ubiquitous in the optimization literature and holds, e.g., for Lipschitz continuous loss functions and data from a bounded domain.

Dear reviewer iqWp,

Thank you for recognizing and highlighting the quality and clarity of our presentation, as well as the relevance of our work. Next, we address your concerns in detail.

W1) straightforward extension

Although we make use of work from Dalleiger et al. on Boolean matrix factorization, our improvements are significant. First, we contribute a novel regularization scheme that clearly outperforms Dalleiger et al.’s approach. Second, our approaches are the first and only truly federated Boolean matrix factorization algorithm in existence, filling an important research gap and addressing real-world needs. Third, we provide rigorous guarantees in terms of convergence.

W2) Proof

We respectfully disagree with the comment that the proof is incorrect. The proof is, in fact, correct. There seems to be a misunderstanding in what approaches zero. It is not the gradient itself, as the reviewer seems to have understood, but rather, we assume that the gradient is limited. It is the gradient component, as opposed to the regularizer, that diminishes towards zero. The proof demonstrates that the gradient is bounded by $R$, and since $\eta_t\propto \lambda_t^-1\rightarrow 0$ for $t\rightarrow \infty$, the limited gradient multiplied by a decreasing learning rate tends to zero. We apologize if the wording caused any confusion, and will rewrite this part to avoid this for any future reader.

We also respectfully disagree that a convergence result is without value if the limit’s utility is not demonstrated. In non-convex optimization, such as for deep learning or federated deep learning, it is common practice to illustrate that $\mathbb{E}[\nabla_w F(w)]$ approaches zero, signifying the attainment of a local minimum or saddle point. These convergence results are highly valuable, although they do not imply the usefulness of that limit.

W3) Matrix Completion

We thank the reviewer for making us aware of related work. We acknowledge that there is related prior art on partially sharing matrices (joint-DP) for federated matrix completion and will reflect this in our related work section. However, federated matrix completion methods are only complementary to our problem. As you also already point out yourself, Algorithms [1-5] focus on non-Boolean data. Imposing Boolean constraints on the resulting factorization is central to our problem setting.

Q1) Datasets

Boolean data is ubiquitous in real-world settings, such as gene mutation data. In many recommender applications, the goal is to distinguish between good or bad recommendations. Factorizing a binarized data matrix with two Boolean factor matrices, will result in sparse (Miettinen et al. 2006), informative, and easily interpretable factorizations by default.

Our datasets are derived from commonly-used and well-known benchmark datasets. However, as we require Boolean inputs, we binarized our datasets first. Comparing aforementioned matrix completion algorithms with our method, would not only compare the performance of different tasks, but would also introduce a bias in favor of our algorithm, as—unlike our approaches—the completion algorithms are not specialized towards Boolean data.

Q2)

The claim is that the server cannot trivially estimate specific attributes about users, since factorizations are not unique (nonnegative factorization are not unique, even in case of infinitesimal rigidity [1], and Boolean factorizations can be shown to be not unique by a simple application of the pigeonhole principle, see [2] for further details). We apologize for the imprecision. As stated in Sec. 4.2, we are well aware that a curious server could in principle obtain information about local data from V - one could imagine approaches similar to gradient leakage or membership inference attacks. This is the whole motivation for the differential privacy mechanism in Sec. 4.2 and our empirical evaluation of it in Sec. 5.1.3.

Q3) Relative Loss

The relative loss can exceed $1$, if the reconstruction consists of more $1$s than the input.

Q4) Sensitivity

Thank you for this great observation. Indeed, we have used a very straight-forward estimation of sensitivity in our experiments, that reveals the maximum number of $1$s in the dataset. Using a differential privacy mechanism to share local maxima is a great idea. Setting a global maximum is a neat practical trick, but requires some domain knowledge to set it right - too low and we have to distort data substantially by subsampling, too large and we decrease the quality due to excessive noise.

Q5) Code

Of course, we will submit a complete, fully documented, and easily usable reproducibility package, that comes as an archive with DOI and a publicly available and maintained GitHub repository.

We thank the reviewer for the constructive feedback that clearly aims to improve our work. In case we answered your questions in a satisfactory way, please do consider raising your score accordingly.

Dear reviewer nPms,

Thank you for your concise summary, for highlighting the quality of our writing, and for recognizing the novelty of our algorithms. We appreciate your valuable feedback and questions that will help us to further improve our work. Next, we address the remaining points.

W1) Limited to binary data

We do not agree that our scope is limited. Our scope is merely different from the scope of non-Boolean matrix factorization. Boolean data is ubiquitous in real-world settings, such as gene mutation data. In many recommender applications, the goal is to distinguish between good or bad recommendations. Factorizing a binarized data matrix with two Boolean factor matrices, will result in sparse, informative, and easily interpretable factorizations by default.

That being said, it would be unfair to experimentally compare binary matrix factorizations of discretized inputs to non-binary matrix factorizations of non-discretized inputs. Applying non-Boolean matrix factorization, e.g. NMF, neither gives such guarantees and often simply does not make sense (e.g. gene activations).

In our experiments, we have selected a mix of easily-recognizable datasets for the MF community and a mix of datasets where the discretization yields results that are sparser and easier to interpret. That is, in those applications it is important to gain insight into which features tend to be jointly present (e.g. yes/no recommendations) resp. for which it primarily matters whether the value is high or low, and the actual values matter much less (e.g. gene expression data).

W2) advantages of a proximal operator

Approaching binary matrix factorization in terms of a proximal algorithm has similar benefits as approaching NMF with proximal gradient descent. That is, by separating loss and binary regularization, we can take a much longer “unregularized” gradient step than the steps taken by e.g., multiplicative update rules (MUR). This will usually result in significantly faster convergence rates in comparison to MUR.

The downside is that we need to compute the proximal step. This, however, is done by a single element-wise matrix operation via an efficient GPU kernel in O(n*k). We will clarify the advantages of our proximal approach in the updated version of the manuscript.

W3) competitors, parameters

We share the desire for having a rigorous and extensive evaluation. We do believe that our evaluation fits this standard well.

W3.1) Regarding reproducibility

• The parameters can be found and are discussed in the “Reproducibility” section in the appendix.
• The implementations for the competing BMF algorithms are publicly available from their respective authors.

W3.2) Regarding results

• We consider a relative loss, normalized by the Frobenius norm of the input matrix, rather than an absolute loss, as this allows for more insightful comparison across datasets.
• During the empirical evaluation, we extensively studied the performance, looked into reconstructions, and validated the correctness of all methods, including the “competing” algorithms. On synthetic data, we observe a different trend in the performance of our “competitors” on synthetic data, which is evidence for this. On real-world data, those algorithms do not allow for an accurate reconstruction in terms of shared coefficient (component) matrices. Because the algorithms perform as expected locally, we discovered that widely-used aggregation strategies fail to address the problem well. We therefore proposed our two methods to address this problem.

Q1) Usefulness of a Regularization Rate

The regularization rate allows us to converge to a Boolean factorization in the limit. This is a crucial aspect of the convergence proof of our algorithm. The exact rates are given in the “Reproducibility” section of the Appendix.

Because FELB and FALB exhibited robust and stable performance behavior, under different yet sensible regularization rates, we skipped a full-blown ablation study for brevity. Therefore, we chose a single exponentially-growing regularization rate, which is $\lambda_t = \lambda · 1.005^t$. As is the case for any method, adversarially chosen parameters will of course yield bad results.

Q2) privacy

The enhanced privacy of occluding observation-specific factors not only reduces the computational complexity on the server-side but also the amount of data that needs to be transmitted. To guarantee differential privacy, we use an additive noise mechanism, which reduces the accuracy—as expected—with regards to having no additive noise.