Paper deep dive
A Fundamental Limit in Decentralized Decision-Making
Marco Carpentiero, Felice Scala, Vincenzo Matta, Ali H. Sayed
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 9/9/2026, 3:59:08 AM
Summary
This paper establishes a fundamental limit in decentralized decision-making, proving that unlike decentralized estimation, decentralized decision strategies exhibit an irreducible error probability loss compared to optimal centralized classifiers. The authors derive a closed-form analytical relation showing this loss depends on the interplay between network topology (node distances) and the statistical properties of the observations (moment generating functions of likelihood ratios).
Entities (7)
Relation Signals (5)
Decentralized Decision Making → exhibits → Irreducible Loss
confidence 96% · we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier.
Irreducible Loss → dependson → Network Topology
confidence 93% · This limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph
Irreducible Loss → dependson → Likelihood Ratios
confidence 93% · the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem.
Decentralized Estimation → contrastswith → Decentralized Decision Making
confidence 90% · While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making.
Network Topology → influences → Error Probability
confidence 89% · we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In decentralized decision-making, several agents connected according to a network graph aim at solving a classification problem by collecting streaming observations. Due to decentralization, they run an iterative algorithm where, at each iteration, they can only exchange information locally with their neighbors. While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making. Specifically, we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier. This result establishes a fundamental limit for the performance of any decentralized decision strategy. We obtain an analytical relation showing that this limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph, while the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem. By applying the derived closed-form relation to different network topologies and inference problems, we observe some interesting and perhaps unexpected behavior emerging. In particular, we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude; and we examine how performance is affected by the relative distance between informative and uninformative agents over the graph.
Tags
Links
- Source: https://arxiv.org/abs/2609.07479v1
- Canonical: https://arxiv.org/abs/2609.07479v1
Trouble viewing inline? Open PDF directly →
Full Text
114,303 characters extracted from source content.
Expand or collapse full text
A Fundamental Limit in Decentralized Decision-Making Thanks: M. Carpentiero, F. Scala, and V. Matta are with the Department of Information and Electrical Engineering and Applied Mathematics (DIEM), University of Salerno, I-84084 Fisciano (SA), Italy, and also with the National Inter-University Consortium for Telecommunications (CNIT), Italy (e-mails: mcarpentiero, fescala, vmatta@unisa.it). A. H. Sayed is with the Institute of Electrical and Micro Engineering, EPFL, CH-1015 Lausanne, Switzerland (e-mail: ali.sayed@epfl.ch). Marco Carpentiero, Felice Scala, Vincenzo Matta, and Ali H. Sayed Abstract In decentralized decision-making, several agents connected according to a network graph aim at solving a classification problem by collecting streaming observations. Due to decentralization, they run an iterative algorithm where, at each iteration, they can only exchange information locally with their neighbors. While decentralized estimation solutions have been shown to match the performance of optimal centralized systems, we show here that surprisingly this conclusion does not hold for decentralized decision-making. Specifically, we prove that the error probability for the best decentralized decision strategy exhibits an irreducible loss with respect to the optimal centralized classifier. This result establishes a fundamental limit for the performance of any decentralized decision strategy. We obtain an analytical relation showing that this limit is related to the interplay between decentralization and classification. The first aspect appears through the distances between the nodes in the graph, while the second aspect plays through the moment generating functions of the likelihood ratios that describe the decision problem. By applying the derived closed-form relation to different network topologies and inference problems, we observe some interesting and perhaps unexpected behavior emerging. In particular, we characterize the scaling law (with the network size) for the loss over popular network topologies, showing that the error probabilities might differ by orders of magnitude; and we examine how performance is affected by the relative distance between informative and uninformative agents over the graph. Index Terms: Social learning, error probability, large deviations, exact asymptotics. I Introduction and Related Work The problem of distributed decision-making refers to a collection of spatially dispersed agents that cooperate to accomplish a classification task. Each agent collects some data and interacts with the other agents according to some network structure. Many earlier works on distributed decision-making focused on architectures with a fusion center that can be reached by any agent [1, 3, 2, 4, 5]. Later on, the rising popularity of fully flat or decentralized architectures led to the following paradigm shift: OPENi)i) each agent acts as a fusion center, meaning that it is responsible for making its own decisions; and OPENii)i) the decisions of the individual agents leverage the information disseminated across the network by means of local consultation steps among neighbors. This fully decentralized paradigm is also referred to as decentralized decision-making or social learning [6, 7]. There exist several useful strategies to perform decentralized decision-making. All of them are characterized by the essential constraint of decentralization: at each round of the inferential algorithm (i.e., at each time epoch), each agent is allowed to receive information only from its neighbors, according to the graph topology that defines the network. Under this constraint, some schemes aggregate the beliefs (i.e., the posterior probabilities) of the neighbors by means of a weighted arithmetic average [8, 9]; while other schemes use a weighted geometric average of the posterior probabilities [10, 11, 12]. One fundamental property that has been shown for both arithmetic and geometric averaging is consistency: under mild conditions on the network connectivity and the identifiability of the classification problem, decentralized decision-making attains a vanishing error probability as time increases [6]. Since consistency is an asymptotic property, different consistent strategies may exhibit very different error probabilities for finite time horizons. Therefore, to properly compare the decentralized decision strategies, it is necessary to go beyond consistency and provide a quantitative evaluation for the error probabilities. The main works addressing this issue focused on a large deviation analysis [6, 13, 10, 11]. The takeaway from these works is that (under geometric averaging) the error probabilities of all agents vanish with time at the same exponential rate. Moreover, when the observations are statistically independent across the agents, this exponent is the one attained by the optimal centralized Bayesian system, i.e., by the maximum a posteriori probability (MAP) classifier [14]. The equivalence between the error exponents attained by the agents may contribute to create a “folklore” in decentralized decision-making, namely, that for sufficiently large amounts of data all agents share the same decision performance. Likewise, the equivalence with the optimal centralized exponent may lead to the conviction that decentralized decision-making is asymptotically optimal. These conclusions are also encouraged by similar findings obtained for decentralized estimation/regression problems, where it has been shown that all agents asymptotically attain the same mean-square-error performance [15, 16]. Unfortunately, in this work we show that the asymptotic optimality of decentralized decision-making does not hold, as we now explain. To start with, observe that large deviations only deal with the error exponent. Hence, we may have two error probabilities, say p1,t=e−tp_1,t=e^-t and p2,t=100e−tp_2,t=100\,e^-t (where t represents the time index), which, albeit sharing the same exponent, differ by two orders of magnitude [17, 18, 6]. As a result, the equivalence itself in terms of error exponents is not enough to claim the asymptotic optimality of decentralized decision-making. Motivated by this issue, recent works examined the higher-order terms (i.e., the terms beyond the error exponent) that affect the error probability in traditional social learning [19, 20, 21]. In [19], for a binary detection problem with bounded likelihood ratios and for a binary Gaussian shift-in mean problem, the authors compute closed-form upper bounds on the asymptotic ratio between the individual agents’ error probabilities and the optimal centralized probability. That is, they show that the loss due to decentralization cannot be larger than a certain amount. For the Gaussian case, the exact asymptotic ratio between the decentralized and the centralized error probabilities is instead evaluated in [21], revealing the analytical form of the loss experienced by traditional social learning with respect to the optimal centralized classifier. In particular, this loss is persistent in the long run, i.e., it cannot be neglected asymptotically. However, it is not clear whether the aforementioned gap is due to the specific decision strategy or is an intrinsic, irreducible gap due to decentralization. In this work, we answer this question. Specifically, in Sec. I we establish a fundamental limit on the performance of any decentralized decision strategy. We ascertain that there exists an irreducible gap between the performance of any decentralized strategy and the optimal centralized strategy. We characterize this loss in terms of a closed-form analytical expression that highlights the interplay between the network topology (through the distances between the agents over the network graph) and the classification problem (through the moment generating functions of the log likelihood ratios). In Sec. IV, we show that traditional social learning does not attain the fundamental limit. Then, in Sec. V-A we examine how the performance scales with the network size under typical network topologies, whereas in Sec. V-B we show how the interplay between the topology and the agents’ informativeness affects the performance loss. I Basic Quantities and Notation In this section we collect the main elements describing the inference problem and the network structure. I-A Inference Problem We consider a decision-making process where a network of agents is interested in learning the state of a given phenomenon of interest, which is represented by a hypothesis θ belonging to a discrete finite set Θ . The hypotheses are distributed according to a prior probability mass function (pmf) denoted by π. To avoid trivial cases, we assume that all entries of π are nonzero. The ensemble of network agents is represented by the set ≜1,2,…,KK \1,2,…,K\. At each time instant t∈ℕt , each agent k∈k gathers an observation k,t∈ℝnk x_k,t ^n_k (we use bold notation for random quantities), where the space dimensionalities nkn_k can be heterogeneous across the agents. The data are assumed independent over time and space (i.e., across the agents). The generative mechanism for the data is as follows. Given the true hypothesis (denoted by θ0 _0), the observations for agent k are identically distributed over time, according to some likelihood model ℓk(xk|θ0) _k(x_k| _0) that, as a function of xkx_k, is a probability density function (pdf) on ℝnkR^n_k. For every fixed agent k∈k , the pdfs ℓk(xk|θ) _k(x_k|θ) have the same support for all θ∈Θθ∈ . We define the log likelihood ratio (LLR) of agent k at time t as k,t(θ0,θ)≜lnℓk(k,t|θ0)ℓk(k,t|θ),θ≠θ0. λ_k,t( _0,θ) _k( x_k,t| _0) _k( x_k,t|θ), θ≠ _0. (1) Assumption 1 (Likelihoods). For each pair of hypotheses (θ0,θ)( _0,θ) with θ≠θ0θ≠ _0, and each agent k∈k , we consider the following two cases: i)i) if the likelihood models ℓk(k|θ0) _k( x_k| _0) and ℓk(k|θ) _k( x_k|θ) are equal, then agent k is unable to distinguish these hypotheses and the log likelihood ratio k,t(θ0,θ) λ_k,t( _0,θ) is equal to zero (with probability 11); ii)i) otherwise, the log likelihood ratio k,t(θ0,θ) λ_k,t( _0,θ) is a random variable distributed, conditionally on θ0 _0, according to some pdf with positive mean θ0k,t(θ0,θ)≜Dk(θ0||θ)>0.E_ _0\, λ_k,t( _0,θ) D_k( _0||θ)>0. (2) Here, the subscript in the expectation operator θ0E_ _0 denotes that the expectation is computed under the true hypothesis θ0 _0, whereas Dk(θ0||θ)D_k( _0||θ) denotes the Kullback-Leibler (KL) divergence between ℓk(k|θ0) _k( x_k| _0) and ℓk(k|θ) _k( x_k|θ) [22]. □ We rule out the extreme situation where the decision problem cannot be solved by the network of agents. In other words, the decision problem is identifiable, which corresponds to saying that, for each pair of hypotheses, the KL divergence between the joint likelihoods across the agents is positive. In view of the additivity of the KL divergence over independent observations, the identifiability condition translates into the following assumption: Assumption 2 (Identifiability). The decision problem is globally identifiable by the network of agents, which means that, for all θ0,θ∈Θ _0,θ∈ , with θ≠θ0θ≠ _0, ∑k=1KDk(θ0||θ)=∑j∈(θ0,θ)Dj(θ0||θ)>0, _k=1^KD_k( _0||θ)= _j ( _0,θ)D_j( _0||θ)>0, (3) where (θ0,θ)≠∅J( _0,θ)≠ is the set of agents for which the pair (θ0,θ)( _0,θ) is identifiable. □ In our analysis, a critical role will be played by the log moment generating function (LMGF) of the log likelihood ratios k,t(θ0,θ) λ_k,t( _0,θ), which we denote by Λk(s,θ0,θ)≜lnθ0exp(sk,t(θ0,θ)), _k(s; _0,θ) _ _0 (s\, λ_k,t( _0,θ) ), (4) where we see that the LMGF does not depend on t due to the identical distribution over time. We assume the following regularity condition. Assumption 3 (LMGF of the log likelihood ratios). For all k∈k , and all θ0,θ∈Θ _0,θ∈ , with θ≠θ0θ≠ _0, we have Λk(s,θ0,θ)<∞∀s∈ℝ. _k(s; _0,θ)<∞ ∀ s . (5) □ We also introduce the global LMGF corresponding to the sum variable t(θ0,θ)≜∑k=1Kk,t(θ0,θ)=∑j∈(θ0,θ)j,t(θ0,θ), λ_t( _0,θ) _k=1^K λ_k,t( _0,θ)= _j ( _0,θ) λ_j,t( _0,θ), (6) namely, Λ(s,θ0,θ) (s; _0,θ) ≜lnθ0exp(st(θ0,θ)) _ _0 (s\, λ_t( _0,θ) ) =∑k=1KΛk(s,θ0,θ)=∑j∈(θ0,θ)Λj(s,θ0,θ), = _k=1^K _k(s; _0,θ)= _j ( _0,θ) _j(s; _0,θ), (7) where the second-to-last equality follows from the additivity of the LMGF for independent random variables, whereas the last equality holds because j,t(θ0,θ)=0 λ_j,t( _0,θ)=0 (almost surely) when j∉(θ0,θ)j ( _0,θ), i.e., when θ0 _0 and θ are not identifiable for agent j. I-B Network Model and Decentralization We assume that the agents can communicate according to a certain network topology, which is described by a graph, whose vertices represent the agents, and whose directed edges represent a communication link from one agent to another. If an edge exists, originating from agent j and pointing toward agent k, then we say that k can receive information from j. Moreover, each agent can always use its own information, which means there is a self-loop connecting each agent to itself. We define the directed neighborhood kN_k for agent k as the set of agents from which k can receive information through a directed link (i.e., in a single hop), including k itself. Definition 1 (Network distances). For each pair (j,k)(j,k), we denote by djkd_jk the (directed) distance that must be traversed, over the graph, to reach node k starting from node j. More precisely, we say that djk=md_jk=m when the shortest path from j to k is equal to m+1m+1 hops.11 1 Typically, in the graph literature, when the number of hops is equal to m+1m+1, the distance is defined as m+1m+1. Instead, we define the distance by subtracting 11 since it is more convenient, in our analysis, to consider that neighboring agents lie at distance zero. This means that djk=0d_jk=0 when j∈kj _k. □ Assumption 4 (Connectivity). We assume djk<∞d_jk<∞ for all pairs (j,k)(j,k), i.e., any agent can be reached through a path that originates at any other agent. □ Fig. 1: Pictorial illustration of the flow of information across a decentralized system. As specified in the legend, the cylindrical container represents a generic function of the observations within it. The next definition summarizes the essential constraints that a decentralized inference system must obey. Definition 2 (Decentralized inference system). By a decentralized system, we mean a network of agents that learn through successive iteration steps t∈ℕt . At each iteration, all agents collect a fresh observation. Then, they compute and deliver over the network a function (e.g., a belief or a likelihood ratio) that depends on the fresh observation and on the information received from the neighbors until time t. Then, this decentralized process obeys the following constraints: • Agent k can receive information only from its (directed) neighbors j∈kj _k, namely, from the agents for which djk=0d_jk=0. • At time t, agent k can compute a decision statistic that can be formally written as fk,t(j,τ=1t−djkj=1K),f_k,t ( \ \ x_j,τ \_τ=1^t-d_jk \_j=1^K ), (8) for some function fk,tf_k,t (which can also be a vector-valued function, such as a probability vector). Here, j,τ=1t−djkj=1K\\ x_j,τ\_τ=1^t-d_jk\_j=1^K represents the largest ensemble of data that can reach agent k at time t. □ Observe that, regardless of the particular learning algorithm, after t steps the information received by agent k cannot be based on observations that are too “recent“ and originate from agents that are too “distant“ from k. This concept can be more conveniently illustrated by means of Fig. 1. Consider the three agents, i, j, and k, connected as shown in the upper-left panel in the figure. At time t=1t=1, agent k collects a new local observation k,1 x_k,1 and receives information from its neighbor j. This information is, in general, some function of the data j,1 x_j,1. Similarly, agent j observes j,1 x_j,1 and receives some function of the data i,1 x_i,1. The agents can then combine the information received from their neighbors. For example, agent k can compute a certain function of j,1 x_j,1 and k,1 x_k,1. Likewise, agent j will compute a certain function of i,1 x_i,1 and j,1 x_j,1. Next, at t=2t=2, agent k (along with the fresh observation k,2 x_k,2), will receive some function of i,1 x_i,1 and j,1 x_j,1 from agent j. After the combination phase, agent k will compute a certain decision statistic from the received (functions of) data. Formally, this decision statistic can be represented as some global function of j,2,k,2,i,1,j,1, x_j,2, x_k,2, x_i,1, x_j,1, and k,1 x_k,1. Note that, at t=2t=2, agent k received no information related to the current observation i,2 x_i,2, since it takes 22 hops to reach k from i. In contrast, agent k has already received information related to the previous-lag observation i,1 x_i,1, because at t=1t=1 (first hop) agent j received information from agent i, and at t=2t=2 agent j forwarded to agent k a function that also incorporates information related to i,1 x_i,1. I Decentralizated Performance We are interested in establishing the best attainable performance (i.e., the lowest error probability) within the class of decentralized strategies identified by Definition 2. To this end, we observe preliminarily that any function (i.e., transformation) of the raw data cannot bring more information than the raw data themselves. Therefore, it is understood that the maximum possible amount of information available to agent k at time t is given by the ensemble of raw data j,τ=1t−djkj=1K. \ \ x_j,τ \_τ=1^t-d_jk \_j=1^K. (9) This is the largest ensemble of data that can reach agent k at time t, compatibly with the decentralization constraints in Definition 2. Note that this is not the total amount of data available over the graph until the time instant t. This is because some agents may be further away from k. Then, the best decision strategy (i.e., the strategy minimizing the error probability) for agent k is the maximum a posteriori probability (MAP) rule applied to the ensemble of data (9). Any decentralized strategy belonging to the family described by Definition 2 will feature an error probability that cannot be lower than the error probability achieved by the MAP classifier operating on the data set (9). We will now examine the MAP classifier. In order to implement it, we need to construct the posterior belief of θ given the data (9), which is given by k,t(θ)∝π(θ)∏j=1K∏τ=1t−djkℓj(j,τ|θ), μ_k,t(θ) π(θ)\, _j=1^K _τ=1^t-d_jk _j( x_j,τ|θ), (10) where, as usual in Bayesian theory, the proportionality sign ∝ hides the normalization factor represented by the marginal pdf of the data. According to (10), the log belief ratio of agent k at time t is k,t(θ0,θ) β_k,t( _0,θ) ≜lnk,t(θ0)k,t(θ) μ_k,t( _0) μ_k,t(θ) =lnπ(θ0)π(θ)+∑j=1K∑τ=1t−djkj,τ(θ0,θ). = π( _0)π(θ)+ _j=1^K _τ=1^t-d_jk λ_j,τ( _0,θ). (11) In order to investigate the loss arising from the decentralization, we need to consider as a benchmark the centralized MAP classifier that is based on all data. The log belief ratio for this optimal system is obtained by setting djk=0d_jk=0 for all j and k in (11), and will be denoted by tcen(θ0,θ) β^cen_t( _0,θ). I-A Definition of some useful quantities Preliminarily, it is convenient to list some definitions that characterize the main quantities used in the forthcoming theorems. Exact asymptotics. For two sequences ata_t and btb_t, the notation at≃bta_t b_t signifies that limt→∞atbt=1. _t→∞ a_tb_t=1. (12) Following a standard terminology used in statistics [17], specifically in the framework of exact asymptotics, when (12) holds, we say that btb_t is an exact asymptotic approximation for ata_t (or vice versa).22 2 The qualification “exact” is used in the literature to indicate that other forms of asymptotic approximations, such as large deviations, do not guarantee the asymptotic equivalence in (12), but only equivalence at the leading exponential order; see also the discussion in the introduction. Error probabilities. For the optimal decentralized system, we define the binary or pairwise error probability for agent k at time t, relative to choosing some wrong hypothesis θ≠θ0θ≠ _0 (the subscript to the probability operator indicates that the probability is evaluated under the true hypothesis θ0 _0): pk,t(θ0,θ)≜ℙθ0[k,t(θ0,θ)≤0]p_k,t( _0,θ) _ _0[ β_k,t( _0,θ)≤ 0] (13) and the total error probability pk,t≜∑θ0∈Θπ(θ0)ℙθ0[minθ≠θ0k,t(θ0,θ)≤0].p_k,t _ _0∈ π( _0)\,P_ _0 [ _θ≠ _0 β_k,t( _0,θ)≤ 0 ]. (14) The corresponding quantities for the optimal centralized system will be denoted by ptcen(θ0,θ)p_t^cen( _0,θ) and ptcenp_t^cen, respectively. Minimizer of the network LMGF. Consider an agent j∈(θ0,θ)j ( _0,θ), i.e., such that θ0j,t(θ0,θ)>0E_ _0\, λ_j,t( _0,θ)>0. By assumption, ℓj(xj|θ0) _j(x_j| _0) and ℓj(xj|θ) _j(x_j|θ) have the same support, and since they both integrate to 11 (as they are pdfs), the log likelihood ratio j,t(θ0,θ) λ_j,t( _0,θ) takes on negative and positive values with nonzero probability. From the same arguments used in the discussion following Assumption 5 in Appendix A, we conclude that: the LMGF Λ(s,θ0,θ) (s; _0,θ) is strictly convex; the equation (we use the prime notation to denote differentiation with respect to the first argument) Λ′(s,θ0,θ)=0 (s; _0,θ)=0 (15) has a unique solution s(θ0,θ)<0s( _0,θ)<0; and Λ(s(θ0,θ),θ0,θ)<0. (s( _0,θ); _0,θ )<0. (16) Furthermore, it is easily verified that Λ(−1,θ0,θ)=Λ(0,θ0,θ)=0 (-1; _0,θ)= (0, _0,θ)=0, which implies that s(θ0,θ)∈(−1,0)s( _0,θ)∈(-1,0). Error exponents. The quantity ℰ(θ0,θ)≜−Λ(s(θ0,θ),θ0,θ)>0E( _0,θ) - (s( _0,θ); _0,θ )>0 (17) will be seen in Theorem 1 to represent the error exponent governing the exponential rate of convergence to zero of the pairwise error probabilities ptcen(θ0,θ)p_t^cen( _0,θ) and pk,t(θ0,θ)p_k,t( _0,θ) for each agent k∈k . We also introduce the worst-case (i.e., the smallest) error exponent across any pair of hypotheses, ℰ⋆≜min(θ0,θ)∈Θ2θ≠θ0ℰ(θ0,θ).E _ subarrayc( _0,θ)∈ ^2\\ θ≠ _0 subarrayE( _0,θ). (18) Likewise, the set ⋆≜argmin(θ0,θ)∈Θ2θ≠θ0ℰ(θ0,θ)S _ subarrayc( _0,θ)∈ ^2\\ θ≠ _0 subarrayE( _0,θ) (19) collects all the (ordered) pairs of hypotheses sharing the smallest error exponent. Asymptotic variance correction. The quantity σ2(θ0,θ)≜s2(θ0,θ)Λ′(s(θ0,θ),θ0,θ)σ^2( _0,θ) s^2( _0,θ)\, (s( _0,θ); _0,θ ) (20) will be seen in Theorem 1 to represent an asymptotic variance correction used to build the approximation for the pairwise error probabilities. Prior correction. The quantity ηπ(θ0,θ)≜(π(θ)π(θ0))|s(θ0,θ)|. _π( _0,θ) ( π(θ)π( _0) )^|s( _0,θ)|. (21) will be seen in Theorem 1 to represent a correction, accounting for uneven prior assignments, used to build the approximation for the pairwise error probabilities. I-B Main results Theorem 1 (Exact asymptotics for the pairwise error probabilities). Let Assumptions 1– 4 be satisfied. For each pair (θ0,θ)( _0,θ) with θ≠θ0θ≠ _0, let the log likelihood ratios k,t(θ0,θ) λ_k,t( _0,θ) fulfill, for all k∈k and t∈ℕt , Assumption 5 from Appendix A. Then, the function tcen(θ0,θ)≜ηπ(θ0,θ)2πσ2(θ0,θ)e−tℰ(θ0,θ)t P_t^cen( _0,θ) _π( _0,θ) 2π\,σ^2( _0,θ)\, e^-t\,E( _0,θ) t (22) is an exact asymptotic approximation for the pairwise error probability of the centralized system, namely, we have ptcen(θ0,θ)≃tcen(θ0,θ).p_t^cen( _0,θ) P_t^cen( _0,θ). (23) The pairwise error probability of each agent k∈k in the optimal decentralized system is instead approximated as pk,t(θ0,θ)≃k,t(θ0,θ),p_k,t( _0,θ) P_k,t( _0,θ), (24) where k,t(θ0,θ)≜tcen(θ0,θ)ℒk(θ0,θ), P_k,t( _0,θ) P_t^cen( _0,θ)\, L_k( _0,θ), (25) and the loss term ℒk(θ0,θ) L_k( _0,θ) is given by33 3 Given two hypotheses θ1 _1 and θ2 _2, from (1) and (4) we see that Λj(s,θ1,θ2)=Λj(−1−s,θ2,θ1). _j(s; _1, _2)= _j(-1-s; _2, _1). (26) In particular, Eq. (26) implies that s(θ2,θ1)=−1−s(θ1,θ2)s( _2, _1)=-1-s( _1, _2), which in turn yields Λj(s(θ1,θ2),θ1,θ2)=Λj(s(θ2,θ1),θ2,θ1) _j(s( _1, _2); _1, _2)= _j(s( _2, _1); _2, _1). As a result, the loss defined by (27) is symmetric with respect to its arguments, namely, ℒk(θ1,θ2)=ℒk(θ2,θ1) L_k( _1, _2)= L_k( _2, _1). ℒk(θ0,θ)≜exp(−∑j=1KdjkΛj(s(θ0,θ);θ0,θ))≥1. L_k( _0,θ) (- _j=1^Kd_jk\, _j (s( _0,θ); _0,θ ) )≥ 1. (27) Proof: The result follows from Theorem 3 in Appendix A, with the following associations: ↦(θ0,θ), ( _0,θ), j,τ↦j,τ(θ0,θ), ξ_j,τ λ_j,τ( _0,θ), (28) γ↦lnπ(θ0)π(θ), γ π( _0)π(θ), dj↦djk, d_j d_jk, (29) Λj(s)↦Λj(s,θ0,θ), _j(s) _j(s; _0,θ), Λ(s)↦Λ(s,θ0,θ). (s) (s; _0,θ). (30) It is straightforward to verify that, under Assumptions 1– 4, the log likelihood ratios j,τ(θ0,θ) λ_j,τ( _0,θ), for j∈(θ0,θ)j ( _0,θ), satisfy the conditions required in Assumption 5 for the random variables j,τ ξ_j,τ. Then, Eq. (24) follows by performing the substitutions in (28)–(30). The companion result for the centralized system in (23) is simply obtained by setting djk=0d_jk=0 for all j and k. Moreover, the inequality in (27) holds because (recall that (θ0,θ)≠∅J( _0,θ)≠ in view of Assumption 2) Λj(s(θ0,θ),θ0,θ)<0∀j∈(θ0,θ). _j (s( _0,θ); _0,θ )<0 ∀ j ( _0,θ). (31) This relation can be explained by observing that s(θ0,θ)∈(−1,0)s( _0,θ)∈(-1,0) and Λj(s,θ0,θ)<0 _j(s; _0,θ)<0 for all s∈(−1,0)s∈(-1,0), which holds since Λj(−1,θ0,θ)=Λj(0,θ0,θ)=0 _j(-1; _0,θ)= _j(0, _0,θ)=0 and, for j∈(θ0,θ)j ( _0,θ), Λj(s,θ0,θ) _j(s; _0,θ) is a strictly convex function; see the discussion following Assumption 5 in Appendix A. ∎ Theorem 2 (Exact asymptotics for the total error probabilities). Under the same assumptions used in Theorem 1, we construct the following approximations for the total error probabilities in terms of the pairwise error probability approximations from (22) and (25): tcen P_t^cen ≜∑θ0∈Θπ(θ0)∑θ≠θ0tcen(θ0,θ), _ _0∈ π( _0) _θ≠ _0 P_t^cen( _0,θ), (32) k,t P_k,t ≜∑θ0∈Θπ(θ0)∑θ≠θ0k,t(θ0,θ). _ _0∈ π( _0) _θ≠ _0 P_k,t( _0,θ). (33) Then, it holds that ptcen≃tcen,pk,t≃k,t.p_t^cen P_t^cen, p_k,t P_k,t. (34) Proof: We prove the claim for the decentralized system, from which the proof for the centralized system will follow immediately. To start with, observe that the approximation k,t P_k,t in (33) is a sum of the approximations k,t(θ0,θ) P_k,t( _0,θ) defined in (25), which decay exponentially with exponents ℰ(θ0,θ)E( _0,θ). Accordingly, only the terms featuring the smallest error exponent ℰ⋆E in (18) will dominate asymptotically. Thus, we are interested in evaluating the limit of the following ratio: k,te−tℰ⋆/2πt=∑θ0∈Θπ(θ0)∑θ≠θ0k,t(θ0,θ)e−tℰ⋆/2πt P_k,te^-t\,E / 2π\,t= _ _0∈ π( _0) _θ≠ _0 P_k,t( _0,θ)e^-t\,E / 2π\,t =∑θ0∈Θπ(θ0)∑θ≠θ0tcen(θ0,θ)ℒk(θ0,θ)e−tℰ⋆/2πt = _ _0∈ π( _0) _θ≠ _0 P_t^cen( _0,θ)\, L_k( _0,θ)e^-t\,E / 2π\,t =∑θ0∈Θπ(θ0)∑θ≠θ0ηπ(θ0,θ)σ(θ0,θ)e−t(ℰ(θ0,θ)−ℰ⋆)ℒk(θ0,θ), = _ _0∈ π( _0) _θ≠ _0 _π( _0,θ)σ( _0,θ)\,e^-t (E( _0,θ)-E ) L_k( _0,θ), (35) where, in the three equalities, we use (33), (25), and (22), respectively. From the definition of the smallest exponent ℰ⋆E in (18) and the set ⋆S in (19), we see that limt→∞k,te−tℰ⋆2πt=∑(θ0,θ)∈⋆π(θ0)ηπ(θ0,θ)σ(θ0,θ)ℒk(θ0,θ), _t→∞ P_k,t e^-t\,E 2π\,t= _( _0,θ) π( _0) _π( _0,θ)σ( _0,θ)\, L_k( _0,θ), (36) We conclude from (36) that, to prove that pk,t≃k,tp_k,t P_k,t, it suffices to show that limt→∞pk,te−tℰ⋆2πt=∑(θ0,θ)∈⋆π(θ0)ηπ(θ0,θ)σ(θ0,θ)ℒk(θ0,θ). _t→∞ p_k,t e^-t\,E 2π\,t= _( _0,θ) π( _0) _π( _0,θ)σ( _0,θ)\, L_k( _0,θ). (37) We proceed then to prove (37). By applying the union bound, the total error probability is upper bounded by the sum of the pairwise error probabilities as follows: pk,t≤∑θ0∈Θπ(θ0)∑θ≠θ0pk,t(θ0,θ),p_k,t≤ _ _0∈ π( _0) _θ≠ _0p_k,t( _0,θ), (38) which, in view of the subadditivity of the limit superior, implies that lim supt→∞pk,te−tℰ⋆2πt≤∑θ0∈Θπ(θ0)∑θ≠θ0lim supt→∞pk,t(θ0,θ)e−tℰ⋆2πt. _t→∞ p_k,t e^-t\,E 2π\,t≤ _ _0∈ π( _0) _θ≠ _0 _t→∞ p_k,t( _0,θ) e^-t\,E 2π\,t. (39) Now, we know from Theorem 1 that the pairwise error probabilities pk,t(θ0,θ)p_k,t( _0,θ) are asymptotically equivalent to the approximations k,t(θ0,θ) P_k,t( _0,θ) defined by (25). This implies that in the limit (39), only the terms with the smallest exponent survive, namely, lim supt→∞pk,te−tℰ⋆2πt≤∑(θ0,θ)∈⋆π(θ0)ηπ(θ0,θ)σ(θ0,θ)ℒk(θ0,θ). _t→∞ p_k,t e^-t\,E 2π\,t≤ _( _0,θ) \!\!\!π( _0) _π( _0,θ)σ( _0,θ)\, L_k( _0,θ). (40) Therefore, the claim in (37) will be proved if we show that the limit inferior fulfills (40) with the reverse inequality. To this end, observe that we can write ℙθ0[minθ≠θ0k,t(θ0,θ)≤0] _ _0 [ _θ≠ _0 β_k,t( _0,θ)≤ 0 ] =ℙθ0[⋃θ≠θ0k,t(θ0,θ)≤0]≤ℙθ0[k,t(θ0,θ)≤0] =P_ _0 [ _θ≠ _0 \ β_k,t( _0,θ)≤ 0 \ ] _ _0 [ β_k,t( _0,θ)≤ 0 ] −12ℙθ0[k,t(θ0,θ)≤0,k,t(θ0,θ′)≤0]⏟≜bt(θ0,θ,θ′), - 12\, P_ _0 [ β_k,t( _0,θ)≤ 0,\, β_k,t( _0,θ )≤ 0 ]_ b_t( _0,θ,θ ), (41) where the last step follows from the second-order Bonferroni’s inequality [30]. Using (41) in (14) we obtain pk,t≥∑θ0∈Θπ(θ0)∑θ≠θ0pk,t(θ0,θ)−12∑θ′≠θ0θ′≠θbt(θ0,θ,θ′).p_k,t≥ _ _0∈ π( _0)\, _θ≠ _0 \p_k,t( _0,θ)- 12 _ subarraycθ ≠ _0\\ θ ≠ _ 0 subarrayb_t( _0,θ,θ ) \. (42) We focus on the following limit inferior: lim inft→∞pk,te−tℰ⋆/2πt≥∑(θ0,θ)∈⋆π(θ0)ηπ(θ0,θ)σ(θ0,θ)ℒk(θ0,θ) _t→∞ p_k,te^-t\,E / 2π\,t≥ _( _0,θ) \!\!\!π( _0) _π( _0,θ)σ( _0,θ)\, L_k( _0,θ) −12∑θ0∈Θθ:(θ0,θ)∈⋆θ′:(θ0,θ′)∈⋆lim supt→∞π(θ0)bt(θ0,θ,θ′)e−tℰ⋆/2πt, - 12 _ subarrayc _0∈ \\ θ :\,( _0,θ ) \\ θ :\,( _0,θ ) subarray _t→∞ π( _0)\,b_t( _0,θ,θ )e^-t\,E / 2π\,t, (43) where the last summation has been restricted to the pairs of hypotheses featuring the smallest exponent ℰ⋆E because the probability of the intersection of two events is dominated by the probabilities of the individual events, and, hence, the joint probabilities bt(θ0,θ,θ′)b_t( _0,θ,θ ) cannot exhibit an exponent smaller than ℰ(θ0,θ)E( _0,θ) and ℰ(θ0,θ′)E( _0,θ ). By applying Theorem 4 from Appendix B, we conclude that the limit superior appearing in (43) is zero, and (37) is proved. ∎ Corollary 1 (Fundamental limit on decentralized decision-making). Under the same assumptions used in Theorem 1, any decentralized strategy fulfilling the constraints in Definition 2 experiences at least the following performance loss with respect to the optimal centralized system: ℒk≜limt→∞pk,tptcen=∑(θ0,θ)∈⋆ω(θ0,θ)ℒk(θ0,θ), L_k _t→∞ p_k,tp_t^cen= _( _0,θ) ω( _0,θ)\, L_k( _0,θ), (44) where ω(θ0,θ)≜π(θ0)ηπ(θ0,θ)/σ(θ0,θ)∑(θ0′,θ′)∈⋆π(θ0′)ηπ(θ0′,θ′)/σ(θ0′,θ′).ω( _0,θ) π( _0)\, _π( _0,θ)/σ( _0,θ)Σ _( _0 ,θ ) π( _0 )\, _π( _0 ,θ )/σ( _0 ,θ ). (45) Proof: Applying (37) to the centralized case (i.e., setting ℒk(θ0,θ)=1 L_k( _0,θ)=1), we have limt→∞ptcene−tℰ⋆2πt=∑(θ0,θ)∈⋆π(θ0)ηπ(θ0,θ)σ(θ0,θ). _t→∞ p_t^cen e^-t\,E 2π\,t= _( _0,θ) π( _0) _π( _0,θ)σ( _0,θ). (46) Combining (37) and (46), we obtain the claim of the theorem. ∎Corollary 1 establishes that there exists an irreducible gap ℒk L_k between the ideal decentralized system and the optimal centralized system. Since the performance of the ideal system represents a fundamental limit that any decentralized strategy cannot surpass, this result also implies that any decentralized strategy cannot reach the performance of the centralized strategy. The loss in terms of error probability can also be translated into a learning delay, as established by the following corollary. Corollary 2 (Learning delay). In the decentralized ideal system, the learning curve pertaining to agent k (i.e., the error probability pk,tp_k,t as a function of time) experiences an irreducible delay Tk=lnℒkℰ⋆T_k= L_kE (47) with respect to the learning curve ptcenp_t^cen of the optimal centralized system. Formally, this means that limt→∞pk,t+Tkptcen=1. _t→∞ p_k,t+T_kp_t^cen=1. (48) Proof: From (37), we can write limt→∞pk,t+Tke−(t+Tk)ℰ⋆2π(t+Tk)=∑(θ0,θ)∈⋆π(θ0)ηπ(θ0,θ)σ(θ0,θ)ℒk(θ0,θ). _t→∞ p_k,t+T_k e^-(t+T_k)\,E 2π\,(t+T_k)= _( _0,θ) π( _0) _π( _0,θ)σ( _0,θ)\, L_k( _0,θ). (49) Combining (46) and (49), we obtain limt→∞pk,t+Tkptcen _t→∞ p_k,t+T_kp_t^cen =e−Tkℰ⋆π(θ0)ηπ(θ0,θ)/σ(θ0,θ)∑(θ0′,θ′)∈⋆π(θ0′)ηπ(θ0′,θ′)/σ(θ0′,θ′) =e^-T_k\,E \, π( _0)\, _π( _0,θ)/σ( _0,θ)Σ _( _0 ,θ ) π( _0 )\, _π( _0 ,θ )/σ( _0 ,θ ) =e−Tkℰ⋆ℒk, =e^-T_k\,E \, L_k, (50) where in the last step we applied the definition of ℒk L_k from (44). The proof is completed by substituting (47) into (50). ∎Corollary 2 provides further insight into the learning behavior of decentralized decision-making systems. The takeaway is that learning is irremediably slowed down due to decentralization. To avoid misunderstanding, we remark that this does not imply in any manner that the decentralized system can attain the centralized performance if one accepts to wait for TkT_k more time instants. The opposite conclusion is true! In fact, in these additional rounds, the centralized system also collects additional information and learns from it. As a result, the decentralized system will experience a persistent delay and will never attain the performance of the centralized system. Examining (44), we see that the general expression for the learning delay TkT_k in (47) depends in a nontrivial manner on the losses ℒk(θ0,θ) L_k( _0,θ) associated with the individual pairs (θ0,θ)∈⋆( _0,θ) and the relative weights ω(θ0,θ)ω( _0,θ) defined by (45). The expression simplifies when the losses ℒk(θ0,θ) L_k( _0,θ) pertaining to the pairs (θ0,θ)( _0,θ) within the set ⋆S assume the same value (which includes the situation where ⋆S contains a single element). Under the equal-loss condition, using (27) in (47), we obtain Tk=lnℒk(θ0,θ)ℰ(θ0,θ)=∑j=1KdjkΛj(s(θ0,θ),θ0,θ)Λ(s(θ0,θ),θ0,θ),T_k= L_k( _0,θ)E( _0,θ)= _j=1^Kd_jk\, _j (s( _0,θ); _0,θ ) (s( _0,θ); _0,θ ), (51) where in the last step we used the definition of ℰ(θ0,θ)E( _0,θ) from (17). By further exploiting the definition of Λ(s(θ0,θ),θ0,θ) (s( _0,θ); _0,θ ) from (7), we see that the weights qj≜Λj(s(θ0,θ),θ0,θ)Λ(s(θ0,θ),θ0,θ)q_j _j (s( _0,θ); _0,θ ) (s( _0,θ); _0,θ ) (52) are convex, i.e., they are nonnegative and add up to 11. Accordingly, Eq. (51) can be recast in the form Tk=∑j=1Kqjdjk.T_k= _j=1^Kq_j\,d_jk. (53) This shows that, under the equal-loss condition, the learning delay experienced by agent k is a convex combination of the distances djkd_jk over the graph. The weight qjq_j in (52) accounts for the relative informativeness of agent j. Accordingly, we see from (53) that each distance djkd_jk contributes to the learning delay TkT_k depending on the “inferential relevance” of agent j. I-C Achievability In the previous section, we established the best attainable performance for any agent k at any time t. To evaluate the performance, we computed the error probability corresponding to the maximum amount of data (9) that agent k could access at time t, according to the decentralization constraints as per Definition 2. A communication protocol that allows each agent k to access the data set (9) is as follows: at each time t, each agent forwards to its neighbors its own fresh observation and the observations received from its neighbors at time t−1t-1. In these transmission steps, the agents attach to the data a label denoting which agent the relayed observation belongs to. The described scheme has the following drawbacks. First, to implement the MAP rule, each agent needs to know the likelihood models of the other agents, an assumption usually considered too strong in many decentralized settings; second, transmitting the raw data usually violates several constraints arising in practical applications, such as privacy or computational constraints (since the data dimensionality could be large). However, it is possible to overcome these limitations by means of the following strategy: at each iteration t, each agent forwards to its neighbors the likelihoods computed for the new observation and the likelihoods received from its neighbors at time t−1t-1. We see that, in this manner, an agent need not know the likelihood models of the other agents and no raw data are transmitted (note also that the likelihood is always a scalar, so the data dimensionality is not an issue).44 4 Technically, it is not necessary that the agents send the likelihoods for all θ∈Θθ∈ . It is possible to show that [6, Thm. 6.1] any belief function can be constructed starting from the likelihood ratios computed with respect to some arbitrarily chosen pivot hypothesis, which requires then to share |Θ|−1| |-1 likelihood ratios. We have thus shown that the limit performance evaluated in Sec. I can be attained by a decentralized protocol where each agent possesses only local private likelihood models and where no raw data are transmitted. IV Traditional Social Learning In Sec. I-C, we identified two strategies that are able to attain the best possible decentralized performance. Observe that these strategies assume that each agent keeps trace of the data or likelihoods received from all the other agents. In the theory of social learning, a different approach is usually proposed, which prescribes that each agent builds its belief k,t(θ) μ_k,t(θ) through the following strategy: k,t(θ) ψ_k,t(θ) =k,t−1(θ)ℓk(k,t|θ)∑θ′∈Θk,t−1(θ′)ℓk(k,t|θ′), = μ_k,t-1(θ)\, _k( x_k,t|θ) _θ ∈ μ_k,t-1(θ )\, _k( x_k,t|θ ), (54) k,t(θ) μ_k,t(θ) =∏j∈k[j,t(θ)]ajk∑θ′∈Θ∏j∈k[j,t(θ′)]ajk. = _j _k[ ψ_j,t(θ)]^a_jk _θ ∈ _j _k[ ψ_j,t(θ )]^a_jk. (55) We see that, at each iteration t, each agent k performs the following steps: OPENi)i) first, it updates an intermediate belief k,t(θ) ψ_k,t(θ) by incorporating the local fresh information k,t x_k,t by means of a local Bayesian update, based on the local likelihood ℓk(k,t|θ) _k( x_k,t|θ) and the previous belief k,t−1(θ) μ_k,t-1(θ); OPENii)i) then, it shares the intermediate beliefs over the network; OPENiii)i) finally, it combines the intermediate beliefs received from its neighbors by means of a weighted geometric average using some combination weights ajk≥0a_jk≥ 0. The weights follow the underlying network structure, in the sense that ajk=0a_jk=0 when there is no directed link from j to k. It is customary to collect these weights into a weighted adjacency matrix A=[ajk]A=[a_jk], a.k.a. combination matrix. Moreover, the weights can be chosen so as to make A a doubly stochastic matrix, i.e., a matrix whose entries add up to 11 across the columns and across the rows. It has been proved that, with doubly stochastic combination matrices, the strategy (54)–(55) attains the same error exponent as the centralized system [6]. Traditional social learning is fundamentally different from the schemes attaining the limit decentralized performance that we described in Sec. I-C. In traditional social learning, each agent does not keep trace of the information flowing over the network, and updates (i.e., overwrites) the same belief function continually. This process is more parsimonious in terms of communication/memory resources. However, the beliefs received by an agent usually contain common pieces of information arriving from multiple paths. Due to the continuous belief overwriting, these redundancies are not disentangled. For this reason, we do not expect traditional social learning to attain the limit performance of decentralized systems. To elaborate on this issue, let us consider a decision problem with two hypotheses θ∈Θ=0,νθ∈ =\0,ν\, which are assumed to be equally distributed a priori, i.e., π(0)=1/2π(0)=1/2. Each agent k at time t collects an observation k,t x_k,t distributed as a unit-variance Gaussian, with means 00 and ν under the two hypotheses, respectively. Let εk≜Δ4∑j=1K∑τ=1∞([Aτ]jkK−1)2, _k 4 _j=1^K _τ=1^∞ ([A^τ]_jk\,K-1 )^2, (56) where [Aτ]jk[A^τ]_jk denotes the (j,k)(j,k) entry of the power matrix AτA^τ. It has been shown in [21] that, when A is a primitive matrix, the loss experienced by agent k in traditional social learning (54)–(55) is ℒkSL=exp(εk). L_k^SL= ( _k). (57) Let us also evaluate the optimal decentralized performance loss ℒk L_k predicted by Theorem 2. It is a straightforward exercise to prove that the log likelihood ratios under the two hypotheses are distributed as follows: k,t(0,ν) λ_k,t(0,ν) ∼(Δ,2Δ),under θ0=0 ( ,2 ), under $ _0=0$ (58) k,t(ν,0) λ_k,t(ν,0) ∼(Δ,2Δ),under θ0=ν, ( ,2 ), under $ _0=ν$, (59) where Δ≜ν2/2 ν^2/2 is the KL divergence between the distributions (which, in this particular example, is the same under both hypotheses), while the notation (a,b)G(a,b) denotes a Gaussian distribution with mean a and variance b. Recalling that the LMGF of a Gaussian variable with mean a and variance b is equal to at+bt2/2at+b\,t^2/2, we conclude that the LMGFs of the log likelihood ratios for each agent k are equal under both hypotheses and are given by Λk(s,0,ν)=Λk(s,ν,0)=Δs(1+s). _k(s;0,ν)= _k(s;ν,0)= \,s (1+s ). (60) Likewise, the global LMGFs in (7) are given by Λ(s,0,ν)=Λ(s,ν,0)=KΔs(1+s), (s;0,ν)= (s;ν,0)=K \,s (1+s ), (61) which implies that the stationary equation (15) has the solution s(0,ν)=s(ν,0)=−12.s(0,ν)=s(ν,0)=- 12. (62) Substituting this result into (60), we find that the performance losses under both hypotheses are ℒk(0,ν)=ℒk(ν,0)=exp(Δ4∑j=1Kdjk). L_k(0,ν)= L_k(ν,0)= ( 4 _j=1^Kd_jk ). (63) Since the weights in (45) add up to 11, we conclude that the overall loss in (44) for agent k is ℒk=exp(Δ4∑j=1Kdjk). L_k= ( 4\, _j=1^Kd_jk ). (64) We now show that the optimal loss in (64) is always smaller than the loss in (57) that characterizes traditional SL. To this aim, we start by observing that the entries of the matrix powers, [Aτ]jk[A^τ]_jk, are nonzero iff there exists a path of length τ that starts at j and ends at k [23, 6]. According to Definition 1, the shortest path from j to k has length djk+1d_jk+1, which means that ∀τ≤djk∀τ≤ d_jk we have [Aτ]jk=0[A^τ]_jk=0, implying ∑τ=1∞([Aτ]jkK−1)2=∑τ=1djk([Aτ]jkK⏟=0−1)2 _τ=1^∞ ([A^τ]_jk\,K-1 )^2= _τ=1^d_jk ( [A^τ]_jk\,K_=0-1 )^2 +∑τ=djk+1∞([Aτ]jkK−1)2 + _τ=d_jk+1^∞ ([A^τ]_jk\,K-1 )^2 =djk+∑τ=djk+1∞([Aτ]jkK−1)2. =d_jk+ _τ=d_jk+1^∞ ([A^τ]_jk\,K-1 )^2. (65) It is well-known that, when A is primitive, all columns in the matrix power AτA^τ converge to the Perron vector [23, 6]. For doubly stochastic matrices, this vector has all its entries equal to 1/K1/K [23, 6]. Since, in general, the convergence of [Aτ]jk[A^τ]_jk to 1/K1/K, takes place asymptotically,55 5 The reader might wonder whether the matrix power entries can converge to the Perron vector entries in a finite number of steps. From a theoretical standpoint, this can happen for some exceptional topologies. We now show that, even in this special case, the decentralized system experiences a loss. Assume the extreme situation where the convergence is met after only two steps, i.e., [Aτ]jk=1/K[A^τ]_jk=1/K for all τ>1τ>1. Note that, since all agents are connected in two hops, we have djk=1d_jk=1 for j∉kj _k. From (56), (57), and (64), we conclude that ℒkSL=ℒk×exp(∑j∈k(ajkK−1)2). L_k^SL= L_k× ( _j _k (a_jk\,K-1 )^2 ). (66) Thus, to achieve ℒkSL=ℒk L_k^SL= L_k, we must have ajk=1/Ka_jk=1/K for all j∈kj _k. However, this means that agent k should be connected to all other agents. Moreover, this cannot happen for all agents, but for the trivial case where the network is fully connected. we conclude that the summation on the RHS is positive, yielding, in view of (56), (57), and (64), ℒkSL>ℒk. L_k^SL> L_k. (67) In summary, the limit decentralized performance in Theorem 2 can be attained by the approaches illustrated in Sec. I-C. Now we have shown, by means of a counterexample, that in traditional social learning the limit decentralized performance is not attained in general. These results pave the way for a new research question, which can be regarded as a rate/distortion formulation of decentralized decision-making. At one extreme, we can consider the scheme that attains the limit decentralized performance as the most expensive scheme in terms of communication/memory resources. In comparison, traditional social learning schemes save resources by maintaining and overwriting one belief vector for each agent. Then, after defining a suitable metric to quantify the communication/memory expense (i.e., the rate), it would be legitimate to investigate the possibility of designing new decentralized strategies that attain an error probability (i.e., the distortion) closer to the optimal decentralized scheme, possibly at the price of an increased rate with respect to traditional SL. The most ambitious and challenging goal would be to establish the optimal rate/distortion curve for decentralized decision-making, i.e., the best error probability achievable for any rate budget. V Illustrative Examples In this section, we apply the performance characterization provided by Theorem 2 to some exemplary scenarios. Specifically, in Sec. V-A we examine the impact of two classic graph structures on the decentralized performance loss, whereas in Sec. V-B we examine the interplay between the inference power of the agents and their connectivity. V-A Scaling Laws under Different Graphs We want to establish how the performance slowdown scales with the number of agents, under two different network constructions, namely, a ring topology and an Erdős-Rényi random graph. To this end, we examine the scaling law for the learning delay TkT_k from Corollary 2. In order to magnify the role of the topology itself, we focus on an inference problem where all agents are equally informed. Later, in the next section, we consider the case where different agents, with different connectivity, have unequal inference power. Specifically, in this section we consider the binary decision problem illustrated in Sec. IV, for which the optimal decentralized loss is represented by (64). Since, in this example, the losses are equal under both hypotheses, we can use the simplified expression (53) to evaluate the learning delay TkT_k. From (60), (61), and (62), we see that, under the considered setting, the weights in (52) are uniform, i.e., qj=1/Kq_j=1/K for all j∈j , yielding Tk=1K∑j=1Kdjk.T_k= 1K _j=1^Kd_jk. (68) We conclude that the weighted structure in (53) (which, we recall, holds because the losses are equal under both hypotheses) translates into the arithmetic average of the distances from any agent j to agent k. This is because we are considering equally informed agents and, hence, the weights qjq_j that quantify the relative importance of each agents are uniform, therefore bringing no difference across the agents. Fig. 2: The directed ring topology used in Sec. V-A, with K=25K=25. Fig. 3: One realization of the Erdős-Rényi graph used in Sec. V-A, with cK=0.1ln(K)c_K=0.1 (K) and K=50K=50. V-A1 Ring topology Let us consider the graph depicted in Fig. 2. Observe that any agent k has exactly one neighbor, one agent at distance djk=1d_jk=1, one agent at distance 22, and so on, until the farthest agent, which is located at distance K−2K-2 (recall that in our notation the distance is given by the number of hops minus 11). According to this description, the learning delay in (68) is given by Tk T_k =1K∑j=1Kdjk=1K∑j=1K−2j=(K−1)(K−2)2K = 1K _j=1^Kd_jk= 1K _j=1^K-2j= (K-1)(K-2)2\,K =K(1−1K)(1−2K), =K\, (1- 1K ) (1- 2K ), (69) which reveals that, over a ring topology, the learning delay for the decentralized system grows linearly with the network size. V-A2 Erdős-Rényi graphs The ring topology is a very structured topology that does not favor inter-agent communication. We now switch to a graph model that lies somehow in the opposite extreme, namely, a random graph. To avoid added complexity, we focus on the simplest generative mechanism, which is the Erdős-Rényi model, where each edge is present with some probability. Since we are interested in connected networks, we focus on the regime where the graph is connected with probability that approaches 11 as K→∞K→∞. It is known that this regime is characterized by a connection probability that scales with K as [24, 25] ρK=lnK+cKK, _K= K+c_KK, (70) where cKc_K is any sequence that tends to ∞ as K→∞K→∞. Fig. 4: Learning delay under Erdős-Rényi network topologies as K varies. cK=0.1ln(K)c_K=0.1 (K), Δ=0.05 =0.05. Fig. 5: Error probabilities of the considered decentralized decision-making strategies for the problem in Sec. V-A, with Δ=0.05 =0.05. The agents are connected according to the ring topology shown in Fig. 2. Fig. 6: Error probabilities of the considered decentralized decision-making strategies for the problem in Sec. V-A, with Δ=0.05 =0.05. The agents are connected according to the Erdős-Rényi topology shown in Fig. 3. In order to capture the scaling law of the loss with the number of agents, we resort to the following approximation for the typical distance between two network nodes [26]: djk≈lnK−γln(KρK)−12,d_jk≈ K-γ (K _K)- 12, (71) where γ is Euler’s constant. Substituting (71) into (68), we obtain Tk≈lnK−γln(KρK)−12.T_k≈ K-γ (K _K)- 12. (72) Considering some slowly increasing sequence, e.g., cK∝lnKc_K K, we see that the main scaling law for the learning delay TkT_k, under an Erdős-Rényi graph, is approximately logarithmic with the network size, which is exponentially better than the law characterizing the ring topology. To check the goodness of the approximation in (71), in Fig. 4 we plot the theoretical learning delay (72) along with the learning delay averaged over the agents, for 1010 realizations of random graphs. We see that the random points follow well the logarithmic trend captured by (72). In summary, by examining the ring and the random Erdős-Rényi graphs, we find that: OPENi)i) over a ring topology, the learning delay caused by the decentralization grows linearly with the network size, while OPENii)i) over an Erdős-Rényi random graph, the significant reduction in the inter-agent distances (which scale logarithmically with the network size) yields an exponential reduction in the learning delay. To gain further insight, in Fig. 5 (ring topology) and Fig. 6 (Erdős-Rényi graph), we display the error probabilities for the optimal centralized decision system, the optimal decentralized decision system, and the traditional social learning strategy described in Sec. IV. For the ring topology, we see from Fig. 5 that the best decentralized system exhibits a loss of about two orders of magnitude with respect to the centralized MAP. Consistently with our theoretical analysis, this gap is not reduced as t increases; in fact, the curves pertaining to the centralized and decentralized systems stay parallel, showing the constant learning delay predicted by Corollary 2. Moreover, as t increases, the predictions for the error probabilities in Theorem 2 (dashed line) match the exact probabilities (solid line). The red curve depicts the performance achieved by traditional social learning. As revealed by (67), traditional social learning exhibits a finite gap with respect to the best decentralized strategy, and we see that this gap is not negligible. All the error probabilities are evaluated exactly in this Gaussian problem [20]. The considerations made for the ring topology are essentially the same for the random graph in Fig. 6. Comparing this figure against Fig. 5, the main difference is that the loss experienced by the optimal decentralized scheme is reduced, which is consistent with the fact that the learning delay for the Erdős-Rényi graph shown in (72) is slower than the delay for the ring topology in (69). Fig. 7: Family of pdfs used in the decision problem from Sec. V-B. likelihood model ℓj(⋅|θ) _j(·|θ) agent θ=1θ=1 θ=2θ=2 θ=3θ=3 j=1,2,…,45j=1,2,…,45 f1f_1 f2f_2 f2f_2 j=46,47,…,50j=46,47,…,50 f1f_1 f2f_2 f3f_3 TABLE I: Likelihood assignment for the example in Sec. V-B. V-B Interplay Between Inference and Topology In this section, we consider a decision problem where K=50K=50 agents feature different levels of informativeness. Specifically, the decision problem consists of three possible hypotheses (namely, we set Θ=1,2,3 =\1,2,3\), which are assumed to be uniformly distributed a priori. The statistical distributions giving rise to the data are chosen from a family of Gaussian mixtures. Specifically, there are 33 possible pdfs, which differ by the number of components and weights in the mixture. Specifically, denoting by g(x)g(x) the pdf of the standard normal, we have the following three pdfs: f1(x) f_1(x) =12g(x+1.5)+12g(x−1.5), = 12\,g(x+1.5)+ 12\,g(x-1.5), f2(x) f_2(x) =13g(x+2)+13g(x)+13g(x−2), = 13\,g(x+2)+ 13\,g(x)+ 13\,g(x-2), f3(x) f_3(x) =14g(x+3)+14g(x+1.5) = 14\,g(x+3)+ 14\,g(x+1.5) +14g(x−1.5)+14g(x−3), + 14\,g(x-1.5)+ 14\,g(x-3), (73) which are displayed in Fig. 7. The agents’ likelihoods are chosen from these pdfs, and we assume that not all hypotheses are distinguishable for all agents. Specifically, the agents are clustered into two groups, corresponding to the likelihood assignment in Table I. For the first 4545 agents, we see from the table that, when θ=1θ=1, the likelihood is given by f1f_1, while the likelihoods corresponding to θ=2θ=2 and θ=3θ=3 are equal to f2f_2. Accordingly, the agents in the first group are able to distinguish hypothesis 11 from 22 and 33, but they confuse 22 and 33. The remaining 55 agents are more informative, as they are able to distinguish all the hypotheses. The goal of this section is to show how formula (44) quantifies the interplay between the agents’ informativeness and the network topology. To this end, we will examine the two topologies represented in Figs. 8 and 9, respectively. Fig. 8: The first topology used for the example in Sec. V-B, with the most informative agents highlighted in green (5 out of 50 agents). Agent 11, whose performance is displayed in Fig. 10, is highlighted in yellow. Fig. 9: The second topology used for the example in Sec. V-B, with the most informative agents highlighted in green (5 out of 50 agents). Agent 11, whose performance is displayed in Fig. 10, is highlighted in yellow. In order to compute the losses ℒk(θ0,θ) L_k( _0,θ) defined by (27) and appearing in (44), we need to evaluate first the solution s(θ0,θ)s( _0,θ) to the stationary equation (15), and then the LMGFs Λj(s(θ0,θ),θ0,θ). _j(s( _0,θ); _0,θ). (74) Then, after computing ℒk(θ0,θ) L_k( _0,θ) for all pairs (θ0,θ)( _0,θ), we also evaluate the weights (45), and finally obtain (44). Actually, in this example the LMGFs of the log likelihood ratios do not admit a closed form. Therefore, all the pertinent calculations have been performed numerically. We are now ready to examine how the topologies in Figs. 8 and 9 affect performance. Specifically, for illustrative purposes we focus on the error probability of agent 11 (represented by the circle highlighted in yellow). Fig. 10: Performance loss experienced by agent 11 under the decision problem considered in Sec. V-B, for the two topologies shown in Figs. 8 and 9. The error probabilities are computed over 1000010000 Monte Carlo trials. Inspecting jointly Table I and the two topologies, we see that: OPENi)i) in Fig. 8 the most informative agents (highlighted in green) are relatively distant from agent 11, which is basically surrounded by the partially informative agents j=1,2,…,45j=1,2,…,45; while OPENii)i) in Fig. 9, agent 11 is surrounded by the most informative agents. Let us see how this difference affects the performance loss experienced by agent 11, which is shown in Fig. 10. We see that the loss is higher for the graph in Fig. 8. This is because, in that graph, the most informative agents are distant, which means that more information is lost due to decentralization. In comparison, for the topology in Fig. 9 no loss is associated with the most informative agents, since they are immediate neighbors of agent 11. Remarkably, the behavior observed empirically matches well the theoretical results. In fact, the analytical characterization provided by Theorems 1 and 2 offer reliable formulas (see the dashed curves in Fig. 10) that are able to quantify precisely how the agents’ informativeness and connectivity interact and impact the final error probability performance. VI Conclusion and Future Work In this work, we established a fundamental limit on the error probability performance for decentralized decision systems. This limit probability admits a closed form that highlights the role of the network topology and the decision problem. The former appears in the analytical formulas through the shortest distances between pairs of agents. The latter is represented by quantities relative to the moment generating functions of the random observations collected by the agents. The analysis revealed that, contrary to a widespread belief, the performance of any decentralized decision strategy cannot reach the performance of the corresponding centralized system. Remarkably, even in the long run, i.e., over infinite streams of data, this gap persists. We also showed that the gap in terms of error probability translates into a learning delay that slows down the decentralized system irremediably. We exploited the aforementioned theoretical formulas to gain insight into useful network structures. First, to magnify the impact of the network topology on the decentralization loss, we considered a scenario where all agents are equally informative. We established that in this case the performance loss scales exponentially with the sum of the network distances. Accordingly, we showed that the error probability for the best decentralized strategy can be larger than the optimal centralized error probability by orders of magnitude. We examined two standard network constructions, namely, the ring topology and the Erdős-Rényi random graphs. In the former case, the learning delay of any agent grows linearly with the number of agents. This is due to the fact that, over a ring network, the average distance between two agents scales linearly with the number of agents. Over the Erdős-Rényi graphs, the learning delay is significantly reduced, namely, it grows logarithmically with the number of agents. This is consistent with the fact that, according to the theory of random graphs, the average distance between two nodes over an Erdős-Rényi topology scales logarithmically with the network size. Second, we used the theoretical formulas to quantify the interplay between the topology and the agents’ informativeness. While it might be intuitive that it is beneficial for an agent to be closer to the most informative agents, the evaluation of the error probability depends in a nontrivial manner on the interplay between the agents’ connectivity (quantified by the distances over the graph) and the level of informativeness (quantified by the moment generating functions). We showed that our formulas are able to provide reliable predictions for the agents’ performance under different conditions where the position of the most informative agents in the network is varied. The derived performance limit should be used as a benchmark for the performance of any decentralized strategy. For example, we showed that traditional social learning schemes exhibits a finite gap with respect to the optimal decentralized strategy. In this connection, one useful extension would be the analytical evaluation of the performance achieved by existing decision-making schemes, to quantify how far they are from the best attainable decentralized performance. Another future research direction is to design decentralized decision schemes under different constraints (e.g., communication constraints) and exploit the rate-distortion tradeoff to quantify how the gap with respect to the best decentralized performance varies with the available communication resources. Finally, our analysis leads to a useful comparison between the two main inferential problems, namely, classification and estimation. In the former case, one deals with categorical variables (the hypotheses), for which it is necessary to employ a hit-or-miss metric like the error probability. In the latter problem, one can resort to error measures suited for real values, like the mean-square-error. For decentralized estimation problems, the optimal mean-square-error can be asymptotically achieved. In contrast, we have proved that the optimal error probability cannot be achieved by any decentralized strategy. This highlights an intrinsic difference between decision-making and estimation. At the same time, the results in the present work suggest that, under interval estimation (where the error probability is used for the performance evaluation of an estimator) the asymptotic optimality observed in the mean-square-error sense needs to be revisited. Appendix A Exact Asymptotics of Certain Random Sums In the following theorems, we will consider a doubly indexed sequence of random variables j,τ ξ_j,τ, for j∈j and τ∈ℕτ , which fulfill the following assumption. Assumption 5 (Regularity conditions on j,τ ξ_j,τ). The random variables j,τ ξ_j,τ are absolutely continuous with respect to the Lebesgue measure on ℝR, and statistically independent (across both indices j and τ). For all τ, they share the same pdf fjf_j, with j,τ>0,infSupp(fj)<0,E\, ξ_j,τ>0, (f_j)<0, (75) where Supp(fj)Supp(f_j) is the support of fjf_j [6, Def. E.1]. For each fjf_j, the characteristic function φj(s)≜exp(ιsj,τ) _j(s) ( \,s\, ξ_j,τ ) (76) (with s∈ℝs and ι=−1 = -1) fulfills the following bound: |φj(s)|≤c|s|δ,|s|≥r,| _j(s)|≤ c|s|^δ, |s|≥ r, (77) for some positive constants δ,c,δ,c, and r. Moreover, the log moment generating function Λj(s)≜lnexp(sj,τ) _j(s) (s\, ξ_j,τ ) (78) is finite for all s∈ℝs . □ Equation (77) represents a mild condition that is verified, for instance, when the pdf fjf_j has an integrable first derivative [29, Lemma 4, Chap. XV]. Regarding the finiteness of the LMGF, some examples satisfying this condition are: all random variables with finite support, the Gaussian distribution, or any Gaussian mixture. Before stating the main result of this appendix, it is useful to introduce the aggregate variable τ≜∑j∈j,τ,τ∈ℕ, ξ_τ _j ξ_j,τ, τ , (79) along with its LMGF Λ(s)≜lnexp(sτ)=∑j∈Λj(s), (s) \, (s\, ξ_τ )= _j _j(s), (80) where the equality follows from the additivity of the LMGF for independent variables. Note that, since each j,τ ξ_j,τ is nondeterministic (being absolutely continuous with respect to the Lebesgue measure on ℝR), then each LMGF Λj(s) _j(s) is strictly convex, which implies that so is Λ(s) (s) [17, 18, 6]. Now, it is known that the limit of the first derivative66 6 We recall that, since by assumption the LMGF Λj(s) _j(s) is finite for all s∈ℝs , it is infinitely differentiable on ℝR [6]. Λ′(s) (s) as s→−∞s→-∞ (resp., s→+∞s→+∞) is equal to the infimum (resp., the supremum) of the support of the pdf of τ ξ_τ [6, proof of Lemma E.1]. On the other hand, from (75) we know that the infimum of the support of fjf_j is negative, while the supremum is positive (because the mean j,τE\, ξ_j,τ is positive). This implies that the stationary equation Λ′(s0)=∑j∈Λj′(s0)=0 (s_0)= _j _j (s_0)=0 (81) has always a solution, which is the unique minimizer of Λ(s) (s) in view of the strict convexity. Moreover, since the first derivative of the LMGF evaluated in 00 is equal to the mean, we have Λ′(0)>0 (0)>0. This implies that the minimizer of Λ(s) (s) is located on the negative axis. Moreover, since Λ(0)=0 (0)=0 by definition, the minimum of Λ(s) (s) is negative. In summary, we have s0<0,Λ(s0)=∑j∈Λj(s0)<0.s_0<0, (s_0)= _j _j(s_0)<0. (82) Theorem 3 (Exact asymptotics of some useful random sums). Let the random variables j,τ ξ_j,τ, for j∈j and τ∈ℕτ , satisfy Assumption 5. For j∈j , let djd_j be nonnegative integer numbers. For t>maxj∈djt> _j d_j, define the random sequence t=∑j∈∑τ=1t−djj,τ+γ, z_t= _j _τ=1^t-d_j ξ_j,τ+γ, (83) where γ∈ℝγ . Let s0<0s_0<0 be the solution to the stationary equation (81) and define σt2≜s02t∑j∈Λj′(s0)σ^2_t s_0^2\,t\, _j _j (s_0) (84) and pt≜12πσt2exp(t∑j∈Λj(s0)−∑j∈djΛj(s0)−|s0|γ).p_t 1 2π\,σ^2_t (t\, _j _j(s_0)- _j d_j _j(s_0)-|s_0|\,γ ). (85) Then, limt→∞ℙ[t≤0]pt=1. _t→∞ P[ z_t≤ 0]p_t=1. (86) Proof: Let us consider the change of measure identified by the so-called tilted pdf [6, App. E] f~j(ξ)=fj(ξ)es0ξeΛj(s0),j∈,ξ∈ℝ. f_j(ξ)=f_j(ξ)\, e^s_0\,ξe _j(s_0), j ,\;ξ . (87) From the definition of the LMGF, it is easily verified that f~j f_j is a pdf. Moreover, it is known that [6, App. E] the first three moments (which will be relevant later in our proof) of j,τ ξ_j,τ under the tilted distribution are given by f~jj,τ _ f_j\, ξ_j,τ =Λj′(s0), = _j (s_0), (88) f~j[(j,τ−f~jj,τ)2] _ f_j [ ( ξ_j,τ-E_ f_j\, ξ_j,τ )^2 ] =Λj′(s0), = _j (s_0), (89) f~j[(j,τ−f~jj,τ)3] _ f_j [ ( ξ_j,τ-E_ f_j\, ξ_j,τ )^3 ] =Λj′(s0), = _j (s_0), (90) where the subscript f~j f_j denotes that the expectation is computed under the tilted distribution. We have the following chain of identities: ℙ[t≤0] [ z_t≤ 0] =[t≤0] =E [I_ z_t≤ 0 ] =(a)∫zt≤0(∏j∈∏τ=1t−djfj(ξj,τ)dξj,τ) (a)= _z_t≤ 0\, ( _j _τ=1^t-d_jf_j( _j,τ)\,d _j,τ ) =(b)∫zt≤0(∏j∈∏τ=1t−djeΛj(s0)es0ξj,τf~j(ξj,τ)dξj,τ) (b)= _z_t≤ 0 ( _j _τ=1^t-d_j e _j(s_0)e^s_0\, _j,τ f_j( _j,τ)\,d _j,τ ) =(c)f~[exp(∑j∈∑τ=1t−djΛj(s0))exp(s0∑j∈∑τ=1t−djj,τ)t≤0] (c)=E_ f [ ( _j _τ=1^t-d_j _j(s_0) ) (s_0\, _j _τ=1^t-d_j ξ_j,τ )\;\;I_ z_t≤ 0 ] =(d)f~[exp(∑j∈(t−dj)Λj(s0))exp(s0(t−γ))t≤0], (d)=E_ f [ ( _j (t-d_j)\, _j(s_0) ) (s_0\,( z_t-γ) )\;\;I_ z_t≤ 0 ], (91) where (a) holds because the random variables j,τ ξ_j,τ are independent across j and τ; (b) follows from (87); in (c) we introduce the subscript f~ f to denote the expectation computed under the tilted measure associated with the product of the tilted pdfs f~j(ξj,τ) f_j( _j,τ); and (d) follows from computing the sum over τ in the numerator (note that the LMGFs Λj _j do not depend on τ) and from applying (83) in the denominator. Pulling the deterministic quantities out of the expectation operator, we can rewrite (91) as ℙ[t≤0] [ z_t≤ 0] =f~[e−s0tt≤0] =E_ f [e^-s_0\, z_t\,I_ z_t≤ 0 ] ×exp(t∑j∈Λj(s0)−∑j∈djΛj(s0)−|s0|γ), × (tΣ _j _j(s_0)-Σ _j d_j _j(s_0)-|s_0|\,γ ), (92) where we used the fact that s0<0s_0<0. Consider now an integer number n>djn>d_j. It is convenient to split the random variable t z_t in (83) as follows: t z_t =∑j∈∑τ=1t−nj,τ+∑j∈∑τ=t−n+1t−djj,τ+γ = _j _τ=1^t-n ξ_j,τ+ _j _τ=t-n+1^t-d_j ξ_j,τ+γ =∑τ=1t−nτ+∑j∈∑τ=t−n+1t−djj,τ+γ, = _τ=1^t-n ξ_τ+ _j _τ=t-n+1^t-d_j ξ_j,τ+γ, (93) where in the last equality we applied the definition of τ ξ_τ from (79). By introducing a random variable 0 ξ_0, statistically independent of the variables j,τ ξ_j,τ and such that 0=d∑j∈∑τ=t−n+1t−djj,τ+γ, ξ_0 = _j _τ=t-n+1^t-d_j ξ_j,τ+γ, (94) where =d = denotes equality in distribution, we get t=d0+∑τ=1t−nτ=∑τ=0t−nτ. z_t = ξ_0+ _τ=1^t-n ξ_τ= _τ=0^t-n ξ_τ. (95) Observe that, in view of (81) and (88), the means, under the tilted distribution, of the random variables defined by (79) are zero. On the other hand, from (94) we see that the mean of 0 ξ_0 under the tilted distribution is given by f~0=n∑j∈Λj′(s0)⏟=0 from (81)−∑j∈djΛj′(s0)+γ.E_ f\, ξ_0=n _j _j (s_0)_=0 from eq:stateq- _j d_j _j (s_0)+γ. (96) Therefore, we can write mz≜f~t=−∑j∈djΛj′(s0)+γ.m_z _ f\, z_t=- _j d_j _j (s_0)+γ. (97) Likewise, by exploiting (88) and the independence of the random variables j,τ ξ_j,τ, we obtain (the notation for the variance should be self-explaining), σz,t2≜ℝf~t=t∑j∈Λj′(s0)−∑j∈djΛj′(s0).σ^2_z,t _ f\, z_t=t _j _j (s_0)- _j d_j\, _j (s_0). (98) Let us introduce the standardized version of t z_t, t≜t−mzσz,t, ζ_t z_t-m_z _z,t, (99) and denote by t F_t its cumulative distribution function (cdf) under the tilted measure. From [28, Thm. 7, Chap. VI] (whose sufficient conditions can be readily verified to hold in view of the properties in Assumption 5), it turns out that: OPENi)i) t ζ_t converges in distribution (under the tilted measure) to a standard normal; OPENii)i) its cdf t F_t can be approximated by the following first-order Edgeworth expansion: ^t(ζ)≜G(ζ)+mz,t(3)6σz,t3h(ζ), F_t(ζ) G(ζ)+ m_z,t^(3)6\, _z,t^3\,h(ζ), (100) where mz,t(3)≜∑τ=0t−nf~[(τ−f~τ)3],h(ζ)≜(1−ζ2)g(ζ),m^(3)_z,t _τ=0^t-nE_ f [ ( ξ_τ-E_ f\, ξ_τ )^3 ], h(ζ) (1-ζ^2)g(ζ), (101) with G and g being the cdf and the pdf of the standard normal, respectively. The approximation holds in the following sense [28, Thm. 7, Chap. VI]: limt→∞tsupζ∈ℝ|t(ζ)−^t(ζ)|=0, _t→∞ t\, _ζ | F_t(ζ)- F_t(ζ) |=0, (102) that is, the error t(ζ)≜t(ζ)−^t(ζ) E_t(ζ) F_t(ζ)- F_t(ζ) (103) between t F_t and the Edgeworth approximation ^t F_t converges to zero faster than 1/t1/ t, and uniformly in ζ. Exploiting the definition of the standardized variable t ζ_t from (99), we have the identities (we recall that s0<0s_0<0) f~[e−s0t≤0]=e−s0mzf~[e−s0σz,tt≤−mz/σz,t] _ f [e^-s_0 z_t\,I_ z_t≤ 0 ]=e^-s_0m_z\,E_ f [e^-s_0 _z,t ζ_t\,I_ ζ_t≤-m_z/ _z,t ] =|s0|σz,te|s0|mz∫−∞−mz/σz,te|s0|σz,tζ[t(−mzσz,t)−t(ζ)]dζ, =|s_0|\, _z,t\,e^|s_0|m_z\!\!\! _-∞^-m_z/ _z,t\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!e^|s_0| _z,tζ [ F_t (- m_z _z,t )- F_t(ζ) ]dζ, (104) where the last equality follows from the definition of the expected value and the rule of integration by parts. By using the change of variable |s0|(σz,tζ+mz)↦ζ|s_0|( _z,t\,ζ+m_z) ζ, we get f~[e−s0tt≤0] _ f [e^-s_0 z_t\,I_ z_t≤ 0 ] =∫−∞0eζ[t(−mzσz,t)−t(ζ−|s0|mz|s0|σz,t)]dζ⏟≜It. = _-∞^0e^ζ [ F_t (- m_z _z,t )- F_t ( ζ-|s_0|m_z|s_0|\, _z,t ) ]dζ_ I_t. (105) Combining (85), (92), and (105), we can write ℙ[t≤0]pt=2πσtIt. P[ z_t≤ 0]p_t= 2π\, _t\,I_t. (106) Therefore, the claim in (86) is equivalent to limt→∞2πσtIt=1. _t→∞ 2π _t\,I_t=1. (107) Let us then elaborate to prove (107). Using (103), the quantity ItI_t defined in (105) can be represented as It I_t =∫−∞0eζ[^t(−mzσz,t)−^t(ζ−|s0|mz|s0|σz,t)]dζ⏟≜I1,t = _-∞^0e^ζ [ F_t (- m_z _z,t )- F_t ( ζ-|s_0|m_z|s_0|\, _z,t ) ]dζ_ I_1,t +∫−∞0eζ[t(−mzσz,t)−t(ζ−|s0|mz|s0|σz,t)]dζ⏟≜I2,t. + _-∞^0e^ζ [ E_t (- m_z _z,t )- E_t ( ζ-|s_0|m_z|s_0|\, _z,t ) ]dζ_ I_2,t. (108) Regarding the term I2,tI_2,t, from the triangle inequality we have the upper bound |I2,t|≤2supζ∈ℝ|t(ζ)|, |I_2,t |≤ 2\, _ζ | E_t(ζ)|, (109) where we also exploited the identity ∫−∞0eζζ=1 _-∞^0e^ζ\,dζ=1. Applying the definition of σt _t from (84), we can write 2πσtI2,t=tI2,t(2πs02∑j∈Λj′(s0))1/2. 2π _t\,I_2,t= t\,I_2,t (2π s_0^2\, _j _j (s_0) )^1/2. (110) From (102), (103), (109), and (110), we conclude that limt→∞2πσtI2,t=0. _t→∞ 2π _t\,I_2,t=0. (111) Thus, to prove (107), it remains to show that limt→∞2πσtI1,t=1. _t→∞ 2π _t\,I_1,t=1. (112) To this end, we exploit the definitions of ^t F_t from (100) and I1,tI_1,t from (108) to write 2πσtI1,t 2π\, _t\,I_1,t =2πσt∫−∞0[G(−mzσz,t)−G(ζ−|s0|mz|s0|σz,t)]eζζ = 2π\, _t\, _-∞^0 [G (- m_z _z,t )-G ( ζ-|s_0|m_z|s_0|\, _z,t ) ]e^ζdζ +π18mz,t(3)σtσz,t3 + π18 m_z,t^(3)\, _t _z,t^3 ×∫−∞0[h(−mzσz,t)−h(ζ−|s0|mz|s0|σz,t)]eζζ. × _-∞^0 [h (- m_z _z,t )-h ( ζ-|s_0|m_z|s_0|\, _z,t ) ]e^ζdζ. (113) First, we focus on the second term. The ratio mz,t(3)σtσz,t3 m_z,t^(3)\, _t _z,t^3 (114) converges to a finite limit as t→∞t→∞ because mz,t(3)m^(3)_z,t scales as t in view of (101), while σt _t and σz,t _z,t scale as t t in view of (84) and (98), respectively. Moreover, since limt→∞[h(−mzσz,t)−h(ζ−|s0|mz|s0|σz,t)]eζ=0, _t→∞ [h (- m_z _z,t )-h ( ζ-|s_0|m_z|s_0|\, _z,t ) ]e^ζ=0, (115) and since the function h is bounded, by applying the dominated convergence theorem we conclude that the second term in (113) vanishes. Let us move on to examining the first term in (113). By applying the rule of integration by parts, we can rewrite that term as 2πσt|s0|σz,t∫−∞0g(ζ−|s0|mz|s0|σz,t)eζζ. 2π _t|s_0| _z,t _-∞^0g ( ζ-|s_0|m_z|s_0| _z,t )e^ζdζ. (116) From (84) and (98) we conclude that the ratio σt/(|s0|σz,t) _t/(|s_0| _z,t) converges to 11. By applying the dominated convergence theorem (observe that g is bounded), we finally obtain limt→∞2πσt|s0|σz,t∫−∞0g(ζ−|s0|mz|s0|σz,t)eζζ _t→∞ 2π _t|s_0| _z,t _-∞^0g ( ζ-|s_0|m_z|s_0| _z,t )e^ζdζ =2πg(0)∫−∞0eζζ=1, = 2πg(0) _-∞^0e^ζdζ=1, (117) which completes the proof. ∎ Appendix B Pairs of Log Likelihood Ratios Lemma 1 (Non-degeneracy of the global LLRs). Let Assumptions 1 and 2 be satisfied. Consider the true hypothesis θ0 _0, and two other hypotheses θ1 _1 and θ2 _2. Then, the global log likelihood ratios t(θ0,θ1) λ_t( _0, _1) and t(θ0,θ2) λ_t( _0, _2) are not proportional to each other. Proof: It is convenient to introduce the vector x=[x1,x2,…,xK]x=[x_1,x_2,…,x_K], which stacks the vectors xk∈ℝnkx_k ^n_k for k∈k . By introducing the global likelihood ℓ(x|θ)≜∏k=1Kℓk(xk|θ),θ∈Θ, (x|θ) _k=1^K _k(x_k|θ), θ∈ , (118) the claim of the lemma is equivalent to showing that lnℓ(x|θ0)ℓ(x|θ1) (x| _0) (x| _1) and lnℓ(x|θ0)ℓ(x|θ2) (x| _0) (x| _2) are not proportional to each other. By contrapositive statement, assume that lnℓ(x|θ0)ℓ(x|θ1)=alnℓ(x|θ0)ℓ(x|θ2) (x| _0) (x| _1)=a\, (x| _0) (x| _2) (119) for some a∈ℝa and all x∈ℝ∑k=1Knkx _k=1^Kn_k, but for a zero probability set under ℓ(x|θ0) (x| _0). Now, the constant a cannot be equal to 00 or 11 because otherwise we would violate the identifiability assumption (in particular, when a=1a=1 we would violate the distinguishability between θ1 _1 and θ2 _2). On the other hand, a cannot be negative, otherwise (since identifiability corresponds to positivity of the KL divergence), we would have 0<∑k=1KDk(θ0||θ1)=a∑k=1KDk(θ0||θ2)<0.0< _k=1^KD_k( _0|| _1)=a\, _k=1^KD_k( _0|| _2)<0. (120) Accordingly the residual possibility is that a>0a>0 with a≠1a≠ 1. If Eq. (119) holds, we have ℓ(x|θ1)=ℓa(x|θ2)ℓ1−a(x|θ0). (x| _1)= ^a(x| _2)\, ^1-a(x| _0). (121) Assume that 0<a<10<a<1, and set u(x)=ℓa(x|θ2),v(x)=ℓ1−a(x|θ0),u(x)= ^a(x| _2), v(x)= ^1-a(x| _0), (122) and p=1a,q=11−a.p= 1a, q= 11-a. (123) In view of Hölder’s inequality ∫u(x)v(x)x≤(∫up(x)x)1p(∫vq(x)x)1q, u(x)\,v(x)\,dx≤ ( u^p(x)\,dx ) 1p\!\! ( v^q(x)\,dx ) 1q\!\!\!, (124) which, by substituting (122) and (123), yields ∫ℓa(x|θ2)ℓ1−a(x|θ0)x≤1. ^a(x| _2)\, ^1-a(x| _0)\,dx≤ 1. (125) However, if (121) holds, the above inequality should in fact be an equality, which, by Hölder’s result, holds iff up(x)∝vq(x),u^p(x) v^q(x), (126) that is, iff ℓ(x|θ2)∝ℓ(x|θ0), (x| _2) (x| _0), (127) which is impossible in view of identifiability.77 7 Since ∫ℓ(x|θ2)x=∫ℓ(x|θ0)x (x| _2)dx= (x| _0)dx, Eq. (127) would correspond to ℓ(⋅|θ2)=ℓ(⋅|θ0) (·| _2)= (·| _0). The case a>1a>1 can be handled similarly, by considering 1/a1/a in place of a and exchanging the role of θ1 _1 and θ2 _2. ∎ Lemma 2 (Strict convexity of the bivariate LMGF). Let Assumptions 1–3 be satisfied, and consider the bivariate LMGF Λ(s1,s2,θ0,θ1,θ2) (s_1,s_2; _0, _1, _2) ≜lnθ0exp(s1t(θ0,θ1)+s2t(θ0,θ2)). _ _0\, (s_1\, λ_t( _0, _1)+s_2\, λ_t( _0, _2) ). (128) Then, Λ(s1,s2,θ0,θ1,θ2) (s_1,s_2; _0, _1, _2) is strictly convex. Proof: For ease of notation, in the following we skip the explicit dependence of the pertinent quantities on θ0 _0, θ1 _1, and θ2 _2. Consider the bivariate moment generating function (MGF) M(s1,s2)≜θ0exp(s11+s22),M(s_1,s_2) _ _0 (s_1\, v_1+s_2\, v_2 ), (129) where we set 1≜t(θ0,θ1),2≜t(θ0,θ2). v_1 λ_t( _0, _1), v_2 λ_t( _0, _2). (130) In view of Assumption 3, the marginal MGFs for 1 v_1 and 2 v_2, say M1(s1)M_1(s_1) and M2(s2)M_2(s_2), exist and are finite over the entire real axis. Then, by applying the Cauchy-Schwarz inequality for random variables, we can write M(s1,s2)≤M1(2s1)M2(2s2),M(s_1,s_2)≤ M_1(2s_1)\,M_2(2s_2), (131) which shows that the bivariate MGF exists and is finite for all (s1,s2)∈ℝ2(s_1,s_2) ^2. Moreover, by exploiting the properties of the exponential function and the dominated convergence theorem, it is possible to show that the MGF is infinitely differentiable over ℝ2R^2 and that its derivatives can be computed by exchanging the differentiation and integration operators, which yields, in particular, for n=1,2n=1,2, [27] ∂M(s1,s2)∂sn=θ0[nes11+s22] ∂ M(s_1,s_2)∂ s_n=E_ _0\, [ v_n\,e^s_1\, v_1+s_2\, v_2 ] (132) and, likewise, for all pairs m,nm,n, including m=nm=n, ∂M(s1,s2)∂sm∂sn=θ0[mnes11+s22]. ∂ M(s_1,s_2)∂ s_m∂ s_n=E_ _0\, [ v_m\, v_n\,e^s_1\, v_1+s_2\, v_2 ]. (133) Since Λ(s1,s2)=lnM(s1,s2) (s_1,s_2)= M(s_1,s_2), from (132) we obtain ∂Λ(s1,s2)∂sn=θ0[nes11+s22]M(s1,s2). ∂ (s_1,s_2)∂ s_n= E_ _0\, [ v_n\,e^s_1\, v_1+s_2\, v_2 ]M(s_1,s_2). (134) Referring to the global likelihood ℓ(x|θ0) (x| _0) defined by (118), we introduce the tilted measure ℓ~(x|θ0)=es1v1+s2v2eΛ(s1,s2)ℓ(x|θ0), (x| _0)= e^s_1v_1+s_2v_2e (s_1,s_2)\, (x| _0), (135) where we note that the variables v1v_1 and v2v_2 depend implicitly on x since they are log likelihood ratios; see (130). Using (135) in (134), we conclude that ∂Λ(s1,s2)∂sn=ℓ~θ0n, ∂ (s_1,s_2)∂ s_n=E_ _ _0 v_n, (136) where the subscript denotes that the expectation is computed under the tilted pdf (135). In order to establish the strict convexity of Λ(s1,s2) (s_1,s_2), we will prove that the associated Hessian matrix is positive definite. Let us accordingly evaluate the second partial derivatives of Λ(s1,s2) (s_1,s_2). Using again the identity Λ(s1,s2)=lnM(s1,s2) (s_1,s_2)= M(s_1,s_2), we have, for all pairs m,nm,n, including m=nm=n, ∂Λ(s1,s2)∂sm∂sn=∂M(s1,s2)∂sm∂snM(s1,s2)−∂M(s1,s2)∂sm∂M(s1,s2)∂snM2(s1,s2), ∂ (s_1,s_2)∂ s_m∂ s_n= ∂ M(s_1,s_2)∂ s_m∂ s_nM(s_1,s_2)\\ - ∂ M(s_1,s_2)∂ s_m ∂ M(s_1,s_2)∂ s_nM^2(s_1,s_2), which, exploiting (132)–(136), can be cast in the form ∂Λ(s1,s2)∂sm∂sn=ℓ~θ0[mn]−ℓ~θ0[m]ℓ~θ0[n]. ∂ (s_1,s_2)∂ s_m∂ s_n=E_ _ _0[ v_m\, v_n]-E_ _ _0[ v_m]\,E_ _ _0[ v_n]. (137) By introducing the vector ≜[1,2]⊤ v [ v_1,\, v_2 ] (138) and the centered (under the tilted measure) version thereof, ¯=−∇Λ(s1,s2), v= v-∇ (s_1,s_2), (139) from (137) we get the following representation for the Hessian matrix of the bivariate LMGF: ∇2Λ(s1,s2)=ℓ~θ0[¯t¯t⊤].∇^2 (s_1,s_2)=E_ _ _0 [ v_t\, v_t ]. (140) That is, the Hessian matrix is the covariance matrix of ¯t v_t. Now, it is known that the covariance matrix is positive definite unless the vector ¯t v_t has at least one deterministic component, or the two components are proportional. However, both cases are impossible in view of Lemma 1, and the strict convexity of Λ(s1,s2) (s_1,s_2) follows. ∎ Theorem 4 (Exponents for joint threshold crossing). Under Assumptions 1–3, consider the true hypothesis θ0 _0 and two other hypotheses θ1 _1 and θ2 _2 such that ℰ(θ0,θ1)=ℰ(θ0,θ2).E( _0, _1)=E( _0, _2). (141) Then,88 8 o(t)o(t) is a function satisfying the condition limt→∞o(t)/t=0 _t→∞o(t)/t=0. ℙ[k,t(θ0,θ1)≤0,k,t(θ0,θ2)≤0]=e−tℰ(θ0,θ1,θ2)+o(t),P [ β_k,t( _0, _1)≤ 0\,, β_k,t( _0, _2)≤ 0 ]=e^-tE( _0, _1, _2)+o(t), (142) with ℰ(θ0,θ1,θ2)>ℰ(θ0,θ1)E( _0, _1, _2)>E( _0, _1). Proof: We start by computing the error exponent for joint threshold crossing, ℰ(θ0,θ1,θ2)E( _0, _1, _2), which appears in (142). To this aim, we will apply the Gärtner-Ellis theorem [17, 18]. First, we need to introduce the bivariate LMGF of the scaled log belief ratios 1tk,t(θ0,θ1),1tk,t(θ0,θ2), 1t\, β_k,t( _0, _1), 1t\, β_k,t( _0, _2), (143) which is given by [17, 18] Λβ _β (s1,s2,θ0,θ1,θ2) (s_1,s_2; _0, _1, _2) ≜lnθ0exp(s1tk,t(θ0,θ1)+s2tk,t(θ0,θ2)). _ _0 ( s_1t\, β_k,t( _0, _1)+ s_2t\, β_k,t( _0, _2) ). (144) The Gärtner-Ellis theorem prescribes to compute the following limit value for the LMGF: limt→∞1tΛβ(s1t,s2t,θ0,θ1,θ2). _t→∞ 1t\, _β(s_1\,t,s_2\,t; _0, _1, _2). (145) Applying the definition of the log belief ratios in (11), we can write 1tΛβ(s1t,s2t,θ0,θ1,θ2) 1t\, _β(s_1\,t,s_2\,t; _0, _1, _2) =1t(s1lnπ(θ0)π(θ1)+s2lnπ(θ0)π(θ2)) = 1t (s_1\, π( _0)π( _1)+s_2\, π( _0)π( _2) ) +1tlnθ0e∑j=1K∑τ=1t−djk(s1j,τ(θ0,θ1)+s2j,τ(θ0,θ2)) + 1t _ _0\,e _j=1^K _τ=1^t-d_jk (s_1 λ_j,τ( _0, _1)+s_2 λ_j,τ( _0, _2) ) =1t(s1lnπ(θ0)π(θ1)+s2lnπ(θ0)π(θ2)) = 1t (s_1\, π( _0)π( _1)+s_2\, π( _0)π( _2) ) +1t∑j=1K∑τ=1t−djklnθ0exp(s1j,τ(θ0,θ1)+s2j,τ(θ0,θ2)), + 1t _j=1^K _τ=1^t-d_jk\!\! _ _0\! (s_1 λ_j,τ( _0, _1)+s_2 λ_j,τ( _0, _2) ), (146) where the last step follows from the independence over space and time. We remark that the expectations are finite in view of Assumption 3 and the Cauchy-Schwarz inequality for random variables. The first term on the RHS in (146) vanishes as t→∞t→∞. We focus next on the second term. Since the distances djkd_jk are finite, we can equivalently compute the limit of the quantity 1t∑j=1K∑τ=1tlnθ0exp(s1j,τ(θ0,θ1)+s2j,τ(θ0,θ2)) 1t _j=1^K _τ=1^t _ _0 (s_1 λ_j,τ( _0, _1)+s_2 λ_j,τ( _0, _2) ) =1t∑τ=1tlnθ0e∑j=1K(s1j,τ(θ0,θ1)+s2j,τ(θ0,θ2)) = 1t _τ=1^t _ _0e _j=1^K (s_1\, λ_j,τ( _0, _1)+s_2\, λ_j,τ( _0, _2) ) =1t∑τ=1tlnθ0exp(s1τ(θ0,θ1)+s2τ(θ0,θ2)) = 1t _τ=1^t _ _0 (s_1\, λ_τ( _0, _1)+s_2\, λ_τ( _0, _2) ) =1t∑τ=1tΛ(s1,s2,θ0,θ1,θ2)=Λ(s1,s2,θ0,θ1,θ2), = 1t _τ=1^t (s_1,s_2; _0, _1, _2)= (s_1,s_2; _0, _1, _2), (147) where: in the first equality we exploited the independence over space; in the second step we applied the definition the aggregate log likelihood ratios from (6); and in the third equality we used the definition of the bivariate LMGF for the aggregate log likelihood ratios from (128). Once the limiting LMGF in (145) exists, the Gärtner-Ellis theorem ensures the exponential behavior for the probability described by (142), with the following error exponent: ℰ(θ0,θ1,θ2)=infy1≤0,y2≤0Λ⋆(y1,y2,θ0,θ1,θ2),E( _0, _1, _2)= _y_1≤ 0,y_2≤ 0 (y_1,y_2; _0, _1, _2), (148) where Λ⋆(y1,y2,θ0,θ1,θ2) (y_1,y_2; _0, _1, _2) is the Fenchel-Legendre transform of Λ(s1,s2,θ0,θ1,θ2) (s_1,s_2; _0, _1, _2), defined as [17, 18]:99 9 We remark that the function in (149) is defined as an extended real number[17]. Λ⋆ (y1,y2,θ0,θ1,θ2)= (y_1,y_2; _0, _1, _2)= sups1,s2∈ℝ2[(s1y1+s2y2)−Λ(s1,s2,θ0,θ1,θ2)]. _s_1,s_2 ^2\, [(s_1y_1+s_2y_2)- (s_1,s_2; _0, _1, _2) ]. (149) From [17, Lemma 2.2.31], we know that the rate function is nonnegative, convex, and that Λ⋆(m1,m2,θ0,θ1,θ2)=0, (m_1,m_2; _0, _1, _2)=0, (150) where m1=θ0τ(θ0,θ1)>0,m2=θ0τ(θ0,θ2)>0.m_1=E_ _0 λ_τ( _0, _1)>0, m_2=E_ _0 λ_τ( _0, _2)>0. (151) (Recall that the positivity of the means follows from Assumption 2). To compute the error exponent in (148), we need to evaluate the infimum of the rate function over the region ℝ−2≜y1≤0,y2≤0R^2_- \y_1≤ 0,y_2≤ 0\. We now show that it is sufficient to focus on the boundary of this region, ∂ℝ−2=y1≤0,y2=0∪y1=0,y2≤0. ^2_-=\y_1≤ 0,y_2=0\∪\y_1=0,y_2≤ 0\. (152) Consider a point yoy^o internal to ℝ−2R^2_-, i.e., yo=[y1o,y2o]⊤∈ℝ−2∖∂ℝ−2y^o=[y^o_1,y^o_2] ^2_- ^2_-, and consider the boundary point y=[y1,y2]⊤∈∂ℝ−2y=[y_1,y_2] ∈ ^2_- that lies over the chord joining yoy^o to m=[m1,m2]⊤m=[m_1,m_2] . For some 0<α<10<α<1, the point y can be represented as y=αyo+(1−α)m.y=α\,y^o+(1-α)\,m. (153) From the convexity of Λ⋆(y1,y2,θ0,θ1,θ2) (y_1,y_2; _0, _1, _2), we have that Λ⋆(y1,y2,θ0,θ1,θ2) (y_1,y_2; _0, _1, _2) ≤αΛ⋆(y1o,y2o,θ0,θ1,θ2)+(1−α)Λ⋆(m1,m2,θ0,θ1,θ2)⏟=0 in view of (150) ≤α (y^o_1,y^o_2; _0, _1, _2)+(1-α) (m_1,m_2; _0, _1, _2)_=0 in view of eq:zerorate ≤Λ⋆(y1o,y2o,θ0,θ1,θ2), ≤ (y^o_1,y^o_2; _0, _1, _2), (154) where the last step follows from the fact that 0<α<10<α<1 and from the nonnegativity of the rate function. Using (154) in (148), we conclude that ℰ(θ0,θ1,θ2)=infy∈∂ℝ−2Λ⋆(y1,y2,θ0,θ1,θ2).E( _0, _1, _2)= _y∈ ^2_- (y_1,y_2; _0, _1, _2). (155) In [17, Lemma 2.2.31], it is also established that Λ⋆(y1,y2,θ0,θ1,θ2) (y_1,y_2; _0, _1, _2) is a “good” rate function. This means [17, p. 4] that its level sets are compact subsets of ℝ2R^2, which in turn implies that the function is coercive, namely, it diverges to +∞+∞ as ‖y‖→+∞\|y\|→+∞. As a result, the infimum is in fact a minimum attained at some point y∈∂ℝ−2y∈ ^2_-. Assume that the minimum is attained at [y¯1,0]⊤[ y_1,0] , for some y¯1≤0 y_1≤ 0 (the following arguments apply even in the complementary case where the minimum is attained at [0,y¯2]⊤[0, y_2] , for some y¯2≤0 y_2≤ 0). Then we can write ℰ(θ0,θ1,θ2) ( _0, _1, _2) =Λ⋆(y¯1,0,θ0,θ1,θ2) = ( y_1,0; _0, _1, _2) =sup(s1,s2)∈ℝ2[s1y¯1−Λ(s1,s2,θ0,θ1,θ2)] = _(s_1,s_2) ^2 [s_1\, y_1- (s_1,s_2; _0, _1, _2) ] ≥sups1∈ℝ[s1y¯1−Λ(s1,0,θ0,θ1,θ2)] ≥ _s_1 [s_1\, y_1- (s_1,0; _0, _1, _2) ] =sups1∈ℝ[s1y¯1−Λ(s1,θ0,θ1)]=Λ⋆(y¯1,θ0,θ1), = _s_1 [s_1\, y_1- (s_1; _0, _1) ]\!=\! ( y_1; _0, _1), (156) where the second-to-last step follows from the fact that the bivariate LMGF is equal to the univariate LMGF whenever one of the two arguments is zero, while the last step follows from the definition of the rate function in the univariate case. Since the univariate rate function Λ⋆(y1,θ0,θ1) (y_1; _0, _1) is minimized at m1>0m_1>0 [17, Lemma 2.2.5], if y¯1<0 y_1<0, the strict convexity of Λ⋆(y1,θ0,θ1) (y_1; _0, _1) [6, Lemma E.1] implies that Λ⋆(y¯1,θ0,θ1)>Λ⋆(0,θ0,θ1)=ℰ(θ0,θ1), ( y_1; _0, _1)> (0; _0, _1)=E( _0, _1), (157) and the claim of the theorem is proved. When y¯1=0 y_1=0, from (156), we know that sup(s1,s2)∈ℝ2[−Λ(s1,s2,θ0,θ1,θ2)] _(s_1,s_2) ^2 [- (s_1,s_2; _0, _1, _2) ] ≥sups1∈ℝ[−Λ(s1,θ0,θ1)] ≥ _s_1 [- (s_1; _0, _1) ] =ℰ(θ0,θ1). =E( _0, _1). (158) Recall that the univariate LMGF Λ(s1,θ0,θ1) (s_1; _0, _1) admits a unique minimizer s(θ0,θ1)s( _0, _1). Thus, if the relation in (158) were satisfied with equality, we would conclude that the function Λ(s1,s2,θ0,θ1,θ2) (s_1,s_2; _0, _1, _2) admits a minimum located at the point (s(θ0,θ1),0)(s( _0, _1),0). Similarly, since Λ(0,s2,θ0,θ1,θ2)=Λ(s2,θ0,θ2), (0,s_2; _0, _1, _2)= (s_2; _0, _2), (159) by exchanging s1s_1 with s2s_2 and θ1 _1 with θ2 _2 in (156), we have sup(s1,s2)∈ℝ2[−Λ(s1,s2,θ0,θ1,θ2)] _(s_1,s_2) ^2 [- (s_1,s_2; _0, _1, _2) ] ≥sups2∈ℝ[−Λ(s2,θ0,θ2)] ≥ _s_2 [- (s_2; _0, _2) ] =ℰ(θ0,θ2), =E( _0, _2), (160) and since ℰ(θ0,θ1)=ℰ(θ0,θ2)E( _0, _1)=E( _0, _2) by assumption, we would conclude that the bivariate LMGF has another minimizer located at the point (0,s(θ0,θ2))(0,s( _0, _2)), which is distinct from (s(θ0,θ1),0)(s( _0, _1),0) since both s(θ0,θ1)s( _0, _1) and s(θ0,θ2)s( _0, _2) are nonzero. On the other hand, the bivariate LMGF is strictly convex in view of Lemma 2, and, thus, it cannot have two distinct minimizers, which in turn implies that the equalities in (158) and (160) cannot hold, and the proof is complete. ∎ References [1] J. F. Chamberland and V. V. Veeravalli, “Decentralized detection in sensor networks,” IEEE Trans. Signal Process., vol. 51, no. 2, p. 407–416, Feb. 2003. [2] R. Viswanathan and P. K. Varshney, “Distributed detection with multiple sensors Part I. Fundamentals,” Proceedings of the IEEE, vol. 85, no. 1, p. 54–63, Jan. 1997. [3] R. S. Blum, S. A. Kassam, and H. V. Poor, “Distributed detection with multiple sensors I. Advanced topics,” Proceedings of the IEEE, vol. 85, no. 1, p. 64–79, Jan. 1997. [4] G. Mergen, V. Naware, and L. Tong, “Asymptotic detection performance of type-based multiple access over multiaccess fading channels,” IEEE Trans. Signal Process., vol. 55, no. 3, p. 1081–1092, Mar. 2007. [5] S. Marano, V. Matta, L. Tong, and P. Willett, “A likelihood-based multiple access for estimation in sensor networks,” IEEE Trans. Signal Process., vol. 55, no. 11, p. 5155–5166, Nov. 2007. [6] V. Matta, V. Bordignon, and A. H. Sayed, Social Learning: Opinion Formation and Decision-Making Over Graphs. Emerald Publishing, 2025. [7] V. Bordignon, V. Matta, and A. H. Sayed, “Socially intelligent networks: A framework for decision making over graphs,” IEEE Sig. Process. Mag., vol. 41, no. 4, p. 20–39, Jul. 2024. [8] X. Zhao and A. H. Sayed, “Learning over social networks via diffusion adaptation,” in Proc. Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, 2012, p. 709–713. [9] A. Jadbabaie, P. Molavi, A. Sandroni, and A. Tahbaz-Salehi, “Non-Bayesian social learning,” Games and Economic Behavior, vol. 76, no. 1, p. 210–225, Sep. 2012. [10] A. Lalitha, T. Javidi, and A. D. Sarwate, “Social learning and distributed hypothesis testing,” IEEE Trans. Inf. Theory, vol. 64, no. 9, p. 6161–6179, Sep. 2018. [11] A. Nedić, A. Olshevsky, and C. A. Uribe, “Fast convergence rates for distributed non-Bayesian learning,” IEEE Trans. Automat. Control, vol. 62, no. 11, p. 5538–5553, Nov. 2017. [12] P. Molavi, A. Tahbaz-Salehi, and A. Jadbabaie, “A theory of non-Bayesian social learning,” Econometrica, vol. 86, no. 2, p. 445–490, Mar. 2018. [13] D. Bajović, D. Jakovetic, J. M. F. Moura, J. Xavier, and B. Sinopoli, “Large deviations performance of consensus+innovations distributed detection with non-Gaussian observations,” IEEE Trans. Signal Process., vol. 60, no. 11, p. 5987–6002, Nov. 2012. [14] S. M. Kay, Fundamentals of Statistical Signal Processing: Detection Theory. Prentice Hall, NJ, 1998. [15] J. Chen and A. H. Sayed, “On the learning behavior of adaptive networks—Part I: Transient analysis,” IEEE Trans. Inf. Theory, vol. 61, no. 6, p. 3487–3517, Jun. 2015. [16] J. Chen and A. H. Sayed, “On the learning behavior of adaptive networks—Part I: Performance analysis,” IEEE Trans. Inf. Theory, vol. 61, no. 6, p. 3518–3548, Jun. 2015. [17] A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications. Springer, 2009. [18] F. den Hollander, Large Deviations. AMS, 2000. [19] B. Huang, I-H. Wang “On the price of decentralization in decentralized detection,” IEEE Trans. Inf. Theory, vol. 71, no. 4, p. 2341–2359, Apr. 2025. [20] F. Scala, M. Carpentiero, V. Matta and A. H. Sayed, “On the performance of social learning,” in Proc. EUSIPCO, Palermo, Italy, Sep. 2025, p. 1040–1044. [21] F. Scala, M. Carpentiero, V. Matta and A. H. Sayed, “Performance evaluation of social learning,” accepted for publication in IEEE Trans. Sig. Process., Jun. 2026, available online at arXiv:2606.09176 [cs.MA]. [22] T. M. Cover and J. A. Thomas, Elements of Information Theory. Wiley, 1991. [23] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 2012. [24] P. Erdős and A. Rényi, “On random graphs I,” Publicationes Mathematicae (Debrecen), vol. 6, p. 290–297, 1959. [25] B. Bollobás, Random Graphs. Cambridge University Press, 2001. [26] A. Fronczak, P. Fronczak, and J. A. Hołyst, “Average path length in random networks,” Phys. Rev. E, vol. 70, no. 056110, p. 056110-1–056110-7, 2004. [27] P. Billingsley, Probability and Measure. Wiley, 1995. [28] V. V. Petrov, Sums of Independent Random Variables. Springer, 1975. [29] W. Feller, An Introduction to Probability and Its Applications, vol. 2, Wiley, 1971. [30] J. Galambos and I. Simonelli, Bonferroni-Type Inequalities with Applications. Springer-Verlag, 1996.