Geometric interpolation conjecture for EXTRA performance guarantees

Let Exκ1,κ2(K,θ)E_{x}^{\kappa_1,\kappa_2}(\mathcal{K},\theta) denote the performance guarantee after K\mathcal{K} iterations of EXTRA with θN\theta \mathcal{N} agents whose local functions belong to Fμ1,L\mathcal{F}_{\mu_1,L} and (1θ)N(1-\theta)\mathcal{N} agents whose local functions belong to Fμ2,L\mathcal{F}_{\mu_2,L}, where θ[0,1]\theta\in[0,1]. Let Exκ1(K)E_{x}^{\kappa_1}(\mathcal{K}) and Exκ2(K)E_{x}^{\kappa_2}(\mathcal{K}) denote the worst-case errors after K\mathcal{K} iterations of EXTRA when all local functions have uniform conditioning, with κ1=L/μ1\kappa_1=L/\mu_1 and κ2=L/μ2\kappa_2=L/\mu_2. By definition,

Exκ1(K)=Exκ1,κ2(K,1),Exκ2(K)=Exκ1,κ2(K,0).E_{x}^{\kappa_1}(\mathcal{K})=E_{x}^{\kappa_1,\kappa_2}(\mathcal{K},1),\qquad E_{x}^{\kappa_2}(\mathcal{K})=E_{x}^{\kappa_1,\kappa_2}(\mathcal{K},0).

Geometric interpolation conjecture. For all K>0\mathcal{K}>0, κ1,κ2>0\kappa_1,\kappa_2>0, and θ[0,1]\theta\in[0,1], the mixed-conditioning performance satisfies

Exκ1,κ2(K,θ)=(Exκ1(K))θ(Exκ2(K))1θ.E_{x}^{\kappa_1,\kappa_2}(\mathcal{K},\theta)=\bigl(E_{x}^{\kappa_1}(\mathcal{K})\bigr)^{\theta}\bigl(E_{x}^{\kappa_2}(\mathcal{K})\bigr)^{1-\theta}.

The conjecture proposes that the performance with two equivalence classes of agents is the geometric interpolation of the uniform-conditioning worst-case errors. The surrounding experiment suggests that the guarantee depends on the relative proportions of the two classes rather than on the total number of agents, but the source provides no resolution of this conjecture.

Sources & referencesView supporting material

Primary source

Sebastien Colla and Julien M. Hendrickx, “Exploiting Agent Symmetries for Performance Analysis of Distributed Optimization Methods”, arXiv:2403.11724 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.