Personalized Dictionary Learning for Heterogeneous Datasets
Authors: Geyu Liang
Naichen Shi
Raed Al Kontar
Salar Fattahi
Venue: NeurIPS 2023 poster (2023)
Keywords: Dictionary Learning
Data Heterogeneity
Personalization

Abstract: We introduce a relevant yet challenging problem named Personalized Dictionary Learning (PerDL), where the goal is to learn sparse linear representations from heterogeneous datasets that share some commonality. In PerDL, we model each dataset's shared and unique features as global and local dictionaries. Challenges for PerDL not only are inherited from classical dictionary learning(DL), but also arise due to the unknown nature of the shared and unique features. In this paper, we rigorously formulate this problem and provide conditions under which the global and local dictionaries can be provably disentangled. Under these conditions, we provide a meta-algorithm called Personalized Matching and Averaging (PerMA) that can recover both global and local dictionaries from heterogeneous datasets. PerMA is highly efficient; it converges to the ground truth at a linear rate under suitable conditions. Moreover, it automatically borrows strength from strong learners to improve the prediction of weak learners. As a general framework for extracting global and local dictionaries, we show the application of PerDL in different learning tasks, such as training with imbalanced datasets and video surveillance.

Personalized Dictionary Learning for Heterogeneous Datasets
Geyu Liang
Naichen Shi University of Michigan Ann Arbor, MI 48109 nai cricchen@uicce ch. edu
Raed Kontar
University of Michigan Ann Arbor, MI 48109 l LianggySumi ch. edu
University of Michigan Ann Arbor, MI 48109 al allottar@um ch, edu
Salar Fattahi University of Michigan Ann Arbor, MI 48 18109 fattahi Sathiihumihh ch. edu
Abstract
We introduce a relevant yet challenging problem named Personalized Dictionary Learning (PerDL), where the goal is learn sparse linear representations from heterogeneous datasets that share some commonality. In PerDL, we model each dataset's shared and unique features as global and local dictionaries. Challenges for PerDL not only are inherited from classical dictionary learning (DL), but also arise due the unknown nature of the shared and unique features. In this paper, we rigorously formulate this problem and provide conditions under which the global and local dictionaries can be provably disentangled. Under these conditions, we provide meta-algorithi. called Personalized Matching and Averaging (PerMA) that can recover both global and local dictionaries from heterogeneous datasets. PerMA is highly efficient; it converges to the ground truth at linear rate under suitable conditions. Moreover, it automatically borrows strength from strong learners to improve the prediction of weak learners. As a general framework for extracting global and local dictionaries. we show the application of PerDL in different learning tasks, such as training with imbalanced datasets and video surveillance.
Introduction
Given set of n signals Y .y....., yn] Rdxn ,dictionary learning (DL) aims to find a dictionary D Rdxr and a corresponding code X = [xi..... X,] Brxa such that: (1) each data sample Y; can be written as y, Dx; for < n, and (2) the code X has as few nonzero elements as
possible. The columns of the dictionary D, also known as atoms, encode the "common features" whose linear combinations form the data samples. A typical approach to solve DL is via the following optimization problem:
min X.D
Y DDX + + ||,
(DL)
Here || - is often modeled as a -nomr (Arora et al. 2015 Agarwal et al. 2016) or fo-(pseudo- norm (Spielman al., 2012 Liang al. 2022) and has the role of promoting sparsity in the estimated sparse code. Due to its effective feature extraction and representation, DL has found immense applications in data analytics, with applications ranging from clustering and classification (Ramirez et al. (2010); Tošić and Frossard (201T), to image denoising (Li et al. (2011)), to document detection KaceeiionKasivissaaaaaaaa al. (2012)), ), medical imaging (Zhao al. (02 )), and many others.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, the existing formulations of DL hinge on a critical assumption: the homogeneity of the data. It is assumed that the samples share the same of features (atoms) collected a single dictionary D. This assumption, however, is challenged in practice the data is typically collected and processed in heterogeneous edge devices (clients). These clients (for instance, smartphones and wearable devices) operate in different conditions (Kontar et al.] (017) while sharing some congruity. Accordingly. the collected datasets are naturally endowed with heterogeneous features while potentially sharing common ones. In such setting, the classical formulation of DL faces a major dilemma: the one hand, a reasonably-sized dictionary (with a moderate number of atoms r) may overlook the unique features specific to different clients. On the other hand, collecting both shared and unique features in a single enlarged dictionary (with a large number of atoms r) may lead to computational, privacy, and identifiability issues. In addition, both approaches fail to provide information about "what is shared and unique" which may offer standalone intrinsic value and can potentially be exploited for improved clustering, classification and anomaly detection, amongst others.
With the goal of addressing data heterogeneity in dictionary learning, in this paper, we propose personalized dictionary learning (PerDL); a framework that can untangle and recover global and local (umique) dictionaries from heterogeneous datasets. The global dictionary, which collects atoms that are shared among all clients, represents the common patterns among datasets and serves conduit of collaboration in our framework. The local dictionaries, on the other hand, provide the necessary flexibility for our model to accommodate data heterogeneity.
We summarize our contributions below:
Identifiability of local and global atoms: We provide conditions under which the local and global dictionaries can be provably identified and separated by solving nonconvex optimization problem. At a high level, our identifiability conditions entail that the true dictionaries are column-wise incoherent, and the local atoms do not have a significant alignment along any nonzero vector.
Federated meta-algorithm: We present a fully federated meta-algorithm, called PerMA (Algorithm []. for solving PerDL. PerMA only requires communicating the estimated dictionaries among the clients, thereby circumventing the need for sharing any raw data. A key property of PerMA is its ability to untangle global and local dictionaries by casting it as a series of shortest path problems over a directed acyclic graph (DAG).
Theoretical guarantees: We prove that, under moderate conditions on the generative model and the clients, PerMA enjoys linear convergence to the ground truth up statistical error. Additionally, PerMA borrows strength from strong clients to improve the performance of the weak ones. More concretely, through collaboration, our framework provides weak clients with the extra benefits of averaged initial condition, convergence rate, and final statistical error.
Practical performance: We showcase the performance of PerMA on synthetic dataset, as well as different realistic learning tasks, such as training with imbalanced datasets and video surveillance. These experiments highlight that our method effectively extract shared global features while preserving unique local ones, ultimately improving performance through collaboration.
1.1 Related Works
Dictionary Learning Spielman et al. (2012): Liang et al. (2022) provide conditions under which [L
can be provably solved, provided that the dictionary a square matrix (also known complete DL).
For the more complex case of overcomplele DL with r >> d. Arora et al. (2014) 2015); Agarwal et al.
(2016) show that alternating minimization achieves desirable statistical and convergence guarantees. Inspired by recent results on the benign landscape of matrix factorization (Ge et al. 2017: Fattahi and Sojoudi 2020), /Sun al. (2016) show that a smoothed variant of iL devoid spurious local solutions. In contrast, distributed or federated variants of DL are far less explored. Huang et al. (2022): Gkillas al. (2022) study iD the federated setting. However, they do not provide any provable guarantees on their proposed method.
Federated Learning Personalization Recent years have seen explosive interest in federated learning (FL) following the seminal paper on federated averaging (McMahan et al.) 2017). Literature

---

along this line has primarily focused on predictive modeling using deep neural networks (DNN), be through enabling faster convergence (Karimireddy et al. 2020). improving aggregation schemes at central server (Wang et al.] 2020), promoting fairness across all clients (Yue et al.) 2022) or protecting against potential adversaries (Bhagoji et al., 2019). A comprehensive survey of existing methodology can be found in (Kontar et al., 2021). More recently, the focus has been placed on tackling heterogeneity across client datasets through personalization. The key idea is to allow each client to retain their own tailored model instead of learning one model that fits everyone. Approaches along this line either split weights of DNN into shared and unique ones and collaborate to learn the shared weights (Liang et al., 2020 Dinh et al., 2020), or follow a train-then- -ee--hhen-erroaalizee approach where a global model is learned and fine-tuned locally, often iteratively (Li et al. 202I). Again such models have mainly focused predictive models. Whilst this literature abounds, personalization that aims to identify what is shared and unique across datasets is very limited. Very recently, personalized PCA (Shi and Kontar 2022) proposed to address this challenge through identifiably extracting shared and unique principal components using distributed Riemannian gradient descent. However, PCA cannot accommodate sparsity in representation and requires orthogonality constraints that may limit its application. In contrast, our work considers a broader setting via sparse dictionary learning.
Notation. For matrix A. use || ||, ||A and ||A|| to denote its spectral norm, Frobenius norm, the maximum of its column-wise 2-norm, and the element- wise 1-norm of A, respectively. We use A; to indicate that it belongs to client i. Moreover, we use A() to denote the i-th column of A. We use ((n) to denote the set of n x signed permutation matrices. We define [n] = (1.2,...,,1,
PerDL: Personalized Dictionary Learning
In PerDL, we given N clients, each with n, samples collected in Y, E iRdx and generated as sparse linear combination r global atoms and rę local atoms:
[ D D( for 1 1= N. Y, D D where D
(1)
Here D E dxx denotes global dictionary that captures the common features shared among all clients, whereas D' E pdxr! denotes the local dictionary specific to each client. Let r; = r + denote the total number of atoms in D Without loss of generality, we assume the columns of Dj have unit nn-nr
[ The goal in PerDL is to recover D and (D/+) /==1 ) as well as the sparse codes {X;) given the datasets (Y, } Before presenting our approach for solving PerDL, we first consider the following fundamental question: under what conditions is the recovery of the dictionaries Dø* [D[ 1 and sparse codes { well-posed?
Mi=1
To answer this question, we first note that it is only possible to recover the dictionaries and sparse codes up to a signed permutation: given any signed permutation matrix II E P(r:). the dictionary- code pairs (D,, X,) and (D,II, II, X.) are equivalent. This invariance with respect signed permutation gives rise to an equivalent class of true solutions with size that grows exponentially with the dimension. To guarantee the recovery of solution from this equivalent class, we need the j-incoherency of the true dictionaries.
Assumption (u-incoherency). For each client 1 siis S N, the dictionary D is p-incoherent for some constant > 0, that is,
(ID)))) j.k
# Vd
max
<
(2)
Assumption is standard in dictionary learning (Agarwal et al. (2016); Arora et al. (201): Chatterji
and Bartlet (2017)) and was independently introduced by Fuchs (2005); y Tropp (0006) in signal processing and Zhao and Yu (2006); Meinshausen and Bühlmann (2006) in statisties. Intuitively,
requires the atoms in each dictionary to be approximately orthogonal. To see the necessity of this assumption, consider a scenario where two atoms of D are perfectly aligned (i.c., p = vd). In this case, using either of these two atoms achieve a similar effect in reconstructing Y, contributing to the ill- iol-posedsess of the problem.
'This assumption is without loss of generality since, for any dictionary-codd pair (D,, X.), the columns of Dj can be normalized to have unit norm by re-weighting the corresponding rows of X,.
3

---

Our next assumption guarantees the separation of local dictionaries from the global one in PerDL. First, we introduce several signed cetpuuatttioiiiviniaaia distance metrics for dictionaries, which will be useful for later analysis.
For two dictionaries D2, Raxr, define their signed crrmmutation-invariinn -12-diistance and fz-distance as follows:
Definition 1.
d1,2(D1,D2) == min (rP(())
| D2
(3)
d2 (D,,, D2) == min neP(r)
|I - D2l12.
(4)
Furthermore, suppose II' = arg minneP())
|I -221112 For any 1 15j r. we define
= Dz) -D.ll-lll
d2.0)) (D1, (2), :
(5)
Assumption 2 (@-identifiablity). The local dictionaries (DI+) Ji=1 are 8-identifiable for some con- stant 1, that is, there exists no vector 12d with ||v||2 1 such that
min d2 (D) S.
(6)
EISN SiSn
Suppose there exists unit-norm satisfying (6) for small / This implies that is sufficiently close to at least one atom from each local dictionary. Indeed, one may treat this atom as part of the global dictionary, thereby violating the identifiability of local and global dictionaries. On the other hand, the infeasibility of (6) for large 8 > implies that the local dictionaries are sufficiently dispersed, which in turn facilitates their identification.
With the above assumptions in place, we are ready to present our proposed optimization problem for solving PerDL:
N
min (D.
Σ Y. D.X. +
Σ
X.
leg s.t. (Di) = D for 1 ISiSN.
(PerDL-NCVX) For each client i, PerDL-NCVX aims recover dictionary-code pair (D,, X2) that match Y, under the constraint that dictionaries for individual clients share the same global components.
Meta-algorithm of Solving PerDL
In this section, we introduce our meta-algorithm (Algorithm) T for solving PerDu--CWW NCVXX which we call Personalized Matching and Averaging (PerMA). In what follows, we explain the steps of PerMA:
Local initialization 3):
PerMA starts with a warm-star step where each client runs their own initialization scheme to obtain D (0) This step is necessary even for the classical DL to the initial point inside basin of attraction of the ground truth. Several spectral methods were proposed to
provide theoretically good inttiaiizationAArozz et al. 2015] Agarwal et al.) 2016),, while in practice,
reported that random initialization followed by a few iterations of alternating minimization
approach will suffice (Ravishankar et al. 2020: Liang et al. 2022).
Global matching scheme (Step Given the clients' initial dictionaries, global matching scheme separates the global and local parts each dictionary by solving a series shortest path problems auxiliary graph. Then, obtains refined estimate of the global dictionary via simple averaging. A detailed explanation of this step is provided in the next section.
During each communication round, the clients refine their own dictionary based on the available data, the aggregated global dictionary, and the previous estimate of their local dictionary. A detailed explanation of this step is provided in the next section.
Dictionary update at each client (Step 10

---

Algorithm PerMA: Federated Matching and Averaging
1: Input: :=1-
2: for client = 1, m. N do
3: Client: Obtain D (0)
based Y,
// Initialization step
4: Client: Send D (0)
to the server.
5: end for
6: Server:
(Da.(0) (D) 1.0) )
|=) gllbal_matchiine (ID )==1
// Separating local from global dictionaries
7: Server: Broadeast Da.10) (D] 1000
lim1
8: 0, ..... T do
9: for client I,... N do
Client: (Da ((((+)))) local_update Y, Da.(t) (0)(),D((0)))
D.
// Updating the local and global dictionaries for each client Client: Send (. to the server.
11:
12: end for
Server: Calculate Da.(++1) = NV EM D (2t(t))) // Averaging global dictionaries
13:
14: Server: Broadcast (a.(t+)).
end for
return (Do. (D. D. )
Global aggregation (Step 13
At the end of each round, the server updates the clients' estimate of the global dictionary by computing their average.
distinguishing property of PerMA is that only requires the clients to communicate their dictionar- ies and not their sparse codes. In fact, after the global matching step the initial dictionaries, the clients only need to communicate their global dictionaries, keeping their local dictionaries private.
3.1 Global Matching and Local Updates
In this section, we provide detailed implementations of Alobal_matcchne and local update local_update subroutines PerMA (Algorithm T..
Given the initial approximations of the clients' dictionaries (D. (d) N N
wwm.amthhinnggg seeks to identify and aggregate the global dictionary by extracting the similarities among the atoms of (D.")). To identify the global components, one approach is to solve the following optimization problem
(D (0) (Dit1 ++
D
II
s.t. II P(rs) for IsisN.
(1:ra)
(1:ra)
The above optimization aims to ob- tain the appropriate signed permu- tation matrices (II, J.M. that align the first atoms of the permuted dictionaries. In the ideal regime
)
[D,)
[D.)
IP....
(P,)
)
[P,)
s
t
where D D < S N, the optimal solution (II; F-m yields zero objective value and satisfies
[P,)
(Pa)
[Dw)
(P,)..
[P))
[D:)
(Pw)
(
(0) II
D However,
(1:r))
Figure 1: A schematic diagram for @lobal_matchhe (Al- gorithm 2p. At each iteration, we find the shortest path from to (highlighted with red), estimate one atom of D using all passed vertices and remove the path (including the vertices) from G.
there are two main challenges with above optimization. First, it is a nonconvex, combinatorial problem over the discrete sets (P(r:)). Sec- ond, the initial dictionaries may not
5

---

coincide with their true counterparts. To address the first challenge, we show that the optimal solution the optimization 7 can be efficiently obtained by solving series of shortest path problems defined over an auxiliary graph. To alleviate the second challenge, we show that our proposed algorithm is robust against possible errors in the initial dictionaries.
Consider weighted N- N-layered directed acyclic graph (DAG) G with r; nodes in layer representing the r; atoms in D,. We connect any node a from layer i any node from layer i++ with directed edge with weight w(a, b) d2 (DD)) e (Di+1), 1)). We add a source node s and connect it to all nodes in layer with weight Similarly, we include a terminal node and connect all nodes in layer N to with weight O. A schematic construction of this graph is presented in Figure I Given the constructed graph, Algorithm aiims solve (7) by running r rounds of the shortest path problem: at each round, the algorithm identifies the most aligned atoms in the imitial dictionaries by obtaining the shortest path from 8 to f. Then it removes the used nodes in the path for the next round. The correctness and robustness of the proposed algorithm are established in the next theorem.
Algorithm global @elobal_matching _matching
1: Input: (D.0) i=
and rº.
2: Construct the weighted N-layer DAG described in Section 3.1
3: Initialize (index,) / as empty sets and (a.(0) as an empty matrix.
4: for 1.....,
pd do
5: Find the shortest path p (s, (D (ar)) (D (aa))" (D (ax).t).
6: Add 1 ΣM sign ((DD (0) (ar); (an)) )) (a.) as new column of De.(0)
N
7: Add a index; for every
N.
8: Remove P from G.
9: end for
10: Set D (.(00) = (D, (0)
(nddiin for every i = 1, I....,N. N.
(o,00) D (D.00)
(00)
N
11: return
Theorem 1 (Correctness and robustness of global matching). Suppose (D;) are j-iincoherent
(Assumption and B-identifiable (Assumption 29. Suppose the initial dictionaries { {D.0) satisfy
i=1
d1. (D( (0) D;) S es with 4 E & min (22 2 2g. 3). Then, the output of Algorithm
satisfies:
d1. (o)
D0*
1 N
E
and
d1. (D. D. S ex, for ISiSN. (8)
According to the above theorem, globbllmatcchie can robustly separate the clients' initial dic- tionaries into global and local parts, provided that the aggregated error in the initial dictionaries is below a threshold. Specific initialization schemes that can satisfy the condition of Theorem T include Algorithm from Agarwal al. (2013) and Algorithm from Arora et al. 2015). We also remark that since the constructed graph is a DAG, the shortest path problem can be solved in time linear in the number of edges, which is O (r1 + r. + N-1 rrri+1) via a simple labeling algorithm (see, e.g., (Ahuja et al. 1988 Chapter 4.4)). Since need to solve the shortest path problem r times, this brings the computational complexity of Algorithm 2 to Or Nr where Tmax = max; r;-
Given the initial local and global dictionaries, the clients progressively refine their estimates by applying T rounds of local_update (Algorithm 3. At high level, each client runs a single iteration of a linearly convergent algorithum A, (see Definition 2). followed by an alignment step that determines the global atoms of the updated dictionary using Do.(1) as a "reference point". Notably, our implementation of local_ _atra_lppatteeeee adaptive to different DI, algorithms. This flexibility is indeed intentional to provide a versatile aeta-algorithm for clients with different DL algorithms.

---

Algorithm 3 llocal_ updat_
1: Input: D Da.(t) D.100] Y;
2: D D((+1) A; Y, D One iteration of linearly-convergeat algoritha thm.
3: Initialize S as an empty set and EER Re2xx"
xx2 as an all-zero matrix.
4: for 1,.... pa do
5: Find k* = arg ming d2 (DD) G)) (D.ttt) (8))
) ((IDO10) ()) (D (D(+t1)
6: Append k² S.
7: Set (i,i)-th entry of P to sign
(
8: end for
9: Output: D (2.(+)) (D. (t+1))
Pand D ((+11) (D. (111)8)
(8)
4 Theoretical Guarantees
In this section, we show that our proposed meta-algorithm provably solves PerDL under suitable initialization, identifiability, and algorithmic conditions. To achieve this goal, we first present the definition of a linearly-converg
DL algorithm.
Definition 2. Given a generative model Y D'X*, a DL algorithu A is called (6, p. t -linnearyy convergent for some parameters vb > and < p < if. for any E Raxe such that (D. D') ) < 6, the output of one iteration D+ A(D, Y), satisfies
d2,65) (D+.D") < pd2,6) (D. + Visjsn.
(9)
One notable linearly convergent algorithm is introduced by (Arora al. 2015 discuss this algorithm in more detail the appendix. Assuming all clients are equipped with linearly convergent algorithms,, our next theorem establishes the convergence of PerMA.
Algorithm 5); will
Theorem 2 (Convergence of PerMA). Suppose { are ju-inchhernnt (Assumption and 8- identifiable (Assumption Z]. Suppose, for every client i, the DL algorithm As used in local update
(Algorithm 3 is (ō., Ps: -linerry convergent with 4 A 8, S min { { 12--20 Va 3 Assume
the initial dictionaries [D (0) I satisfy:
d2.2 N
D
(0)
D
min 8, ISiS
d12 D (.0) D.+) s Sg. for i= 1= (10)
1=1
Then, every evver 2 0, PerMA (Algorithm) satisfies
1 N
d (De..0.Dr Do* s
Pi d1.2 (De.(0) D&*
Dh.
(11)
N
d1. (D/100, D S p.d1,
(41(0)) DD!))
+ thi for i N.
(12)
The above theorem sheds light on number of key benefits of PerMA:
Relaxed initial condition for weak clients. Our algorithm relaxes the initial condition on the global dictionaries. In particular, it only requires the average of the initial global dictionaries to be close to the true global dictionary. Consequently, it enjoys provable convergence guarantee even some of the clients do not provide high-quality initial dictionary to the server.
Improved convergence rate for slow clients. During the course of the algorithm, the global dictionary error decreases an average rate of N Eie Pis improving upon the convergence rate of the slow clients.
7

---

Improved statistical error for weak clients. A linearly convergent DL algorithm A, stops making
progress upon reaching a neighborhood around the true dictionary D with radius O ((v)) ). This type
of guarantee is common among DI. algorithms (Arora et al., 2015 Liang et al.) (022) and often corresponds to their statistical error, In light of this, PerMA improves the performance of weak clients (i.e., clients with weak statistical guarantees) by borrowing strength from strong ones.
5 Numerical Experiments
In this section, we showcase the effectiveness of Algorithm I Jusing synthetic and real data. All experiments are performed MacBook Pro 2021 with the Apple M1 Pro chip and 16GB unified memory for a serial implementation MATLAB 2022a. Due to limited space, we will only provide the high-level motivation and implication of our experiments. We defer implementation details and comparisons with the existing methods to the appendix.
5.1 Synthetic Dataset
In this section, we validate our theoretical results on synthetic dataset. We consider ten clients, each with dataset generated according to the model [ The details of our construction are presented pendix. Specifically, we compare the performances of two strategies: (1) independent strategy, where each client solves DL without any collaboration, and (2) col- laborative strategy, where clients collaboratively learn the ground truth dictionaries by solving PerDL via the proposed meta-algorithm PerMA, We initialize both
Colmmssafie Blove Chataal Dictinnrr
Non converging Cliont
Converging Clints PwMM
the ap-
strategies using the same (D) (0) J The initial dic-
tionaries are obtained via a warm-up method proposed in (Liang et al.] [022], Algorithm 4). For fair compar- ison between independent and collaborative strategies, we use the same DL algorithm (Liang et al.) 2022 Algorithm 1)) for different clients. Note that in the independent strategy, the clients cannot separate global from local dictionaries. Nonetheless, to evaluate their performance, we collect the atoms that best align with the true global dictionary D and treat them as the estimated global dictionaries. As can be seen in Figure 2 three out ten clients are weak learners and fail to recover the global dictionary with desirable accuracy. On the contrary, in the collaborative strategy, all clients recover the same global dictionary almost exactly.
Figure 2: PerMA improves the accuracy of the recovered global dictionary for all clients, even if some (three out of ten) are weak learners.
5.2 Training with Imbalanced Data
In this section, we showcase the application of PerDL in training with imbalanced datasets. We consider an image reconstruction task on MNIST dataset. This dataset corresponds a set of handwritten digits (see the first row of Figure 3}. The goal is to recover a single concise global dictionary that can be used to reconstruct the original handwritten digits accurately as possible. In particular, we study a setting where the clients have imbalanced label distributions. Indeed, data imbalance can drastically bias the performance of the trained model in favor of the majority groups, while hurting its performance on the minority groups (Leevy et al. 2018: Thabtah et al. (2020). Here, we consider a setting where the clients have highly imbalanced datasets, where 90% their samples have the same label. More specifically, for client i, we assume that 90% of the samples correspond to the handwritten digit "z" with the remaining 10% corresponding other digits. The second row of Figure 3 shows the effect of data imbalance on the performance of the recovered dictionary on a single client, when the clients do not collaborate. The last row of Figure shows shows the improved performance of the recovered dictionary via PerDL on the same client. Our experiment clearly shows the ability of PerDL to effectively address the data imbalance issue by combining the strengths of different clients.
8

---

5
4
3
9
8
8
0
6
9
4
5
7
3
6
6
3
2
7
2
3 4
8
4
8
8
3
8
2
2
8
9
2
7
2
5
4
5
7
7
9
6
7
4
5
7
8
6
6
3
8
7
2
3
Figure 3: PerMA improves training with imbalanced datasets. We consider the image reconstruction task on the imbalanced MNIST dataset using only five atoms from learned global dictionary. The first row corresponds to the original images. The second row is based on the dictionary learned on a single client with an imbalanced dataset. The third row shows the improved performance of the learned dictionary using our proposed method on the same client.
Original Image
Global Atoms Reconstruction
Local Atoms Reconstruction
Figure 4: PerMA effectively separates the background from moving objects in video frames. Here we reconstruct the surveillance video frames using global and local dictionaries learned by PerMA. We reconstruct the frames using only 50 atoms from the combined dictionaries.
5.3 Surveillance Video Dataset
As proof of concept, consider video surveillance task, where the goal is to separate the background from moving objects. Our data is collected from Vacavant et al.] (2013) (see the first column of Figure 4p. As these frames same background corresponding to the global features we aim to extract. The frames also exhibit heterogeneity as moving objects therein are different from the background. This problem be modeled as an instance of PerDL, where each video frame can be assigned to a "client", with the global dictionary capturing the background and local dictionaries modeling the moving objects. We solve PerDL by applying PerMA to obtain a global dictionary and several local dictionaries for this dataset. Figure 4 shows the reconstructed background and moving objects via the recovered global and local dictionaries. Our results clearly show the ability of our proposed framework to separate global and local features.
taken from surveillance camera, they share the
indeed
"We note that moving object detection in video frames has been extensively studied in the literature and typically solved very accurately via different representation learning methods (such as robust and neural network modeling); see (Yazdi and Bouwmans (018) for a recent survey. Here, we use this case study as a proof' of concept to illustrate the versatility of PerMA in handling heterogeneity, even in settings where the data is not physically distributed among clients.

---

6 Social Impact, Limitations and Future Directions
Our novel approach for personalized dictionary learning presents versatile solution with immediate applications across various domains, such as video surveillance and object detection. While these applications offer valuable benefits, they also bring to the forefront ethical and societal concerns, particularly concerning privacy, bias, and potential misuse. In the context of video surveillance, deploying object detection algorithms may inadvertently capture private information, leading to concerns about violating individuals' right to privacy. However, it is important emphasize that our proposed algorithm is specifically designed to focus on separating unique and common features within the data, without delving into the realm of personal information. Thus, it adheres to ethical principles by ensuring that private data is not processed or used without explicit consent. Bias is another critical aspect that necessitates careful consideration in the deployment of object detection algorithms. Biases can manifest in various forms, such as underrepresentation or misclassification of certain groups, leading to discriminatory outcomes. Our approach acknowledges the importance of mitigating biases by solely focusing on the distinction between common and unique features, rather than introducing any inherent bias into the learning process. Furthermore, the potential misuse of object detection algorithms in unauthorized surveillance or invasive tracking scenarios raises valid concerns. As responsible researchers, we are cognizant of such risks and stress that our proposed algorithm is meant to be deployed in a controlled and legitimate manner, adhering to appropriate regulations and ethical guidelines.
Even though our meta-algorithm PerMA enjoys strong theoretical guarantees and practical perfor- mance, there are still several avenues for improvement. For instance, the theoretical success of PerMA, especially the Global Matching step, relies on an individual initial error of O(1/N). In other words, the initial error should decrease as the number of clients grows. As future work, we plan to relax such dependency via a more delicate analysis. We also note that imposing an upper bound on the initial error is not unique our setting, as virtually all existing algorithms for classical (non-pen non-personnlized) dictionary learning require certain conditions on the initial error. On the other hand, once the assumption on the initial error is satisfied, our meta-al aeta-alggrithm achieves a final error with the same dependency on d (the dimensionality of the data) and n (the number of samples) as the state-of-the-art algorithms for classical dictionary learning (Agarwal al. (2016), Arora et al. (2015)). ) Remarkably, this implies that personalization is achieved without incurring any additional cost on or n, making PerMA highly efficient and competitive its performance.
Acknowledgements
S.F. is supported, in part, by NSF Award DMS-2152776. ONR Award N00014-22-1-2127,, and MICDE Catalyst Grant. R. A. K. is supported in part by NSF CAREER 2144147.
References
Agarwal, A., Anandkumar, A., Jain, P., and Netrapalli, P. (2016). Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Optimization, 26(4):2775-27) 2799.
Agarwal, A., Anandkumar, A., and Netrapalli, P. (2013). Exact recovery of sparsely used overcom- plete dictionaries. stat, 1050:8-39.
Ahuja, R. K., Magnanti, L., and Orlin, J. B. (1988). Network flows.
Arora, S., Ge, R., Ma, T., and Moitra, A. (2015). Simple, efficient, and neural algorithms for sparse coding. In Conference on learning theory, pages 113-149, PMLR.
Arora, S., Ge, R., and Moitra, A. (2014). New algorithms for learning incoherent and overcomplete dictionaries. In Conference on Learning Theory, pages 779-806. PMLR.
Bhagoji. A. N., Chakraborty, S., Mittal, P., and Calo, S. (2019). Analyzing federated learning through an adversarial lens. In International Conference Machine Learning, pages 634 633. PMLR.
Chatterji, N. and Bartlett, L.. (2017). Alternating minimization for dictionary learning with random initialization. Advances in Neural Information Processing Systems, 30.
10

---

Fattahi, S. and Sojoudi, S. (2020). Exact guarantees on the absence of spurious local minima for non-negative rank-1 robust principal component analysis. Journal machine learning research.
Fuchs, J.JJ. (2005). Recovery of exact sparse representations in the presence of bounded noise. IEEE Transactions on Information Theory, 51(10)36001366) -3608..
Ge, R., Jin, C., and Zheng, Y. (2017). No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR.
Gkillas, A.. Ampeliotis. D., and Berberidis, K. (2022). Federated dictionary learning from non- iid data. 2022 IEER 14th Image, Video, and Multidimensional Signal Processing Workshop (IVMSP), pages 1-5, IEEE.
Huang, Liu, Xi, Yang, C., Kaynak, O., and Huang, T. (2022). A federated dictionary learning method for process monitoring with industrial applications. JEEE Transactions on Artificial Intelligence.
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. (2020). Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR.
Kasiviswanathan, S., Wang. H.,, Banerjee, A., and Melville, P. (2012). Online I1 -l-dictionary learning with application to novel document detection. Advances neural information processing systems. 25.
Kontar, R., Shi, N., Yue, X., Chung, S., Byon, E., Chowdhury, M., Jin, J., Kontar, W., Masoud, N., Nouiehed, M., et al. (2021). The internet of federated things (ioft). IEEE Access, 9: 9:156071- 156113.
Kontar, R., Zhou, S., Sankavaram, C., Du, X., and Zhang, Y. (2017). Nomparanetric-comdiion----e remaining useful life prediction incorporating external factors. IEEE Transactions on Reliability, 67(1):41-52.
LeCun, Y., Cortes, C., Burges, C., et al. (2010). Mnist handwritten digit database.
Leevy J. L., Khoshgoftaar, T. M., Bauder, R. A., and Seliya, N. (2018). A survey on addressing high-class imbalance in big data. Journal of Big Data, 5(1):1-30.
Li, S., Fang, L., and Yin, H. (2011) 1). efficient dictionary learning algorithm and its application to 3-d medical image denoising. IEEE transactions biomedical engineering, 59(2):417-42)
Li, T., Hu, S., Beirami, A., and Smith, V. (2021). Ditto: Fair and robust federated learning through personalization. International Conference on Machine Learning.
Liang, G., Zhang. G., Fattahi, S., and Zhang, Y. (2022). Simple alternating minimization provably solves complete dictionary learning. arXiv preprint arXiv:2210.12811
Liang, P. P., Liu, T., Ziyin, L.,, Allen, N. B., Auerbach, R. P., Brent, D., Salakhutdinov, R., and Morency, L.-P. (2020). Think locally, act globally: Federated learning with local and global representations. arXiv preprint arXiv:2001 .01523.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. (2017). Communication- efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statisties, pages 1273-1282 1282. PMLR.
Meinshausen, N. and Bühlmann, P. (2006). High-dimensional graphs and variable selection with the lasso. Annals of Statistics.
Ramirez, I., Sprechmann, P., and Sapiro, G. (2010). Classification and clustering via dictionary learn- ing with structured incoherence and shared features. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 3501-3508. IEEE.
Ravishankar, S., Ma, A., and Needell, (2020). Analysis of fast structured dictionary learning. Information and Inference: A Journal of the IMA, 9(4):785-811.

---

Shi, N. and Kontar, R. A. (2022). Personalized pea: Decoupling shared and unique features. arXiv preprint SXXv:22077.08441.
Spielman, D. A., Wang, H., and Wright, J. (2012). Exact recovery of sparsely-used dictionaries. In Conference on Learning Theory, pages 37-1. JMLR Workshop and Conference Proceedings.
Sun, J., Qu, Q., and Wright, J. (2016). Complete dictionary recovery over the sphere i: Overview and the geometric picture. IEEE Transactions on Information Theory, 63(2):853 884.
Dinh, C., Tran, N., and Nguyen, J. (2020). Personalized federated learning with moreau envelopes. Advances in Neural Information Processing Systems, 33:21394-21405.
Thabtah, F., Hammoud, S., Kamalov, F., and Gonsalves, (2020). Data imbalance in classification: Experimental evaluation. Information Sciences, 513:429-444
Tošić, I. and Frossard, P. (2011). Dictionary learning. ICEE Signal Processing Magazine, 28(2):27- 38.
Tropp. J. A. (2006). Just relax: Convex programming methods for identifying sparse signals in noise. IEEE transactions information theory, 52(3):1030-1033 1051.
Vacavant, A., Chateau, T., Wilhelm, A., and Lequievre, I.. (2013). A benchmark dataset for outdoor foreground/background extraction. In Computer Vision-ACCV 2012 Workshops: ACCV 2012 International Workshops. Daejeon, Korea, November 5-6, 2012, Revised Selected Papers, Part 11, pages 291-300, Springer.
Wang, H., Yurochkin, M., Sun, Y., Papailiopoulos, D., and Khazaeni, Y. (2020). Federated learning with matched averaging. arXiv preprint arXiv:2002.064400.
Yazdi, M. and Bouwmans, T. (2018). New trends on moving object detection in video images captured by moving camera: A survey. Computer Science Review, 28:157-177.
Yue, X., Nouiehed, M., and Al Kontar, R. (2022). Gifair-fl: A framework for group and individual fairness in federated learning. INFORMS Journal on Data Science.
Zhao, P. and Yu, B. (2006). On model selection consistency of lasso. The Journal of Machine Learning Research, 7:2541-2563.
Zhao, R., Li, H., and Liu, X. (2021). survey of dictionary learning in medical image analysis and its application for glaucoma diagnosis. Archives of Computational Methods in Engineering. 28(2):43-447)
12

---

A Further Details on the Experiments
In this section, we provide further details the numerical experiments reported in Section 5
A.1 Details of Section 5.1
In Section 5.1 generate the synthetic datasets according Model with N 10, d 6, ri
and n; = 200 for each 1 < i S 10. Each D; is an orthogonal matrix with the first 1 = 3 columns shared with every other client and the last r = 3 columns unique to themselves. Each X is first generated from Gaussian-Beraan Bernoulli distribution where each entry is non-zero with a probability 0.2. Then, X is further truncated, where all the entries (Xi) with (X)) 0.3 are replaced by (X; (AA) 0.3 sign( (Xi (G,)))
We use the orthogonal DL algorithm (Algorithm 4 introduced in (Liang et al. 2022 Algorithm 1) as the local DL algorithm for each client. This algorithm simple to implement and comes equipped with strong convergence guarantee (see (Liang et al. 22022] Theorem I)). Here (+), denotes the hard-thresholding operator at level Ç, which is defined as:
(i.)) if |A(s)) 2 C, to
(HT (HT<(A))(S))
if ((J)) <.
Specifically, we use 0.15 for the experiments in Section 5.1 Polar(.) denotes the polar decomposition operater, which is defined as Polar(A) UAVA. where U UAEAVI is the Singular Value Decomposition (SVD) of A.
Algorithm 4 Alternating minimization for orthogonal dictionary learning (Liang al. (2022)
1: Input: Y,, (
2: Set X( (+) = H (D,)TTY)
3: Set D (++1) Polar (Y.X(OT)
4: return D (++1)
For fair comparison, we initialize both strategies using the same (D( ( R== which is obtained by iteratively calling Algorithm 4 with a random initial dictionary and shrinking thresholds Ç. For detailed discussion on such an initialization scheme we refer the reader to Liang et al. (2022).
A.2 Details of Section
In section 5.2 we aim to learn dictionary with imbalanced data collected from MNIST dataset (LeCun al. 2010). Specifically, we consider 10 clients, each with 500 handwritten images. Each image is comprised of 28 x 28 pixels. Instead of randomly assigning images, we construct dataset i such that contains 450 images digit and 50 images of other digits. Here client 10 corresponds to digit O. After vectorizing each image into a 784 x one-dimension signal, our imbalanced dataset contains 10 matrices Y, E 781x500 ; 1,..,, 10.
We first use A to learn an orthogonal dictionary for each client, using their own imbalanced dataset. For client i, given the output of Algorithm after T iterations D
reconstruct new signal y using the top k atoms according to the following steps: first, we solve a sparse coding problem find the sparse code x such that y (D() This can be achieved by Step in Algorithm Second, we find the top entries x that have the largest magnitude: X(o1.))>
X(o2.1)>"" ((,. Finally, calculate the reconstructed signal ý as
(1s.1) (D(T)).
y
The second row of Figure is generated by the above procedure with k 5 using the dictionary learned by Client The third row of Figure 3 corresponds the reconstructed images using the output of PerMA.
13

---

A.3 Details of Section 5.3
Our considered dataset in section 5.3 contains 62 frames, each of which is a 480 x 640 x 3 RGB image. We consider each frame patches, we obtain each data matrix Y, E R576x1600 Then we apply PerMA to {Y)) 02 with
client (N 62). After dividing each frame into 40 40
r, = 576 for all i and rd = 30. Consider D D = D D( which is the output of PerMA
for client i. We reconstruct each Y, using the procedure described in the previous section with 50. Specifically, we separate the contribution Ds.(T) from D Consider the reconstructed
matrix Y; as
Y. D
D
X X
De. X
The second column and the third column of Figure A correspond to reconstructed results of Y and Y! respectively. We can see clear separation of the background (which is shared among all frames) from the moving objects (which unique to each frame).
One notable difference between this experiment and the previous one is in the choice of the DL algorithm A, To provide more flexibility, we relax the orthogonality condition for the dictionary. Therefore, we use the alternating minimization algorithm introduced in Arora et al. (2015) for each client (see Algorithm 5 The main difference between this algorithm and Algorithm 4 that the polar decomposition step in Algorithm 4 is replaced by single iteration of the gradient descent applied to the loss function L(D.X) DXX Y
Algorithm 5 Alternating minimization for general dictionary learning (Arora et al. (2015))
1: Input: Y, D
2: Set x HT, (D Y, TY,
3: Set D (t+1)
D 2n D -())) x T!!TT
-
4: return D (1+1)
Even with the computational saving brought up by Algorithm 5 the runtime significantly slows down for PerMA due to large N, d, and p. Here report practical trick to speed up PerMA. which is a local refinement procedure (Algorithm (6) added immediately before local_ update (Step 10 of Algorithm 1. At high level, local_ dictionary matrix Y by removing the contribution of the global dictionary. Then iteratively refines the local dictionary with respect to Y We observed that local_de dddctiionari eettoonary_ree _ref inmeent significantly improves the local reconstruction quality. We leave its theoretical analysis as possible direction for future work.
local_update
inement first finds the local residual data
Algorithm 6 local, dwwtiiiarr_reeiinneeie
1: Input:
((
(t)
D (.00)
Y;
2: Find
X X
such that Y, D D
10)
X X
// Solving sparse coding problem
3: Set Y Y, Do.10 X
4: Set D. (0) (1)
5: for 0, 1,..,, Trefine do
6: Set D refine = A, ( D (r)
// Improving local dictionary
7: end for
8: return Diefine (Teeee,eTrrefuug as refined (1)
14

---

B Additional Experiments
In this section, we present the results of some additional experiments to better showcase the efficiency of PerMA compared with the existing methods and its potential to adapt parameter- algorithm.
B.1 Comparison with Existing Methods
To the best of our knowledge, the problem of personalized dictionary learning (PerDL) has not been previously explored and formally defined. While existing methods federated learning bear some resemblance PerDL, they lack provable guarantees in recovering the global and local dictionaries. To clarify these distinctions, we present a detailed comparison between our work and the most closely related papers by Huang et al. (2022) and Gkillas et al. (2022). We compare methods under the same setting as in Section The results can be seen in Figure [ which shows that PerMA consistently outperforms methods proposed by [Giillas et al. (2022) and Huang al. (2022).
method with these
Calla
TucMA
JuS Flacay N015
Tlace 2012
53 030 03
630 30
TucMA
Figure 5: Comparisons of different methods on synthetic datasets. In the first row, clients are provided with heterogeneous datasets with similar sizes; in the second row, we consider the special cases in which one of the clients has an insufficient sample size and evaluate the performance of the dictionary learned by that specific client. The first column corresponds to final errors with varying d; the second column corresponds to total running times with varying d; the third column corresponds to final errors with varying N; and the forth column corresponds final errors with varying sparsity level. All the results are averaged over independent trials.
Next, in the context of Section 5.2
we compare the quality of the reconstructed images using dictionaries learned from different methods under three metrics: MSE, PSNR and SSIM. A smaller MSE, a larger PSNR, and an SSIM closer to indicate better image reconstruction quality. In Table I k denotes the number of atoms used to reconstruct the image. As can be seen in the table, PerMA achieves the best result in all sections except for the training time.
Finally, in this paper we use PerMA on the surveillance video datasets, with the goal of separating common elements shared by clients (the background) and unique elements (different cars). Such a task cannot be accomplished by Gkillas et al.) (2022) and Huang et al. (2022) due to their lack of personalization. On the other hand, a recently proposed method based on personalized PCA (PerPCA) has been shown to be effective in separating common and unique elements (Shi and Kontar] (022). As a result, we run PerPCA on the same dataset to compare performance with our method. According to Figure 6 PerDL outperforms PerPCA by achieving better separation and higher resolution.
B.2 Auto-tuning of rg
One can easily see from Section 3 that rg is an important prree-pprammetr of our algorithm. A larger ry means more global atoms are sent between central servers and clients, which leads stronger collaboration between them. In the synthetic experiment, assume to know the value of rg. while in
15

---

Global PC Reconstruction
Local PC Reconstruction
Original Image
Figure 6: Objects and background separation by PerPCA.
real-life applications, one needs to fine-tune this parameter. An interesting observation we made is that the proposed PerMA algorithm can be augmented by simple detection mechanism for identifying the correct choice rg. Specifically, during the Global Matching step, where we iteratively remove shortest paths,
monitor the length of the obtained shortest path. By terminating the removal of paths (i.e., adding global atoms) when the length of the path experiences a significant increase beyond predefined threshold, knowledge. This detection mechanism alleviates the burden fine-tuning Tg and allows for a more practical and robust implementation of the algorithm.
effectively identify the appropriate value of rg without requiring prior
To validate the efficacy of this approach, we conducted series of experiments, the results of which are presented in Figure 7 We use different т, 4, 6, with 10 and monitor the lengths of paths. As evident from the outcomes, clear and drastic increase in the length of the Tg + 1-th shortest path is observed, signifying the correct value of rg.
Figure 7: Increase path length for different Tg. Here the r-axis denotes the number of iterations for Algorithm and the z-axis denotes the distance of the P for each iteration.
16

---

Methods
MSE
PSNR
SSIM
Running Time
k
10
=0
== 10
b= 20
6 10
À = 20
(seconds)
PerMA
0.0319
0.0207
15.3795
17.3771
0.6286
0.7074
40.8
Local DL
0.0448
0.0330
14.1936
15.7203
0.5538
0.6162
4.9
Gkillas et al.
0.1069
0.1084
9.8930
9.8360
0.2736
0.2659
3600+
Huang et al.
0.1062
0. 1062
9.9203
9.9212
0.2737
0.2628
3600+
PerPCAA
0.0837
0.0734
11.0118
11.6426
0.3520
0.3959
59.3
Table 1: Comparisons of different methods on MNIST datasets. A smaller MSE, larger PSNR, and
an SSIM closer to indicate better image reconstruction quality. Here denotes the number of atoms used to reconstruct the image.
C Further Discussion on Linearly Convergent Algorithms
In this section, we discuss a linearly convergent DL algorithm that satisfies the conditions of our Theorem 2 In particular, the next theorem is adapted from (Arora et al. 2013, Theorem 12) and shows that modified variant of Algorithm introduced in (Arora et al. 2015 Algorithm 5) is indeed linearly-convergee convergent.
Theorem 3 (Linear convergence of Algorithm in Arora et al. 2015) Suppose that the data matrix satisfies Y = D*X", where D' is an u-incoherent dictionary and the sparse code X sutisfies the generative model introduced Section 1.2 and Section of Arora et al. (205). For any initial dictionary ||D(0)] l|2 1, Algorithm 5 in Arora et al. 2015 (0, p. -lineerrry convergent with 5 OL/ log d), p (1/2, 1), and v/ w(1-).
Algorithm 5 in Arora et al. 2015) is refinement of Algorithm || where the error is further reduced by projecting out the components along the column currently being updated. For brevity, do not discuss the exact implementation of the algorithm; an interested reader may refer to roforoa et al. (2155) for more details. Indeed, have observed in experiments that the additional projection step does not provide a significant benefit over Algorithm
D Proof of Theorems
D.1 Proof of Theorem
To begin with, establish triangular inequality for d1,2(-;-,, which will be important in subsequent arguments:
Lemma (Triangular inequality for .)) For any dictionary D1, D2, D3 E Rdxr, we have
d1.2 (D1, s d1,2 (D1, D2) + d1,2 (D3; D2)
(13)
Proof. Suppose II133 and II3 satisfy d1,2 (Di, D3) |D D3ll1,2 and d1,2 (D3, D2)
[D - -D,l1,,211.2 Then we have
d1,2 (D,, Dz) + d1,2 (Da, D2)
= [D, 11.3 Dall.2 2 + |D3 D2
2 | 22
(14)
2 d1,2 (D,. Dz).
Given how the directed graph 9 is constructed and modified, any directed path from to / will be of the form P (or client) contributes exactly one node (or atom), and the path is determined by a(-) [N] - [r]. Recall that D = D D for every < < N. Assume, without loss of generality, that for
(D(²) )a(1) (D) )a(2)
(D (0)))) + Specifically, each layer
)a(N))
every client 1 S i N,
Lxx,, = arg min
D -
(15)
IMP(())
1.2
17

---

In other words, the first r atoms in the initial dictionaries {D, ) dictionary. Now consider the special path P for 1 S j - r defined as
Ji=1 are aligned with the global
(16) To prove that Algorithm correctly selects and aligns global atoms from clients, it suffices show that (P)) the top-r shortest paths from in G. The length of the path Pj can be bounded as
Pj = ( 00 ...
O +t.
2 (P))
Σ
00) d2 (D,
31 (D
00 (.)))))
min {IIDD.") (1 - _0) 122 +
(D))) (DD 1111)
[((D)") (D.1))bb
(17)
[I(D; 1 + [1 (D()), (,ll),
(G + 4+11
N
4
1=1
We move on to prove that all the other paths from to t will have a distance longer than 2 2 Consider a general directed path P + (D
(D())a(1) )a(1) + (D!") )a(2) + (D (0) )a(N) - that
is not in [P3 ) Based on whether or not P contains atoms that align with the true global ground atoms, there are two situations:
Case 1: Suppose there exists 1 S i S N such that a(1) S r Given Model and the assumed equality (15), we know that for layer i, P contains a global atom. Since P is not in (Pz) there must exist is # i such that a(k) * (t). As a result, we have
(a) C(P)
d1.2 (D. (D! (a( (D) )a(M)))
min [I(D))a(s (a)))(()))))))))))))))))) lla, (D) + (Di)a()))2
-[()))a() (D. (0) Lac [I (a(()) (D (0)
)a(a)laa
IVS
22 (DD (i)a(w))
(18)
max C3 1855N
1
max 6
Vd
15igN
N
Here (a) and (b) are due to Lemma (c) is due to assumed equality (15 (d) is due to the μ- incoherency of Dr and finally (e) is given by the assumption of Theorem
Case 2: Suppose a(i) > 7 for all < i < N. which means that the path P local atoms. Consider the ground truth of these approxi- mations, (Di)an)) (D2) (D)a(2))..., (Di)a(N)- There must exist 1 < i,j < N such that d1,2 ((D))a() (Dj)a()) 2 B. Otherwise, is easy to see that (D. Jiz1 would not be 8-identifiable
only uses approximations
18

---

because any (D; (Di)(()) (a(i) will satisfy (6). As a result, we have the following:
C(P) 2 d1,2 (D. (0)
Ja()) (D) (D)))a() Ja(i)
2 2,, (a6)) (Dj)a()) (a()))(()) - (D,")) )aco) 122 (I(D))at) - (D)))a(s))) )a(s)ll2
maxes E3
N
2 2 E
==1
(19)
So we have shown that (P are the top-r9 shortest paths from to & in G. Moreover, it is easy show that sign (((D))) )ز (D) );) algorithm correctly recovers the global dictionaries (with the correct identity permutation). Finally, have Dz.(0) N Σ (0) )rro, which leads
1 for small enough { Therefore, the proposed
(D.
d1.2 (Da.10) D s
( )2 (D"*),
max 15
N
1=1
Σ
(D. )0) - -DD9)),
S max isire
N
(20)
Σ
max
N
1=1
N
1=
This completes the proof of Theorem 1
D.2 Proof of Theorem 2
Throughout this section, we define:
N
Pc:
(21)
N
We will prove the convergence of the global dictionary in Theorem 2 by proving the following induction: at each f 2 1, we have
d1,2 ( D s pdl.2 (t)
D
+ gb.
(22)
At the beginning of communication round t, each client performs local_update to get D (++1)
given Da.(()
D
Without loss generality, we assume
Ixx,, arg min IEP(())
D
Da
D
(())
(23)
1,2
Lxx, arg min HEP((:)
D D
((+1)
(24)
1.2
Assumed equalities (23 and (44 imply that the permutation matrix that aligns the input and the output of A, is also Irxxr. Specifically, the linear convergence property of A, and Theorem thus suggest:
(D!+t))) (01)),)(000) (D))
SPi (Dacco) -DD)), + VI 1SiS,,1si N. (25)
2
19

---

However, our algorithm is unaware of this trivial alignment. We will next show the remaining steps Docal_udatte correctly recovers the identity permutation. The proof very similar to the proof of Theorem | since we are essentially running Algorithm 2 on a two-layer g. For every I i & N, 1 j Σ r we have
21, (D!(tt)) (Da(tt))) s d112
(DD (Di)), + +11. (IDi),, (Delt))) (26)
26,
Meanwhile for k + j.
d12 ((D!ti1)) (Do..O)))
2 d1, (Di)x 4 (Di),) ) d1.2 ((D(tt))) (Di)x) d1.2 (D:),, (Dektt))
(27)
2p
26,-
vd
2 20,
As result, we successfully recover the identity permutation, which implies
(DP(Ct"), - (D.),, S p:
(DexC))
- (D.
+ + viSisM,SsiS (28)
Finally, the aggregation step (Step 13
Algorithm T gives:
N
d12 Da.(tt1),D90
1
D (i(+++)
D
N
1=1
1,2
(D09),
max 15
N
(Dallttt)
(D
max SSjse N
(29)
Pi (Del.t)) - -(D
max 1rjrro
+ 1//
N
(pdd1,
(o.((0) Doe) + th:
i=1
pd1,2
(t)(t)
D
D
Z.
As result, prove the induction (22 for all 0 < l T 1. Inequality (12) is by-product of the accurate separation global and local atoms and can be proved by similar arguments. The proof hence complete.
20


Reviews:
[{"review_id": "E4Pv4XmA0L", "reviewer": "Reviewer_JdsU", "summary": "This paper proposed a challenging problem named Personalized Dictionary Learning (PerDL), which learned a shared global dictionary and individual local dictionary for heterogeneous datasets. \n\nIn order to investigate the feasibility of the problem, several definitions and assumptions are provided to make the theoretical guarantee. Under these conditions, a meta-algorithm called Personalized Matchina and Averaging (PerMA) is proposed to solve the problem. The convergence of PerMA is theoretically guaranteed. \n\nExperiments are conducted on synthetic, imbalanced digits reconstruction and video surveillance datasets, which show the effectiveness of PerMA. ", "questions": "The comparison is a bit weak.   \nIs it possible to compare with other baselines in Dictionary learning or Federated learning? ", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1). The problem is well-defined to ensure identifiability, feasibility, and convergence with the help of certain mild assumptions and definitions. This involves Assumptions 1 and 2, Definitions 1 and 2. This way, it is natural to investigate and derive a solution under the federated learning context.   \n\n(2). A federated meta-algorithm (PerMA) is proposed to solve the PerDL problem. In particular, Global Matching and Local Updates steps are designed in the federated setting. Global matching utilized a shortest path algorithm to tackle the non-convex and different initialization problems. Local updates employed a linearly-convergent algorithm. \n\n(3). With proper assumption and mild conditions, the convergence of PerMA is proved, being a theoretical contribution to ensure the feasibility of the PerDL problem. \n\n(4). Experiments on three settings verify the rationale of PerDL and the effectiveness of PerMA. ", "weaknesses": "Overall, the theory and method is good.   \nThe experiment is a bit weak, considering only an independent strategy is adopted as the baseline.   \nCan it be compared with other methods, such as personalized PCA? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Can it be compared with other methods, such as personalized PCA?/Is it possible to compare with other baselines in Dictionary learning or Federated learning?\n\nThank you for this helpful suggestion. We kindly refer the reviewer to our general response, where we have included numerical comparisons between our method and other existing methods in our global response. Our method indeed exhibits superior performances in all three case studies."}, {"review_id": "q0O5p7SbHA", "reviewer": "Reviewer_Kgxg", "summary": "This paper studies the problem of personalized federated learning with each client conducting dictionary learning on heterogeneous tasks. This paper splits the learned dictionary into a global dictionary and local dictionaries. It provides the conditions that two types of dictionaries can be provably identified. It designs a federated meta-algorithm where clients only pass estimated global dictionaries to the center. It also provides the linear convergence for the federated learning procedure under some assumptions.", "questions": "1. Please discuss the related techniques about graph methods when tackling the dictionary problem.\n2. The dimension r_g of the global dictionary is the most important hyper-parameter of the algorithm. How to choose it in the experiments? How does the dimension r_g influence the algorithm? More discussions should be added.", "limitations": "More experiments should be added. Authors could take more experiments on tabular data sets. It is better to test how the dimension of the global dictionary r_g influences the performance.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The objective function is concise for the described personalized dictionary learning problem.\n2. It gives conditions when global dictionaries and local dictionaries can be identified. The two conditions satisfy the intuition.\n3. The algorithm finds the global dictionaries given initial client dictionaries by finding the shortest path based on DAG, which is an interesting solution.\n4. The overall algorithm is theoretically guaranteed.\n5. The writing of the paper is good. The description of the algorithm is clear.", "weaknesses": "The experiments are somewhat weak. Using each frame as a client is also strange in the third experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your insightful comments and suggestions. \n\n> The experiments are somewhat weak.\n\nWe kindly refer the reviewer to our general response, where we have included numerical comparisons between our method and other existing methods in our global response. Our method indeed exhibits superior performances in all three case studies.\n\n> Using each frame as a client is also strange in the third experiment.\n\nWe agree with the reviewer's observation that the utilization of each frame as a \"client\" is not a conventional approach. However, in this context, the definition of a \"client\" is somewhat artificial, driven by the ultimate objective of distinguishing common and individually distinctive elements, such as the background and the cars. In this framework, each \"client\" captures the unique features of a frame. It is worth noting that our definition of a client may also mirror real-world scenarios, where each client only has access to a limited number of frames that share local features (e.g., frames captured from a specific angle). Although such applications hold significance, they are not the primary focus of this paper.\n\n> Please discuss the related techniques about graph methods when tackling the dictionary problem.\n\nThe authors thank the reviewer for this comment. On the theoretical studies of dictionary learning, graph-based methods have been used to provide early-stage estimations of the true dictionary, followed by classic alternating methods to achieve exact recovery. In *Arora et al.(2014)*, the authors provide a novel method for dictionary learning based on a connection graph, whose purpose is to detect whether or not two samples (or signals) share the same atom. Such an idea is further developed in *Agarwal et al.(2014)* and *Arora et al.(2015)*. \n\nThe graph-based method in this paper, however, is fundamentally different from the previous works. The main idea behind our approach is to detect the commonalities and similarities among the atoms by casting it as a series of shortest path problems over a synthetically generated directed acyclic graph (DAG). To the best of our knowledge, such an approach has not been used before for identifying the common features in dictionary learning. The closest to our proposed method is the Federated\nMatched Averaging (FedMA) algorithm introduced by *Wang et al. (2020)* for the federated learning of neural network architectures. In this method, identifying a global model is cast as a series of assignment problems over bipartite graphs. This approach is a special case of our proposed graph-based method, where the number of layers is limited to two.\n\nFinally, to solve the shortest path problems, we used the well-known labeling algorithm, which can solve the single source shortest path problem in linear time (with respect to the number of edges in the graph). This algorithm is already implemented in the built-in MATLAB function \"shortestpath.m\". \n\n> The dimension $r_g$ of the global dictionary is the most important hyper-parameter of the algorithm. How to choose it in the experiments? How does the dimension $r_g$ influence the algorithm? More discussions should be added.\n\nWe sincerely thank the reviewer for this very insightful comment. As the reviewer correctly mentioned, $r_g$ is an important hyper-parameter of our algorithm. A larger $r_g$ means more global atoms are sent between central servers and clients, which leads to a stronger collaboration between them. In the synthetic experiment, we assume to know the value of $r_g$, while in real-life applications, one needs to fine-tune this parameter. An interesting observation we made, which was omitted due to limited space, is that the proposed PerMA algorithm can be augmented by a simple detection mechanism for identifying the correct choice of $r_g$. Specifically, during the Global Matching step, where we iteratively remove shortest paths, we can closely monitor the length of the obtained shortest path. By terminating the removal of paths (i.e., adding global atoms) when the path's length experiences a significant increase beyond a predefined threshold, we can effectively identify the appropriate value of $r_g$ without requiring prior knowledge. This detection mechanism alleviates the burden of fine-tuning $r_g$ and allows for a more practical and robust implementation of the algorithm.\n\nTo validate the efficacy of this approach, we conducted a series of experiments, the results of which are presented in Figure 3 in the pdf file. We use different $r_g = 4,6,8$ with $r=10$ and monitor the lengths of paths. As evident from the outcomes, a clear and drastic increase in the length of the $r_g+1$-th shortest path is observed, signifying the correct value of $r_g$.\n\nWe will add the new experiments to the revised manuscript.\n\n### Reference\n\nAgarwal, A., Anandkumar, A., Jain, P., Netrapalli, P., and Tandon, R. (2014). Learning sparsely used overcomplete dictionaries. In Conference on Learning Theory, pages 123–137. PMLR.\n\nArora, S., Ge, R., Ma, T., and Moitra, A. (2015). Simple, efficient, and neural algorithms for sparse coding. In Conference on learning theory, pages 113–149. PMLR.\n\nArora, S., Ge, R., and Moitra, A. (2014). New algorithms for learning incoherent and overcomplete dictionaries. In Conference on Learning Theory, pages 779–806. PMLR.\n\nWang, H., Yurochkin, M., Sun, Y., Papailiopoulos, D., and Khazaeni, Y. (2020). Federated learning with matched averaging. arXiv preprint arXiv:2002.06440.209\n\n\n"}, {"review_id": "G3gQt3DxIy", "reviewer": "Reviewer_zsPp", "summary": "This work tackles the problem of heterogeneity in federated learning through dictionary learning. The authors name this problem _Personalized Dictionary Learning_ (PerDL), which seeks to learn (linear) representations for the heterogeneous datasets from clients, which are supposed to share common characteristics. The insight of their approach is that PerDL will disentangle global/general and local/unique features from clients via DL. The authors provide a thorough analysis of convergence of their method, as well as a federated strategy for learning the dictionaries (PerMA).\n\n__Post-Rebuttal Acknowledgment__\n\nI have read the authors rebuttal, and other reviewers comments. In their rebuttal, the authors fully addressed my concerns, and provided important results and discussion, including further discussion on the ethical impacts of their work. Overall, I think the authors rebuttal greatly improves the quality of their submission. As a result, I increased my score to 6. Weak Accept.", "questions": "## Suggestions\n\nHere, authors may find a list of suggestions associated with the raised weaknesses.\n\n__S1.__ Authors should include the federated learning motivation in their abstract.\n\n__S2.__ Include quantitative results in Sections 5.2 and 5.3. Concerning image reconstruction, a table comparing PSNR, MSE or SSIM metrics of the different tested strategies would be intersting. The same metrics would apply to the data of individual clients. Concerning surveillance video, the authors could consider the F-score as done in [Cuevas et al., 2016, Table 7].\n\n__S3.__ Compare their method against SOTA methods (e.g., [Gkillas et al., 2022] and/or [Huang et al., 2022])\n\n__S4.__ Include a discussion about the possible impacts of the authors work in video surveillance.", "limitations": "The authors did not explicitly discuss the limitations of their work in the main paper. Some discussion is given in the appendix A.3, where the authors comment on the performance of their method when $N$, $d$ and $p$ are large. Furthermore, in section 3.1 the authors analyze the complexity of their method. I think the authors could contextualize this discussion with the overall challenges of large scale tasks (such as video surveillance).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "__Originality.__ The authors present an original and theoretically grounded work for dictionary learning in a federated setting.\n\n__Quality and Clarity.__ The paper is well written and clear. Assumptions are clearly stated and the concepts behind theorems are clearly defined. Analyzing the abstract alone, the federated aspect of this work is not clear (see W1 and S4 below).\n\n__Significance.__ While I consider the authors contribution novel, the fact that in the paper only qualitative results are shown, and that the authors do not draw comparisons with other SOTA methods hinders the significance of this work.", "weaknesses": "Below I list a series of weaknesses of the current paper. Please see my suggestions in the next section on how to improve these points.\n\n__Concerning Clarity__\n\n__W1.__ Even though it is clear from the introduction, the abstract does not mention federated learning at all.\n\n__Concerning the authors experiments__\n\n__W2.__ Sections 5.2 only contain qualitative results (i.e., Figures 3 and 4). This hinders the assessment of their method, especially in comparison to other strategies.\n\n__W3.__ The authors only provide comparisons with non-collaborative/non-federated approaches. A comparison with the methods of [Gkillas et al., 2022] and/or [Huang et al., 2022] would improve the impact of the authors results.\n\n__Concerning Ethical Considerations__\n\n__W4.__ Even though the authors method is not especifically tailored for video surveillance, I think that authors should provide a broader discussion on the ethical impacts of their experiment.\n\n__Post Rebuttal__\n\nIn their rebuttal, the authors correctly addressed all of the above weaknesses. As a result I raised my score from 3. Reject towards 6. Weak Accept.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We really appreciate the reviewer's helpful comments and detailed suggestions.\n\n> W1/S1 \n\nWe thank the reviewer for this comment and apologize for not mentioning federated learning in the abstract. Rest assured, we will address this issue by adding federated learning motivation to our abstract.\n\n>W2/W3/S2/S3\n\nWe acknowledge and apologize for the insufficiency of comparisons and quantification in our numerical sections. We kindly refer the reviewer to our general response, where we validate the effectiveness and efficiency of our method compared to various SOTA methods (including those mentioned by the reviewer) and with quantifiable metrics. We will add these new experiments to our revised paper.\n\n>W4/S4\n\nWe thank the reviewer for raising their concern regarding the ethical impact of our work. This concern has been further investigated by two additional ethics reviewers, and both indicated that neither our method nor our simulations raise any significant ethical issues. \n\nNonetheless, we plan to add the following discussion on the broader and social impact of our work:\n\n\"Our novel approach for personalized dictionary learning presents a versatile solution with immediate applications across various domains, such as video surveillance and object detection. While these applications offer valuable benefits, they also bring to the forefront ethical and societal concerns, particularly concerning privacy, bias, and potential misuse.\n\nIn the context of video surveillance, deploying object detection algorithms may inadvertently capture private information, leading to concerns about violating individuals' right to privacy. However, it is important to emphasize that our proposed algorithm is specifically designed to focus on separating unique and common features within the data, without delving into the realm of personal information. Thus, it adheres to ethical principles by ensuring that private data is not processed or used without explicit consent.\n\nBias is another critical aspect that necessitates careful consideration in the deployment of object detection algorithms. Biases can manifest in various forms, such as underrepresentation or misclassification of certain groups, leading to discriminatory outcomes. Our approach acknowledges the importance of mitigating biases by solely focusing on the distinction between common and unique features, rather than introducing any inherent bias into the learning process. \n\nFurthermore, the potential misuse of object detection algorithms in unauthorized surveillance or invasive tracking scenarios raises valid concerns. As responsible researchers, we are cognizant of such risks and stress that our proposed algorithm is meant to be deployed in a controlled and legitimate manner, adhering to appropriate regulations and ethical guidelines.\"\n\n\n> The authors did not explicitly discuss the limitations of their work in the main paper.\n\nWe thank the reviewer for their comment. To address it, we will add the following paragraph to the paper:\n\n\"Even though our meta-algorithm PerMA enjoys strong theoretical guarantees and practical performance, there are still several avenues for improvement. For instance, the theoretical success of PerMA, especially the Global Matching step, relies on an individual initial error of $O(1/N)$. In other words, the initial error should decrease as the number of clients grows. As a future work, we plan to relax such dependency via a more delicate analysis. We also note that imposing an upper bound on the initial error is not unique to our setting, as virtually all existing algorithms for classical (non-personalized) dictionary learning require certain conditions on the initial error.  On the other hand, once the assumption on the initial error is satisfied, our meta-algorithm achieves a final error with the same dependency on $d$ (the dimensionality of the data) and $n$ (the number of samples) as the state-of-the-art algorithms for classical dictionary learning (*Agarwal et al. (2016)*, *Arora et al. (2015)*). Remarkably, this implies that personalization is achieved without incurring any additional cost on $d$ or $n$, making PerMA highly efficient and competitive in its performance.\"\n\n### Reference\n\nAgarwal, A., Anandkumar, A., Jain, P., and Netrapalli, P. (2016). Learning sparsely used overcomplete dictionaries via alternating minimization. SIAM Journal on Optimization, 26(4):2775–2799.\n\nArora, S., Ge, R., Ma, T., and Moitra, A. (2015). Simple, efficient, and neural algorithms for sparse coding. In Conference on learning theory, pages 113–149. PMLR."}, {"review_id": "mx3DTiqZFb", "reviewer": "Reviewer_ED5i", "summary": "This paper tackles the problem of personalized dictionary learning (PerDL) for heterogeneous datasets that share some commonality. The authors propose a federated meta-algorithm called PerMA that can provably recover both global and local dictionaries from heterogeneous datasets. They show the applications of PerDL in different learning tasks, such as training with imbalanced datasets and video surveillance.\n\n--post rebuttal\nAfter reading the rebuttal, I would like to keep my score. \n", "questions": "My biggest concern is about the insufficient experiments. This paper lacks a comparison between existing dictionary learning methods. Moreover, there is no actual numerical result in experiments. I’d like to see more experiments during the rebuttal.", "limitations": "n/a", "rating": 4, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "•\tThe paper proposes a federated meta-algorithm called PerMA that can provably recover both global and local dictionaries from heterogeneous datasets.\n•\tThe paper provides theoretical guarantees on the identifiability, convergence, and robustness of PerMA, and demonstrates its applications in different learning tasks. The result on the Surveillance Video Dataset looks interesting.\n", "weaknesses": "•\tThe paper does not compare PerMA with other existing methods for dictionary learning or federated learning, such as personalized PCA (PerPCA), which would be helpful to evaluate its performance and advantages.\n•\tIn Surveillance Video experiments, why there is only one original image and one local atom? The author is encouraged to give some explanation. Moreover, only one case study seems insufficient.\n•\tFederated Learning is a long studying problem so far, the author is needed to further highlight the difference between their proposed ``global matching and local update” with existing methods.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors truly appreciate the reviewer's insightful comments.\n\n> The paper does not compare PerMA with other existing methods for dictionary learning or federated learning, such as personalized PCA (PerPCA), which would be helpful to evaluate its performance and advantages.\n\nWe kindly refer the reviewer to our general response, where we validate the effectiveness and efficiency of our method compared to various state-of-the-art methods (including PerPCA). We will add these new experiments to our revised paper.\n\n>In Surveillance Video experiments, why there is only one original image and one local atom? The author is encouraged to give some explanation. Moreover, only one case study seems insufficient.\n\nThere seems to be a misunderstanding in our experimental setup, and we apologize for any confusion caused. To clarify, there is indeed more than one local and global atom corresponding to each frame. During our training process, there are in total $61$ different images that share common backgrounds but have individually unique components (cars). For each frame, we learned 30 global atoms and 546 local atoms. The pictures on the second and third columns are reconstructions of the original images using only 50 atoms of the learned dictionary. We apologize for the lack of clarity in our explanation, which will be addressed in the revised paper.\n\nRegarding the reviewer's claim about the numerical section, we want to clarify that our work indeed includes three case studies, and two of these case studies specifically pertain to real-life applications in image and video processing.\n\n> Federated Learning is a long studying problem so far, the author is needed to further highlight the difference between their proposed ``global matching and local update” with existing methods.\n\nWe express our gratitude to the reviewer for raising this important comment. It is crucial to emphasize that, to the best of our knowledge, the problem of personalized dictionary learning (PerDL) has not been previously explored and formally defined. While existing methods in federated learning bear some resemblance to PerDL, they are not directly applicable to address this problem with provable guarantees. To clarify these distinctions, we present a detailed comparison between our work and the most closely related papers by *Huang et al. (2022)* and *Gkillas et al.(2022)*.\n\nFirstly, we rigorously define the problem of personalized dictionary learning in our paper, and our proposed method PerMA is explicitly tailored to extract commonality while preserving heterogeneity across clients. In *Huang et al. (2022)*, no personalization is considered, and in *Gkillas et al.(2022)*, their solution to personalization involves merely broadcasting frequently used atoms without a comprehensive approach to address the underlying challenges.\n\nSecondly, a critical aspect in solving PerDL is the alignment of atoms from different clients, and we address this challenge through our novel graph-based method. In contrast, *Huang et al. (2022)* proposes a brute-force approach for atom alignment, while *Gkillas et al.(2022)* does not consider this important aspect at all.\n\nThirdly, existing works on federated learning, including the two papers mentioned above, have a broader scope and lack specific guarantees on PerDL. In contrast, our meta-algorithm is explicitly designed to tackle PerDL and is equipped with provable guarantees, ensuring its efficacy and effectiveness in personalized dictionary learning scenarios.\n\nFinally, we kindly refer the reviewer to our general response, where we provide a detailed comparison between the performance of our method and these methods. \n\n### Reference\n\nGkillas, A., Ampeliotis, D., and Berberidis, K. (2022). Federated dictionary learning from non-iid data. In 2022 IEEE 14th Image, Video, and Multidimensional Signal Processing Workshop(IVMSP), pages 1–5. IEEE.\n\nHuang, K., Liu, X., Li, F., Yang, C., Kaynak, O., and Huang, T. (2022). A federated dictionary learning method for process monitoring with industrial applications. IEEE Transactions on Artificial Intelligence."}]

Author rebuttal:
We are thankful to the reviewers for carefully reading and commenting on the strengths and weaknesses of our paper. A recurring comment among the reviewers was on the limitation of our experiments. We have thoroughly addressed this comment by conducting more experiments on our method and comparing its performance with three methods (suggested by the reviewers). The results can be found in the uploaded pdf file. We upload the code anonymously via [this link](https://anonymous.4open.science/r/PerMA-4B9E/README.md). We will integrate the results into the final version of our paper. In what follows, we briefly explain our new experiments.

### Synthetic Dataset

In this section, we compare our method with *Gkillas et al. (2022)* and *Huang et al. (2022)* under the same setting as in Section 5.1. The results can be seen in Figure 1. In the first row, clients are provided with heterogeneous datasets with similar sizes; in the second row, we consider the special cases in which one of the clients has an insufficient sample size and evaluate the performance of the dictionary learned by that specific client. The first column corresponds to final errors with varying $d$; the second column corresponds to total running times with varying $d$; the third column corresponds to final errors with varying $N$; and the fourth column corresponds to final errors with varying sparsity levels. All the results are averaged over 3 independent trials. As it can be seen in Figure 1, PerMA consistently outperforms methods proposed by *Gkillas et al. (2022)* and *Huang et al. (2022)*.

### MNIST Dataset

Thanks to the suggestions by Reviewer zsPp, we compare the quality of the reconstructed images using dictionaries learned from different methods under three metrics: MSE, PSNR and SSIM. A smaller MSE, a larger PSNR, and a larger SSIM indicate better image reconstruction quality. In Table 1, $k$ denotes the number of atoms used to reconstruct the image. 
As can be seen in the table, PerMA achieves the best result in all sections except for the training time.

### Surveillance Video Dataset

In this paper, we use PerMA on the surveillance video datasets, with the goal of separating common elements shared by all clients (the background) and unique elements (different cars). Such a task cannot be accomplished by *Gkillas et al. (2022)* and *Huang et al. (2022)* due to their lack of personalization. We refer interested reviewers to our response to Reviewer zsPp for further discussion of PerMA on video surveillance.  As a result, to compare our method with the state-of-the-art, we run Personalized PCA (PerPCA) introduced by *Shi and Kontar (2022)* on the same datasets. According to Figure 2, PerDL outperforms PerPCA by achieving better separation and higher resolution. We notice that Reviewer zsPp's suggestion to use F-score to quantify our result. However, F-score is mainly used as a metric to evaluate the accuracy of object detection strategy. Turning PerMA into an object detection strategy is an interesting future research direction but is not the focus of our paper. 

### Reference
Gkillas, A., Ampeliotis, D., and Berberidis, K. (2022). Federated dictionary learning from non-iid data. In 2022 IEEE 14th Image, Video, and Multidimensional Signal Processing Workshop(IVMSP), pages 1–5. IEEE.

Huang, K., Liu, X., Li, F., Yang, C., Kaynak, O., and Huang, T. (2022). A federated dictionary learning method for process monitoring with industrial applications. IEEE Transactions on Artificial Intelligence.

Shi, N. and Kontar, R. A. (2022). Personalized pca: Decoupling shared and unique features. arXiv preprint arXiv:2207.08041.


Meta-review: The paper receives four informative reviews. After the author rebuttal, the majority of the reviews agree that the paper is contributive and suggest acceptance. Reviewer ED5i, who didn’t response to the authors’ rebuttal, remains negative. As far as I can see, the authors’ rebuttal has addressed properly Reviewer ED5i's concerns about the experimental comparisons. Thus, I would recommend accepting the paper.
Decision: Accept (poster)