Paper deep dive
Bregman Consensus
Andrei N. Soklakov
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 9/30/2026, 6:24:21 AM
Summary
The paper introduces 'Bregman Consensus', a nonlinear generalization of the linear DeGroot consensus model. It proposes an iterative algorithm where agents update their parameter estimates by moving to the weighted Bregman barycenter of all agents' views, with weights reflecting trust. The authors prove that this process converges to a unique consensus estimate, which is itself a Bregman barycenter weighted by the stationary distribution of the trust matrix. The work connects to quasi-arithmetic means and provides convergence rate analysis based on the second-largest eigenvalue of the trust matrix.
Entities (8)
Relation Signals (6)
Andrei N. Soklakov → authored → Bregman Consensus
confidence 99% · Bregman Consensus Andrei N. Soklakov
Bregman Consensus → uses → Bregman divergence
confidence 98% · The agents agree to use the same Bregman-type divergence to quantify disagreement... Each agent is happy to revise their estimate by moving to the weighted barycenter
Bregman Consensus → convergesto → Unique Consensus Estimate
confidence 97% · We show that such revisions naturally lead to an iterative algorithm which converges to a unique consensus estimate of the parameters.
Bregman Consensus → generalizes → DeGroot model
confidence 95% · It replaces the arithmetic average in DeGroot’s iteration with a Bregman barycenter... provides a geometric divergence-based nonlinear generalisation of the linear consensus model.
Bregman Consensus → relatedto → Quasi-arithmetic Means
confidence 92% · The present paper sits at the intersection of these traditions... provides a partial generalisation of Matkowski’s convergence result to the case of non-scalar means
Bregman Consensus → similarmechanismto → PageRank
confidence 85% · the same mechanism underlies the PageRank algorithm for web ranking
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Consider a community of agents who are seeking consensus on a set of parameters. The agents agree to use the same Bregman-type divergence to quantify disagreement between their individual estimates of the parameters but have varying confidence in each other's abilities. Each agent is happy to revise their estimate by moving to the weighted barycenter of all individual estimates with higher weights applied to more trusted agents. We show that such revisions naturally lead to an iterative algorithm which converges to a unique consensus estimate of the parameters. Furthermore, since the consensus estimate is itself a barycenter with computable weights, the group emerges as a collective super-agent with a well-formed opinion regarding the ability of each individual agent.
Tags
Links
- Source: https://arxiv.org/abs/2609.35930v1
- Canonical: https://arxiv.org/abs/2609.35930v1
Trouble viewing inline? Open PDF directly →
Full Text
17,043 characters extracted from source content.
Expand or collapse full text
Bregman Consensus Andrei N. Soklakov Note: Andrei.Soklakov@gmail.com Consider a community of agents who are seeking consensus on a set of parameters. The agents agree to use the same Bregman-type divergence to quantify disagreement between their individual estimates of the parameters but have varying confidence in each other’s abilities. Each agent is happy to revise their estimate by moving to the weighted barycenter of all individual estimates with higher weights applied to more trusted agents. We show that such revisions naturally lead to an iterative algorithm which converges to a unique consensus estimate of the parameters. Furthermore, since the consensus estimate is itself a barycenter with computable weights, the group emerges as a collective super-agent with a well-formed opinion regarding the ability of each individual agent. 1 Introduction Information aggregation from multiple sources is an incredibly rich field with many practical applications. The mathematical roots of the problem lie in two distinct traditions. In the statistical literature, DeGroot [4] considered a group of agents who repeatedly update their estimates as a weighted arithmetic average of the group’s previous estimates to achieve consensus. This linear consensus framework has since become a standard tool in distributed averaging and opinion dynamics. In parallel, the theory of quasi-arithmetic means, developed independently by Kolmogorov [8], Nagumo [10], and de Finetti [3], characterized the class of scalar means that can be written as Mf(x1,…,xN)=f−1(∑iwif(xi))M_f(x_1,…,x_N)=f^-1( _iw_if(x_i)) for a continuous strictly monotone function f. Matkowski [9] extended this to iterations of mean-type mappings, proving convergence to invariant scalar means. The present paper sits at the intersection of these traditions. It replaces the arithmetic average in DeGroot’s iteration with a Bregman barycenter, so that agents with varying trust in one another’s abilities converge to a consensus that is itself a weighted Bregman barycenter of the initial estimates. In doing so, it provides a geometric divergence-based nonlinear generalisation of the linear consensus model. At the same time, it provides a partial generalisation of Matkowski’s convergence result to the case of non-scalar means [11] by providing a concrete analytical example. We use the rest of this introduction to fix basic notation by recalling the classic notion of Bregman barycenters. Section 2 introduces center-seeking agents and provides the main theorem regarding the collective evolution of such agents towards a unique consensus. In Section 3 we look at the emergent group behaviour as a whole. In Section 4 we estimate the speed of convergence. Finally, we discuss the connection to the theory of generalised means in Section 5. Let x be a d-dimensional vector of parameters and let ⊂ℝdX ^d be an open convex set containing all possible values of x. The Bregman divergence [1] between two vectors x and ′ x is defined as DF(,′)=F()−F(′)−⟨−′,∇F(′)⟩,D_F( x, x )=F( x)-F( x )- x- x ,∇ F( x ) \,, (1) where F:→ℝF:X is a strictly convex differentiable function. We furthermore require that the gradient map ∇F:→∇ F:X is a homeomorphism onto an open convex set ⊂ℝdY ^d. Given a list of N vectors 1:N=(1,2,…,N) x_1:N=( x_1, x_2,…, x_N) and a corresponding list of positive weights w1:N=(w1,w2,…,wN)w_1:N=(w_1,w_2,…,w_N) such that ∑i=1Nwi=1 _i=1^Nw_i=1, the (left) Bregman barycenter, ¯ x, is defined as ¯(1:N,w1:N)=argmin∑i=1NwiDF(,i). x( x_1:N,w_1:N)= _ x _i=1^Nw_iD_F( x, x_i)\,. (2) This optimisation problem is easy to solve analytically with the result ¯(1:N,w1:N)=∇F−1(∑i=1Nwi∇F(i)), x( x_1:N,w_1:N)=∇ F^-1 ( _i=1^Nw_i∇ F( x_i) )\,, (3) where ∇F−1∇ F^-1 is the inverse of the gradient map ∇F∇ F. 2 Center-seeking agents Definition 1 (centripetal agent). Consider a group of N agents with individual views given by the list 1:N x_1:N of vectors from X. We shall call an agent centripetal for the group if she is always willing to change her view to the barycenter ¯(1:N,w1:N) x( x_1:N,w_1:N). The weights w1:Nw_1:N allow the centripetal agent to express the varying confidence she may have in the abilities of each individual member of the group. Theorem 1. Consider a group of N centripetal agents with views 1:N x_1:N. The agents’ weights can be arranged into a square row-stochastic matrix W=(wij),wij>0,∑j=1Nwij=1foralli.W=(w_ij),\ w_ij>0,\ _j=1^Nw_ij=1\ for\ all\ i. (4) The group engages in an iterative procedure in which all views are published, then each agent updates their individual view in light of the published information, and the process repeats. The group iteratively converges to a unique consensus view ¯ x which is given by ¯=∇F−1(∑i=1Nπi∇F(i)), x=∇ F^-1 ( _i=1^N _i∇ F( x_i) )\,, (5) where π=(π1,…,πN)π=( _1,…, _N) is the stationary distribution of W, that is πW=π,∑j=1Nπj=1,πj>0.π W=π, _j=1^N _j=1, _j>0. (6) Proof. Let 1:N(k) x_1:N^(k) be the list of views for all N agents after the k-th iteration starting from 1:N(0)=1:N x_1:N^(0)= x_1:N. The i-th agent computes i(k+1)=argmin∑j=1NwijDF(,j(k)). x_i^(k+1)= _ x _j=1^Nw_ijD_F( x, x_j^(k))\,. (7) The corresponding analytic solution i(k+1)=∇F−1(∑j=1Nwij∇F(j(k))). x_i^(k+1)=∇ F^-1 ( _j=1^Nw_ij∇ F( x_j^(k)) )\,. (8) By applying ∇F∇ F to both sides of this equation and introducing i(k)=∇F(i(k)) y_i^(k)=∇ F( x_i^(k)) (9) we obtain i(k+1)=∑j=1Nwijj(k), y_i^(k+1)= _j=1^Nw_ij y_j^(k)\,, (10) and therefore i(k)=∑j=1N(Wk)ijj(0). y_i^(k)= _j=1^N(W^k)_ij y_j^(0)\,. (11) Since W is row-stochastic and positive, it is primitive. By the Perron-Frobenius theorem [7], W has a simple eigenvalue 1 and all other eigenvalues have modulus strictly smaller than 1. Moreover, the powers of W converge limk→∞(Wk)ij=πj, _k→∞(W^k)_ij= _j\,, (12) where π=(π1,π2,…,πN)π=( _1, _2,…, _N) is the unique stationary row vector satisfying πW=π,∑j=1Nπj=1,πj>0.π W=π, _j=1^N _j=1, _j>0. (13) Since ∇F−1∇ F^-1 is continuous, Eqs. (9), (11) and (12) imply limk→∞i(k)=∇F−1(∑j=1Nπj∇F(j(0))). _k→∞ x_i^(k)=∇ F^-1 ( _j=1^N _j∇ F( x^(0)_j) )\,. (14) Note that the right-hand side of this equation does not depend on i and so all agents converge to the same consensus view (5). ∎ The above proof only requires W to be primitive. The positivity requirement, wij>0w_ij>0, in the statement of the theorem is unnecessarily restrictive. The purpose of that is entirely pedagogical, to make the theorem more intuitive in the first reading. 3 Emergence of the group agent We see that the emergent net behaviour of the group converges to that of a single centripetal agent who compiles her view ¯ x as the barycenter ¯=argmin∑i=1NπiDF(,i). x= _ x _i=1^N _iD_F( x, x_i)\,. (15) While this collective agent does not belong to the original group, she behaves as if she had an opinion regarding the relative abilities of each individual agent. This collective opinion is represented by the stationary vector of weights π. This happens even when the individual agents are operating completely autonomously and keep their confidence weights private. 4 Performance In the case where the number of agents is small, a hypothetical central planner who knows the individual views and confidence weights would be able to compute the emergent group consensus using Eqs. (5) and (6). The complexity of doing so is dominated by finding the left eigenvector of W which takes O(N3)O(N^3) operations in general. When the agents do not share their confidence weights, or when the number of agents is too large to be processed as a group, we can compute the group’s consensus by implementing the iterative procedure (7). In the rest of this section we estimate the complexity of this approach. Before we calculate the complexity of the iterative algorithm, we should note that the Perron-Frobenius convergence mechanism (12) is used in a great variety of applications. Besides the already mentioned linear DeGroot’s model [4], the same mechanism underlies the PageRank algorithm for web ranking [2], the Friedkin-Johnsen model of opinion dynamics with stubborn agents [5], average-consensus algorithms in distributed multi-agent control [12], and Markov chain Monte Carlo methods [6], among many others. In each case, the asymptotic rate of convergence is derived from that of (12), which depends on the second-largest eigenvalue of the iteration matrix W [7]. Because our framework includes the classical linear consensus model as a special case11 1 Consider F()=∥22F( x)= x ^2_2., we start the convergence analysis in the same vein until we encounter and handle the nonlinearity. By Theorem 8.5.1 from [7], for any W as defined by Eq. (4) and for any sufficiently small ϵ>0ε>0 there exists a constant C=C(W,ϵ)C=C(W,ε) such that ∥Wk−P∥∞≤C(|λ2|+ϵ)kforallk=1,2,…, W^k-P _∞≤ C(| _2|+ε)^k\ \ for\ all\ k=1,2,…, (16) where Pij=πjP_ij= _j and |λ2|<1| _2|<1 is the modulus of the second-largest eigenvalue of W. Let us assemble the N iterates i(k) y_i^(k) defined by Eq. (9) into a matrix Yk∈ℝN×dY_k ^N× d. In this notation, Eq. (11) becomes Yk=WkY0Y_k=W^kY_0, and we compute ∥Yk−Y∞∥∞ Y_k-Y_∞ _∞ =∥(Wk−P)Y0∥∞≤∥Wk−P∥∞∥Y0∥∞ = (W^k-P)Y_0 _∞≤ W^k-P _∞ Y_0 _∞ (17) ≤C(|λ2|+ϵ)k∥Y0∥∞forallk=1,2,…. ≤ C(| _2|+ε)^k Y_0 _∞\ \ for\ all\ k=1,2,…. (18) For simplicity, let us focus on dynamics away from the boundary ∂ , i.e., we assume that the agents’ initial estimates 1:N x_1:N, the subsequent iterations (k)1:N x^(k)_1:N and the consensus ¯ x lie in a compact convex ⊂K . Furthermore, let us assume that the Hessian ∇2F∇^2F is continuous on K. Let m_K be the smallest eigenvalue of ∇2F∇^2F on K m=min∈λmin(∇2F()).m_K= _ x _ (∇^2F( x) )\,. (19) Because F is strictly convex, ∇2F()∇^2F( x) is positive definite for every ∈ x . Furthermore, since K is compact and ∇2F∇^2F is continuous on K, the minimum eigenvalue is attained and is strictly positive m>0m_K>0. Consider a pair of vectors ,′∈ x, x , ≠′ x≠ x . Since K is convex, any such pair defines a linear segment [,′]=+t(′−)|t∈(0,1)⊂[ x, x ]=\ x+t( x - x)|t∈(0,1)\ . By the mean value theorem one can find a point ∈[,′] c∈[ x, x ] such that ⟨−′,∇F()−∇F(′)⟩ x- x ,∇ F( x)-∇ F( x ) =⟨−′,∇2F()(−′)⟩ = x- x ,∇^2F( c)( x- x ) (20) ≥m∥−′∥22. ≥ m_K x- x _2^2\,. (21) At the same time, by Cauchy-Schwarz inequality, ⟨−′,∇F()−∇F(′)⟩≤∥−′∥2⋅∥∇F()−∇F(′)∥2, x- x ,∇ F( x)-∇ F( x ) ≤ x- x _2· ∇ F( x)-∇ F( x ) _2\,, (22) and therefore m∥−′∥2≤∥∇F()−∇F(′)∥2.m_K x- x _2≤ ∇ F( x)-∇ F( x ) _2\,. (23) Applying this to the iterates (9) ∥ik−¯∥2≤∥ik−¯∥2/m, x_i^k- x _2≤ y_i^k- y _2/m_K\,, (24) where ¯=∇F(¯) y=∇ F( x). We can now combine this with Eq. (18). Because the L2L_2 norm of a single row is always smaller or equal to the infinity norm of an entire matrix, and noticing that ¯=∑j=1Nπjj(0) y= _j=1^N _j y_j^(0), ∥ik−¯∥2≤C′(|λ2|+ϵ)kforallk=1,2,…, x_i^k- x _2≤ C (| _2|+ε)^k\ \ for\ all\ k=1,2,…, (25) where C′C is a constant. We see a classic convergence pattern, where each agent rapidly converges to the consensus with the convergence rate determined by the magnitude of the second-largest eigenvalue of W. Since evaluating ∇F∇ F does not depend on N, a single iteration (8) would cost each agent O(N)O(N), and the overall effort for each agent is O(Nlnϵ2/ln|λ2|)O(N _2/ | _2|) where ϵ2 _2 is the maximum acceptable error in the L2L_2 norm. 5 Non-scalar means Let ⊆ℝI be an interval. A scalar mean is defined as a function M:N→M:I^N such that for all x1:N∈Nx_1:N ^N min(x1,…,xN)≤M(x1:N)≤max(x1,…,xN). (x_1,…,x_N)≤ M(x_1:N)≤ (x_1,…,x_N)\,. (26) N such means, M1,…,MNM_1,…,M_N, define an iterative mean-type mapping Mi,kM_i,k on the cube NI^N as follows. For the first iteration Mi,1=Mi,i=1,2,…,N,M_i,1=M_i,\ \ \ i=1,2,…,N\,, (27) and for all subsequent iterations Mi,k+1=Mi(M1,k(x1:N),…,MN,k(x1:N)).M_i,k+1=M_i(M_1,k(x_1:N),…,M_N,k(x_1:N)). (28) Matkowski [9] proved that under some natural conditions the iterations converge limk→∞Mi,k(x1:N)=A(x1:N), _k→∞M_i,k(x_1:N)=A(x_1:N)\,, (29) where the mean A is often called invariant under the mapping (27,28) as it stops responding to subsequent iterations. The structure of Eq. (3) bears a striking resemblance to that of the scalar quasi-arithmetic means [8, 10, 3] except, of course, 1:N x_1:N are not scalars. This observation motivated Nielsen [11] to extend the definition of the quasi-arithmetic mean to non-scalar types, such as M∇F(1:N,w1:N)=∇F−1(∑i=1Nwi∇F(i)).M_∇ F( x_1:N,w_1:N)=∇ F^-1 ( _i=1^Nw_i∇ F( x_i) )\,. (30) We recognize our result as a constructive generalization of Matkowski’s convergence theorems to the non-scalar mean (30) with Eq. (14) being a direct analogue of Eq. (29). References [1] L. M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200–217, 1967. [2] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks and ISDN Systems, 30(1-7):107–117, 1998. [3] B. deFinetti. Sul concetto di media. Giornale dell’Instituto, Italiano degli Attuari, 2(3):369–396, 1931. [4] M. H. DeGroot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118–121, 1974. [5] N. E. Friedkin and E. C. Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193–206, 1990. [6] W. R. Gilks, S. Richardson, and D. J. Spiegelhalter, editors. Markov Chain Monte Carlo in Practice. Chapman & Hall, London, 1996. [7] R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge University Press, Cambridge, 1985. [8] A. N. Kolmogorov. Sur la notion de la moyenne. Rend. Accad. dei Lincei, 12(6):388–391, 1930. [9] J. Matkowski. Iterations of mean-type mappings and invariant means. Annales Mathematicae Silesianae, 13:211–226, 1999. [10] M. Nagumo. Über eine klasse der mittelwerte. Jap. Jour. of Math., 7:71–79, 1930. [11] F. Nielsen. Beyond scalar quasi-arithmetic means: Quasi-arithmetic averages and quasi-arithmetic mixtures in information geometry, 2023. arXiv.org/abs/2301.10980. [12] R. Olfati-Saber, J. A. Fax, and R. M. Murray. Consensus and cooperation in networked multi-agent systems. Proceedings of the IEEE, 95(1):215–233, 2007.