Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms Yaiza Bermudez∗ , Samir M. Perlaza∗†§ , and Iñaki Esnaola‡§ Emails: [email protected] and [email protected] ∗ Centre Inria d’Université Côte d’Azur, INRIA, Sophia Antipolis, France. † Laboratoire GAATI, Université de la Polynésie française, Fa‘a‘ā, French Polynesia. ‡ School of Electrical and Electronic Engineering, University of Sheffield, Sheffield, United Kingdom.
arXiv:2604.20492v1 [stat.ML] 22 Apr 2026
§ ECE Dept. Princeton University, Princeton, 08544 NJ, USA.
Abstract—In this paper, it is shown, for the first time, that centralized performance is achievable in decentralized learning without sharing the local datasets. Specifically, when clients adopt an empirical risk minimization with relative-entropy regularization (ERM-RER) learning framework and a forwardbackward communication between clients is established, it suffices to share the locally obtained Gibbs measures to achieve the same performance as that of a centralized ERM-RER with access to all the datasets. The core idea is that the Gibbs measure produced by client 𝑘 is used, as reference measure, by client 𝑘 + 1. This effectively establishes a principled way to encode prior information through a reference measure. In particular, achieving centralized performance in the decentralized setting requires a specific scaling of the regularization factors with the local sample sizes. Overall, this result opens the door to novel decentralized learning paradigms that shift the collaboration strategy from sharing data to sharing the local inductive bias via the reference measures over the set of models.
arise as solutions to empirical risk minimizations with relativeentropy regularization (ERM-RER) [5]–[8]. This viewpoint also connects to exponential-weights predictors and PAC-Bayesian posteriors, which reason directly in terms of distributions on hypotheses [9]–[14]. Beyond their variational interpretation, Gibbs measures also capture the long-run distribution of stochastic gradient methods under suitable regimes [15]–[18]. From this standpoint, a complementary line of work studies Gibbs measures as solutions to ERM-RER problems and their extensions [6]–[8], [19]. Other studies focus on change-ofmeasure techniques to quantify the variation of an expectation when the underlying probability measure changes [5], [20]. These developments provide tools to interpret and manipulate Gibbs measures as first-class objects in learning systems, and to reason about how information is transported through probability measures rather than through datasets.
I. I NTRODUCTION This paper shows that centralized performance guarantees Decentralized learning studies how a collection of clients can can be achieved in a decentralized system through a strategic collaboratively tune a learning algorithm by communicating design of (i) the reference measures and (ii) the regularization only over a network, without explicitly exchanging raw datasets. factors that define the clients’ Gibbs algorithm. More precisely, This setting extends early work on distributed and asynchronous a peer-to-peer communication protocol is introduced, in which optimization, where coordination is achieved through local each client transmits its Gibbs probability measure to its succomputations and intermittent message passing [1], [2]. It cessor, which adopts it as reference measure. This mechanism becomes particularly relevant when a central coordinator is unembeds information from datasets into the learning process available or undesirable, or when data transfers are impractical without explicitly transmitting such datasets. A closed-form due to bandwidth, latency, ownership, privacy, or regulatory expression is obtained for the resulting decentralized Gibbs constraints [3]. A standard benchmark for collaborative learning probability measures, together with conditions under which it is the centralized regime in which all local datasets are pooled coincides with the Gibbs measure induced by the centralized and a single training procedure is run on the aggregated pooled-data benchmark. data. While conceptually simple, the pooled-data benchmark is often unachievable in decentralized environments due to The paper is organized as follows. Section II introduces communication constraints and/or restricted disclosure of local the notation and formalizes the decentralized learning setting. datasets [3], [4]. This benchmark is revisited through the lens Section III defines Gibbs conditional probability measures and of Gibbs algorithms, i.e., data-dependent Gibbs probability their interpretation within the context of ERM-RER. Section IV measures on the model space. Such Gibbs measures naturally presents the communication protocol and the main results establishing centralized-performance guarantees. Section V This work is supported in part by the European Commission through the H2020-MSCA-RISE-2019 project 872172; the French National Agency for sketches the proof of the main result. Section VI concludes Research (ANR) through the Project ANR-21-CE25-0013 and the project and discusses practical challenges, including the impact of ANR-22-PEFT-0010 of the France 2030 program PEPR Réseaux du Futur; distortions when probability measures are communicated under and in part by the Agence de l’innovation de défense (AID) through the project UK-FR 2024352. finite-rate constraints.
II. S UPERVISED M ACHINE L EARNING
III. G IBBS A LGORITHMS
Consider a decentralized learning system in which 𝐾 clients collaboratively tune their local learning algorithms by communicating with each other. For all 𝑘 ∈ {1, 2, . . . , 𝐾 }, let M 𝑘 , X𝑘 and Y𝑘 , with M 𝑘 ⊆ R𝑑𝑘 and 𝑑 𝑘 ∈ N, be sets of models, patterns, and labels, respectively, at client 𝑘. The training data available for client 𝑘 consists of 𝑛 𝑘 data points (𝑥 𝑘,1 , 𝑦 𝑘,1 ), (𝑥 𝑘,2 , 𝑦 𝑘,2 ), . . ., (𝑥 𝑘,𝑛𝑘 , 𝑦 𝑘,𝑛𝑘 ), which are elements of the set Z𝑘 ≜ X𝑘 × Y𝑘 . Such data points form the local training dataset, denoted by 𝒛 𝑘 ∈ Z𝑘𝑛𝑘 , which can be explicitly written as 𝒛 𝑘 ≜ (𝑥 𝑘,1 , 𝑦 𝑘,1 ), (𝑥 𝑘,2 , 𝑦 𝑘,2 ), . . . , (𝑥 𝑘,𝑛𝑘 , 𝑦 𝑘,𝑛𝑘 ) . (1) The dataset obtained by the aggregation of all local datasets, denoted by 𝒛 0 , satisfies 𝒛0 ≜ (𝒛1 , 𝒛2 , . . . , 𝒛 𝐾 ) ∈ Z1𝑛1 × Z2𝑛2 × . . . × Z𝑘𝑛𝐾 = (𝑥0,1 , 𝑦 0,1 ), (𝑥0,2 , 𝑦 0,2 ), . . . , (𝑥 0,𝑛0 , 𝑦 0,𝑛0 ) .
(2) (3)
Hence, the total Í number of data points, denoted by 𝑛0 ∈ N, satisfies 𝑛0 ≜ 𝐾 𝑘=1 𝑛 𝑘 . Given a model 𝜽 ∈ M 𝑘 for client 𝑘, the loss induced by such a model with respect to a data point (𝑥, 𝑦) ∈ Z𝑘 is ℓ𝑘 (𝑥, 𝑦, 𝜽), where the function ℓ𝑘 : Z𝑘 × M 𝑘 → [0, +∞),
(4)
is referred to as the loss function of client 𝑘. Such a loss function is assumed to be Borel measurable. The empirical risk induced by such a model 𝜽 ∈ M 𝑘 , with respect to the dataset 𝒛 𝑘 in (1), is determined by the function ( Z𝑘𝑛𝑘 × M 𝑘 −→ [0, +∞) L𝑘 : (5) Í𝑛𝑘 (𝒛 𝑘 , 𝜽) ↦−→ 𝑛1𝑘 𝑖=1 ℓ𝑘 𝑥 𝑘,𝑖 , 𝑦 𝑘,𝑖 , 𝜽 , where the function ℓ𝑘 is defined in (4). The set of all probability measures on the measurable space M 𝑘 , ℱM 𝑘 is denoted by △ M 𝑘 , ℱM 𝑘 , or simply △(M 𝑘 ). The set of all probability measures on M 𝑘 conditioned on 𝑛𝑘 𝑛𝑘 an element of Z𝑘 is denoted by △ M 𝑘 | Z𝑘 . Moreover, the set of probability measures in △ (M 𝑘 ) that are absolutely continuous with respect to 𝑄 𝑘 is denoted by △𝑄𝑘 (M 𝑘 ). Using this notation, a supervised machine learning algorithm is represented by a conditional probability measure, as defined hereunder.
The learning framework of client 𝑘, with 𝑘 ∈ {1, 2, . . . , 𝐾 }, is defined by an ERM-RER problem. To formalize this optimization problem, consider a dataset 𝒛 𝑘 ∈ Z𝑘𝑛𝑘 and the functional R 𝑘,𝒛 𝑘 defined as follows, ( △ (M 𝑘 ) −→ [0, +∞) ∫ R 𝑘,𝒛 𝑘 : (6) 𝑃 ↦−→ L 𝑘 (𝒛 𝑘 , 𝜽) d𝑃 (𝜽) , where the function L 𝑘 is defined in (5). The corresponding ERM-RER problem is min
𝑃∈ △𝑄 𝑘 ( M 𝑘 )
R 𝑘,𝒛 𝑘 (𝑃) + 𝜆 𝑘 𝐷 (𝑃 ∥ 𝑄 𝑘 ) ,
where 𝑄 𝑘 ∈ △ (M 𝑘 ) is a 𝜎-finite measure; 𝜆 𝑘 ∈ (0, +∞) is the regularization factor; and 𝐷 (· ∥ ·) represents the relative entropy, [20, Definition 3]. As shown later in Lemma 1, the solution to (7), whenever it exists, admits a closedform expression. This expression is a probability measure parametrized by the empirical risk function L 𝑘 ; the 𝜎-finite measure 𝑄 𝑘 ∈ △ (M 𝑘 ); and the dataset 𝒛 𝑘 ∈ Z𝑘𝑛𝑘 . Such measures are referred to as Gibbs probability measures. In order to define them, consider the following function: ( R −→ R ∫ K 𝑘,𝑄𝑘 ,𝒛 𝑘 : (8) 𝑡 ↦−→ log exp (𝑡 L 𝑘 (𝒛 𝑘 , 𝜽 𝑘 )) d𝑄 𝑘 (𝜽 𝑘 ) , where the function L 𝑘 is defined in (5). Under the assumption that the reference measure 𝑄 𝑘 is a probability measure, the function K 𝑘,𝑄𝑘 ,𝒛 𝑘 in (8) is the cumulant generating function of the random variable L 𝑘 (𝒛 𝑘 , 𝜽 𝑘 ), for some fixed dataset 𝒛 𝑘 ∈ Z𝑘𝑛𝑘 , when the model 𝜽 𝑘 is sampled from 𝑄 𝑘 . Using this notation, the definition of the Gibbs conditional probability measure is presented hereunder. Definition 2. Given the function L 𝑘 in (5); a 𝜎-finite measure 𝑄 𝑘 ; and a 𝜆 𝑘 ∈ (0, +∞), with 𝑘 ∈ {1, 2, . . . , 𝐾 }, the (𝑄 𝑘 ,𝜆 𝑘 ) probability measure 𝑃𝚯 | 𝒁 ∈ △ M 𝑘 |Z𝑘𝑛𝑘 is said to be 𝑘 𝑘 an (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs conditional probability measure if −1 ∀𝒛 𝑘 ∈ Z 𝑛𝑘 , K 𝑘,𝑄𝑘 ,𝒛 𝑘 < +∞; (9) 𝜆𝑘 and for all (𝒛 𝑘 , 𝜽 𝑘 ) ∈ Z 𝑛𝑘 × supp 𝑄 𝑘 , d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) −1 −1 𝑘 𝑘 𝑘 (𝜽 𝑘 )=exp L 𝑘 (𝒛 𝑘 , 𝜽 𝑘 ) − K 𝑘,𝑄𝑘 ,𝒛 𝑘 , (10) d𝑄 𝑘 𝜆𝑘 𝜆𝑘 where the function K 𝑘,𝑄𝑘 ,𝒛 𝑘 is defined in (8). Note that, while 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘 ) in (10) is referred to as a 𝑘
Definition 1 (Algorithm). For all 𝑘 ∈ {1, 2, . . . , 𝐾 }, a conditional probability measure 𝑃𝚯𝑘 | 𝒁 𝑘 ∈ △ M 𝑘 | Z𝑘𝑛𝑘 is said to represent a supervised machine learning algorithm. Let 𝑃𝚯𝑘 | 𝒁 𝑘 ∈ △ M 𝑘 | Z𝑘𝑛𝑘 be an algorithm. Hence, the instance of such an algorithm trained upon the dataset 𝒛 𝑘 in (1) is denoted by 𝑃𝚯𝑘 | 𝒁 𝑘 =𝒛 𝑘 , which is simply a probability measure in △ (M 𝑘 ).
(7)
𝑘
Gibbs conditional probability measure, the measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) , 𝑘 𝑘 𝑘 obtained by conditioning upon a given dataset 𝒛 𝑘 ∈ Z𝑘𝑛𝑘 , is referred to as a Gibbs probability measure. The following lemma formalizes the connection stated above between Gibbs measures and the ERM-RER problem in (7). Lemma 1. Assume that the optimization problem in (7) admits a solution. Then, the (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) in (10) is the unique solution. 𝑘
𝑘
𝑘
Proof: The proof follows from [20, Lemma 1]. This result has also been reported for other 𝑓 -divergences in [7], [8]. Interestingly, the probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑘 𝑘 𝑘 in (10) is the long-run distribution of a stochastic gradient descent algorithm [18]. In statistical learning, such a distribution is often referred to as the Gibbs algorithm [21]. Another optimization problem that is closely related to the probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) in (10) is the following: 𝑘
𝑘
min
𝑃 ∈ △𝑄 𝑘 ( M 𝑘 )
s.t.
𝑘
R 𝑘,𝒛 𝑘 (𝑃)
(11a)
𝐷 (𝑃 ∥ 𝑄 𝑘 ) ⩽ 𝛾 𝑘 ,
(11b)
for some 𝛾 𝑘 > 0. The following lemma establishes the connection. Lemma 2. Assume that the optimization problem in (11) admits a solution and that 𝜆 𝑘 is such that 𝐷 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑄 𝑘 = 𝛾𝑘 . (12) 𝑘
𝑘
𝑘
Then, the (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑘 𝑘 𝑘 in (10) is the unique solution to (11). Proof: The proof follows from [20, Lemma 4]. Lemma 2 implies that the probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑘 𝑘 𝑘 in (10) minimizes the training empirical risk over all probability measures in the following neighborhood of 𝑄 𝑘 , 𝑃 ∈ △𝑄𝑘 (M 𝑘 ) : 𝐷 (𝑃 ∥ 𝑄 𝑘 ) ⩽ 𝛾 𝑘 . (13) This observation is important for presenting the main results. IV. M AIN RESULT The main result of this work (Theorem 3) is presented in Subsection IV-B. In order to present such a result, the peer-topeer communication protocol used by the clients is introduced. The section ends by stating the necessary conditions under which centralized performance is obtained.
B. Decentralized Algorithms The main result of this work is presented by the following theorem. Theorem 3. For all 𝑘 ∈ {1, 2, . . . , 𝐾 }, consider an (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs probability measure, denoted conditional by 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘 ) ∈ △ M 𝑘 |Z𝑘𝑛𝑘 , where the reference measure 𝑄 𝑘 𝑘 𝑘 satisfies ( 𝑄1 if 𝑘 = 1 𝑄𝑘= (14) 𝑃𝚯(𝑄𝑘−1| 𝒁,𝜆𝑘−1=𝒛) if 𝑘 ⩾ 2, 𝑘−1
𝑘−1
𝑘−1
for some given 𝑄 1 . Then, for all 𝜽 ∈ supp 𝑄 1 , Í exp 𝑘𝑗=1 −1 L𝑗 𝒛 𝑗, 𝜽 d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝜆 𝑗 𝑘 𝑘 𝑘 Í (𝜽) = ∫ . (15) 𝑘 −1 d𝑄 1 (𝒛 exp 𝑖=1 L , 𝝂) d𝑄 (𝝂) 𝑖 𝑖 1 𝜆𝑖 Proof: The proof is presented in [22]. The choice of reference measures 𝑄 1 , 𝑄 2 , . . ., 𝑄 𝐾 in (14) induces a nested structure. Under this structure, the training performed by client 𝑘 uses only its local dataset, while the influence of the previous clients’ datasets is carried out through the reference measure 𝑄 𝑘 . The relevance of this nested structure, in which client 𝑘 shares its Gibbs probability measure (algorithm) with its successor, client 𝑘 + 1, is made clear by Lemma 1. More specifically, the probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑘 𝑘 𝑘 in (15) is the unique solution to (7) and, simultaneously, the unique minimizer of the following optimization problem: ∫ ∑︁ 𝑘 ª 1 © min L 𝑗 𝒛 𝑗 , 𝜽 ® d𝑃 (𝜽) + 𝐷 (𝑃 ∥ 𝑄 1 ) . (16) 𝑃∈ △𝑄1 ( M 𝑘 ) 𝜆𝑗 « 𝑗=1 ¬ The following corollary of Theorem 3 formalizes this observation. Corollary 4. Under the assumption that the measures 𝑄 1 , 𝑄 2 , . . ., 𝑄 𝐾 satisfy (14), the solutions to the optimization problems in (7) and (16) are unique and coincide with the (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs probability measure 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) in (15).
A. Communication Protocol 𝑘 𝑘 𝑘 Figure 1 depicts the forward–backward peer-to-peer commuGiven 𝑘 > 1, the optimization problem in (7) depends nication protocol used in this work. In the forward direction exclusively on the local training dataset 𝒛 . While the reference 𝑘 (blue arrows), for all 𝑘 ∈ {1, 2, . . . , 𝐾 − 1}, client 𝑘 transmits to client 𝑘 + 1 the (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs probability measure 𝑄 𝑘 in (14) depends on the training datasets of the 𝑘 − 1 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) in (10), obtained as the solution to the ERM-RER previous clients, such datasets do not need to be explicitly 𝑘 𝑘 𝑘 problem in (7). Client 𝑘 + 1 adopts this transmitted measure as known for solving (7). In particular, solving (7) requires access its reference measure 𝑄 𝑘+1 in (7). This choice induces a nested to the probability measure 𝑄 𝑘 ∈ △ (M 𝑘 ), but not access to structure of the reference measure, as 𝑄 𝑘+1 = 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) , with the training datasets of all previous clients. This is because for 𝑘 𝑘 𝑘 𝑘 ∈ {1, 2, . . . , 𝐾 − 1}. This is formalized later in Theorem 3. fixed training datasets, 𝑄 𝑘 is simply a probability measure on The backward direction (red arrows) disseminates the final the model space. In contrast, solving the optimization problem Gibbs probability measure. More specifically, once client 𝐾 in (16) requires knowing the training datasets of client 𝑗, has computed its (L𝐾 , 𝑄 𝐾 , 𝜆 𝐾 )-Gibbs probability measure for all 𝑗 ∈ {1, 2, . . . , 𝑘 }. In this case, the reference measure, 𝑃𝚯(𝑄𝐾𝐾| 𝒁,𝜆𝐾𝐾=𝒛) 𝐾 in (10), this measure is transmitted back along 𝑄 1 , does not depend on any training dataset. The fact that the chain, from client 𝐾 to client 𝐾 − 1, then from client 𝐾 − 1 problems (7) and (16) share the same solution unveils an to client 𝐾 − 2, and so on until client 1. This backward important observation: providing client 𝑘 with a reference transmission provides all clients with access to the same final measure 𝑄 𝑘 of the form in (14) reproduces the effect of having Gibbs algorithm. The following subsection describes such a access to the training datasets of the 𝑘 − 1 previous clients. The following subsection unveils, under specific conditions, final algorithm. the centralized-type guarantees of the nested structure.
𝑄1
Client 1 𝑃𝚯(𝑄|1𝒁,𝜆1=𝒛) 1
1
( 𝑄1 ,𝜆1 ) = 𝑄2 𝑃𝚯 |𝒁 =𝒛 1
1
1
1
( 𝑄 ,𝜆𝐾 ) 𝑃𝚯 𝐾 |𝒁 =𝒛 𝐾
𝐾
𝒛1
Client 2 𝑃𝚯(𝑄|2𝒁,𝜆2=𝒛) 2
2
( 𝑄2 ,𝜆2 ) = 𝑄3 𝑃𝚯 |𝒁 =𝒛 2
2
,𝜆𝐾 −1 ) (𝑄 𝑃𝚯 𝐾 −1 |𝒁 =𝒛 𝐾 −1
2
𝐾 −1
𝐾 −1
= 𝑄𝐾
··· 2
𝐾
( 𝑄 ,𝜆𝐾 ) 𝑃𝚯 𝐾 |𝒁 =𝒛 𝐾
𝐾
( 𝑄 ,𝜆𝐾 ) 𝑃𝚯 𝐾 |𝒁 =𝒛
𝐾
𝐾
𝐾
Client 𝐾 𝑃𝚯(𝑄𝐾𝐾| 𝒁,𝜆𝐾𝐾=𝒛) 𝐾
𝐾
𝒛2
𝒛𝐾
Figure 1. Nested Structure: the Gibbs measure produced by client 𝑘 becomes the reference measure 𝑄 𝑘+1 used by client 𝑘 + 1.
C. Centralized Performance Guarantees An important observation is that a strategic choice of 𝜆1 , 𝜆2 , . . ., 𝜆 𝐾 in (15) can lead to achieving the same Gibbs probability distribution as in a setting in which the training datasets of all clients are available to all clients. This describes a decentralized system whose distributed nature does not prevent it from achieving the same Gibbs algorithm that would have been obtained if all the training datasets were available to all clients. The following theorem formalizes this observation.
0) for some 𝛾0 > 0, the probability measure 𝑃𝚯(𝑄𝐾1|,𝜆 in (19) is 𝒁 0 =𝒛 0 also the solution to the following optimization problem: ∫ 𝑛0 1 ∑︁ min ℓ 𝑥 0,𝑖 , 𝑦 0,𝑖 , 𝜽 d𝑃 (𝜽) (22a) 𝑃∈ △𝑄1 ( M 𝐾 ) 𝑛0 𝑖=1
s.t.
𝐷 (𝑃 ∥ 𝑄 1 ) ⩽ 𝛾0 .
From (18), it follows that the measures
(22b) 𝑃𝚯(𝑄𝐾𝐾| 𝒁,𝜆𝐾𝐾=𝒛) 𝐾
and
0) 𝑃𝚯(𝑄𝐾1|,𝜆 are identical, which implies that the nested structure, 𝒁 0 =𝒛 0
induced by the choice of reference measures in (14) and the regularization factors in (17), allows achieving in a Theorem 5. Assume that the loss functions in (4) satisfy decentralized system, the same learning algorithm that would ℓ1 = ℓ2 = . . . = ℓ𝐾 = ℓ and for all 𝑘 ∈ {1, . . . , 𝐾 }, have been obtained in a centralized system in which all training 𝑛0 𝜆 0 datasets are available to all clients. 𝜆𝑘 = , (17) Under the forward–backward communication protocol in 𝑛𝑘 Section IV-A, after 𝐾 − 1 forward messages (blue arrows for some 𝜆0 > 0 and some loss function ℓ. Consider some in Figure 1) client 𝐾 obtains the probability measure that measures 𝑄 1 , 𝑄 2 , · · · , 𝑄 𝐾 satisfying (14). Then, for all 𝜽 ∈ minimizes the empirical risk with respect to all training datasets supp 𝑄 1 , it follows that, within the neighborhood of 𝑄 1 . The backward dissemination d𝑃𝚯(𝑄𝐾𝐾| 𝒁,𝜆𝐾𝐾=𝒛) 𝐾 (red arrows in Figure 1) provides each client with the same (𝜽) = 1, (18) Gibbs algorithm, minimizing within a neighborhood of the (𝑄1 ,𝜆0 ) d𝑃𝚯𝐾 | 𝒁 =𝒛 0 0 form in (13) around 𝑄 1 the empirical risk with respect to the (𝑄𝐾 ,𝜆𝐾 ) where the probability measure 𝑃𝚯𝐾 | 𝒁 𝐾 =𝒛 𝐾 is defined in (15); aggregated dataset. 0) V. P ROOF OF M AIN R ESULT the measure 𝑃𝚯(𝑄𝐾1|,𝜆 satisfies for all 𝜽 ∈ supp 𝑄 1 , 𝒁 0 =𝒛 0 This section first introduces the preliminaries needed for the Í𝑛0 0) exp 𝑛−1 ℓ 𝑥 , 𝑦 ,𝜽 proof of Theorem 3, and then outlines the main steps. A more d𝑃𝚯(𝑄𝐾1|,𝜆 0,𝑖 0,𝑖 𝜆 𝑖=1 0 0 𝒁 0 =𝒛 0 (𝜽) = ∫ ; (19) detailed proof appears in [22]. Í 𝑛0 d𝑄 1 exp 𝑛−1 𝑖=1 ℓ 𝑥 0,𝑖 , 𝑦 0,𝑖 ,𝝂 d𝑄 1 (𝝂) 0 𝜆0 A. Preliminaries and 𝑥0,𝑖 , 𝑦 0,𝑖 are data points of the aggregated dataset 𝒛0 Lemma 6. For all 𝑘 ∈ {1, 2, . . . , 𝐾 }, consider an (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )in (2). Gibbs conditional probability measure, denoted by 𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘 ) ∈ 𝑘 𝑘 Proof: The proof is presented in [22]. △ M 𝑘 |Z𝑘𝑛𝑘 , where the reference measure 𝑄 𝑘 satisfies (14). The relevance of Theorem 5 is highlighted by the following Then, for all 𝜽 ∈ supp 𝑄 1 , observations. Under the assumptions of Theorem 5, in particular ) d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) d𝑃𝚯(𝑄1| 𝒁,𝜆𝑘=𝒛 that the loss functions satisfy ℓ1 = ℓ2 = · · · = ℓ𝐾 = ℓ, the 𝑘 𝑘 𝑘 𝑘 𝑘 𝑘 (𝜽) = (𝜽) exp (𝐶 𝑘 ) , (23) equality in (17) together with [21, Lemma 4] allows rewriting d𝑄 𝑘 d𝑄 1 the optimization problem in (16) as where the measure 𝑃𝚯(𝑄1| 𝒁,𝜆𝑘 ) is an (L 𝑘 , 𝑄 1 , 𝜆 𝑘 )-Gibbs condi𝑘 𝑘 ∫ ∑︁ 𝑛0 tional probability measure and 𝐶 𝑘 ∈ R satisfies 1 min ℓ 𝑥0,𝑖,𝑦 0,𝑖,𝜽 d𝑃 (𝜽) +𝜆 0 𝐷 (𝑃 ∥ 𝑄 1), (20) 𝑃 ∈ △𝑄1 ( M 𝐾 ) 𝑛0 𝑖=1 𝐶𝑘 ≜ ! 𝑘−1 ∫ ∑︁ 1 which requires access to the training datasets of all clients. ©exp K 𝑘,𝑄 ,𝒛 −1 exp − L𝑖 (𝒛𝑖,𝝂) d𝑄 1 (𝝂)ª® 1 𝑘 𝜆𝑘 Interestingly, from Lemma 1, it follows that the probability 𝜆 𝑖 ® 𝑖=1 0) ®, (24) log measure 𝑃𝚯(𝑄𝐾1|,𝜆 in (19) is the solution to (20). More ∫ ® Í 𝒁 0 =𝒛 0 𝑘 1 ′ d𝑄 (𝝂 ′) ® L 𝒛 ,𝝂 exp − 𝑗 𝑗 1 importantly, from Lemma 2, if 𝜆 is chosen such that 𝑗=1 𝜆 𝑗 0 ® (𝑄1 ,𝜆0 ) 𝐷 𝑃𝚯𝐾 | 𝒁 =𝒛 𝑄 1 = 𝛾0 , (21) « ¬ 0 0
where the functional K 𝑘,𝑄1 ,𝒛 𝑘 is defined in (8). Proof: The proof is presented in [22]. The relevance of this lemma lies in the fact that the Radon– Nikodym derivative of an (L 𝑘 , 𝑄 𝑘 , 𝜆 𝑘 )-Gibbs conditional probability measure with respect to its reference measure 𝑄 𝑘 can be re-expressed relative to the fixed reference measure 𝑄 1 , up to a factor, 𝐶 𝑘 in (24), that does not depend on the model. Moreover, this factor admits an information-theoretic characterization in terms of Kullback–Leibler divergences; see [22, Lemma 9]. Lemma 6 constitutes a main step in the proof of Theorem 3 and is explained in the following subsection.
B. Sketched proof of Theorem 3 Using [23, Theorem 4] (chain rule), the Radon–Nikodym derivative in the left-hand side of (23) can be written as follows d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑘
𝑘
d𝑄 𝑘
𝑘
(𝜽)=
d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑘
𝑘
d𝑄 1
𝑘
d𝑄 1 (𝜽) (𝜽) , d𝑄 𝑘
(25)
where (29) follows from (14); and (30) follows from Definition 2 and Lemma 6. Substituting (30) in (26) yields Í 𝑘−1 1 (𝒛 exp − 𝑖=1 L , 𝜽) d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) 𝑖 𝑖 𝜆𝑖 𝑘 𝑘 𝑘 Í (𝜽)= ∫ 𝑘−1 1 d𝑄 1 exp − 𝑖=1 𝜆𝑖 L𝑖 (𝒛 𝑖 , 𝝂) d𝑄 1 (𝝂) ) d𝑃𝚯(𝑄1| 𝒁,𝜆𝑘=𝒛 𝑘
𝑘
𝑘
(𝜽) exp (𝐶 𝑘 ) (31) Í 𝑘 1 exp − 𝑖=1 𝜆𝑖 L𝑖 (𝒛 𝑖 , 𝜽) Í =∫ 𝑘−1 1 (𝒛 exp − 𝑖=1 L , 𝝂) d𝑄 1 (𝝂) 𝑖 𝑖 𝜆𝑖 Í ∫ 𝑘−1 1 exp − 𝑖=1 𝜆𝑖 L𝑖 (𝒛 𝑖 ,𝝂) d𝑄 1 (𝝂) Í (32) ∫ exp − 𝑘𝑗=1 𝜆1𝑗 L 𝑗 𝒛 𝑗 ,𝝂 ′ d𝑄 1 (𝝂 ′ ) Í 𝑘 1 (𝒛 L ,𝜽) exp − 𝑖=1 𝑖 𝑖 𝜆𝑖 Í =∫ ,(33) 𝑘 1 exp − 𝑖=1 𝜆𝑖 L𝑖 (𝒛𝑖 ,𝝂 ′ ) d𝑄 1 (𝝂 ′ ) d𝑄 1
where (32) follows from (24); and (33) yields (15). This completes the proof. VI. C ONCLUSIONS AND F INAL R EMARKS
This work establishes that, in a decentralized machine Then, from Lemma 6 and [23, Theorem 5], the equality in learning scenario, an appropriate choice of reference measures (25) yields (𝑄 1 , 𝑄 2 , . . . , 𝑄 𝐾 ) and regularization factors (𝜆1 , 𝜆2 , . . . , 𝜆 𝐾 ) allows guaranteeing the same performance as a centralized (𝑄1 ,𝜆 𝑘 ) d𝑃𝚯(𝑄𝑘| 𝒁,𝜆𝑘=𝒛) d𝑃 system in which all training datasets are aggregated and d𝑄 𝑘 𝚯 𝑘 | 𝒁 𝑘 =𝒛 𝑘 𝑘 𝑘 𝑘 (𝜽)= (𝜽) (𝜽) exp (𝐶 𝑘 ) . (26) jointly available. The construction of such regularization factors d𝑄 1 d𝑄 1 d𝑄 1 is rather simple. The regularization factor of client 𝑘 shall be the product of a strictly positive real (common to all Moreover, from [6, Lemma 3], the Radon–Nikodym derivatives clients) and the ratio of the sizes of the training dataset of in (25) and in (26) are well defined. client 𝑘 and the aggregated training dataset. The reference d𝑄 𝑘 The next step consists in expressing using the nested measure of client 𝑘, 𝑘 > 1, is the Gibbs measure (Gibbs d𝑄 1 definition of the reference measures in (14). This nested con- algorithm) from which client 𝑘 − 1 samples its models. The struction implies the absolute continuity assumptions required first client uses a given reference 𝑄 1 . Under such a choice, to apply a chain rule for Radon–Nikodym derivatives. The client 𝐾 obtains a Gibbs probability measure that solves the resulting product decomposition isolates successive changes ERM-RER problem, with respect to the aggregated dataset, of reference measure and therefore allows each factor to within a neighborhood of 𝑄 1 . Via backward dissemination, be handled separately using Lemma 6. Then, from [23, all clients obtain the same probability measure (algorithm). This choice of reference measures induces a nested structure Theorem 4], it follows that whose construction requires transmitting 𝐾 − 1 probability measures with common support [6, Lemma 3]. Several practical 𝑘 Ö d𝑄 𝑗 d𝑄 𝑘 (𝜽) = (𝜽) (27) challenges arise from this requirement. A main limitation is d𝑄 1 d𝑄 finite-rate communication, possibly under delay constraints, 𝑗 −1 𝑗=2 which implies that the probability measure transmitted by 𝑘 Ö d𝑄 𝑗 d𝑄 2 client 𝑘 may be received by client 𝑘 + 1 with distortion. (𝜽) (𝜽) = (28) d𝑄 1 d𝑄 Characterizing the impact of such distortions on the nested 𝑗 −1 𝑗=3 construction remains an open problem and is not addressed ( 𝑄 𝑗 ,𝜆 𝑗 ) 𝑘−1 d𝑃 Ö d𝑃𝚯(𝑄|1𝒁,𝜆1=𝒛) here. A further limitation is the potentially large support of 𝚯 𝑗 | 𝒁 𝑗 =𝒛 𝑗 1 1 1 (𝜽) (𝜽) = (29) the involved Gibbs probability measures, which can make the d𝑄 1 d𝑄 𝑗 𝑗=2 communication requirement comparable to transmitting the Í 𝑘−1 1 training datasets. Nonetheless, the transmission of a probability (𝒛 exp − 𝑖=1 L , 𝜽) 𝑖 𝜆𝑖 𝑖 Í =∫ , (30) measure is more privacy-preserving than the actual transmission 𝑘−1 1 exp − 𝑖=1 of training datasets. 𝜆𝑖 L𝑖 (𝒛 𝑖 , 𝝂) d𝑄 1 (𝝂)
R EFERENCES [1] J. N. Tsitsiklis, D. P. Bertsekas, and M. Athans, “Distributed asynchronous deterministic and stochastic gradient optimization algorithms,” IEEE Transactions on Automatic Control, vol. 31, no. 9, pp. 803–812, Sep. 1986. [2] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, 1st ed. Englewood Cliffs, NJ: Prentice-Hall, 1989. [3] P. Kairouz, B. H. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. d’Oliveira, S. E. Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. He, Z. Huo, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P. Mittal, M. Mohri, R. Nock, A. Ozgür, R. Pagh, M. Raykova, H. Qi, D. Ramage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, J. Wang, L. Xiong, Z. Xu, Q. Yang, F. X. Yu, H. Yu, and S. Zhao, Advances and Open Problems in Federated Learning. Now Publishers, 2021, vol. 14, no. 1–2. [4] C. Dwork, “Differential privacy,” in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), vol. 4052, Venice, Italy, Jul. 2006, pp. 1–12. [5] I. Csiszár, “𝐼-divergence geometry of probability distributions and minimization problems,” The Annals of Probability, vol. 3, no. 1, pp. 146–158, Feb. 1975. [6] S. M. Perlaza, G. Bisson, I. Esnaola, A. Jean-Marie, and S. Rini, “Empirical risk minimization with relative entropy regularization,” IEEE Transactions on Information Theory, vol. 70, no. 7, pp. 5122 – 5161, Jul. 2024. [7] F. Daunas, I. Esnaola, S. M. Perlaza, and H. V. Poor, “Equivalence of empirical risk minimization to regularization on the family of 𝑓 divergences,” in Proceedings of the IEEE International Symposium on Information Theory (ISIT), Athens, Greece, Jul. 2024, pp. 759–764. [8] ——, “Asymmetry of the relative entropy in the regularization of empirical risk minimization,” IEEE Transactions on Information Theory, vol. 71, no. 8, pp. 6198–6226, Aug. 2025. [9] N. Cesa-Bianchi and G. Lugosi, Prediction, Learning, and Games, 1st ed. New York, NY, USA: Cambridge University Press, 2006. [10] D. A. McAllester, “Some PAC-Bayesian theorems,” Machine Learning, vol. 37, no. 3, pp. 355–363, Dec. 1999. [11] M. Seeger, “PAC-Bayesian generalisation error bounds for Gaussian process classification,” Journal of Machine Learning Research, vol. 3, pp. 233–269, Oct. 2002.
[12] J. Langford and J. Shawe-Taylor, “PAC-Bayes and margins,” in Proceedings of the International Conference on Neural Information Processing Systems (NeurIPS), vol. 15, Vancouver, Canada, Dec. 2002, pp. 439–446. [13] O. Catoni, PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning, 1st ed. Beachwood, OH, USA: Institute of Mathematical Statistics Lecture Notes - Monograph Series, 2007, vol. 56. [14] P. Alquier, “User-friendly introduction to PAC-Bayes bounds,” Foundations and Trends in Machine Learning, vol. 17, no. 2, pp. 174–303, 2024. [15] M. Welling and Y. W. Teh, “Bayesian learning via stochastic gradient Langevin dynamics,” in Proceedings of the 28th International Conference on Machine Learning (ICML), Bellevue, Washington, USA, Jun. 2011, pp. 681–688. [16] S. Mandt, M. D. Hoffman, and D. M. Blei, “Stochastic gradient descent as approximate Bayesian inference,” Journal of Machine Learning Research, vol. 18, no. 1, pp. 4873 – 4907, Jan. 2017. [17] M. Raginsky, A. Rakhlin, and M. Telgarsky, “Non-convex learning via stochastic gradient Langevin dynamics: A nonasymptotic analysis,” in Proceedings of the Conference on Learning Theory (COLT), vol. 65, Amsterdam, Netherlands, Jul. 2017, pp. 1674–1703. [18] W. Azizian, F. Lutzeler, J. Malick, and P. Mertikopoulos, “What is the long-run distribution of stochastic gradient descent? A large deviations analysis,” in Proceedings of the International Conference on Machine Learning (ICML), Vienna, Austria, Jul. 2024, pp. 2168 – 2229. [19] Y. Bermudez, S. M. Perlaza, and I. Esnaola, “Machine unlearning for Gibbs supervised learning algorithms,” in Proceedings of the International Symposium on Information Theory (ISIT), Guangzhou, China, Jun. 2026. [20] S. M. Perlaza and G. Bisson, “Variations on the expectation due to changes in the probability measure,” Entropy, vol. 27, no. 8:865, pp. 1–20, Aug. 2025. [21] S. M. Perlaza, I. Esnaola, G. Bisson, and H. V. Poor, “On the validation of Gibbs algorithms: Training datasets, test datasets and their aggregation,” in Proceedings of the International Symposium on Information Theory (ISIT), Taipei, Taiwan, Jun. 2023, pp. 328–333. [22] Y. Bermudez, S. M. Perlaza, and I. Esnaola, “Decentralized machine learning with centralized performance guarantees via Gibbs algorithms,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9608, Jan. 2026. [23] Y. Bermudez, G. Bisson, I. Esnaola, and S. M. Perlaza, “Proofs for folklore theorems on the Radon-Nikodym derivative,” INRIA, Centre Inria d’Université Côte d’Azur, Sophia Antipolis, France, Tech. Rep. RR-9591, Jul. 2025.