Home / Curated / Algorithms / L2GD (Loopless Local Gradient Descent for Mixture Federated Learning)

L2GD (Loopless Local Gradient Descent for Mixture Federated Learning)

Algorithms AIMech:L2gdLooplessLocalGradientDescentForMixtureFederatedLearning DRAFT

Aliases: L2GD, Loopless Local Gradient Descent, Mixture Federated Learning with L2GD

A personalized federated optimization formulation and randomized loopless algorithm (Hanzely & Richtarik 2020, Section 2, Equation 2; Section 4, Algorithm 1, Equations 14-15) that minimizes the penalized mixture objective min_{x_1, ..., x_n in R^d} F(x) = (1/n) sum_{i=1}^n f_i(x_i) + (lambda / (2 n)) sum_{i=1}^n ||x_i - bar_x||^2 (where bar_x = (1/n) sum_{i=1}^n x_i) by flipping a coin xi_k ~ Bernoulli(p) at each iteration k: with probability 1 - p (xi_k = 0), every client i performs a purely local gradient step x_i^{k+1} = x_i^k - (alpha / (1 - p)) nabla f_i(x_i^k); with probability p (xi_k = 1), the server computes bar_x^k and every client takes an averaging-contraction step x_i^{k+1} = (1 - alpha lambda / p) x_i^k + (alpha lambda / p) bar_x^k.

Identity Notes & Concept Scope Distinct from pFedMe (AIMech:PFedMePersonalizedFederatedLearningWithMoreauEnvelopes, T. Dinh et al. 2020), which solves nested bi-level Moreau envelope subproblems at every local step using an auxiliary global variable w, and from Local SGD / FedAvg (AIMech:FederatedAveraging, McMahan et al. 2017), which forces full consensus x_1 = ... = x_n (the lambda -> infinity limit) and suffers O(alpha) bias on heterogeneous objectives, whereas L2GD is an unbiased variance-reduced stochastic solver on the two-term sum F(x) = f(x) + lambda psi(x) that converges linearly to the exact mixture optimum x^*(lambda) for any constant step size.

Claims & Grounded Evidence

4 Claims

Mechanism #r445-exact-kkt-gradient-average-identity-and-spectrum-interpolation

For every penalty parameter lambda in (0, infinity), the unique minimizer x^*(lambda) = (x_1^*(lambda), ..., x_n^*(lambda)) of F(x) = f(x) + lambda psi(x) satisfies nabla f_i(x_i^*(lambda)) + lambda(x_i^*(lambda) - bar_x^*(lambda)) = 0 and therefore the exact zero-sum gradient identity (1/n) sum_{i=1}^n nabla f_i(x_i^*(lambda)) = 0 (Theorem 3.2, Eq. 5), while interpolating monotonically between purely local training at lambda = 0 (Theorem 3.1) and the classical consensus global optimum x^*(lambda) -> 1 x^* with x_i^*(lambda) - bar_x^*(lambda) = -(1/lambda) nabla f_i(x^*) + o(1/lambda) as lambda -> infinity (Theorem 3.5).

supports Source: Federated Learning of a Mixture of Global and Local Models · Locator: Section 3 Properties of the Optimal Solution (Theorems 3.1-3.5, Equations 4-9), pp. 4-6

Mechanism #r445-unbiased-two-summand-sgd-equivalence-and-optimal-communication-probability

Interpreting F(x) = f(x) + lambda psi(x) as a two-summand finite sum and sampling G(x^k) = nabla f(x^k) / (1 - p) with probability 1 - p and lambda nabla psi(x^k) / p with probability p makes G(x^k) an unbiased estimator E[G(x^k) | x^k] = nabla F(x^k) (Section 4.1, Eq. 13); applying control variates (L2GD+) or non-uniform sampling achieves global linear convergence O(max(L / ((1 - p) mu), lambda / (p mu)) log(1/epsilon)) where the optimal communication probability p^* = lambda / (lambda + L) minimizes expected communication rounds to O((lambda L / (lambda + L)) / mu * log(1/epsilon)) (Theorems 4.4, 5.2, and Corollary 4.5).

supports Source: Federated Learning of a Mixture of Global and Local Models · Locator: Section 4.1-4.3 Convergence of L2GD (Equations 13-17, Theorem 4.4, Corollary 4.5) & Section 5 Variance Reduced L2GD+ (Theorem 5.2), pp. 6-12

Limitation #r445-variance-floor-without-control-variates-and-strong-convexity-limitation

Because nabla f_i(x_i^*(lambda)) = -lambda(x_i^*(lambda) - bar_x^*(lambda)) != 0 whenever client optima differ and lambda > 0, vanilla L2GD with constant step size alpha converges to an O(alpha sigma_*^2) neighborhood of x^*(lambda) unless diminishing step sizes or the variance-reduced control-variate extension L2GD+ (Section 5) are used.

supports Source: Federated Learning of a Mixture of Global and Local Models · Locator: Section 4.3 Theorem 4.4 Neighborhood Analysis & Section 5 L2GD+ with Control Variates, pp. 8-11

Application #r445-personalized-l2-regularized-logistic-regression-federated-application

Applied to personalized federated l_2-regularized logistic regression across heterogeneous LIBSVM client datasets (a1a, mushrooms, madelon, phishing), reducing communication rounds relative to full-consensus gradient descent as heterogeneity increases.

supports Source: Federated Learning of a Mixture of Global and Local Models · Locator: Section 6 Experiments (Figures 1-4), pp. 13-15

⚠️ Curated Limitations & Negative Results

Linear convergence guarantees require mu-strongly convex and L-smooth local objectives f_i.
Exact convergence with constant step size requires maintaining control variates (L2GD+).

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:FederatedLearning` Federated Learning	narrow_match	L2GD formulates and solves personalized federated learning as a quadratically coupled mixture of local and global models with randomized loopless communication.
`AIO:LogisticRegression` Logistic Regression	related_match	Evaluated on personalized federated l_2-regularized logistic classification.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r445-primary-pdf`	Federated Learning of a Mixture of Global and Local Models Filip Hanzely, Peter Richtarik	primary paper full_text	ID: https://arxiv.org/abs/2002.05516 sha256:20107b7a9e9b…
`r445-arxiv-abs`	Federated Learning of a Mixture of Global and Local Models (arXiv abstract) Filip Hanzely, Peter Richtarik	primary paper abstract_only	ID: https://arxiv.org/abs/2002.05516 sha256:f1b9b1e06e9c…
`r445-metadata-cr`	Federated Learning of a Mixture of Global and Local Models (Crossref metadata) Filip Hanzely, Peter Richtarik	primary paper abstract_only	ID: https://arxiv.org/abs/2002.05516 sha256:985ae86e7cc1…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T08:48:00Z

Updated: 2026-10-19T08:48:00Z

Source File: data/curated/L2gdLooplessLocalGradientDescentForMixtureFederatedLearning.yaml · Schema: curated_concept.yaml

Explore across X-Mech

Related computational & biological Mechs: Embedding Map Network Graph ProteinTraitsMech (ESM-2 pLM) DUFMech (Domain pLM) TraitMech CultureMech All 14 X-Mech Repositories