Introduction
Federated learning (FL) provides a collaborative training paradigm in which multiple clients jointly learn a global model without sharing their raw data, thereby preserving data privacy while leveraging distributed data resources [31 , 3 ] (Li et al. 2020a). A typical FL algorithm involves iterative rounds of local training followed by aggregating updates via node-to-center communications. When FL is applied to real-time systems, e.g., low-earth orbit (LEO) satellite constellations [4 ] , it is critical that the FL algorithm design aligns well with the system constraints, such as limited connection bandwidth/windows and high communication latency. Therefore, a successful FL framework must be communication-efficient and tolerate low aggregation frequency. Despite its empirical success in large-scale applications, most existing FL algorithms (e.g., [22 , 23 , 39 ] (Li et al. 2020b)), are designed within a frequentist framework and focus on point estimation, which makes it difficult to quantify uncertainty in model predictions and parameters. Bayesian federated learning (BFL) addresses this limitation by inferring the full posterior, thus enabling principled uncertainty quantification and robust decision-making under data heterogeneity and limited local samples. However, scalable Bayesian FL inference remains challenging due to multiple factors: (i) high-dimensional parameter spaces, (ii) heterogeneous and potentially non-IID client data, and (iii) strict communication and privacy constraints.
Hamiltonian Monte Carlo (HMC, Duane et al. [10 ] ; Neal [35 ] ) is a MCMC method for sampling from complex posteriors, which exploits gradient information and an auxiliary momentum variable to construct proposals that can efficiently explore high-dimensional distributions. Compared with first-order methods such as stochastic gradient Langevin dynamics (SGLD, Welling & Teh [41 ] ; Sato & Nakagawa [37 ] ), HMC and its stochastic variants often achieve superior mixing and lower asymptotic variance but its second-order nature also makes theoretical analysis and distributed implementation more involved. Extending HMC to the federated setting is nontrivial, because naive combinations of stochastic HMC with FedAvg-style aggregation (McMahan et al., [31 ] ) can easily suffer from bias accumulation, instability of global dynamics, and inefficient communication.
To address these challenges, recent work proposes the Federated Averaging stochastic Hamiltonian Monte Carlo (FA-HMC, Liang et al. [26 ] ) algorithm, which integrates stochastic HMC updates on local clients with periodic aggregation of both positions and momenta at a central server. Liang et al. [26 ] showed that FA-HMC requires O ( d / ϵ ) O(\sqrt{d}/\epsilon) O ( d / ϵ ) communication cost (equivalently, O ( d / ϵ ) O(\sqrt{d}/\epsilon) O ( d / ϵ ) updates occur in the center node) to achieve ϵ \epsilon ϵ Wasserstein sampling error. In contrast, under non-distributed settings, HMC achieves a tight O ( ( d / ϵ 2 ) 1 / 4 ) O((d/\epsilon^{2})^{1/4}) O (( d / ϵ 2 ) 1/4 ) gradient computation cost (Mangoubi & Vishnoi, [30 ] ). It naturally leads to the question: can we further close the gap between the communication cost in FL paradigm and the computation cost in the non-FL paradigm, in terms of the dimension dependency?
This work introduces an adaptive variant, Adaptive Federated Hamiltonian Monte Carlo (AFHMC), which incorporates surrogate leapfrog steps and an additional global shift vector to better align local and global dynamics. We conduct refine analysis which explicitly characterizes the discrepancy between surrogate and exact leapfrog dynamics, and establish non-asymptotic convergence guarantees under standard smoothness and strong convexity assumptions. AFHMC can achieve improved dependence on the number of clients, communication rounds, and stochastic gradient noise level, and our experiments demonstrate competitive or superior performance compared with existing Bayesian federated baselines.
Related Works and Our Contributions
Federated optimization Early studies, such as FedAvg (McMahan et al., [31 ] ), established convergence guarantees for smooth and strongly convex objectives, typically achieving sublinear rates in the presence of data heterogeneity. To address this challenge, subsequent work introduced variance reduction and control variate techniques, such as SCAFFOLD (Karimireddy et al., [20 ] ) and its variants, which improve convergence by mitigating client drift and reducing bias induced by heterogeneous local updates. In particular, Mitra et al. [33 ] provided the first result establishing linear convergence rates in terms of communication complexity using control variates, while Mishchenko et al. [32 ] further advanced this line of research by proposing randomized algorithms that achieve constant communication complexity under suitable conditions.
Bayesian federated learning. Bayesian extensions of federated learning aim to characterize posterior uncertainty over model parameters or predictions while respecting client-level privacy and communication constraints. Existing approaches include variational Bayes formulations (e.g., Zhang et al., [43 ] ; Guo et al., [16 ] ), hierarchical Bayesian models for heterogeneous clients (e.g., Vedadi et al., [38 ] ; Kim & Hospedales, [21 ] ), and Bayesian variants of federated averaging where each client maintains local posterior approximations that are periodically aggregated (e.g., Al-Shedivat et al., [2 ] ; Chen & Chao, [5 ] ; Liu et al., [27 ] ). These methods often rely on factorized approximations or conjugate priors to keep the communication and computation overhead manageable.Our work instead targets exact (or asymptotically exact) MCMC-based Bayesian inference in federated environments, and develops HMC-based algorithms that can operate under realistic communication budgets.
HMC and stochastic variants. HMC is an efficient sampler for complex high-dimensional Bayesian inference, with rigorous guarantees on convergence and mixing under smoothness and curvature conditions of the target distribution (Durmus et al., [12 ] ; Mangoubi & Smith, [28 , 29 ] ). To scale HMC to large datasets, stochastic gradient HMC (SGHMC Chen et al. [6 ] ) utilizes mini-batch estimates, typically introducing extra friction or correction terms to control the additional stochastic noise. Subsequent works have investigated the convergence behavior of SGHMC (Zou & Gu, [45 ] ), variance-reduction techniques (Zou et al., [46 ] ), low-precision sampling techniques (Wang et al., [40 ] ) and etc. These developments, however, are primarily designed for centralized settings, and their direct application to federated learning is hindered by client heterogeneity and limited access to the full dataset.
Adaptive and geometry-aware HMC. A line of research has explored adaptive HMC schemes that adjust hyperparameters such as step sizes, mass matrices, and integrator structures using information gathered during sampling. Examples include Hoffman & Gelman [19 ] ; Hoffman et al. [18 ] ; Hirt et al. [17 ] ; Fernández-Pendás et al. [14 ] ; Girolami & Calderhead [15 ] , all aiming to enhance stability and sampling efficiency in complex geometries. More recently, adaptive tuning strategies have been proposed to automatically select splitting integrators and hyperparameter ranges for (generalized) HMC, reducing reliance on heuristic tuning in practice [1 , 34 ] . Our AFHMC algorithm is conceptually related to these works in that it uses a surrogate Hamiltonian flow informed by global information, but it is tailored to the federated setting, where the adaptation must be communication-efficient and robust to client heterogeneity.
Beyond existing results, the main contributions of this paper are summarized as follows:
We propose AFHMC, an adaptive HMC algorithm for FL tasks based on surrogate leapfrog updates. The new algorithm introduces a global drift control variate to address the heterogeneity among local gradient update trajectories.
We introduce a principled framework to analyze divergence errors induced by approximate Hamiltonian dynamics.
Under strong convexity, we derive non-asymptotic error bounds that quantify the interplay between the surrogate leapfrog integrator and data heterogeneity. In particular, we prove that AFHMC achieves O ( { d / ϵ 2 } 1 / 3 ) O(\{d/\epsilon^2\}^{1/3}) O ({ d / ϵ 2 } 1/3 ) communication cost under extreme heterogeneity, and O ( log ( d / ϵ 2 ) ) O(\log(d/\epsilon^2)) O ( log ( d / ϵ 2 )) communication cost under low heterogeneity. To the best of our knowledge, both rates of communication complexity have never been achieved by prior federated sampling algorithms. Not only do we obtain a better communication rate, but we also don’t rely on stringent Hessian smoothness conditions that are commonly required to achieve an advanced rate (e.g., Liang et al. [26 ] ; Mangoubi & Vishnoi [30 ] ; Plassier et al. [36 ] ). Please refer to Table 1 for a comprehensive comparison against prior theoretical works. Note that if we indeed enforce an extra Hessian smoothness condition, we could technically obtain even better results.
Table 1. Comparison of Bayesian theoretical results: requires assumptions, rate of communication and rate of gradient computation to achieve ϵ \epsilon ϵ Wasserstein convergence
We empirically demonstrate that the proposed method achieves improved computational efficiency and stability in distributed and approximate-gradient settings.
Motivation and Algorithm
The goal of a standard sampling problem is to generate approximate samples from the target posterior π ( θ ) ∝ exp ( − f ( θ ) ) \pi(\theta) \propto\exp(-f(\theta)) π ( θ ) ∝ exp ( − f ( θ )) where f f f is the potential function. In the standard leapfrog HMC, as illustrated in Figure 1 (left), the parameter θ \theta θ is evolved using a randomly sampled Gaussian momentum for K K K leapfrog steps (defined later in (2)), after which the momentum is resampled before starting a new sequence of leapfrog updates. In Mangoubi & Vishnoi [30 ] , it is shown that performing O ( log d ) O(\log d) O ( log d ) such leapfrog trajectories, each consisting of O ( { d / ϵ 2 } 1 / 4 ) O(\{d/\epsilon^2\}^{1/4}) O ({ d / ϵ 2 } 1/4 ) steps, suffices to ensure convergence of the task distribution. Therefore, the total gradient computational cost of the overall procedure is dominated by the number of leapfrog steps, leading to a total complexity of order O ( d 1 / 4 ) O(d^{1/4}) O ( d 1/4 ) up to logarithmic factors.
Figure 1. An illustration of the centralized HMC algorithm (left panel) and the federated HMC algorithm (right panel).
Let [ N ] = { 1 , … , N } [N] = \{1,\ldots,N\} [ N ] = { 1 , … , N } index the clients. In federated settings, each client c c c has a local potential f ( c ) ( θ ) f^{(c)}(\theta) f ( c ) ( θ ) with weight w c ≥ 0 w_c \ge0 w c ≥ 0 and thus global potential f ( θ ) = ∑ c = 1 N w c f ( c ) ( θ ) f(\theta)=\sum_{c=1}^{N}w_cf^{(c)}(\theta) f ( θ ) = ∑ c = 1 N w c f ( c ) ( θ ) , where ∑ c = 1 N w c = 1 \sum_{c=1}^{N}w_c=1 ∑ c = 1 N w c = 1 . To achieve logarithmic communication complexity in federated sampling, the above theoretical insight motivates us to integrate communication steps into the alternating leapfrog procedure, expecting that the order of FL communication cost matches O ( log d ) O(\log d) O ( log d ) order of leapfrog trajectories in centralized HMC. To be concrete, as illustrated in Figure 1 (right), we aim that each local node performs K K K leapfrog steps followed by a communication round (e.g., averaging the local parameters across nodes), before proceeding to the next leapfrog phase. This corresponds to the FA-HMC algorithm Liang et al., [26 ] with T = 1 T=1 T = 1 . Unfortunately, Liang et al. [26 ] establishes a lower bound showing that, under high federated heterogeneity, the communication cost of such an HMC scheme is at least on the order of O ( { d / ϵ 2 } 1 / 2 ) O(\{d/\epsilon^2\}^{1/2}) O ({ d / ϵ 2 } 1/2 ) . Thus, additional non-trivial FL training designs are necessary to reach a better rate.
In any FL optimization tasks, a key challenge to achieve efficient communication is to control the local shift caused by heterogeneity across local nodes. Local gradient updates move the local parameter toward the location optimum, resulting in a global bias after aggregating local solutions. A breakthrough was introduced by Karimireddy et al. [20 ] , which introduced a control shift technique that reduces the communication cost of FedAvg (McMahan et al., [31 ] ) from O ( d / ϵ 2 ) O(d/\epsilon^2) O ( d / ϵ 2 ) to O ( log ( d / ϵ 2 ) ) O(\log(d/\epsilon^2)) O ( log ( d / ϵ 2 )) . In the FL sampling regime, FA-LD (Deng et al., [9 ] ), a Langevin-counterpart of FedAvg also incurs a communication cost of O ( d / ϵ 2 ) O(d/\epsilon^2) O ( d / ϵ 2 ) . Plassier et al. [36 ] further improved the sampling algorithm by adapting the control shift technique of (Karimireddy et al., [20 ] ).
Inspired by existing works on local shift control, we propose an adaptive HMC federated update rule by introducing a drift variate. Given an energy function F F F , the HMC dynamics follow the Hamiltonian equations:
d θ ( t ) = p ( t ) d t , d p ( t ) = − ∇ θ F ( θ ( t ) ) d t . (1) \mathrm{d}\theta(t) = p(t)\mathrm{d}t,\qquad\mathrm{d}p(t) = -\nabla_\theta F(\theta(t))\mathrm{d}t. \tag*{(1)} d θ ( t ) = p ( t ) d t , d p ( t ) = − ∇ θ F ( θ ( t )) d t . (1)
The above continuous-time dynamic cannot be solved analytically. Commonly, one uses the leapfrog integrator to discretize the dynamics over a step size η \eta η by
θ k + 1 = θ k + η p k − η 2 2 ∇ F ( θ k ) , p k + 1 = p k − η 2 ∇ F ( θ k ) − η 2 ∇ F ( θ k + 1 ) . (2) \theta_{k+1} = \theta_k + \eta p_k - \frac{\eta^2}{2}\nabla F(\theta_k),\qquad p_{k+1} = p_k - \frac{\eta}{2}\nabla F(\theta_k) - \frac{\eta}{2}\nabla F(\theta_{k+1}). \tag*{(2)} θ k + 1 = θ k + η p k − 2 η 2 ∇ F ( θ k ) , p k + 1 = p k − 2 η ∇ F ( θ k ) − 2 η ∇ F ( θ k + 1 ) . (2)
Under the FL setting, update algorithm (2) is running on local nodes, and F F F represents a local energy function which can differ substantially from the global energy function f f f due to node heterogeneity. To account for this potential gap between local F F F and global f f f , we inject a bias correction term to the gradient and replace all ∇ F ( ⋅ ) \nabla F(\cdot) ∇ F ( ⋅ ) terms in (2) with ∇ F ( ⋅ ) − ∇ F ( θ 0 ) + ∇ f ( θ 0 ) \nabla F(\cdot) - \nabla F(\theta_0) + \nabla f(\theta_0) ∇ F ( ⋅ ) − ∇ F ( θ 0 ) + ∇ f ( θ 0 ) (see, Algorithm 1). This bias correction term ∇ f ( θ 0 ) − ∇ F ( θ 0 ) \nabla f(\theta_0) - \nabla F(\theta_0) ∇ f ( θ 0 ) − ∇ F ( θ 0 ) addresses the discrepancy between local and global losses, and the drift variate ∇ f ( θ 0 ) \nabla f(\theta_0) ∇ f ( θ 0 ) needs to be broadcast to all local nodes. This novel local update rule is named the surrogate leapfrog update.
The AFHMC algorithm consists of the following iterative steps: 1. After synchronizing parameter θ t \theta_t θ t across all nodes, each node c c c shares the local ∇ f ( c ) ( θ t ) \nabla f^{(c)}(\theta_t) ∇ f ( c ) ( θ t ) to obtain a global drift variate ∇ f ( θ t ) \nabla f(\theta_t) ∇ f ( θ t ) . 2. All local nodes run K K K surrogate leapfrog steps, with the shared global drift variate, initialized from the same position and momentum. 3. All nodes share and synchronize the local parameter θ t + 1 \theta_{t+1} θ t + 1 , after K K K leapfrog steps. The algorithm can be found in Algorithm 2. In contrast to FA-HMC (Liang et al., [26 ] ), which runs multiple local HMC steps where each HMC step consists of K K K leapfrog updates, the proposed AFHMC only runs one single local HMC step (i.e., K K K updates of surrogate leapfrog, see Figure 1 ). As discussed previously, this design is to ensure minimal communication cost, because every local HMC step will need a fresh new drift control variate, which requires communication.
The AFHMC algorithm can be easily implemented with stochastic gradients for acceleration purposes, similarly to Liang et al. [26 ] , but our analysis in this paper focuses on the use of the exact gradient.
Algorithm 1 Surrogate leapfrog approximation h ~ L F ( ⋅ ) \widetilde{h}_{\mathrm{LF}}(\cdot) h LF ( ⋅ )
Input: energy function F ( ⋅ ) F(\cdot) F ( ⋅ ) , initial position θ 0 \theta_0 θ 0 , drift vector ∇ f ( θ 0 ) \nabla f(\theta_0) ∇ f ( θ 0 ) , momentum p 0 p_0 p 0 , stepsize η \eta η , leapfrog step K K K
for k = 0 k=0 k = 0 to K − 1 K-1 K − 1 do
θ k + 1 = θ k + η p k − η 2 2 ( ∇ F ( θ k ) − ∇ F ( θ 0 ) + ∇ f ( θ 0 ) ) \theta_{k+1}=\theta_k+\eta p_k-\frac{\eta^2}{2}\left(\nabla F(\theta_k)-\nabla F(\theta_0)+\nabla f(\theta_0)\right) θ k + 1 = θ k + η p k − 2 η 2 ( ∇ F ( θ k ) − ∇ F ( θ 0 ) + ∇ f ( θ 0 ) )
p k + 1 = p k − η 2 ∇ F ( θ k ) − η 2 ∇ F ( θ k + 1 ) + η ( ∇ F ( θ 0 ) − ∇ f ( θ 0 ) ) p_{k+1}=p_k-\frac{\eta}{2}\nabla F(\theta_k)-\frac{\eta}{2}\nabla F(\theta_{k+1})+\eta\left(\nabla F(\theta_0)-\nabla f(\theta_0)\right) p k + 1 = p k − 2 η ∇ F ( θ k ) − 2 η ∇ F ( θ k + 1 ) + η ( ∇ F ( θ 0 ) − ∇ f ( θ 0 ) )
end for
Output: h ~ L F ( F , θ 0 , ∇ f ( θ 0 ) , p 0 , η , K ) = θ K \widetilde{h}_{\mathrm{LF}}(F,\theta_0,\nabla f(\theta_0),p_0,\eta,K)=\theta_K h LF ( F , θ 0 , ∇ f ( θ 0 ) , p 0 , η , K ) = θ K
Algorithm 2 Adaptive federated hamiltonian monte carlo (AFHMC) algorithm
Input: initial position θ 0 \theta_0 θ 0 , stepsize η \eta η ; leapfrog update step K K K
Each local node receives the initial parameter θ 0 \theta_0 θ 0 from the center
for t = 0 t=0 t = 0 to t max t_{\max} t m a x do
1st broadcast: The c c c -th local node sends ∇ f ( c ) ( θ t ) \nabla f^{(c)}(\theta_t) ∇ f ( c ) ( θ t ) to the center, for all c = 1 , … , N c=1,\ldots,N c = 1 , … , N ;
1st communicate: The center node samples Gaussian momentum p t p^t p t , and sends p t p_t p t and drift vector ∇ f ( θ t ) : = ∑ c = 1 N w c ∇ f ( c ) ( θ t ) \nabla f(\theta_t):=\sum_{c=1}^{N}w_c\nabla f^{(c)}(\theta_t) ∇ f ( θ t ) := ∑ c = 1 N w c ∇ f ( c ) ( θ t ) to all local nodes;
for c = 1 , 2 , … , N c=1,2,\ldots,N c = 1 , 2 , … , N do
Initialize θ t , 0 ( c ) = θ t \theta_{t,0}^{(c)}=\theta_t θ t , 0 ( c ) = θ t , p t , 0 ( c ) = p t p_{t,0}^{(c)}=p_t p t , 0 ( c ) = p t ;
update θ t , K ( c ) = h ~ L F ( f ( c ) , θ t , 0 ( c ) , ∇ f ( θ t ) , p t , 0 ( c ) , η , K ) \theta_{t,K}^{(c)}=\widetilde{h}_{\mathrm{LF}}(f^{(c)},\theta_{t,0}^{(c)},\nabla f(\theta_t),p_{t,0}^{(c)},\eta,K) θ t , K ( c ) = h LF ( f ( c ) , θ t , 0 ( c ) , ∇ f ( θ t ) , p t , 0 ( c ) , η , K ) ;
end for
2nd broadcast: The c c c -th local node sends θ t , K ( c ) \theta_{t,K}^{(c)} θ t , K ( c ) to the center for all c = 1 , … , N c=1,\ldots,N c = 1 , … , N ;
2nd communicate: The center node sends back θ t + 1 : = ∑ c = 1 N w c θ t , K ( c ) \theta_{t+1}:=\sum_{c=1}^{N}w_c\theta_{t,K}^{(c)} θ t + 1 := ∑ c = 1 N w c θ t , K ( c ) to all local nodes;
end for
Output: { θ t : t = 0 , … , t max } \{\theta_t:t=0,\ldots,t_{\max}\} { θ t : t = 0 , … , t m a x }
Convergence Analysis
Let z i ( c ) z_i^{(c)} z i ( c ) , 1 ≤ i ≤ n c 1\le i\le n_c 1 ≤ i ≤ n c , 1 ≤ c ≤ N 1\le c\le N 1 ≤ c ≤ N be the local data at the c c c -th node, θ ∈ R d \theta\in\mathbb{R}^d θ ∈ R d and ℓ ( θ ; z i ( c ) ) \ell(\theta;z_i^{(c)}) ℓ ( θ ; z i ( c ) ) be the negative log-likelihood (or loss) function. Define w c = n c / ∑ c = 1 N n c w_c=n_c/\sum_{c=1}^{N}n_c w c = n c / ∑ c = 1 N n c , and f ( c ) ( θ ) : = ∑ i = 1 n c ℓ ( θ ; z i ( c ) ) / w c f^{(c)}(\theta):=\sum_{i=1}^{n_c}\ell(\theta;z_i^{(c)})/w_c f ( c ) ( θ ) := ∑ i = 1 n c ℓ ( θ ; z i ( c ) ) / w c is the local loss function of accessible to the c c c -th local node. The goal is to simulate the global target distribution π ( θ ) ∝ exp ( − f ( θ ) ) \pi(\theta)\propto\exp(-f(\theta)) π ( θ ) ∝ exp ( − f ( θ )) , where f ( θ ) = ∑ c = 1 N w c f ( c ) ( θ ) f(\theta)=\sum_{c=1}^{N}w_cf^{(c)}(\theta) f ( θ ) = ∑ c = 1 N w c f ( c ) ( θ ) , w c ≥ 0 w_c\ge0 w c ≥ 0 with ∑ c w c = 1 \sum_cw_c=1 ∑ c w c = 1 .
This section will investigate the theoretical properties of AFHMC algorithm. Before stating our main results, we specific the model assumption as follows:
Assumption 4.1 (m m m -Strongly Convex). For each c = 1 , 2 , … , N c=1,2,\ldots,N c = 1 , 2 , … , N , f ( c ) f^{(c)} f ( c ) is m m m -strongly convex for some μ > 0 \mu>0 μ > 0 , i.e., ∀ x , y ∈ R d \forall x,y\in\mathbb{R}^d ∀ x , y ∈ R d
f ( c ) ( y ) ≥ f ( c ) ( x ) + ⟨ ∇ f ( c ) ( x ) , y − x ⟩ + m 2 ∥ y − x ∥ 2 . f^{(c)}(y)\ge f^{(c)}(x)+\langle\nabla f^{(c)}(x),y-x\rangle+\frac{m}{2}\lVert y-x\rVert^2. f ( c ) ( y ) ≥ f ( c ) ( x ) + ⟨ ∇ f ( c ) ( x ) , y − x ⟩ + 2 m ∥ y − x ∥ 2 .
Assumption 4.2 (M M M -Smoothness). For each c = 1 , 2 , … , N c=1,2,\ldots,N c = 1 , 2 , … , N , f ( c ) f^{(c)} f ( c ) is M M M -smooth for some M > 0 M>0 M > 0 , i.e., ∀ x , y ∈ R d \forall x,y\in\mathbb{R}^d ∀ x , y ∈ R d , we have ∥ ∇ f ( c ) ( y ) − ∇ f ( c ) ( x ) ∥ ≤ M ∥ x − y ∥ \lVert\nabla f^{(c)}(y)-\nabla f^{(c)}(x)\rVert\le M\lVert x-y\rVert ∥ ∇ f ( c ) ( y ) − ∇ f ( c ) ( x )∥ ≤ M ∥ x − y ∥ .
The assumptions are fairly standard in the theoretical literature of gradient-based MCMC algorithms (e.g., Dalalyan, [7 ] ; Mangoubi & Vishnoi, [30 ] ; Dalalyan & Karagulyan, [8 ] ; Erdogdu & Hosseinzadeh, [13 ] ). Unlike prior advanced results (e.g., Dalalyan & Karagulyan, [8 ] ; Liang et al., [26 ] ; Plassier et al., [36 ] ; Mangoubi & Vishnoi, [30 ] ), we don’t require any second-order smoothness (e.g., Hessian) of the energy functions.
Our first result provides a non-asymptotic bound, studying how the gap between θ t \theta_t θ t and θ t π \theta_t^\pi θ t π contracts, where θ t π \theta_t^\pi θ t π is a coupled stationary continuous HMC process satisfying θ t π ∼ π \theta_t^\pi\sim\pi θ t π ∼ π for all t ≥ 0 t\ge0 t ≥ 0 (refer to Appendix Section A.1 for formal definitions).
Theorem 4.3 (Convergence). Under Assumptions 4.1–4.2 , there exist sufficient large constants C 0 , C 1 , C 2 C_0,C_1,C_2 C 0 , C 1 , C 2 such that { θ t } t \{\theta_t\}_t { θ t } t satisfies that, for K η ≤ m / ( C 0 M ) ≤ m / ( 2 M ) K\eta\le\sqrt{m}/(C_0M)\le\sqrt{m}/(2M) K η ≤ m / ( C 0 M ) ≤ m / ( 2 M ) ,
E ∥ θ t + 1 − θ t + 1 π ∥ 2 ≤ ( 1 − m ( K η ) 2 16 ) E ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 M 2 m d + C 2 ( K η ) 8 M 2 m H (3) \mathbb{E}\lVert\theta_{t+1}-\theta_{t+1}^{\pi}\rVert^2\le\left(1-\frac{m(K\eta)^2}{16}\right)\mathbb{E}\lVert\theta_t-\theta_t^\pi\rVert^2+C_1K^2\eta^4\frac{M^2}{m}d+C_2(K\eta)^8\frac{M^2}{m}H \tag*{(3)} E ∥ θ t + 1 − θ t + 1 π ∥ 2 ≤ ( 1 − 16 m ( K η ) 2 ) E ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 m M 2 d + C 2 ( K η ) 8 m M 2 H (3)
where H : = max i ≤ K ∑ c = 1 N w c E ∥ 1 η ( ∇ f ( c ) ( H ˉ η i ( θ π ) ) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ˉ η i ( θ π ) ) ) ∥ 2 H := \max_{i \le K}\sum_{c=1}^{N} w_c \mathbb{E}\left\|\frac{1}{\eta}\left(\nabla f^{(c)}(\bar{\mathcal{H}}_{\eta}^{i}(\theta^{\pi}))-\nabla f^{(c)}(\theta^{\pi})+\nabla f(\theta^{\pi})-\nabla f(\bar{\mathcal{H}}_{\eta}^{i}(\theta^{\pi}))\right)\right\|^2 H := max i ≤ K ∑ c = 1 N w c E η 1 ( ∇ f ( c ) ( H ˉ η i ( θ π )) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ˉ η i ( θ π )) ) 2 is a metric quantifying the federated heterogeneity.
The H ˉ η i ( θ ) \bar{\mathcal{H}}_{\eta}^{i}(\theta) H ˉ η i ( θ ) (formally defined in Appendix Section A.1) denotes the output by running i η i\eta i η -length ideal continuous HMC dynamic (i.e., (4) with F F F being replaced by f f f ) initialized from θ \theta θ . Remark 4.4. H H H is a metric only related to the target distribution and local distribution. It characterizes the client-level gradient heterogeneity under the target distribution. H H H is a theoretical quantity usually unknown in practice. But in terms of its dependency on the dimension, due to the nature of the squared L 2 L_2 L 2 norm, one can prove that H = O ( d ) H = O(d) H = O ( d ) . The proof of this bound and examples of calculating the exact H H H are given in Appendix Section C.
Sketch of proof We decompose ∥ θ t + 1 − θ t + 1 π ∥ 2 \|\theta_{t+1}-\theta_{t+1}^{\pi}\|^2 ∥ θ t + 1 − θ t + 1 π ∥ 2 into two terms: ∥ H ˉ η K ( θ t ) − θ t + 1 π ∥ 2 \|\bar{\mathcal{H}}_{\eta}^{K}(\theta_t)-\theta_{t+1}^{\pi}\|^2 ∥ H ˉ η K ( θ t ) − θ t + 1 π ∥ 2 and ∥ θ t + 1 − H ˉ η K ( θ t ) ∥ 2 \|\theta_{t+1}-\bar{\mathcal{H}}_{\eta}^{K}(\theta_t)\|^2 ∥ θ t + 1 − H ˉ η K ( θ t ) ∥ 2 . The first term is subject to the classic contraction theorem of ideal HMC dynamics. The second term can be characterized by (i) the divergence between θ t , k ( c ) \theta_{t,k}^{(c)} θ t , k ( c ) and ∑ c = 1 N w c θ t , k ( c ) \sum_{c=1}^{N} w_c\theta_{t,k}^{(c)} ∑ c = 1 N w c θ t , k ( c ) , and (ii) the divergence between ideal HMC dynamics H ˉ η i ( θ ) \bar{\mathcal{H}}_{\eta}^{i}(\theta) H ˉ η i ( θ ) and the discretized HMC dynamics H η i ( θ ) \mathcal{H}_{\eta}^{i}(\theta) H η i ( θ ) . Thanks to the local shift control mechanism, we establish a new technical bound (Lemma B.6) to study the surrogate error and give E ∥ θ t , k ( c ) − ∑ c = 1 N w c θ t , k ∥ 2 ≈ O ( ( K η ) 6 H ) \mathbb{E}\|\theta_{t,k}^{(c)}-\sum_{c=1}^{N}w_c\theta_{t,k}\|^2 \approx O((K\eta)^6H) E ∥ θ t , k ( c ) − ∑ c = 1 N w c θ t , k ∥ 2 ≈ O (( K η ) 6 H ) , and bound the divergence caused by discretizations by O ( η 4 d ) O(\eta^4d) O ( η 4 d ) (via Lemma B.10 ).
Based on the recursive contraction result in Theorem 4.3, one can easily derive the convergence rate for E ∥ θ t + 1 − θ t + 1 π ∥ 2 \mathbb{E}\|\theta_{t+1}-\theta_{t+1}^{\pi}\|^2 E ∥ θ t + 1 − θ t + 1 π ∥ 2 . Let π t \pi_t π t be the marginal distribution of θ t \theta_t θ t and W 2 ( μ , ν ) W_2(\mu,\nu) W 2 ( μ , ν ) denote the Wasserstein-2 distance between probability measures μ \mu μ and ν \nu ν . Then, by definition, W 2 2 ( π t , π ) = inf θ ∼ π E ∥ θ t − θ ∥ 2 ≤ E ∥ θ t − θ t π ∥ 2 W_2^2(\pi_t,\pi)=\inf_{\theta\sim\pi}\mathbb{E}\|\theta_t-\theta\|^2\leq\mathbb{E}\|\theta_t-\theta_t^\pi\|^2 W 2 2 ( π t , π ) = inf θ ∼ π E ∥ θ t − θ ∥ 2 ≤ E ∥ θ t − θ t π ∥ 2 , leading to
W 2 2 ( π t , π ) ≤ ( 1 − m ( K η ) 2 16 ) t W 2 2 ( π 0 , π ) + C 1 ′ η 2 M 2 d m 2 + C 2 ′ K 6 η 6 M 2 H m 2 . W_2^2(\pi_t,\pi)\leq\left(1-\frac{m(K\eta)^2}{16}\right)^tW_2^2(\pi_0,\pi)+C_1'\eta^2\frac{M^2d}{m^2}+C_2'K^6\eta^6\frac{M^2H}{m^2}. W 2 2 ( π t , π ) ≤ ( 1 − 16 m ( K η ) 2 ) t W 2 2 ( π 0 , π ) + C 1 ′ η 2 m 2 M 2 d + C 2 ′ K 6 η 6 m 2 M 2 H .
This leads to our next theorem, which studies the communication cost rate for AFHMC. Theorem 4.5. Under Assumptions 4.1–4.2 and if H ≫ M 4 ϵ 2 / m > 0 H\gg M^4\epsilon^2/m>0 H ≫ M 4 ϵ 2 / m > 0 , then there exists some small absolute constant C C C such that if we choose
K η = C ( ϵ 2 m 2 H M 2 ) 1 / 6 ≪ C m M and η = C ( ϵ 2 m 2 M 2 d ) 1 / 2 , K\eta=C\left(\frac{\epsilon^2m^2}{HM^2}\right)^{1/6}\ll C\frac{\sqrt{m}}{M}
\qquad\text{and}\qquad
\eta=C\left(\frac{\epsilon^2m^2}{M^2d}\right)^{1/2}, K η = C ( H M 2 ϵ 2 m 2 ) 1/6 ≪ C M m and η = C ( M 2 d ϵ 2 m 2 ) 1/2 ,
W 2 ( π t ϵ , π ) ≤ ϵ W_2(\pi_{t_\epsilon},\pi)\leq\epsilon W 2 ( π t ϵ , π ) ≤ ϵ can be attained with communication times
t ϵ ≍ ( H M 2 ϵ 2 m 5 ) 1 / 3 log ( W 2 2 ( π 0 , π ) / ϵ 2 ) . t_\epsilon\asymp\left(\frac{HM^2}{\epsilon^2m^5}\right)^{1/3}\log\left(W_2^2(\pi_0,\pi)/\epsilon^2\right). t ϵ ≍ ( ϵ 2 m 5 H M 2 ) 1/3 log ( W 2 2 ( π 0 , π ) / ϵ 2 ) .
The corresponding local iteration number is
K ≍ M 2 / 3 d 1 / 2 ϵ 2 / 3 m 2 / 3 H 1 / 6 . K\asymp\frac{M^{2/3}d^{1/2}}{\epsilon^{2/3}m^{2/3}H^{1/6}}. K ≍ ϵ 2/3 m 2/3 H 1/6 M 2/3 d 1/2 .
Moreover, if H ≪ M 4 ϵ 2 / m H\ll M^4\epsilon^2/m H ≪ M 4 ϵ 2 / m (i.e., heterogeneity across local nodes is very small), it only requires
t ϵ ≍ log ( W 2 2 ( π 0 , π ) / ϵ 2 ) , t_\epsilon\asymp\log\left(W_2^2(\pi_0,\pi)/\epsilon^2\right), t ϵ ≍ log ( W 2 2 ( π 0 , π ) / ϵ 2 ) ,
achieving a linear rate with respect to the communication cost.
For a heterogeneous situation, the communication cost t ϵ t_\epsilon t ϵ implicitly depends on the model dimension via the quantity H H H . As discussed in Remark 4.4, H H H can scale linearly with d d d , leading to t ϵ ≲ ( d / ϵ 2 ) 1 / 3 log ( d / ϵ 2 ) t_\epsilon\lesssim(d/\epsilon^2)^{1/3}\log(d/\epsilon^2) t ϵ ≲ ( d / ϵ 2 ) 1/3 log ( d / ϵ 2 ) . For a homogeneous situation where H ≈ 0 H\approx0 H ≈ 0 , the communication cost reduces to O ( log ( d / ϵ 2 ) ) O(\log(d/\epsilon^2)) O ( log ( d / ϵ 2 )) . To the best of our knowledge, both rates have never been achieved by prior Bayesian FL methods in the literature. Moreover, our analysis do not require extra stringent Hessian smoothness conditions that are commonly required to achieve an advanced rate e.g., Assumption A3 in Plassier et al. [36 ] , Assumption 3.3 in Liang et al. [26 ] . We compare all these results in Table 1 .
This theorem can also be interpreted from a different perspective. AFHMC can have two training phases: in the first phase (fast convergence), the sampling error linearly decays until W 2 2 ( π t , π ) ∼ m H / M 4 W_2^2(\pi_t,\pi)\sim mH/M^4 W 2 2 ( π t , π ) ∼ m H / M 4 ; in the second phase (slow convergence), it needs O ( ( d / ϵ 2 ) 1 / 3 log ( d / ϵ 2 ) ) O((d/\epsilon^2)^{1/3}\log(d/\epsilon^2)) O (( d / ϵ 2 ) 1/3 log ( d / ϵ 2 )) communications to reach W 2 2 ( π t , π ) = ϵ 2 = o ( m H / M 4 ) W_2^2(\pi_t,\pi)=\epsilon^2=o(mH/M^4) W 2 2 ( π t , π ) = ϵ 2 = o ( m H / M 4 ) . Note that these two phases do require different tuning of K K K and η \eta η , as shown by the proof of Theorem 4.5 .
Remark 4.6. Our main theory is derived based on using the exact gradient updates. While it is of great interest to investigate the theoretical behavior when stochastic gradient is used instead, it poses great challenges to obtain a sharp rate that surpasses the Langevin counterpart. Such a result doesn’t exist so far, even for the centralized HMC algorithm. With a lack of theoretical guarantee, we still believe in the advantage of AFHMC under noisy gradient, which is empirically justified by our numerical studies.
Numerical Evidences
In this section, we present our numerical results, including both simulation studies and real data applications, to support our theoretical claims. We compare the empirical performance of AFHMC, FA-HMC and FA-LD, and demonstrate the superiority of the proposed AFHMC algorithm. Throughout this section, a communication round refers to one outer iteration of the federated algorithm. Each AFHMC round consists of two server exchanges (the gradient aggregation for the drift correction and the parameter aggregation after the surrogate trajectory; see the two broadcasts in Algorithm 2), whereas each FA-HMC or FA-LD round consists of one. This constant factor does not change the communication complexity rates. For an empirical comparison at an equal number of server exchanges, we compare AFHMC at round R R R with FA-HMC at round 2 R 2R 2 R .
Simulated Bayesian logistic regression. Following Liang et al. [26 ] ; Mangoubi & Vishnoi [30 ] , we consider Bayesian logistic regression with a standard Gaussian prior on θ ∈ R d \theta\in\mathbb{R}^d θ ∈ R d . Given feature vectors x i ∈ R d x_i \in\mathbb{R}^d x i ∈ R d and binary labels y i ∈ { − 1 , + 1 } y_i \in\{-1,+1\} y i ∈ { − 1 , + 1 } , the posterior is
π ( θ ) ∝ exp ( − 1 2 ∥ θ ∥ 2 ) ∏ i = 1 n σ ( y i x i T θ ) , \pi(\theta) \propto\exp\left(-\frac{1}{2}\lVert\theta\rVert^2\right)\prod_{i=1}^{n}\sigma(y_i x_i^{\mathsf{T}}\theta), π ( θ ) ∝ exp ( − 2 1 ∥ θ ∥ 2 ) i = 1 ∏ n σ ( y i x i T θ ) ,
where σ ( ⋅ ) \sigma(\cdot) σ ( ⋅ ) denotes the sigmoid function. The n = 1000 n=1000 n = 1000 observations are split evenly across N = 20 N=20 N = 20 clients. We evaluate the samplers in two settings: (1) a high-dimensional case with d = 1000 d=1000 d = 1000 and exact local gradients; (2) a lower-dimensional case with d = 10 d=10 d = 10 with inaccurate gradients. Specifically, we add N ( 0 , 100 I d ) \mathcal{N}(0,100I_d) N ( 0 , 100 I d ) noise to the exact gradients, simulating the stochastic mini-batching.
The algorithms (FA-LD, FA-HMC, and AFHMC) are implemented with the following tuning parameter settings. FA-LD uses T = 10 T=10 T = 10 local Langevin steps (each Langevin step is equivalent to K = 1 K=1 K = 1 leapfrog step). FA-HMC uses T = 10 T=10 T = 10 local HMC steps, and each HMC step consists of K F K_F K F classic leapfrog steps. We pick K F K_F K F over a grid centered around the trajectory-length rule K F η ≈ π / 3 K_F\eta\approx\pi/3 K F η ≈ π /3 (Mangoubi & Vishnoi, [30 ] ). AFHMC uses K A K_A K A local surrogate leapfrog steps, and we consider two candidates of K A K_A K A : (i) K A = K F K_A=K_F K A = K F such that AFHMC and FA-HMC match the HMC dynamic trajectory length, and (ii) K A = 10 K F K_A=10K_F K A = 10 K F such that AFHMC and FA-HMC match the same number of leapfrog steps between consecutive rounds of communication. For different η \eta η , the K A K_A K A and K F K_F K F values that deliver the best performance are chosen. For each (algorithm, η \eta η , K K K ) configuration, we run M = 20 M=20 M = 20 independent chains with a total leapfrog budget of 2 × 10 6 2\times10^6 2 × 1 0 6 and discard the first half of each chain as burn-in. We measure performance using the marginal error
M E = 1 d ∑ i = 1 d W 1 ( μ ^ i , μ i M H M C ) , (4) \mathrm{ME}=\frac{1}{d}\sum_{i=1}^{d}W_1\left(\hat{\mu}_i,\mu_i^{\mathrm{MHMC}}\right), \tag*{(4)} ME = d 1 i = 1 ∑ d W 1 ( μ ^ i , μ i MHMC ) , (4)
where μ ^ i \hat{\mu}_i μ ^ i is the empirical marginal of the i i i -th coordinate produced by the candidate sampler, μ i M H M C \mu_i^{\mathrm{MHMC}} μ i MHMC is the surrogate true posterior margins, approximated by a centralized Metropolis-adjusted HMC reference chain with 10 7 10^7 1 0 7 steps, and W 1 W_1 W 1 denotes the Wasserstein-1 distance. For each (algorithm, η \eta η ) pair, we report the best-performing K K K from the candidate grid; the full grid is provided in Appendix § 11 .§ 1 .
Figure 2 reports the resulting marginal error curves for the exact-gradient and noisy-gradient settings. In the exact-gradient high-dimensional setting, AFHMC maintains low marginal error over a broader range of small stepsizes: for example, at η = 5 × 10 − 4 \eta= 5 \times10^{-4} η = 5 × 1 0 − 4 , AFHMC attains ME = 2.3 × 10 − 2 = 2.3 \times10^{-2} = 2.3 × 1 0 − 2 , compared with 5.3 × 10 − 2 5.3 \times10^{-2} 5.3 × 1 0 − 2 for FA-HMC and 3.9 × 10 − 1 3.9 \times10^{-1} 3.9 × 1 0 − 1 for FA-LD. In the noisy-gradient setting, AFHMC achieves the best overall marginal error in the sweep, ME = 2.7 × 10 − 3 = 2.7 \times10^{-3} = 2.7 × 1 0 − 3 , and remains competitive with the best tuned FA-HMC and FA-LD configurations at the other stepsizes.
Figure 2. Simulated Bayesian logistic regression. Left: d = 1000 d = 1000 d = 1000 with exact gradients. Right: d = 10 d = 10 d = 10 with coordinate-wise N ( 0 , 100 ) \mathcal{N}(0, 100) N ( 0 , 100 ) gradient noise. Each panel reports marginal error relative to a centralized MHMC reference chain under a fixed total leapfrog budget. AFHMC is more stable across stepsizes and improves the small-stepsize behavior of FA-HMC and FA-LD.
Dimension scaling on heterogeneous Gaussian targets. Following the heterogeneous Gaussian experiment of Liang et al. [26 ] , we study how the communication cost scales with dimension on a controlled federated Gaussian benchmark. There are N = 10 N = 10 N = 10 clients. For half of the clients the local target is N ( 201 d , I d ) \mathcal{N}(201d, I_d) N ( 201 d , I d ) , and for the remaining clients it is N ( 1 d , 4 I d ) \mathcal{N}(1_d, 4I_d) N ( 1 d , 4 I d ) . Averaging the local quadratic potentials gives the global target N ( 16.21 d , 1.6 I d ) \mathcal{N}(16.21d, 1.6I_d) N ( 16.21 d , 1.6 I d ) . We vary d ∈ { 2 , 50 , 100 , 150 , … , 500 } d \in\{2, 50, 100, 150, \ldots, 500\} d ∈ { 2 , 50 , 100 , 150 , … , 500 } and measure convergence by the squared 2-Wasserstein distance to this global Gaussian target. Note that the empirical 2-Wasserstein distance is expensive to compute for high-dimensional data, therefore, we approximate the posterior distribution by fitting a multivariate Gaussian and compute the 2-Wasserstein distance between the fitted Gaussian distribution and the target distribution via the closed-form formula.
Suggested by the theoretical choice provided by Theorem 4.5 , for AFHMC, the leapfrog count and stepsize are scaled with dimension as
K ( d ) = max { 1 , ⌈ 50 ( d / 100 ) 1 / 3 ⌉ } , η ( d ) = 0.006 ( d / 100 ) − 1 / 2 , K(d) = \max\left\{1, \left\lceil50(d/100)^{1/3} \right\rceil\right\}, \qquad\eta(d) = 0.006(d/100)^{-1/2}, K ( d ) = max { 1 , ⌈ 50 ( d /100 ) 1/3 ⌉ } , η ( d ) = 0.006 ( d /100 ) − 1/2 ,
so that K ( 100 ) = 50 K(100) = 50 K ( 100 ) = 50 and η ( 100 ) = 0.006 \eta(100) = 0.006 η ( 100 ) = 0.006 . Thus, as d d d increases, AFHMC uses longer trajectories but smaller leapfrog steps. We run AFHMC until W 2 2 < 0.1 W_2^2 < 0.1 W 2 2 < 0.1 for 20 consecutive checks and record the first communication round at which the threshold is crossed. The 2-Wasserstein distance calculation is based on M ( d ) = 100 d ( d − 1 ) M(d) = 100d(d - 1) M ( d ) = 100 d ( d − 1 ) independent parallel chains (note that we need to estimate a d d d -dimensional covariance matrix).
As a matched-budget baseline, we run FA-HMC with the same η ( d ) \eta(d) η ( d ) and the same number of communication rounds as AFHMC. FA-HMC uses T = 10 T = 10 T = 10 local HMC update, and the leapfrog step count within each HMC update is chosen as
K F ( d ) = max { 1 , ⌈ K ( d ) / 10 ⌉ } , K_{\mathrm{F}}(d) = \max\left\{1, \left\lceil K(d)/10 \right\rceil\right\}, K F ( d ) = max { 1 , ⌈ K ( d ) /10 ⌉ } ,
so that the total number of leapfrog updates per communication round is matched to AFHMC up to rounding. To check that the gap below is not caused by giving FA-HMC the AFHMC stepsize, we additionally run FA-HMC for 2 R ( d ) 2R(d) 2 R ( d ) rounds, i.e., the same number of server exchanges as AFHMC at round R ( d ) R(d) R ( d ) , under two FA-HMC-specific schedules: the dimension-scaling setting of Liang et al. [26 ] , K F = 5 K_{\mathrm{F}} = 5 K F = 5 , T = 10 T = 10 T = 10 and η ( d ) = 0.02 d − 1 / 4 \eta(d) = 0.02d^{-1/4} η ( d ) = 0.02 d − 1/4 ; and the stepsize suggested by Theorem 4.1 of Liang et al. [26 ] , η ( d ) = 0.006 ( d / 100 ) − 7 / 12 \eta(d) = 0.006(d/100)^{-7/12} η ( d ) = 0.006 ( d /100 ) − 7/12 , with T = 10 T = 10 T = 10 and K F ( d ) K_{\mathrm{F}}(d) K F ( d ) as above (see Appendix § 11 .§ 2 ).
Figure 3 summarizes the dimension-scaling experiment. The left panel shows that the number of communication rounds required by AFHMC increases from 42 at d = 2 d = 2 d = 2 to 430 at d = 500 d = 500 d = 500 . As shown by the figure, the empirical behavior closely resembles the theoretical trend illustrated by the dotted black curve. When fitting the plot by regression C ( d / ϵ 2 ) α log ( d / ϵ 2 ) C(d/\epsilon^2)^\alpha\log(d/\epsilon^2) C ( d / ϵ 2 ) α log ( d / ϵ 2 ) with ϵ 2 = 0.1 \epsilon^2 = 0.1 ϵ 2 = 0.1 (excluding the outlier case d = 2 d = 2 d = 2 ), we have α ^ = 0.282 \hat{\alpha} = 0.282 α ^ = 0.282 . This log-corrected scaling is close to the predicted O ( ( d / ϵ 2 ) 1 / 3 log ( d / ϵ 2 ) ) O((d/\epsilon^2)^{1/3}\log(d/\epsilon^2)) O (( d / ϵ 2 ) 1/3 log ( d / ϵ 2 )) communication complexity, especially on the larger-dimensional regime. The right panel reports the W 2 2 W_2^2 W 2 2 error of FA-HMC when FA-HMC spends the same dimension-dependent budget used by AFHMC, together with the two FA-HMC-specific schedules at the equal server-exchange budget. The horizontal “adaptive threshold” line marks W 2 2 = 0.1 W_2^2 = 0.1 W 2 2 = 0.1 , the stopping accuracy used for AFHMC in the left panel. Under the matched budget, FA-HMC remains orders of magnitude above this threshold: its final W 2 2 W_2^2 W 2 2 ranges from 3.28 × 10 2 3.28 \times10^2 3.28 × 1 0 2 at d = 2 d = 2 d = 2 to 3.81 × 10 4 3.81 \times10^4 3.81 × 1 0 4 at d = 500 d = 500 d = 500 , with empirical growth speed O ( d 0.843 ) O(d^{0.843}) O ( d 0.843 ) . The FA-HMC-specific schedules do not close the gap even with twice as many rounds: at d = 500 d = 500 d = 500 , they reach W 2 2 = 1.19 × 10 4 W_2^2 = 1.19 \times10^4 W 2 2 = 1.19 × 1 0 4 and 1.98 × 10 4 1.98 \times10^4 1.98 × 1 0 4 after 860 rounds, whereas AFHMC crosses 0.1 at round 430, and their errors grow as O ( d 1.23 ) O(d^{1.23}) O ( d 1.23 ) and O ( d 0.97 ) O(d^{0.97}) O ( d 0.97 ) , i.e., roughly linearly in d d d , as expected from a heterogeneity bias. This significant performance gap between AFHMC and FA-HMC indicates that the FA-HMC dynamics retain a persistent heterogeneity bias, whereas AFHMC reaches a higher level of accuracy and efficiency.
Figure 3. Dimension scaling on Gaussian targets. Left: communication rounds required by AFHMC to reach W 2 2 < 0.1 W_2^2 < 0.1 W 2 2 < 0.1 on the heterogeneous target as dimension increases. Middle: the same quantity on the low-heterogeneity target (mean ± \pm ± sd over three seeds), with the fitted logarithmic law. Right: FA-HMC W 2 2 W_2^2 W 2 2 on the heterogeneous target under the original setting (R ( d ) R(d) R ( d ) rounds) and under two FA-HMC-specific stepsize schedules at the equal server-exchange budget 2 R ( d ) 2R(d) 2 R ( d ) ; the horizontal line is the AFHMC stopping threshold W 2 2 = 0.1 W_2^2 = 0.1 W 2 2 = 0.1 .
Low-heterogeneity regime. To examine the O ( log ( d / ϵ 2 ) ) O(\log(d/\epsilon^2)) O ( log ( d / ϵ 2 )) communication complexity predicted by Theorem 4.5 when the heterogeneity is small, we keep N = 10 N = 10 N = 10 clients but estimate every local Gaussian from 10 5 10^5 1 0 5 samples drawn from the same distribution N ( 16.211 d , 1.6 I d ) \mathcal{N}(16.21\mathbf{1}_d, 1.6I_d) N ( 16.21 1 d , 1.6 I d ) , so that the heterogeneity only comes from sampling error; the pooled samples define the target. We use K ( d ) = ⌈ 50 ( d / 100 ) 1 / 2 ⌉ K(d) = \lceil50(d/100)^{1/2}\rceil K ( d ) = ⌈ 50 ( d /100 ) 1/2 ⌉ and η ( d ) = 0.006 ( d / 100 ) − 1 / 2 \eta(d) = 0.006(d/100)^{-1/2} η ( d ) = 0.006 ( d /100 ) − 1/2 , and repeat each setting with three random seeds. AFHMC reaches W 2 2 < 0.1 W_2^2 < 0.1 W 2 2 < 0.1 for every dimension and seed (Figure 3 , middle), and the first-crossing round is well described by R ( d ) = 104.9 + 16.8 log ( d / ϵ 2 ) R(d) = 104.9 + 16.8\log(d/\epsilon^2) R ( d ) = 104.9 + 16.8 log ( d / ϵ 2 ) with R 2 = 0.996 R^2 = 0.996 R 2 = 0.996 . As d d d grows from 50 to 500, R ( d ) R(d) R ( d ) only increases from 212 to 248 (a factor of 1.17), compared with an increase from 162 to 430 (a factor of 2.65) on the heterogeneous target. This provides direct numerical evidence for the logarithmic communication complexity in the low-heterogeneity regime (details in Appendix § 11 .§ 2 ).
Logistic regression for FMNIST. We next evaluate the proposed method on a Bayesian multinomial logistic regression task using the Fashion-MNIST (FMNIST) dataset ([42 ] ), which consists of 60,000 training images and 10,000 test images from 10 clothing categories. The dataset is released by Zalando Research under the MIT license. Each image is a 28 × \times × 28 grayscale image, flattened into a 784-dimensional feature vector. To model client heterogeneity, we partition the training data across N = 10 N = 10 N = 10 clients using a label-skewed Dirichlet split with concentration parameter α = 0.1 \alpha= 0.1 α = 0.1 , see Appendix § 11 .§ 3 for details.
We compare FA-LD, FA-HMC, and AFHMC under the same heterogeneous data split. For FA-LD we use the K = 1 K = 1 K = 1 case, while for FA-HMC and AFHMC we evaluate K ∈ { 10 , 50 , 100 } K \in\{10, 50, 100\} K ∈ { 10 , 50 , 100 } . Each method is run for 3600 server exchanges, i.e., 3600 rounds for FA-LD and FA-HMC and 1800 rounds for AFHMC. Between two synchronizations, each client performs 50 leapfrog steps in FA-LD and FA-HMC and K K K leapfrog steps in AFHMC. For each reported metric, we select the stepsize separately for every method and K K K value.
Figure 4 reports the test accuracy against the number of server exchanges. AFHMC with K ∈ { 10 , 100 } K \in\{10, 100\} K ∈ { 10 , 100 } overtakes all FA-HMC variants after about 1000 exchanges, stays ahead thereafter, and attains the highest final accuracy (0.842, versus 0.841 for the best FA-HMC at the same number of exchanges and 0.836 at the same number of rounds). With K = 10 K = 10 K = 10 , AFHMC achieves this using about ten times fewer gradient evaluations per client than FA-HMC. This result shows that the drift correction in AFHMC continues to be useful beyond the Gaussian experiments and transfers to a non-Gaussian Bayesian logistic regression posterior with real image data. Additional predictive-quality metrics, including Brier score and negative log-likelihood, are reported in Appendix § 11 .§ 3 .
Figure 4. Test accuracy for Bayesian logistic regression on heterogeneous FMNIST against the number of server exchanges (one per round for FA-LD and FA-HMC, two per round for AFHMC).
Conclusions and Discussions
In this work, we propose a novel Bayesian Federated sampling algorithm based on the Hamiltonian dynamics. We incorporate a global drift control variate into the leapfrog integrator to alleviate the local drifting caused by the data heterogeneity. This surrogate leapfrog update rule leads to a significant advancement of the theoretical behavior, especially for the communication cost with respect to the system’s high dimensionality. Our analysis shows that to achieve an ϵ \epsilon ϵ sampling accuracy, AFHMC only requires O ( ( d / ϵ 2 ) 1 / 3 ) O((d/\epsilon^2)^{1/3}) O (( d / ϵ 2 ) 1/3 ) communication rounds. Compared with the O ( ( d / ϵ 2 ) 1 / 2 ) O((d/\epsilon^2)^{1/2}) O (( d / ϵ 2 ) 1/2 ) rate achieved by Langevin-based federated sampler ([36 , 9 ] ), our result reaffirms the superiority of Hamiltonian dynamics over Langevin dynamics for the Federated sampling task, promoting the communities to utilize HMC-based Federated learning methods for complicated high-dimensional tasks. The advantage claimed by our theory is justified by empirical evidence. In addition, AFHMC can achieve O ( log ( d / ϵ 2 ) ) O(\log(d/\epsilon^2)) O ( log ( d / ϵ 2 )) rate for communication complexity under low heterogeneity, matching the rate of communication cost for the Federated optimization realm; our low-heterogeneity Gaussian experiment in § 5 confirms this logarithmic scaling numerically.
Limitations. The scope of our theoretical investigation is limited to the log-convex target distribution and doesn’t consider the stochastic gradient. The theoretical analysis for Hamiltonian dynamics or HMC is highly non-trivial. In the literature, not limited to FL, no result achieves an advanced dimension-dependent rate for HMC under nonconvexity or stochastic gradients. Our contribution is mainly theoretical, hence our numerical experiments are on a small scale, similarly to prior theoretical works, serving for the purpose of validating our theorems.
Acknowledgments and Disclosure of Funding
Guang Lin gratefully acknowledges the support from DARPA MATHBAC program under grant number: HR0011-26-3-E152, the National Science Foundation (DMS-2533878, DMS-2053746, DMS-2134209, ECCS-2328241, CBET-2347401 and OAC-2311848), and U.S. Department of Energy (DOE) Office of Science Advanced Scientific Computing Research program under the "Uncertainty Quantification for Multifidelity Operator Learning (MOLUcQ)" project (Project No. 81739), DE-SC0023161, the SciDAC LEADS Institute, and DOE–Fusion Energy Science, under grant number: DE-SC0024583.
Algorithm, assumption and notations
notations and definitions
The ideal HMC dynamic for the global loss f f f is defined as:
d θ ( t ) = p ( t ) d t , d p ( t ) = − ∇ θ f ( θ ( t ) ) d t . (5) d\theta(t)=p(t)dt,\qquad dp(t)=-\nabla_{\theta}f(\theta(t))dt. \tag*{(5)} d θ ( t ) = p ( t ) d t , d p ( t ) = − ∇ θ f ( θ ( t )) d t . (5)
According to Algorithm 2, we define θ t , j ( c ) \theta_{t,j}^{(c)} θ t , j ( c ) and p t , j ( c ) p_{t,j}^{(c)} p t , j ( c ) to be the local position variable and local momentum variable at the j j j -th surrogate leapfrog step of the c c c -th local node within the t t t -th global iteration. In particular, p t , 0 ( c ) = p t p_{t,0}^{(c)}=p_t p t , 0 ( c ) = p t is a freshly sampled Gaussian variable at iteration t t t shared by all local nodes; for j > 0 j>0 j > 0 , p t , j ( c ) p_{t,j}^{(c)} p t , j ( c ) is generated following the local surrogate leapfrog. Also, we have θ t : = ∑ c = 1 N w c θ t − 1 , K ( c ) \theta_t:=\sum_{c=1}^{N}w_c\theta_{t-1,K}^{(c)} θ t := ∑ c = 1 N w c θ t − 1 , K ( c ) aggregated from local nodes and θ t , 0 ( c ) : = θ t \theta_{t,0}^{(c)}:=\theta_t θ t , 0 ( c ) := θ t broadcast from the center node.
Define θ t , k : = ∑ c = 1 N w c θ t , j ( c ) \theta_{t,k}:=\sum_{c=1}^{N}w_c\theta_{t,j}^{(c)} θ t , k := ∑ c = 1 N w c θ t , j ( c ) as the corresponding (implicit) global position variable, and p t , k = ∑ c = 1 N w c p t , j ( c ) p_{t,k}=\sum_{c=1}^{N}w_cp_{t,j}^{(c)} p t , k = ∑ c = 1 N w c p t , j ( c ) is the corresponding (implicit) global momentum variable.
Define H η ( θ ) : = θ + η p − η 2 2 ∇ f ( θ ) H_{\eta}(\theta):=\theta+\eta p-\frac{\eta^2}{2}\nabla f(\theta) H η ( θ ) := θ + η p − 2 η 2 ∇ f ( θ ) as the classical discrete leapfrog update from position θ \theta θ associated with momentum p p p and stepsize η \eta η and H ˉ η ( θ ) : = θ + ∫ 0 η p ( t ) d t \bar{H}_{\eta}(\theta):=\theta+\int_{0}^{\eta}p(t)dt H ˉ η ( θ ) := θ + ∫ 0 η p ( t ) d t as the classical continuous leapfrog update from position θ \theta θ associated with momentum p ( t ) p(t) p ( t ) and length η \eta η , following the HMC dynamic (4). Similarly, define H η ( p ) : = p − η 2 ( ∇ f ( θ ) + ∇ f ( θ + η p − η 2 2 ∇ f ( θ ) ) ) H_{\eta}(p):=p-\frac{\eta}{2}\left(\nabla f(\theta)+\nabla f\left(\theta+\eta p-\frac{\eta^2}{2}\nabla f(\theta)\right)\right) H η ( p ) := p − 2 η ( ∇ f ( θ ) + ∇ f ( θ + η p − 2 η 2 ∇ f ( θ ) ) ) as a classical discrete leapfrog update from p p p associated with position θ \theta θ and stepsize η \eta η and H ˉ η ( p ) : = p − ∫ 0 η θ ( t ) d t \bar{H}_{\eta}(p):=p-\int_{0}^{\eta}\theta(t)dt H ˉ η ( p ) := p − ∫ 0 η θ ( t ) d t as a classical continuous leapfrog update from p p p associated with position θ ( t ) \theta(t) θ ( t ) and length η \eta η following the HMC dynamic (4).
Based on these, we use the shorthands H η 1 ( θ ) : = H η ( θ ) H_{\eta}^{1}(\theta):=H_{\eta}(\theta) H η 1 ( θ ) := H η ( θ ) , H η i + 1 ( θ ) : = H η ( H η i ( θ ) ) = H η i ( θ ) + η H η i ( p ) − η 2 2 ∇ f ( H η i ( θ ) ) H_{\eta}^{i+1}(\theta):=H_{\eta}(H_{\eta}^{i}(\theta))=H_{\eta}^{i}(\theta)+\eta H_{\eta}^{i}(p)-\frac{\eta^2}{2}\nabla f(H_{\eta}^{i}(\theta)) H η i + 1 ( θ ) := H η ( H η i ( θ )) = H η i ( θ ) + η H η i ( p ) − 2 η 2 ∇ f ( H η i ( θ )) , and H η 1 ( p ) : = H η ( p ) H_{\eta}^{1}(p):=H_{\eta}(p) H η 1 ( p ) := H η ( p ) , H η i + 1 ( p ) : = H η ( H η i ( p ) ) = H η i ( p ) − η 2 ( ∇ f ( H η i ( θ ) ) + ∇ f ( H η i ( θ ) + η H η i ( p ) − η 2 2 ∇ f ( H η i ( θ ) ) ) ) H_{\eta}^{i+1}(p):=H_{\eta}(H_{\eta}^{i}(p))=H_{\eta}^{i}(p)-\frac{\eta}{2}\left(\nabla f(H_{\eta}^{i}(\theta))+\nabla f\left(H_{\eta}^{i}(\theta)+\eta H_{\eta}^{i}(p)-\frac{\eta^2}{2}\nabla f(H_{\eta}^{i}(\theta))\right)\right) H η i + 1 ( p ) := H η ( H η i ( p )) = H η i ( p ) − 2 η ( ∇ f ( H η i ( θ )) + ∇ f ( H η i ( θ ) + η H η i ( p ) − 2 η 2 ∇ f ( H η i ( θ )) ) ) . We also use the shorthands H ˉ η i ( θ ) = θ + ∫ 0 i η p ( s ) d s \bar{H}_{\eta}^{i}(\theta)=\theta+\int_{0}^{i\eta}p(s)ds H ˉ η i ( θ ) = θ + ∫ 0 i η p ( s ) d s and H ˉ η i ( p ) : = p − ∫ 0 i η θ ( s ) d s \bar{H}_{\eta}^{i}(p):=p-\int_{0}^{i\eta}\theta(s)ds H ˉ η i ( p ) := p − ∫ 0 i η θ ( s ) d s .
In addition, we define a coupled continuous HMC process as follows. θ t π \theta_t^{\pi} θ t π follows the target distribution π ∝ exp ( − f ) \pi\propto\exp(-f) π ∝ exp ( − f ) . θ t , 0 π : = θ t π \theta_{t,0}^{\pi}:=\theta_t^{\pi} θ t , 0 π := θ t π , θ t , k + 1 π : = H ˉ η ( θ t , k π ) \theta_{t,k+1}^{\pi}:=\bar{H}_{\eta}(\theta_{t,k}^{\pi}) θ t , k + 1 π := H ˉ η ( θ t , k π ) , and θ t + 1 π : = θ t , K π = H ˉ K η ( θ t , 0 π ) \theta_{t+1}^{\pi}:=\theta_{t,K}^{\pi}=\bar{H}_{K\eta}(\theta_{t,0}^{\pi}) θ t + 1 π := θ t , K π = H ˉ K η ( θ t , 0 π ) . For this process, the associated initial momentum is the same as the discrete HMC process, i.e., p t , 0 π = p t π = p t p_{t,0}^{\pi}=p_t^{\pi}=p_t p t , 0 π = p t π = p t .
We also denote θ ∗ = argmin θ f ( θ ) \theta^*=\operatorname*{argmin}_{\theta}f(\theta) θ ∗ = argmin θ f ( θ ) .
Proofs
main proof
Theorem 4.5. Under Assumptions 4.1-4.2 and if H ≫ M 4 ϵ 2 / m > 0 H\gg M^4\epsilon^2/m>0 H ≫ M 4 ϵ 2 / m > 0 , then there exists some small absolute constant C C C such that if we choose
K η = C ( ϵ 2 m 2 H M 2 ) 1 / 6 ≪ C m M and η = C ( ϵ 2 m 2 M 2 d ) 1 / 2 , K\eta=C\left(\frac{\epsilon^2m^2}{HM^2}\right)^{1/6}\ll C\frac{\sqrt{m}}{M}
\qquad\text{and}\qquad
\eta=C\left(\frac{\epsilon^2m^2}{M^2d}\right)^{1/2}, K η = C ( H M 2 ϵ 2 m 2 ) 1/6 ≪ C M m and η = C ( M 2 d ϵ 2 m 2 ) 1/2 , W 2 ( π t ϵ , π ) ≤ ϵ W_2(\pi_{t_\epsilon},\pi)\leq\epsilon W 2 ( π t ϵ , π ) ≤ ϵ can be attained with communication times
t ϵ ≲ ( H M 2 ϵ 2 m 2 ) 1 / 3 log ( W 2 2 ( π 0 , π ) / ϵ 2 ) . t_\epsilon\lesssim\left(\frac{HM^2}{\epsilon^2m^2}\right)^{1/3}\log\left(W_2^2(\pi_0,\pi)/\epsilon^2\right). t ϵ ≲ ( ϵ 2 m 2 H M 2 ) 1/3 log ( W 2 2 ( π 0 , π ) / ϵ 2 ) . The corresponding local iteration number is
K ≲ M 2 / 3 d 1 / 2 ϵ 2 / 3 m 2 / 3 H 1 / 6 . K\lesssim\frac{M^{2/3}d^{1/2}}{\epsilon^{2/3}m^{2/3}H^{1/6}}. K ≲ ϵ 2/3 m 2/3 H 1/6 M 2/3 d 1/2 .
Moreover, if H ≪ M 4 ϵ 2 / m H \ll M^{4}\epsilon^{2}/m H ≪ M 4 ϵ 2 / m (i.e., heterogeneity across local nodes is very small), it only requires
t ϵ ≍ log ( W 2 2 ( π 0 , π ) / ϵ 2 ) , t_{\epsilon} \asymp\log(W_{2}^{2}(\pi_{0},\pi)/\epsilon^{2}), t ϵ ≍ log ( W 2 2 ( π 0 , π ) / ϵ 2 ) ,
achieving a linear rate with respect to the communication cost.
Proof. Let us define
K 2 η 2 = C ( ϵ 2 m 2 H M 2 ) 1 / 3 , η 2 = C ϵ 2 m 2 M 2 d (6) K^{2}\eta^{2}=C\left(\frac{\epsilon^{2}m^{2}}{HM^{2}}\right)^{1/3}, \qquad\eta^{2}=C\frac{\epsilon^{2}m^{2}}{M^{2}d} \tag*{(6)} K 2 η 2 = C ( H M 2 ϵ 2 m 2 ) 1/3 , η 2 = C M 2 d ϵ 2 m 2 (6)
for some sufficiently small C C C , we have
K 2 η 4 M 2 m d m K 2 η 2 = C ϵ 2 ≤ 1 3 ϵ 2 , ( K η ) 8 M 2 m H m K 2 η 2 = C 3 ϵ 2 ≤ 1 3 ϵ 2 . (7) \frac{K^{2}\eta^{4}\frac{M^{2}}{m}d}{mK^{2}\eta^{2}}=C\epsilon^{2}\leq\frac{1}{3}\epsilon^{2}, \qquad\frac{(K\eta)^{8}\frac{M^{2}}{m}H}{mK^{2}\eta^{2}}=C^{3}\epsilon^{2}\leq\frac{1}{3}\epsilon^{2}. \tag*{(7)} m K 2 η 2 K 2 η 4 m M 2 d = C ϵ 2 ≤ 3 1 ϵ 2 , m K 2 η 2 ( K η ) 8 m M 2 H = C 3 ϵ 2 ≤ 3 1 ϵ 2 . (7)
One can check that if
t ≥ log ( ϵ 2 / ( 3 E ∥ θ 0 − θ 0 π ∥ 2 ) ) log ( 1 − C m ( H M 2 ϵ 2 m 5 ) 1 / 3 / 16 ) ≳ 1 C ( H M 2 ϵ 2 m 5 ) 1 / 3 log ( 3 E ∥ θ 0 − θ 0 π ∥ 2 / ϵ 2 ) , t\geq\frac{\log(\epsilon^{2}/(3\mathbb{E}\lVert\theta_{0}-\theta_{0}^{\pi}\rVert^{2}))}{\log(1-Cm(\frac{HM^{2}}{\epsilon^{2}m^{5}})^{1/3}/16)}
\gtrsim\frac{1}{C}\left(\frac{HM^{2}}{\epsilon^{2}m^{5}}\right)^{1/3}\log(3\mathbb{E}\lVert\theta_{0}-\theta_{0}^{\pi}\rVert^{2}/\epsilon^{2}), t ≥ log ( 1 − C m ( ϵ 2 m 5 H M 2 ) 1/3 /16 ) log ( ϵ 2 / ( 3 E ∥ θ 0 − θ 0 π ∥ 2 )) ≳ C 1 ( ϵ 2 m 5 H M 2 ) 1/3 log ( 3 E ∥ θ 0 − θ 0 π ∥ 2 / ϵ 2 ) ,
we have
( 1 − m ( K η ) 2 / 16 ) t E ∥ θ t − θ t π ∥ 2 ≤ 1 3 ϵ 2 . (8) (1-m(K\eta)^{2}/16)^{t}\mathbb{E}\lVert\theta_{t}-\theta_{t}^{\pi}\rVert^{2}\leq\frac{1}{3}\epsilon^{2}. \tag*{(8)} ( 1 − m ( K η ) 2 /16 ) t E ∥ θ t − θ t π ∥ 2 ≤ 3 1 ϵ 2 . (8)
Combining (6)-(7) and by Theorem 4.3, we can see that, for enough small C C C and set (5), we can have
E ∥ θ t − θ t π ∥ 2 ≤ ϵ 2 . \mathbb{E}\lVert\theta_{t}-\theta_{t}^{\pi}\rVert^{2}\leq\epsilon^{2}. E ∥ θ t − θ t π ∥ 2 ≤ ϵ 2 .
This justifies the required communication round
t ϵ ≥ 1 C ( H M 2 ϵ 2 m 5 ) 1 / 3 log ( 3 E ∥ θ 0 − θ 0 π ∥ 2 / ϵ 2 ) . t_{\epsilon}\geq\frac{1}{C}\left(\frac{HM^{2}}{\epsilon^{2}m^{5}}\right)^{1/3}\log(3\mathbb{E}\lVert\theta_{0}-\theta_{0}^{\pi}\rVert^{2}/\epsilon^{2}). t ϵ ≥ C 1 ( ϵ 2 m 5 H M 2 ) 1/3 log ( 3 E ∥ θ 0 − θ 0 π ∥ 2 / ϵ 2 ) .
On the other hand, if H ≪ M 4 ϵ 2 / m H\ll M^{4}\epsilon^{2}/m H ≪ M 4 ϵ 2 / m (i.e., the heterogeneity cross local nodes is small), by choosing enough small C C C such that K 2 η 2 = C m / M 2 K^{2}\eta^{2}=Cm/M^{2} K 2 η 2 = C m / M 2 and η 2 = C ϵ 2 m 2 / ( M 2 d ) \eta^{2}=C\epsilon^{2}m^{2}/(M^{2}d) η 2 = C ϵ 2 m 2 / ( M 2 d ) , we have
K 2 η 4 M 2 m d m K 2 η 2 ≤ C 2 ϵ 2 ≤ 1 3 ϵ 2 , ( K η ) 8 M 2 m H m K 2 η 2 = C 3 m M 4 H ≪ ϵ 2 ≤ 1 3 ϵ 2 . (9) \frac{K^{2}\eta^{4}\frac{M^{2}}{m}d}{mK^{2}\eta^{2}}\leq C^{2}\epsilon^{2}\leq\frac{1}{3}\epsilon^{2}, \qquad\frac{(K\eta)^{8}\frac{M^{2}}{m}H}{mK^{2}\eta^{2}}=C^{3}\frac{m}{M^{4}}H\ll\epsilon^{2}\leq\frac{1}{3}\epsilon^{2}. \tag*{(9)} m K 2 η 2 K 2 η 4 m M 2 d ≤ C 2 ϵ 2 ≤ 3 1 ϵ 2 , m K 2 η 2 ( K η ) 8 m M 2 H = C 3 M 4 m H ≪ ϵ 2 ≤ 3 1 ϵ 2 . (9)
One can check that if
t ≥ log ( ϵ 2 / ( 3 E ∥ θ 0 − θ 0 π ∥ 2 ) ) log ( 1 − C m 2 / ( 16 M 2 ) ) , t\geq\frac{\log(\epsilon^{2}/(3\mathbb{E}\lVert\theta_{0}-\theta_{0}^{\pi}\rVert^{2}))}{\log(1-Cm^{2}/(16M^{2}))}, t ≥ log ( 1 − C m 2 / ( 16 M 2 )) log ( ϵ 2 / ( 3 E ∥ θ 0 − θ 0 π ∥ 2 )) ,
we have
( 1 − C m 2 / M 2 ) t E ∥ θ t − θ t π ∥ 2 ≤ 1 3 ϵ 2 . (10) (1-Cm^{2}/M^{2})^{t}\mathbb{E}\lVert\theta_{t}-\theta_{t}^{\pi}\rVert^{2}\leq\frac{1}{3}\epsilon^{2}. \tag*{(10)} ( 1 − C m 2 / M 2 ) t E ∥ θ t − θ t π ∥ 2 ≤ 3 1 ϵ 2 . (10)
Combining (8)-(9) and by Theorem 4.3, we obtain that E ∥ θ t − θ t π ∥ 2 ≤ ϵ 2 \mathbb{E}\lVert\theta_{t}-\theta_{t}^{\pi}\rVert^{2}\leq\epsilon^{2} E ∥ θ t − θ t π ∥ 2 ≤ ϵ 2 . This justified the required communication round to be
t ϵ ≥ C ′ log ( 3 E ∥ θ 0 − θ 0 π ∥ 2 / ϵ 2 ) . t_{\epsilon}\geq C'\log(3\mathbb{E}\lVert\theta_{0}-\theta_{0}^{\pi}\rVert^{2}/\epsilon^{2}). t ϵ ≥ C ′ log ( 3 E ∥ θ 0 − θ 0 π ∥ 2 / ϵ 2 ) .
Finally, we can choose θ 0 π \theta_{0}^{\pi} θ 0 π such that W 2 ( π t , π ) = E ∥ θ 0 − θ 0 π ∥ 2 W^{2}(\pi_{t},\pi)=\mathbb{E}\lVert\theta_{0}-\theta_{0}^{\pi}\rVert^{2} W 2 ( π t , π ) = E ∥ θ 0 − θ 0 π ∥ 2 , which concludes the proof.
Theorem 4.3 (Convergence). Under Assumptions 4.1-4.2, there exist sufficient large constants C 0 , C 1 , C 2 C_{0},C_{1},C_{2} C 0 , C 1 , C 2 such that { θ t } t \{\theta_{t}\}_{t} { θ t } t satisfies that, for K η ≤ m / ( C 0 M ) ≤ m / ( 2 M ) K\eta\leq\sqrt{m}/(C_{0}M)\leq\sqrt{m}/(2M) K η ≤ m / ( C 0 M ) ≤ m / ( 2 M ) ,
E ∥ θ t + 1 − θ t + 1 π ∥ 2 ≤ ( 1 − m ( K η ) 2 16 ) E ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 M 2 m d + C 2 ( K η ) 8 M 2 m H \mathbb{E}\lVert\theta_{t+1}-\theta_{t+1}^{\pi}\rVert^{2}\leq\left(1-\frac{m(K\eta)^{2}}{16}\right)\mathbb{E}\lVert\theta_{t}-\theta_{t}^{\pi}\rVert^{2}+C_{1}K^{2}\eta^{4}\frac{M^{2}}{m}d+C_{2}(K\eta)^{8}\frac{M^{2}}{m}H E ∥ θ t + 1 − θ t + 1 π ∥ 2 ≤ ( 1 − 16 m ( K η ) 2 ) E ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 m M 2 d + C 2 ( K η ) 8 m M 2 H where H : = max i ≤ K ∑ c = 1 N w c E ∥ 1 n ( ∇ f ( c ) ( H ˉ i η ( θ π ) ) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ˉ i η ( θ π ) ) ) ∥ 2 H:=\max_{i\leq K}\sum_{c=1}^{N}w_{c}\mathbb{E}\left\lVert\frac{1}{n}\left(\nabla f^{(c)}(\bar{H}_{i}^{\eta}(\theta^{\pi}))-\nabla f^{(c)}(\theta^{\pi})+\nabla f(\theta^{\pi})-\nabla f(\bar{H}_{i}^{\eta}(\theta^{\pi}))\right)\right\rVert^{2} H := max i ≤ K ∑ c = 1 N w c E n 1 ( ∇ f ( c ) ( H ˉ i η ( θ π )) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ˉ i η ( θ π )) ) 2 is a metric quantifying the federated heterogeneity.
Proof. We introduce an intermediate variable H ˉ η K ( θ t ) \bar{H}_{\eta}^{K}(\theta_t) H ˉ η K ( θ t ) being the continuously updated version of θ t , K π \theta_{t,K}^{\pi} θ t , K π from θ t \theta_t θ t . For c 1 , c 2 > 0 c_1,c_2>0 c 1 , c 2 > 0 with c 1 + c 2 = 1 c_1+c_2=1 c 1 + c 2 = 1 , by Lemma B.12, we can separate the errors into two parts
∥ θ t , K − θ t , K π ∥ 2 ≤ 1 c 1 ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ⏟ discrete divergence error + 1 c 2 ∥ H ˉ η K ( θ t ) − θ t , K π ∥ 2 ⏟ ideal convergence error (11) \left\|\theta_{t,K}-\theta_{t,K}^{\pi}\right\|^2 \le\frac{1}{c_1}\underbrace{\left\|\theta_{t,K}-\bar{H}_{\eta}^{K}(\theta_t)\right\|^2}_{\text{discrete divergence error}}+\frac{1}{c_2}\underbrace{\left\|\bar{H}_{\eta}^{K}(\theta_t)-\theta_{t,K}^{\pi}\right\|^2}_{\text{ideal convergence error}} \tag*{(11)} θ t , K − θ t , K π 2 ≤ c 1 1 discrete divergence error θ t , K − H ˉ η K ( θ t ) 2 + c 2 1 ideal convergence error H ˉ η K ( θ t ) − θ t , K π 2 (11)
The convergence of the ideal process has been well studied in the literature Zongchen Chen [44 ] . Indeed, recall the definitions that that H ˉ η K ( θ t ) \bar{H}_{\eta}^{K}(\theta_t) H ˉ η K ( θ t ) and θ t , K π \theta_{t,K}^{\pi} θ t , K π share the same initial momentum p t p_t p t for each t t t , by Lemma B.1, it can be bounded by a contraction factor of the distance between their initial positions
∥ H ˉ η K ( θ t ) − θ t , K π ∥ 2 ≤ ( 1 − m ( K η ) 2 4 ) ∥ θ t − θ t π ∥ 2 , for K η ≤ 1 / ( 2 M ) . (12) \left\|\bar{H}_{\eta}^{K}(\theta_t)-\theta_{t,K}^{\pi}\right\|^2 \le\left(1-\frac{m(K\eta)^2}{4}\right)\left\|\theta_t-\theta_t^{\pi}\right\|^2,\qquad\text{for }K\eta\le1/(2\sqrt{M}). \tag*{(12)} H ˉ η K ( θ t ) − θ t , K π 2 ≤ ( 1 − 4 m ( K η ) 2 ) ∥ θ t − θ t π ∥ 2 , for K η ≤ 1/ ( 2 M ) . (12)
We choose c 1 , c 2 c_1,c_2 c 1 , c 2 such that 1 − m ( K η ) 2 / 4 c 2 = 1 − m ( K η ) 2 / 8 \frac{1-m(K\eta)^2/4}{c_2}=1-m(K\eta)^2/8 c 2 1 − m ( K η ) 2 /4 = 1 − m ( K η ) 2 /8 , and it follows
c 2 = 1 − m ( K η ) 2 / 4 1 − m ( K η ) 2 / 8 , c 1 = m ( K η ) 2 / 8 1 − m ( K η ) 2 / 8 ≥ m ( K η ) 2 8 (13) c_2=\frac{1-m(K\eta)^2/4}{1-m(K\eta)^2/8},\qquad c_1=\frac{m(K\eta)^2/8}{1-m(K\eta)^2/8}\ge\frac{m(K\eta)^2}{8} \tag*{(13)} c 2 = 1 − m ( K η ) 2 /8 1 − m ( K η ) 2 /4 , c 1 = 1 − m ( K η ) 2 /8 m ( K η ) 2 /8 ≥ 8 m ( K η ) 2 (13)
This choice ensures that, after amplification by 1 / c 1 1/c_1 1/ c 1 , the contraction factor in (10) is still strictly smaller than 1.
In the following, to finish the proof, it suffice to show that the divergence error
E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ m ( K η ) 2 16 ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 M 2 m d + C 2 ( K η ) 8 M 2 m H , \mathbb{E}\left\|\theta_{t,K}-\bar{H}_{\eta}^{K}(\theta_t)\right\|^2\le\frac{m(K\eta)^2}{16}\left\|\theta_t-\theta_t^{\pi}\right\|^2+C_1K^2\eta^4\frac{M^2}{m}d+C_2(K\eta)^8\frac{M^2}{m}H, E θ t , K − H ˉ η K ( θ t ) 2 ≤ 16 m ( K η ) 2 ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 m M 2 d + C 2 ( K η ) 8 m M 2 H ,
or some constants C 1 , C 2 > 0 C_1,C_2>0 C 1 , C 2 > 0 . To study the discrete divergence error, we separate the error within the leapfrog-step level. Since by definitions θ t , K = ∑ c = 1 N θ t , K ( c ) \theta_{t,K}=\sum_{c=1}^{N}\theta_{t,K}^{(c)} θ t , K = ∑ c = 1 N θ t , K ( c ) and θ t = θ t , 0 \theta_t=\theta_{t,0} θ t = θ t , 0 we can write
θ t , K − H ˉ η K ( θ t ) = θ t , K − H ˉ η K ( θ t , 0 ) = ∑ k = 1 K H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) . \theta_{t,K}-\bar{H}_{\eta}^{K}(\theta_t)=\theta_{t,K}-\bar{H}_{\eta}^{K}(\theta_{t,0})=\sum_{k=1}^{K}\bar{H}_{\eta}^{K-k}(\theta_{t,k})-\bar{H}_{\eta}^{K-k+1}(\theta_{t,k-1}). θ t , K − H ˉ η K ( θ t ) = θ t , K − H ˉ η K ( θ t , 0 ) = k = 1 ∑ K H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) .
By convexity of ∥ ⋅ ∥ 2 \|\cdot\|^2 ∥ ⋅ ∥ 2 and Lemma B.12,
∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 = ∥ ∑ k = 1 K H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) ∥ 2 ≤ K ∑ k = 1 K ∥ H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) ∥ 2 \begin{aligned}
\left\|\theta_{t,K}-\bar{H}_{\eta}^{K}(\theta_t)\right\|^2=\left\|\sum_{k=1}^{K}\bar{H}_{\eta}^{K-k}(\theta_{t,k})-\bar{H}_{\eta}^{K-k+1}(\theta_{t,k-1})\right\|^2 \\
&\le K\sum_{k=1}^{K}\left\|\bar{H}_{\eta}^{K-k}(\theta_{t,k})-\bar{H}_{\eta}^{K-k+1}(\theta_{t,k-1})\right\|^2
\end{aligned} θ t , K − H ˉ η K ( θ t ) 2 = k = 1 ∑ K H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) 2 ≤ K k = 1 ∑ K H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) 2
We emphasis that H ˉ η K − k ( θ t , k ) \bar{H}_{\eta}^{K-k}(\theta_{t,k}) H ˉ η K − k ( θ t , k ) starts with position θ t , k \theta_{t,k} θ t , k and momentum p t , k p_{t,k} p t , k while H ˉ η K − k + 1 ( θ t , k − 1 ) \bar{H}_{\eta}^{K-k+1}(\theta_{t,k-1}) H ˉ η K − k + 1 ( θ t , k − 1 ) can be viewed as a ( K − k ) η (K-k)\eta ( K − k ) η -length process starting with position H ˉ η ( θ t , k − 1 ) \bar{H}_{\eta}(\theta_{t,k-1}) H ˉ η ( θ t , k − 1 ) and momentum H ˉ η ( p t , k − 1 ) \bar{H}_{\eta}(p_{t,k-1}) H ˉ η ( p t , k − 1 ) . Lemma B.1 yields
∥ H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) ∥ 2 ≤ 2 ∥ θ t , k − H ˉ η ( θ t , k − 1 ) ∥ 2 + 2 ( K − k ) 2 η 2 ∥ p t , k − H ˉ η ( p t , k − 1 ) ∥ 2 . \left\|\bar{H}_{\eta}^{K-k}(\theta_{t,k})-\bar{H}_{\eta}^{K-k+1}(\theta_{t,k-1})\right\|^2\le2\left\|\theta_{t,k}-\bar{H}_{\eta}(\theta_{t,k-1})\right\|^2+2(K-k)^2\eta^2\left\|p_{t,k}-\bar{H}_{\eta}(p_{t,k-1})\right\|^2. H ˉ η K − k ( θ t , k ) − H ˉ η K − k + 1 ( θ t , k − 1 ) 2 ≤ 2 θ t , k − H ˉ η ( θ t , k − 1 ) 2 + 2 ( K − k ) 2 η 2 p t , k − H ˉ η ( p t , k − 1 ) 2 .
It follows that, we can bound the divergence error as follow
∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ 2 K ∑ k = 1 K ( ∥ θ t , k − H ˉ η ( θ t , k − 1 ) ∥ 2 ⏟ error induced by inaccurate positions + ( K − k ) 2 η 2 ∥ p t , k − H ˉ η ( p t , k − 1 ) ∥ 2 ⏟ error induced by inaccurate momentums ) . (14) \left\|\theta_{t,K}-\bar{H}_{\eta}^{K}(\theta_t)\right\|^2\le2K\sum_{k=1}^{K}\left(\underbrace{\left\|\theta_{t,k}-\bar{H}_{\eta}(\theta_{t,k-1})\right\|^2}_{\text{error induced by inaccurate positions}}+(K-k)^2\eta^2\underbrace{\left\|p_{t,k}-\bar{H}_{\eta}(p_{t,k-1})\right\|^2}_{\text{error induced by inaccurate momentums}}\right). \tag*{(14)} θ t , K − H ˉ η K ( θ t ) 2 ≤ 2 K k = 1 ∑ K error induced by inaccurate positions θ t , k − H ˉ η ( θ t , k − 1 ) 2 + ( K − k ) 2 η 2 error induced by inaccurate momentums p t , k − H ˉ η ( p t , k − 1 ) 2 . (14)
The divergence errors can be further separated into systematic leapfrog approximation error and surrogate-induced error. To see this, by definitions
θ t , k − H ˉ η ( θ t , k − 1 ) = H η ( θ t , k − 1 ) − H ˉ η ( θ t , k − 1 ) ⏟ systematic leapfrog gap − η 2 2 ∑ c = 1 N w c ( ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) ) ⏟ surrogate induced gap \theta_{t,k}-\bar{H}_{\eta}(\theta_{t,k-1})=\underbrace{H_{\eta}(\theta_{t,k-1})-\bar{H}_{\eta}(\theta_{t,k-1})}_{\text{systematic leapfrog gap}}-\frac{\eta^2}{2}\sum_{c=1}^{N}\underbrace{w_c\left(\nabla f^{(c)}(\theta_{t,k-1}^{(c)})-\nabla f^{(c)}(\theta_{t,k-1})\right)}_{\text{surrogate induced gap}} θ t , k − H ˉ η ( θ t , k − 1 ) = systematic leapfrog gap H η ( θ t , k − 1 ) − H ˉ η ( θ t , k − 1 ) − 2 η 2 c = 1 ∑ N surrogate induced gap w c ( ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) )
p t , k − H ˉ η ( p t , k − 1 ) = H η ( p t , k − 1 ) − H ˉ η ( p t , k − 1 ) ⏟ systematic leapfrog gap − η 2 ∑ c = 1 N w c ( ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) + ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) ⏟ surrogate induced gap ) . p_{t,k}-\bar{H}_{\eta}(p_{t,k-1})=\underbrace{H_{\eta}(p_{t,k-1})-\bar{H}_{\eta}(p_{t,k-1})}_{\text{systematic leapfrog gap}}-\frac{\eta}{2}\sum_{c=1}^{N}w_c\left(\underbrace{\nabla f^{(c)}(\theta_{t,k-1}^{(c)})-\nabla f^{(c)}(\theta_{t,k-1})+\nabla f^{(c)}(\theta_{t,k}^{(c)})-\nabla f^{(c)}(\theta_{t,k})}_{\text{surrogate induced gap}}\right). p t , k − H ˉ η ( p t , k − 1 ) = systematic leapfrog gap H η ( p t , k − 1 ) − H ˉ η ( p t , k − 1 ) − 2 η c = 1 ∑ N w c surrogate induced gap ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) + ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) .
Applying Lemma B.12, we can have
∥ θ t , k − H ˉ η ( θ t , k − 1 ) ∥ 2 ≤ 2 ∥ H η ( θ t , k − 1 ) − H ˉ η ( θ t , k − 1 ) ∥ 2 + 2 η 4 4 ∑ c = 1 N w c ∥ ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) ∥ 2 \left\|\theta_{t,k}-\bar{\mathcal{H}}_{\eta}(\theta_{t,k-1})\right\|^{2}\leq2\left\|\mathcal{H}_{\eta}(\theta_{t,k-1})-\bar{\mathcal{H}}_{\eta}(\theta_{t,k-1})\right\|^{2}+2\frac{\eta^{4}}{4}\sum_{c=1}^{N}w_{c}\left\|\nabla f^{(c)}(\theta_{t,k-1}^{(c)})-\nabla f^{(c)}(\theta_{t,k-1})\right\|^{2} θ t , k − H ˉ η ( θ t , k − 1 ) 2 ≤ 2 H η ( θ t , k − 1 ) − H ˉ η ( θ t , k − 1 ) 2 + 2 4 η 4 c = 1 ∑ N w c ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) 2
∥ p t , k − H ˉ η ( p t , k − 1 ) ∥ 2 ≤ 2 ∥ H η ( p t , k − 1 ) − H ˉ η ( p t , k − 1 ) ∥ 2 + 2 η 2 4 ∑ c = 1 N w c ∑ j = k − 1 k 2 ∥ ∇ f ( c ) ( θ t , j ( c ) ) − ∇ f ( c ) ( θ t , j ) ∥ 2 . \left\|p_{t,k}-\bar{\mathcal{H}}_{\eta}(p_{t,k-1})\right\|^{2}\leq2\left\|\mathcal{H}_{\eta}(p_{t,k-1})-\bar{\mathcal{H}}_{\eta}(p_{t,k-1})\right\|^{2}+2\frac{\eta^{2}}{4}\sum_{c=1}^{N}w_{c}\sum_{j=k-1}^{k}2\left\|\nabla f^{(c)}(\theta_{t,j}^{(c)})-\nabla f^{(c)}(\theta_{t,j})\right\|^{2}. p t , k − H ˉ η ( p t , k − 1 ) 2 ≤ 2 H η ( p t , k − 1 ) − H ˉ η ( p t , k − 1 ) 2 + 2 4 η 2 c = 1 ∑ N w c j = k − 1 ∑ k 2 ∇ f ( c ) ( θ t , j ( c ) ) − ∇ f ( c ) ( θ t , j ) 2 .
Inserting these beck to (13), we have
∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ 2 K ∑ k = 1 K ( 2 ∥ H η ( θ t , k − 1 ) − H ˉ η ( θ t , k − 1 ) ∥ 2 + 2 ( K − k ) η 2 ∥ H η ( p t , k − 1 ) − H ˉ η ( p t , k − 1 ) ∥ 2 + η 4 2 ∑ c = 1 N w c ( ∥ ∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) ∥ 2 + ( K − k ) 2 ∑ j = k − 1 k ∥ ∇ f ( c ) ( θ t , j ( c ) ) − ∇ f ( c ) ( θ t , j ) ∥ 2 ) ≤ 5 K ∑ k = 0 K − 1 ( ∥ H η ( θ t , k ) − H ˉ η ( θ t , k ) ∥ 2 + ( K − k ) 2 η 2 ∥ H η ( p t , k ) − H ˉ η ( p t , k ) ∥ 2 + ( K η ) 2 η 2 ∑ c = 1 N w c ∥ ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) ∥ 2 ) . (15) \begin{aligned}
\|\theta_{t,K}-\bar{\mathcal{H}}_{\eta}^{K}(\theta_t)\|^{2}
&\leq2K\sum_{k=1}^{K}\Bigl(2\|\mathcal{H}_{\eta}(\theta_{t,k-1})-\bar{\mathcal{H}}_{\eta}(\theta_{t,k-1})\|^{2}+2(K-k)\eta^{2}\|\mathcal{H}_{\eta}(p_{t,k-1})-\bar{\mathcal{H}}_{\eta}(p_{t,k-1})\|^{2}\\
&\qquad+\frac{\eta^{4}}{2}\sum_{c=1}^{N}w_{c}(\|\nabla f^{(c)}(\theta_{t,k-1}^{(c)})-\nabla f^{(c)}(\theta_{t,k-1})\|^{2}+(K-k)^{2}\sum_{j=k-1}^{k}\|\nabla f^{(c)}(\theta_{t,j}^{(c)})-\nabla f^{(c)}(\theta_{t,j})\|^{2}\Bigr)\\
&\leq5K\sum_{k=0}^{K-1}\Bigl(\|\mathcal{H}_{\eta}(\theta_{t,k})-\bar{\mathcal{H}}_{\eta}(\theta_{t,k})\|^{2}+(K-k)^{2}\eta^{2}\|\mathcal{H}_{\eta}(p_{t,k})-\bar{\mathcal{H}}_{\eta}(p_{t,k})\|^{2}\\
&\qquad+(K\eta)^{2}\eta^{2}\sum_{c=1}^{N}w_{c}\|\nabla f^{(c)}(\theta_{t,k}^{(c)})-\nabla f^{(c)}(\theta_{t,k})\|^{2}\Bigr). \tag*{(15)}
\end{aligned} ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ 2 K k = 1 ∑ K ( 2∥ H η ( θ t , k − 1 ) − H ˉ η ( θ t , k − 1 ) ∥ 2 + 2 ( K − k ) η 2 ∥ H η ( p t , k − 1 ) − H ˉ η ( p t , k − 1 ) ∥ 2 + 2 η 4 c = 1 ∑ N w c ( ∥∇ f ( c ) ( θ t , k − 1 ( c ) ) − ∇ f ( c ) ( θ t , k − 1 ) ∥ 2 + ( K − k ) 2 j = k − 1 ∑ k ∥∇ f ( c ) ( θ t , j ( c ) ) − ∇ f ( c ) ( θ t , j ) ∥ 2 ) ≤ 5 K k = 0 ∑ K − 1 ( ∥ H η ( θ t , k ) − H ˉ η ( θ t , k ) ∥ 2 + ( K − k ) 2 η 2 ∥ H η ( p t , k ) − H ˉ η ( p t , k ) ∥ 2 + ( K η ) 2 η 2 c = 1 ∑ N w c ∥∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) ∥ 2 ) . (15)
where we have applied 2 η 4 ( 1 / 2 + 2 ( K − k ) 2 ) ≤ 5 K 2 η 4 2\eta^{4}(1/2+2(K-k)^{2})\leq5K^{2}\eta^{4} 2 η 4 ( 1/2 + 2 ( K − k ) 2 ) ≤ 5 K 2 η 4 for k < K k<K k < K in the last inequality.
By M M M -smoothness assumption,
∑ c = 1 N w c E ∥ ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) ∥ 2 ≤ ∑ c = 1 N w c M 2 E ∥ θ t , k ( c ) − θ t , k ∥ 2 . \sum_{c=1}^{N}w_{c}\mathbb{E}\left\|\nabla f^{(c)}(\theta_{t,k}^{(c)})-\nabla f^{(c)}(\theta_{t,k})\right\|^{2}\leq\sum_{c=1}^{N}w_{c}M^{2}\mathbb{E}\left\|\theta_{t,k}^{(c)}-\theta_{t,k}\right\|^{2}. c = 1 ∑ N w c E ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) 2 ≤ c = 1 ∑ N w c M 2 E θ t , k ( c ) − θ t , k 2 .
and further by Lemma B.6 that ∑ c = 1 N w c E ∥ θ t , k ( c ) − θ t , k ∥ 2 ≤ k 3 η 4 ∑ i = 1 k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) \sum_{c=1}^{N}w_{c}\mathbb{E}\|\theta_{t,k}^{(c)}-\theta_{t,k}\|^{2}\leq k^{3}\eta^{4}\sum_{i=1}^{k-1}(16M^{2}\mathbb{E}\|\theta_{t,i}^{\pi}-\theta_{t,i}\|^{2}+16M^{2}\mathbb{E}\|\theta_{t}^{\pi}-\theta_{t}\|^{2}+4(k\eta)^{2}H) ∑ c = 1 N w c E ∥ θ t , k ( c ) − θ t , k ∥ 2 ≤ k 3 η 4 ∑ i = 1 k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) , we have
∑ c = 1 N w c E ∥ ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) ∥ 2 ≤ k 3 η 4 M 2 ∑ i = 1 k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) . (16) \sum_{c=1}^{N}w_{c}\mathbb{E}\left\|\nabla f^{(c)}(\theta_{t,k}^{(c)})-\nabla f^{(c)}(\theta_{t,k})\right\|^{2}\leq k^{3}\eta^{4}M^{2}\sum_{i=1}^{k-1}\left(16M^{2}\mathbb{E}\left\|\theta_{t,i}^{\pi}-\theta_{t,i}\right\|^{2}+16M^{2}\mathbb{E}\left\|\theta_{t}^{\pi}-\theta_{t}\right\|^{2}+4(k\eta)^{2}H\right). \tag*{(16)} c = 1 ∑ N w c E ∇ f ( c ) ( θ t , k ( c ) ) − ∇ f ( c ) ( θ t , k ) 2 ≤ k 3 η 4 M 2 i = 1 ∑ k − 1 ( 16 M 2 E θ t , i π − θ t , i 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) . (16)
Here we recall that H : = max i ≤ K ∑ c = 1 N w c E ∥ 1 η ( ∇ f ( c ) ( H ˉ η i ( θ π ) ) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ˉ η i ( θ π ) ) ) ∥ 2 H:=\max_{i\leq K}\sum_{c=1}^{N}w_{c}\mathbb{E}\left\|\frac{1}{\eta}\left(\nabla f^{(c)}(\bar{\mathcal{H}}_{\eta}^{i}(\theta^{\pi}))-\nabla f^{(c)}(\theta^{\pi})+\nabla f(\theta^{\pi})-\nabla f(\bar{\mathcal{H}}_{\eta}^{i}(\theta^{\pi}))\right)\right\|^{2} H := max i ≤ K ∑ c = 1 N w c E η 1 ( ∇ f ( c ) ( H ˉ η i ( θ π )) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ˉ η i ( θ π )) ) 2 is a quantity measuring the federated heterogeneity.
As for the systematic leapfrog approximation errors, by Lemma B.3 and Lemma B.4, we have
∥ H η ( θ t , k ) − H ˉ η ( θ t , k ) ∥ 2 ≤ η 6 ( M 2 10 ∥ p t , k ∥ 2 + M 4 η 2 60 ∥ θ t , k − θ ∗ ∥ 2 ) \left\|\mathcal{H}_{\eta}(\theta_{t,k})-\bar{\mathcal{H}}_{\eta}(\theta_{t,k})\right\|^{2}\leq\eta^{6}\left(\frac{M^{2}}{10}\left\|p_{t,k}\right\|^{2}+\frac{M^{4}\eta^{2}}{60}\left\|\theta_{t,k}-\theta^{*}\right\|^{2}\right) H η ( θ t , k ) − H ˉ η ( θ t , k ) 2 ≤ η 6 ( 10 M 2 ∥ p t , k ∥ 2 + 60 M 4 η 2 ∥ θ t , k − θ ∗ ∥ 2 )
∥ H η ( p t , k ) − H ˉ η ( p t , k ) ∥ 2 ≤ η 4 ( 5 M 2 2 ∥ p t , k ∥ 2 + 2 η 2 M 4 3 ∥ θ t , k − θ ∗ ∥ 2 ) . (17) \left\|\mathcal{H}_{\eta}(p_{t,k})-\bar{\mathcal{H}}_{\eta}(p_{t,k})\right\|^{2}\leq\eta^{4}\left(\frac{5M^{2}}{2}\left\|p_{t,k}\right\|^{2}+\frac{2\eta^{2}M^{4}}{3}\left\|\theta_{t,k}-\theta^{*}\right\|^{2}\right). \tag*{(17)} H η ( p t , k ) − H ˉ η ( p t , k ) 2 ≤ η 4 ( 2 5 M 2 ∥ p t , k ∥ 2 + 3 2 η 2 M 4 ∥ θ t , k − θ ∗ ∥ 2 ) . (17)
Inserting (15)-(16) back to (14) and applying Lemma B.10 on p t , k p_{t,k} p t , k and θ t , k \theta_{t,k} θ t , k , we obtain
E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ 5 K ∑ k = 0 K − 1 ( η 6 M 2 10 + ( K η ) 2 η 4 5 M 2 2 ) E ∥ p t , k ∥ 2 + ( η 8 M 4 60 + ( K η ) 2 2 η 6 M 4 3 ) E ∥ θ t , k − θ ∗ ∥ 2 + K 5 η 8 M 2 ∑ i = 1 k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) ≤ 5 K ∑ k = 0 K − 1 ( η 6 M 2 10 + ( K η ) 2 η 4 5 M 2 2 ) ( 5 E ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 E ∥ θ t − θ ∗ ∥ 2 ) + ( η 8 M 4 60 + ( K η ) 2 2 η 6 M 4 3 ) ( 4 ( k η ) 2 E ∥ p t ∥ 2 + 3 E ∥ θ t − θ ∗ ∥ 2 ) + K 5 η 8 M 2 ∑ i = 1 k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) . \begin{aligned}
\mathbb{E}\|\theta_{t,K}-\bar{\mathcal{H}}_{\eta}^{K}(\theta_t)\|^2
&\le5K\sum_{k=0}^{K-1}\left(\frac{\eta^6M^2}{10}+\frac{(K\eta)^2\eta^4 5M^2}{2}\right)\mathbb{E}\|p_{t,k}\|^2+\left(\frac{\eta^8M^4}{60}+\frac{(K\eta)^2 2\eta^6M^4}{3}\right)\mathbb{E}\|\theta_{t,k}-\theta^*\|^2\\
&\quad+K^5\eta^8M^2\sum_{i=1}^{k-1}\left(16M^2\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2+16M^2\mathbb{E}\|\theta^\pi_t-\theta_t\|^2+4(k\eta)^2H\right)\\
&\le5K\sum_{k=0}^{K-1}\left(\frac{\eta^6M^2}{10}+\frac{(K\eta)^2\eta^4 5M^2}{2}\right)\left(5\mathbb{E}\|p_t\|^2+5M^2(k\eta)^2\mathbb{E}\|\theta_t-\theta^*\|^2\right)\\
&\quad+\left(\frac{\eta^8M^4}{60}+\frac{(K\eta)^2 2\eta^6M^4}{3}\right)\left(4(k\eta)^2\mathbb{E}\|p_t\|^2+3\mathbb{E}\|\theta_t-\theta^*\|^2\right)\\
&\quad+K^5\eta^8M^2\sum_{i=1}^{k-1}\left(16M^2\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2+16M^2\mathbb{E}\|\theta^\pi_t-\theta_t\|^2+4(k\eta)^2H\right).
\end{aligned} E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ 5 K k = 0 ∑ K − 1 ( 10 η 6 M 2 + 2 ( K η ) 2 η 4 5 M 2 ) E ∥ p t , k ∥ 2 + ( 60 η 8 M 4 + 3 ( K η ) 2 2 η 6 M 4 ) E ∥ θ t , k − θ ∗ ∥ 2 + K 5 η 8 M 2 i = 1 ∑ k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) ≤ 5 K k = 0 ∑ K − 1 ( 10 η 6 M 2 + 2 ( K η ) 2 η 4 5 M 2 ) ( 5 E ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 E ∥ θ t − θ ∗ ∥ 2 ) + ( 60 η 8 M 4 + 3 ( K η ) 2 2 η 6 M 4 ) ( 4 ( k η ) 2 E ∥ p t ∥ 2 + 3 E ∥ θ t − θ ∗ ∥ 2 ) + K 5 η 8 M 2 i = 1 ∑ k − 1 ( 16 M 2 E ∥ θ t , i π − θ t , i ∥ 2 + 16 M 2 E ∥ θ t π − θ t ∥ 2 + 4 ( k η ) 2 H ) .
Rearranging the coefficients, it can be seen that
E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ ( 5 2 K 2 η 6 M 2 + 125 2 K 4 η 6 M 2 + K 4 η 10 M 4 3 + 40 K 6 η 10 M 4 3 ) E ∥ p t ∥ 2 + ( 5 2 K 4 η 8 M 4 + 125 2 K 6 η 8 M 4 + K 2 η 8 M 4 4 + 80 K 4 η 8 M 4 ) E ∥ θ t − θ ∗ ∥ 2 + 80 ∑ k = 0 K − 1 K 6 η 8 M 4 ∑ i = 1 k − 1 E ∥ θ t , i π − θ t , i ∥ 2 + 80 ( K η ) 8 M 4 E ∥ θ t π − θ t ∥ 2 + 20 ( K η ) 10 M 2 H ≤ C K 4 η 6 M 2 d + C K 6 η 8 M 4 E ∥ θ t − θ ∗ ∥ 2 + C K 7 η 8 M 4 ∑ i = 1 K − 2 E ∥ θ t , i π − θ t , i ∥ 2 + C ( K η ) 8 M 4 E ∥ θ t π − θ t ∥ 2 + C ( K η ) 10 M 2 H \begin{aligned}
\mathbb{E}\|\theta_{t,K}-\bar{\mathcal{H}}_{\eta}^{K}(\theta_t)\|^2
&\le\left(\frac{5}{2}K^2\eta^6M^2+\frac{125}{2}K^4\eta^6M^2+\frac{K^4\eta^{10}M^4}{3}+\frac{40K^6\eta^{10}M^4}{3}\right)\mathbb{E}\|p_t\|^2\\
&\quad+\left(\frac{5}{2}K^4\eta^8M^4+\frac{125}{2}K^6\eta^8M^4+\frac{K^2\eta^8M^4}{4}+80K^4\eta^8M^4\right)\mathbb{E}\|\theta_t-\theta^*\|^2\\
&\quad+80\sum_{k=0}^{K-1}K^6\eta^8M^4\sum_{i=1}^{k-1}\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2\\
&\quad+80(K\eta)^8M^4\mathbb{E}\|\theta^\pi_t-\theta_t\|^2\\
&\quad+20(K\eta)^{10}M^2H\\
&\le CK^4\eta^6M^2d+CK^6\eta^8M^4\mathbb{E}\|\theta_t-\theta^*\|^2+CK^7\eta^8M^4\sum_{i=1}^{K-2}\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2\\
&\quad+C(K\eta)^8M^4\mathbb{E}\|\theta^\pi_t-\theta_t\|^2+C(K\eta)^{10}M^2H
\end{aligned} E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ ( 2 5 K 2 η 6 M 2 + 2 125 K 4 η 6 M 2 + 3 K 4 η 10 M 4 + 3 40 K 6 η 10 M 4 ) E ∥ p t ∥ 2 + ( 2 5 K 4 η 8 M 4 + 2 125 K 6 η 8 M 4 + 4 K 2 η 8 M 4 + 80 K 4 η 8 M 4 ) E ∥ θ t − θ ∗ ∥ 2 + 80 k = 0 ∑ K − 1 K 6 η 8 M 4 i = 1 ∑ k − 1 E ∥ θ t , i π − θ t , i ∥ 2 + 80 ( K η ) 8 M 4 E ∥ θ t π − θ t ∥ 2 + 20 ( K η ) 10 M 2 H ≤ C K 4 η 6 M 2 d + C K 6 η 8 M 4 E ∥ θ t − θ ∗ ∥ 2 + C K 7 η 8 M 4 i = 1 ∑ K − 2 E ∥ θ t , i π − θ t , i ∥ 2 + C ( K η ) 8 M 4 E ∥ θ t π − θ t ∥ 2 + C ( K η ) 10 M 2 H
for enough large C C C and K η ≤ 1 / ( 2 M ) K\eta\le1/(2\sqrt{M}) K η ≤ 1/ ( 2 M ) .
Combining this with E ∥ θ t − θ ∗ ∥ 2 ≤ 2 E ∥ θ t − θ t π ∥ 2 + 2 E ∥ θ t π − θ ∗ ∥ 2 \mathbb{E}\|\theta_t-\theta^*\|^2\le2\mathbb{E}\|\theta_t-\theta^\pi_t\|^2+2\mathbb{E}\|\theta^\pi_t-\theta^*\|^2 E ∥ θ t − θ ∗ ∥ 2 ≤ 2 E ∥ θ t − θ t π ∥ 2 + 2 E ∥ θ t π − θ ∗ ∥ 2 and Lemma B.2 that E ∥ θ t π − θ ∗ ∥ 2 ≤ d / m \mathbb{E}\|\theta^\pi_t-\theta^*\|^2\le d/m E ∥ θ t π − θ ∗ ∥ 2 ≤ d / m , we get
E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ C ′ K 4 η 6 M 2 d + C ′ K 7 η 8 M 4 ∑ i = 1 K − 2 E ∥ θ t , i π − θ t , i ∥ 2 + C ′ ( K η ) 8 M 4 E ∥ θ t π − θ t ∥ 2 + C ′ ( K η ) 10 M 2 H (18) \mathbb{E}\|\theta_{t,K}-\bar{\mathcal{H}}_{\eta}^{K}(\theta_t)\|^2
\le C'K^4\eta^6M^2d+C'K^7\eta^8M^4\sum_{i=1}^{K-2}\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2+C'(K\eta)^8M^4\mathbb{E}\|\theta^\pi_t-\theta_t\|^2+C'(K\eta)^{10}M^2H \tag*{(18)} E ∥ θ t , K − H ˉ η K ( θ t ) ∥ 2 ≤ C ′ K 4 η 6 M 2 d + C ′ K 7 η 8 M 4 i = 1 ∑ K − 2 E ∥ θ t , i π − θ t , i ∥ 2 + C ′ ( K η ) 8 M 4 E ∥ θ t π − θ t ∥ 2 + C ′ ( K η ) 10 M 2 H (18)
for enough large C ′ C' C ′ .
Finally, combining it with (10)-(12), it can be seen that for an enough large C ′ ′ C'' C ′′
E ∥ θ t , K − θ t , K π ∥ 2 ≤ ( 1 − m ( K η ) 2 8 + C ′ ′ ( K η ) 6 M 4 m ) E ∥ θ t − θ t π ∥ 2 + C ′ ′ K 2 η 4 M 2 m d + C ′ ′ K 5 η 6 M 4 m ∑ i = 1 K − 2 E ∥ θ t , i π − θ t , i ∥ 2 + C ′ ′ ( K η ) 8 M 2 m H . (19) \begin{aligned}
\mathbb{E}\|\theta_{t,K}-\theta^\pi_{t,K}\|^2
&\le\left(1-\frac{m(K\eta)^2}{8}+\frac{C''(K\eta)^6M^4}{m}\right)\mathbb{E}\|\theta_t-\theta^\pi_t\|^2+C''K^2\eta^4\frac{M^2}{m}d\\
&\quad+C''K^5\eta^6\frac{M^4}{m}\sum_{i=1}^{K-2}\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2+C''(K\eta)^8\frac{M^2}{m}H. \tag*{(19)}
\end{aligned} E ∥ θ t , K − θ t , K π ∥ 2 ≤ ( 1 − 8 m ( K η ) 2 + m C ′′ ( K η ) 6 M 4 ) E ∥ θ t − θ t π ∥ 2 + C ′′ K 2 η 4 m M 2 d + C ′′ K 5 η 6 m M 4 i = 1 ∑ K − 2 E ∥ θ t , i π − θ t , i ∥ 2 + C ′′ ( K η ) 8 m M 2 H . (19)
To prove our final claim of this theorem, we use induction to tackle ∑ i = 1 K − 2 E ∥ θ t , i π − θ t , i ∥ 2 \sum_{i=1}^{K-2}\mathbb{E}\|\theta^\pi_{t,i}-\theta_{t,i}\|^2 ∑ i = 1 K − 2 E ∥ θ t , i π − θ t , i ∥ 2 . In specific, we are going to show that there exist constants C 0 C_0 C 0 , C 1 C_1 C 1 , C 2 C_2 C 2 (to be determined later) such that for K η ≤ m / ( C 0 M ) ≤ 1 / ( 2 M ) K\eta\le\sqrt{m}/(C_0M)\le1/(2\sqrt{M}) K η ≤ m / ( C 0 M ) ≤ 1/ ( 2 M )
E ∥ θ t , K − θ t , K π ∥ 2 ≤ ( 1 − m ( K η ) 2 16 ) E ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 M 2 m d + C 2 ( K η ) 8 M 2 m H . (20) \mathbb{E}\|\theta_{t,K}-\theta^\pi_{t,K}\|^2\le\left(1-\frac{m(K\eta)^2}{16}\right)\mathbb{E}\|\theta_t-\theta^\pi_t\|^2+C_1K^2\eta^4\frac{M^2}{m}d+C_2(K\eta)^8\frac{M^2}{m}H. \tag*{(20)} E ∥ θ t , K − θ t , K π ∥ 2 ≤ ( 1 − 16 m ( K η ) 2 ) E ∥ θ t − θ t π ∥ 2 + C 1 K 2 η 4 m M 2 d + C 2 ( K η ) 8 m M 2 H . (20)
Firstly, (19) holds for K = 0 , 1 , 2 K=0,1,2 K = 0 , 1 , 2 by (18) for a C 0 C_0 C 0 with 16 C 0 4 > C ′ ′ 16C_0^4>C'' 16 C 0 4 > C ′′ .
Next, assume that (19) holds for all K ≤ K ~ − 1 K\leq\widetilde{K}-1 K ≤ K − 1 , we are going to show that (19) also holds for K = K ~ K=\widetilde{K} K = K .
Applying our induction assumption on (18), we have
E ∥ θ t , K ~ − H ~ η K ~ ( θ t ) ∥ 2 ≤ ( 1 − m ( K η ) 2 8 + C ′ ′ ( K η ) 6 M 4 m ) E ∥ θ t − θ t π ∥ 2 + C ′ ′ K 2 η 4 M 2 m d + C ′ ′ ( K η ) 8 M 2 m H + C ′ ′ K 5 η 6 M 4 m ∑ i = 1 K − 2 ( ( 1 − m ( i η ) 2 16 ) E ∥ θ t − θ t π ∥ 2 + C 1 i 2 η 4 M 2 m d + C 2 ( i η ) 8 M 2 m H ) ≤ ( 1 − m ( K η ) 2 8 + C ′ ′ ( K η ) 6 M 4 m + C ′ ′ ( K η ) 6 M 4 m ) E ∥ θ t − θ t π ∥ 2 + ( C ′ ′ + C ′ ′ K 6 η 6 M 4 m C 1 ) K 2 η 4 M 2 m d + ( C ′ ′ + C ′ ′ K 6 η 6 C 2 ) ( K η ) 8 M 2 m H . \begin{aligned}
\mathbb{E}\lVert\theta_{t,\widetilde{K}}-\widetilde{H}_{\eta}^{\widetilde{K}}(\theta_t)\rVert^2
&\leq\left(1-\frac{m(K\eta)^2}{8}+\frac{C''(K\eta)^6M^4}{m}\right)\mathbb{E}\lVert\theta_t-\theta_t^\pi\rVert^2+C''K^2\eta^4\frac{M^2}{m}d+C''(K\eta)^8\frac{M^2}{m}H\\
&\quad+C''K^5\eta^6\frac{M^4}{m}\sum_{i=1}^{K-2}\left(\left(1-\frac{m(i\eta)^2}{16}\right)\mathbb{E}\lVert\theta_t-\theta_t^\pi\rVert^2+C_1i^2\eta^4\frac{M^2}{m}d+C_2(i\eta)^8\frac{M^2}{m}H\right)\\
&\leq\left(1-\frac{m(K\eta)^2}{8}+\frac{C''(K\eta)^6M^4}{m}+C''(K\eta)^6\frac{M^4}{m}\right)\mathbb{E}\lVert\theta_t-\theta_t^\pi\rVert^2\\
&\quad+\left(C''+C''K^6\eta^6\frac{M^4}{m}C_1\right)K^2\eta^4\frac{M^2}{m}d+\left(C''+C''K^6\eta^6C_2\right)(K\eta)^8\frac{M^2}{m}H.
\end{aligned} E ∥ θ t , K − H η K ( θ t ) ∥ 2 ≤ ( 1 − 8 m ( K η ) 2 + m C ′′ ( K η ) 6 M 4 ) E ∥ θ t − θ t π ∥ 2 + C ′′ K 2 η 4 m M 2 d + C ′′ ( K η ) 8 m M 2 H + C ′′ K 5 η 6 m M 4 i = 1 ∑ K − 2 ( ( 1 − 16 m ( i η ) 2 ) E ∥ θ t − θ t π ∥ 2 + C 1 i 2 η 4 m M 2 d + C 2 ( i η ) 8 m M 2 H ) ≤ ( 1 − 8 m ( K η ) 2 + m C ′′ ( K η ) 6 M 4 + C ′′ ( K η ) 6 m M 4 ) E ∥ θ t − θ t π ∥ 2 + ( C ′′ + C ′′ K 6 η 6 m M 4 C 1 ) K 2 η 4 m M 2 d + ( C ′′ + C ′′ K 6 η 6 C 2 ) ( K η ) 8 m M 2 H .
To finish the induction, we need to satisfy that for K η ≤ m / ( C 0 M ) K\eta\leq\sqrt{m}/(C_0M) K η ≤ m / ( C 0 M ) ,
m ( K η ) 2 8 − 2 C ′ ′ ( K η ) 6 M 4 m ≥ m ( K η ) 2 16 , ( C ′ ′ + C ′ ′ K 6 η 6 M 4 m C 1 ) ≤ C 1 , ( C ′ ′ + C ′ ′ K 6 η 6 C 2 ) ≤ C 2 . \frac{m(K\eta)^2}{8}-\frac{2C''(K\eta)^6M^4}{m}\geq\frac{m(K\eta)^2}{16},\qquad\left(C''+C''K^6\eta^6\frac{M^4}{m}C_1\right)\leq C_1,\qquad\left(C''+C''K^6\eta^6C_2\right)\leq C_2. 8 m ( K η ) 2 − m 2 C ′′ ( K η ) 6 M 4 ≥ 16 m ( K η ) 2 , ( C ′′ + C ′′ K 6 η 6 m M 4 C 1 ) ≤ C 1 , ( C ′′ + C ′′ K 6 η 6 C 2 ) ≤ C 2 .
which holds trivially for an enough large constant C 0 C_0 C 0 .
Noting that M ≥ m M\geq m M ≥ m and that θ t + 1 = θ t , K \theta_{t+1}=\theta_{t,K} θ t + 1 = θ t , K and θ t + 1 π = θ t , K π \theta^\pi_{t+1}=\theta^\pi_{t,K} θ t + 1 π = θ t , K π , this finishes the proof.
ideal process
Lemma B.1 (Lemma D.3 in Liang et al. [26 ] ). Under Assumption 4.2 consider two HMC systems θ ( t ) \theta(t) θ ( t ) and θ ˉ ( t ) \bar{\theta}(t) θ ˉ ( t ) starting with the same initial positions and different initial momentum p ( 0 ) p(0) p ( 0 ) and p ~ ( 0 ) \tilde{p}(0) p ~ ( 0 ) respectively. We have
∥ θ ( t ) − θ ˉ ( t ) ∥ 2 ≤ 1 M sinh ( M t ) ∥ p ( 0 ) − p ~ ( 0 ) ∥ 2 . \lVert\theta(t)-\bar{\theta}(t)\rVert_2\leq\frac{1}{\sqrt{M}}\sinh(\sqrt{M}t)\lVert p(0)-\tilde{p}(0)\rVert_2. ∥ θ ( t ) − θ ˉ ( t ) ∥ 2 ≤ M 1 sinh ( M t ) ∥ p ( 0 ) − p ~ ( 0 ) ∥ 2 . Further if we have Assumption 4.1 , consider two HMC systems θ ( t ) \theta(t) θ ( t ) and θ ~ ( t ) \tilde{\theta}(t) θ ~ ( t ) starting with initial positions θ ( 0 ) \theta(0) θ ( 0 ) and θ ~ ( 0 ) \tilde{\theta}(0) θ ~ ( 0 ) , and initial momentum p ( 0 ) p(0) p ( 0 ) and p ~ ( 0 ) \tilde{p}(0) p ~ ( 0 ) respectively, then for 0 ≤ t ≤ 2 M 0\leq t\leq\frac{2}{\sqrt{M}} 0 ≤ t ≤ M 2 , we have
∥ θ ( t ) − θ ~ ( t ) ∥ 2 ≤ ( 1 − m 4 t 2 ) ∥ θ ( 0 ) − θ ~ ( 0 ) ∥ 2 + t ∥ p ( 0 ) − p ~ ( 0 ) ∥ 2 . \lVert\theta(t)-\tilde{\theta}(t)\rVert_2\leq\left(1-\frac{m}{4}t^2\right)\lVert\theta(0)-\tilde{\theta}(0)\rVert_2+t\lVert p(0)-\tilde{p}(0)\rVert_2. ∥ θ ( t ) − θ ~ ( t ) ∥ 2 ≤ ( 1 − 4 m t 2 ) ∥ θ ( 0 ) − θ ~ ( 0 ) ∥ 2 + t ∥ p ( 0 ) − p ~ ( 0 ) ∥ 2 .
Lemma B.2 (Proposition 1 in Durmus & Moulines [11 ] ). Let x ∗ ∈ R d x^*\in\mathbb{R}^d x ∗ ∈ R d be the global minimizer of a loss function f ( ⋅ ) f(\cdot) f ( ⋅ ) satisfying Assumption 4.1 and x π x^\pi x π be a random variable following distribution ∝ e − f ( x ) \propto e^{-f(x)} ∝ e − f ( x ) , then
E ∥ x ∗ − x π ∥ 2 2 ≤ d m . \mathbb{E}\lVert x^*-x^\pi\rVert_2^2\leq\frac{d}{m}. E ∥ x ∗ − x π ∥ 2 2 ≤ m d .
discrete error control
Lemma B.3 (Approximation error on position of classical HMC). Suppose p p p is the associated initial momentum of position q q q . Under Assumption 4.2,
∥ H η ( q ) − H ‾ η ( q ) ∥ 2 2 ≤ η 6 ( M 2 10 ∥ p ∥ 2 + M 4 η 2 60 ∥ q − θ ∗ ∥ 2 ) . \lVert\mathcal{H}_{\eta}(q)-\overline{\mathcal{H}}_{\eta}(q)\rVert_2^2\leq\eta^6\left(\frac{M^2}{10}\lVert p\rVert^2+\frac{M^4\eta^2}{60}\lVert q-\theta^*\rVert^2\right). ∥ H η ( q ) − H η ( q ) ∥ 2 2 ≤ η 6 ( 10 M 2 ∥ p ∥ 2 + 60 M 4 η 2 ∥ q − θ ∗ ∥ 2 ) .
Proof. By definitions,
H η ( q ) − H ‾ η ( q ) = q + η p − η 2 2 ∇ f ( q ) − ( q + ∫ 0 η p ( s ) d s ) , with p ( s ) = p − ∫ 0 s ∇ f ( q ( u ) ) d u (21) \mathcal{H}_{\eta}(q)-\overline{\mathcal{H}}_{\eta}(q)=q+\eta p-\frac{\eta^2}{2}\nabla f(q)-\left(q+\int_0^\eta p(s)\,ds\right),\qquad\text{with}\qquad p(s)=p-\int_0^s\nabla f(q(u))\,du \tag*{(21)} H η ( q ) − H η ( q ) = q + η p − 2 η 2 ∇ f ( q ) − ( q + ∫ 0 η p ( s ) d s ) , with p ( s ) = p − ∫ 0 s ∇ f ( q ( u )) d u (21)
Inserting p ( s ) = p − ∫ 0 s ∇ f ( q ( u ) ) d u p(s)=p-\int_{0}^{s}\nabla f(q(u))du p ( s ) = p − ∫ 0 s ∇ f ( q ( u )) d u and η 2 2 ∇ f ( q ) = ∫ 0 η ∫ 0 s ∇ f ( q ) d u d s \frac{\eta^{2}}{2}\nabla f(q)=\int_{0}^{\eta}\int_{0}^{s}\nabla f(q)duds 2 η 2 ∇ f ( q ) = ∫ 0 η ∫ 0 s ∇ f ( q ) d u d s , we get
H η ( q ) − H ‾ η ( q ) = ∫ 0 η ∫ 0 s ∇ f ( q ( u ) ) − ∇ f ( q ) d u d s \mathcal{H}_{\eta}(q)-\overline{\mathcal{H}}_{\eta}(q)=\int_{0}^{\eta}\int_{0}^{s}\nabla f(q(u))-\nabla f(q)duds H η ( q ) − H η ( q ) = ∫ 0 η ∫ 0 s ∇ f ( q ( u )) − ∇ f ( q ) d u d s
By Jensen inequality (i.e., Lemma B.12 with λ ≡ 1 \lambda\equiv1 λ ≡ 1 ) and M M M -smoothness assumption of ∇ f \nabla f ∇ f ,
∥ H η ( q ) − H ‾ η ( q ) ∥ 2 ≤ η 2 2 ∫ 0 η ∫ 0 s M 2 ∥ q ( u ) − q ∥ 2 d u d s . (22) \left\|\mathcal{H}_{\eta}(q)-\overline{\mathcal{H}}_{\eta}(q)\right\|^{2}\leq\frac{\eta^{2}}{2}\int_{0}^{\eta}\int_{0}^{s}M^{2}\left\|q(u)-q\right\|^{2}duds. \tag*{(22)} H η ( q ) − H η ( q ) 2 ≤ 2 η 2 ∫ 0 η ∫ 0 s M 2 ∥ q ( u ) − q ∥ 2 d u d s . (22)
In the following, we are going to apply Lemma B.1 to bound ∥ q ( u ) − q ∥ 2 \left\|q(u)-q\right\|^{2} ∥ q ( u ) − q ∥ 2 . First, by Cauchy–Schwarz inequality and Lemma B.12
∥ q ( u ) − q ∥ 2 = ∥ u p − ∫ 0 u ∫ 0 s ∇ f ( q ( t ) ) d t d s ∥ 2 ≤ 2 ∥ u p ∥ 2 + 2 ∥ ∫ 0 u ∫ 0 s ∇ f ( q ( t ) ) d t d s ∥ 2 \left\|q(u)-q\right\|^{2}=\left\|up-\int_{0}^{u}\int_{0}^{s}\nabla f(q(t))dtds\right\|^{2}\leq2\left\|up\right\|^{2}+2\left\|\int_{0}^{u}\int_{0}^{s}\nabla f(q(t))dtds\right\|^{2} ∥ q ( u ) − q ∥ 2 = u p − ∫ 0 u ∫ 0 s ∇ f ( q ( t )) d t d s 2 ≤ 2 ∥ u p ∥ 2 + 2 ∫ 0 u ∫ 0 s ∇ f ( q ( t )) d t d s 2
≤ 2 ∥ u p ∥ 2 + u 2 ∫ 0 u ∫ 0 s ∥ ∇ f ( q ( t ) ) ∥ 2 d t d s \leq2\left\|up\right\|^{2}+u^{2}\int_{0}^{u}\int_{0}^{s}\left\|\nabla f(q(t))\right\|^{2}dtds ≤ 2 ∥ u p ∥ 2 + u 2 ∫ 0 u ∫ 0 s ∥ ∇ f ( q ( t )) ∥ 2 d t d s
Inserting result from Lemma B.5 that ∥ ∇ f ( q ( t ) ) ∥ 2 ≤ 2 M 2 ( ∥ q − θ ∗ ∥ 2 + t 2 ∥ p ∥ 2 ) \left\|\nabla f(q(t))\right\|^{2}\leq2M^{2}\left(\left\|q-\theta^{*}\right\|^{2}+t^{2}\left\|p\right\|^{2}\right) ∥ ∇ f ( q ( t )) ∥ 2 ≤ 2 M 2 ( ∥ q − θ ∗ ∥ 2 + t 2 ∥ p ∥ 2 ) into the last inequality, we have
∥ q ( u ) − q ∥ 2 ≤ ( 2 u 2 + M 2 u 6 6 ) ∥ p ∥ 2 + M 2 u 4 ∥ q − θ ∗ ∥ 2 \left\|q(u)-q\right\|^{2}\leq\left(2u^{2}+\frac{M^{2}u^{6}}{6}\right)\left\|p\right\|^{2}+M^{2}u^{4}\left\|q-\theta^{*}\right\|^{2} ∥ q ( u ) − q ∥ 2 ≤ ( 2 u 2 + 6 M 2 u 6 ) ∥ p ∥ 2 + M 2 u 4 ∥ q − θ ∗ ∥ 2
Since u ≤ η ≤ 1 / ( 2 M ) u\leq\eta\leq1/(2\sqrt{M}) u ≤ η ≤ 1/ ( 2 M ) , we also have
∥ q ( u ) − q ∥ 2 ≤ 24 10 u 2 ∥ p ∥ 2 + M 2 u 4 ∥ q − θ ∗ ∥ 2 \left\|q(u)-q\right\|^{2}\leq\frac{24}{10}u^{2}\left\|p\right\|^{2}+M^{2}u^{4}\left\|q-\theta^{*}\right\|^{2} ∥ q ( u ) − q ∥ 2 ≤ 10 24 u 2 ∥ p ∥ 2 + M 2 u 4 ∥ q − θ ∗ ∥ 2
and inserting back to (20) yields the claim.
Lemma B.4 (Approximation error on momentum of classical HMC). Suppose q q q is the associated initial position of momentum p p p . Under Assumption 4.2 and η ≤ 1 / ( 2 M ) \eta\leq1/(2\sqrt{M}) η ≤ 1/ ( 2 M ) ,
∥ H η ( p ) − H ‾ η ( p ) ∥ 2 ≤ 5 2 η 4 M 4 ∥ p ∥ 2 + 2 3 η 6 M 4 ∥ q − θ ∗ ∥ 2 \left\|\mathcal{H}_{\eta}(p)-\overline{\mathcal{H}}_{\eta}(p)\right\|^{2}\leq\frac{5}{2}\eta^{4}M^{4}\left\|p\right\|^{2}+\frac{2}{3}\eta^{6}M^{4}\left\|q-\theta^{*}\right\|^{2} H η ( p ) − H η ( p ) 2 ≤ 2 5 η 4 M 4 ∥ p ∥ 2 + 3 2 η 6 M 4 ∥ q − θ ∗ ∥ 2
Proof. By definitions,
H η ( p ) − H ‾ η ( p ) = p − η 2 ( ∇ f ( q ) + ∇ f ( H η ( q ) ) ) − ( p − ∫ 0 η ∇ f ( q ( s ) ) d s ) \mathcal{H}_{\eta}(p)-\overline{\mathcal{H}}_{\eta}(p)=p-\frac{\eta}{2}\left(\nabla f(q)+\nabla f(\mathcal{H}_{\eta}(q))\right)-\left(p-\int_{0}^{\eta}\nabla f(q(s))ds\right) H η ( p ) − H η ( p ) = p − 2 η ( ∇ f ( q ) + ∇ f ( H η ( q )) ) − ( p − ∫ 0 η ∇ f ( q ( s )) d s )
Inserting ∇ f ( q ( s ) ) = ∇ f ( q ) + ∫ 0 s ∇ 2 f ( q ( u ) ) p ( u ) d u \nabla f(q(s))=\nabla f(q)+\int_{0}^{s}\nabla^{2}f(q(u))p(u)du ∇ f ( q ( s )) = ∇ f ( q ) + ∫ 0 s ∇ 2 f ( q ( u )) p ( u ) d u into above, we get
H η ( p ) − H ‾ η ( p ) = η 2 ( ∇ f ( q ) − ∇ f ( H η ( q ) ) ) + ∫ 0 η ∫ 0 s ∇ 2 f ( q ( u ) ) p ( u ) d u d s \mathcal{H}_{\eta}(p)-\overline{\mathcal{H}}_{\eta}(p)=\frac{\eta}{2}\left(\nabla f(q)-\nabla f(\mathcal{H}_{\eta}(q))\right)+\int_{0}^{\eta}\int_{0}^{s}\nabla^{2}f(q(u))p(u)duds H η ( p ) − H η ( p ) = 2 η ( ∇ f ( q ) − ∇ f ( H η ( q )) ) + ∫ 0 η ∫ 0 s ∇ 2 f ( q ( u )) p ( u ) d u d s
Applying Lemma B.12 , we can get
∥ H η ( p ) − H ‾ η ( p ) ∥ 2 ≤ 2 ∥ η 2 ( ∇ f ( q ) − ∇ f ( H η ( q ) ) ) ∥ 2 + 2 ∥ ∫ 0 η ∫ 0 s ∇ 2 f ( q ( u ) ) p ( u ) d u d s ∥ 2 \left\|\mathcal{H}_{\eta}(p)-\overline{\mathcal{H}}_{\eta}(p)\right\|^{2}\leq2\left\|\frac{\eta}{2}\left(\nabla f(q)-\nabla f(\mathcal{H}_{\eta}(q))\right)\right\|^{2}+2\left\|\int_{0}^{\eta}\int_{0}^{s}\nabla^{2}f(q(u))p(u)duds\right\|^{2} H η ( p ) − H η ( p ) 2 ≤ 2 2 η ( ∇ f ( q ) − ∇ f ( H η ( q )) ) 2 + 2 ∫ 0 η ∫ 0 s ∇ 2 f ( q ( u )) p ( u ) d u d s 2
≤ 2 ∥ η 2 ( ∇ f ( q ) − ∇ f ( H η ( q ) ) ) ∥ 2 + 2 η 2 2 ∫ 0 η ∫ 0 s ∥ ∇ 2 f ( q ( u ) ) p ( u ) ∥ 2 d u d s = η 2 2 ∥ ∇ f ( q ) − ∇ f ( H η ( q ) ) ∥ 2 + η 2 ∫ 0 η ∫ 0 s ∥ ∇ 2 f ( q ( u ) ) p ( u ) ∥ 2 d u d s . \begin{aligned}
\leq2\left\|\frac{\eta}{2}\left(\nabla f(q)-\nabla f(\mathcal{H}_{\eta}(q))\right)\right\|^{2}+2\frac{\eta^{2}}{2}\int_{0}^{\eta}\int_{0}^{s}\left\|\nabla^{2}f(q(u))p(u)\right\|^{2}duds \\
&=\frac{\eta^{2}}{2}\left\|\nabla f(q)-\nabla f(\mathcal{H}_{\eta}(q))\right\|^{2}+\eta^{2}\int_{0}^{\eta}\int_{0}^{s}\left\|\nabla^{2}f(q(u))p(u)\right\|^{2}duds.
\end{aligned} ≤ 2 2 η ( ∇ f ( q ) − ∇ f ( H η ( q )) ) 2 + 2 2 η 2 ∫ 0 η ∫ 0 s ∇ 2 f ( q ( u )) p ( u ) 2 d u d s = 2 η 2 ∥ ∇ f ( q ) − ∇ f ( H η ( q )) ∥ 2 + η 2 ∫ 0 η ∫ 0 s ∇ 2 f ( q ( u )) p ( u ) 2 d u d s .
Since f f f satisfies M M M -smoothness assumption, we further have
∥ H η ( p ) − H ‾ η ( p ) ∥ 2 ≤ η 2 M 2 2 ∥ q − H η ( q ) ∥ 2 + η 2 M 2 ∫ 0 η ∫ 0 s ∥ p ( u ) ∥ 2 d u d s (23) \left\|\mathcal{H}_{\eta}(p)-\overline{\mathcal{H}}_{\eta}(p)\right\|^{2}\leq\frac{\eta^{2}M^{2}}{2}\left\|q-\mathcal{H}_{\eta}(q)\right\|^{2}+\eta^{2}M^{2}\int_{0}^{\eta}\int_{0}^{s}\|p(u)\|^{2}\,du\,ds \tag*{(23)} H η ( p ) − H η ( p ) 2 ≤ 2 η 2 M 2 ∥ q − H η ( q ) ∥ 2 + η 2 M 2 ∫ 0 η ∫ 0 s ∥ p ( u ) ∥ 2 d u d s (23)
To bound the RHS, setting F = f F=f F = f in Lemma B.8 gives
∥ q − H η ( q ) ∥ 2 ≤ 2 η 2 ∥ p ∥ 2 + η 4 M 2 ∥ q − θ ∗ ∥ 2 \left\|q-\mathcal{H}_{\eta}(q)\right\|^{2}\leq2\eta^{2}\|p\|^{2}+\eta^{4}M^{2}\left\|q-\theta^{*}\right\|^{2} ∥ q − H η ( q ) ∥ 2 ≤ 2 η 2 ∥ p ∥ 2 + η 4 M 2 ∥ q − θ ∗ ∥ 2
and at the same time,
∥ p ( u ) ∥ 2 = ∥ p − ∫ 0 u ∇ f ( q ( s ) ) d s ∥ 2 ≤ 2 ∥ p ∥ 2 + 2 ∥ ∫ 0 u ∇ f ( q ( s ) ) d s ∥ 2 ≤ 2 ∥ p ∥ 2 + 2 u ∫ 0 u ∥ ∇ f ( q ( s ) ) ∥ 2 d s ≤ 2 ∥ p ∥ 2 + 2 u ∫ 0 u 2 M 2 ( ∥ q − θ ∗ ∥ 2 + s 2 ∥ p ∥ 2 ) d s = ( 2 + u 4 M 2 3 ) ∥ p ∥ 2 + 4 u 2 M 2 ∥ q − θ ∗ ∥ 2 ≤ 3 ∥ p ∥ 2 + 4 u 2 M 2 ∥ q − θ ∗ ∥ 2 , \begin{aligned}
\|p(u)\|^{2}&=\left\|p-\int_{0}^{u}\nabla f(q(s))\,ds\right\|^{2}\leq2\|p\|^{2}+2\left\|\int_{0}^{u}\nabla f(q(s))\,ds\right\|^{2}\\
&\leq2\|p\|^{2}+2u\int_{0}^{u}\|\nabla f(q(s))\|^{2}\,ds\leq2\|p\|^{2}+2u\int_{0}^{u}2M^{2}\left(\|q-\theta^{*}\|^{2}+s^{2}\|p\|^{2}\right)\,ds\\
&=\left(2+\frac{u^{4}M^{2}}{3}\right)\|p\|^{2}+4u^{2}M^{2}\|q-\theta^{*}\|^{2}\leq3\|p\|^{2}+4u^{2}M^{2}\|q-\theta^{*}\|^{2},
\end{aligned} ∥ p ( u ) ∥ 2 = p − ∫ 0 u ∇ f ( q ( s )) d s 2 ≤ 2∥ p ∥ 2 + 2 ∫ 0 u ∇ f ( q ( s )) d s 2 ≤ 2∥ p ∥ 2 + 2 u ∫ 0 u ∥∇ f ( q ( s )) ∥ 2 d s ≤ 2∥ p ∥ 2 + 2 u ∫ 0 u 2 M 2 ( ∥ q − θ ∗ ∥ 2 + s 2 ∥ p ∥ 2 ) d s = ( 2 + 3 u 4 M 2 ) ∥ p ∥ 2 + 4 u 2 M 2 ∥ q − θ ∗ ∥ 2 ≤ 3∥ p ∥ 2 + 4 u 2 M 2 ∥ q − θ ∗ ∥ 2 ,
where the first inequality is by Cauchy–Schwarz inequality, the second inequality is by Lemma B.12, the third inequality is by Lemma B.5, and the last inequality is by u ≤ η ≤ 1 / ( 2 M ) u\leq\eta\leq1/(2\sqrt{M}) u ≤ η ≤ 1/ ( 2 M ) .
Inserting these back to (23) yields
∥ H η ( p ) − H ‾ η ( p ) ∥ 2 ≤ 5 2 η 4 M 2 ∥ p ∥ 2 + 2 3 η 6 M 4 ∥ q − θ ∗ ∥ 2 . \left\|\mathcal{H}_{\eta}(p)-\overline{\mathcal{H}}_{\eta}(p)\right\|^{2}\leq\frac{5}{2}\eta^{4}M^{2}\|p\|^{2}+\frac{2}{3}\eta^{6}M^{4}\|q-\theta^{*}\|^{2}. H η ( p ) − H η ( p ) 2 ≤ 2 5 η 4 M 2 ∥ p ∥ 2 + 3 2 η 6 M 4 ∥ q − θ ∗ ∥ 2 .
This finishes the proof. □
Lemmas
Lemma B.5. Suppose p p p is the associated initial momentum of position q q q . Under Assumption 4.2
∥ ∇ f ( q ) ∥ 2 ≤ M 2 ∥ q − θ ∗ ∥ 2 , ∥ ∇ f ( q ( t ) ) ∥ 2 ≤ 2 M 2 ( ∥ q − θ ∗ ∥ 2 + t 2 ∥ p ∥ 2 ) \|\nabla f(q)\|^{2}\leq M^{2}\|q-\theta^{*}\|^{2},\qquad\|\nabla f(q(t))\|^{2}\leq2M^{2}\left(\|q-\theta^{*}\|^{2}+t^{2}\|p\|^{2}\right) ∥∇ f ( q ) ∥ 2 ≤ M 2 ∥ q − θ ∗ ∥ 2 , ∥∇ f ( q ( t )) ∥ 2 ≤ 2 M 2 ( ∥ q − θ ∗ ∥ 2 + t 2 ∥ p ∥ 2 )
Proof. Noting that ∥ ∇ f ( q ( t ) ) ∥ 2 = ∥ ∇ f ( q ( t ) ) − ∇ f ( θ ∗ ) ∥ 2 ≤ M 2 ∥ q ( t ) − θ ∗ ∥ 2 \|\nabla f(q(t))\|^{2}=\|\nabla f(q(t))-\nabla f(\theta^{*})\|^{2}\leq M^{2}\|q(t)-\theta^{*}\|^{2} ∥∇ f ( q ( t )) ∥ 2 = ∥∇ f ( q ( t )) − ∇ f ( θ ∗ ) ∥ 2 ≤ M 2 ∥ q ( t ) − θ ∗ ∥ 2 , and by Lemma B.1
∥ q ( t ) − θ ∗ ∥ ≤ ∥ q − θ ∗ ∥ + t ∥ p − 0 ∥ . \|q(t)-\theta^{*}\|\leq\|q-\theta^{*}\|+t\|p-0\|. ∥ q ( t ) − θ ∗ ∥ ≤ ∥ q − θ ∗ ∥ + t ∥ p − 0∥.
Noting that f f f satisfies M M M -smoothness assumption
∥ ∇ f ( q ( t ) ) ∥ 2 ≤ M 2 ∥ q ( t ) − θ ∗ ∥ 2 ≤ M 2 ( ∥ q − θ ∗ ∥ + t ∥ p ∥ ) 2 . \|\nabla f(q(t))\|^{2}\leq M^{2}\|q(t)-\theta^{*}\|^{2}\leq M^{2}\left(\|q-\theta^{*}\|+t\|p\|\right)^{2}. ∥∇ f ( q ( t )) ∥ 2 ≤ M 2 ∥ q ( t ) − θ ∗ ∥ 2 ≤ M 2 ( ∥ q − θ ∗ ∥ + t ∥ p ∥ ) 2 .
We finish the proof by applying Cauchy–Schwarz inequality on the RHS. □
Lemma B.6. For any q , p , q π ∈ R d q,p,q^{\pi}\in\mathbb{R}^{d} q , p , q π ∈ R d , let q k ( c ) = h ~ L F ( f ( c ) , q , ∇ f ( q ) , p 0 , η , k ) q_{k}^{(c)}=\widetilde{h}_{\mathrm{LF}}(f^{(c)},q,\nabla f(q),p_{0},\eta,k) q k ( c ) = h LF ( f ( c ) , q , ∇ f ( q ) , p 0 , η , k ) , q k = ∑ c = 1 N w c q k ( c ) q_{k}=\sum_{c=1}^{N}w_{c}q_{k}^{(c)} q k = ∑ c = 1 N w c q k ( c ) and q ~ k = H ~ η k ( q π ) \widetilde{q}_{k}=\widetilde{\mathcal{H}}_{\eta}^{k}(q^{\pi}) q k = H η k ( q π ) . Under the smoothness Assumption 4.2, we have
∑ c = 1 N w c E ∥ q k ( c ) − q k ∥ 2 ≤ 2 k 3 η 4 ∑ i = 1 k − 1 ( 16 M 2 E ∥ q i π − q i ∥ 2 + 16 M 2 E ∥ q π − q ∥ 2 + 4 ( k η ) 2 H ) \sum_{c=1}^{N}w_{c}\mathbb{E}\|q_{k}^{(c)}-q_{k}\|^{2}\leq2k^{3}\eta^{4}\sum_{i=1}^{k-1}\left(16M^{2}\mathbb{E}\|q_{i}^{\pi}-q_{i}\|^{2}+16M^{2}\mathbb{E}\|q^{\pi}-q\|^{2}+4(k\eta)^{2}H\right) c = 1 ∑ N w c E ∥ q k ( c ) − q k ∥ 2 ≤ 2 k 3 η 4 i = 1 ∑ k − 1 ( 16 M 2 E ∥ q i π − q i ∥ 2 + 16 M 2 E ∥ q π − q ∥ 2 + 4 ( k η ) 2 H )
where H : = max i ≤ K ∑ c = 1 N w c E ∥ 1 η ( ∇ f ( c ) ( q i π ) − ∇ f ( c ) ( q π ) + ∇ f ( q π ) − ∇ f ( q i π ) ) ∥ 2 H:=\max_{i\leq K}\sum_{c=1}^{N}w_{c}\mathbb{E}\left\|\frac{1}{\eta}\left(\nabla f^{(c)}(q_{i}^{\pi})-\nabla f^{(c)}(q^{\pi})+\nabla f(q^{\pi})-\nabla f(q_{i}^{\pi})\right)\right\|^{2} H := max i ≤ K ∑ c = 1 N w c E η 1 ( ∇ f ( c ) ( q i π ) − ∇ f ( c ) ( q π ) + ∇ f ( q π ) − ∇ f ( q i π ) ) 2 is a quantity measuring the federated heterogeneity.
Proof. To prove this lemma, we use mathematical induction to remove the discrete heterogeneous term ∑ c = 1 N w c E ∥ q k ( c ) − q k ∥ 2 \sum_{c=1}^{N}w_{c}\mathbb{E}\|q_{k}^{(c)}-q_{k}\|^{2} ∑ c = 1 N w c E ∥ q k ( c ) − q k ∥ 2 . In specific, we are going to use induction to prove that there are constants C 1 , C 2 C_{1},C_{2} C 1 , C 2 (to be determined later) such that
∑ c = 1 N w c E ∥ q j ( c ) − q j ∥ 2 ≤ ( j − 1 ) 3 η 4 ∑ k = 1 j − 1 ( C 1 M 2 E ∥ q k π − q k ∥ 2 + C 1 M 2 E ∥ q π − q ∥ 2 + C 2 ( k η ) 2 H ) . (24) \sum_{c=1}^{N}w_{c}\mathbb{E}\|q_{j}^{(c)}-q_{j}\|^{2}\leq(j-1)^{3}\eta^{4}\sum_{k=1}^{j-1}\left(C_{1}M^{2}\mathbb{E}\|q_{k}^{\pi}-q_{k}\|^{2}+C_{1}M^{2}\mathbb{E}\|q^{\pi}-q\|^{2}+C_{2}(k\eta)^{2}H\right). \tag*{(24)} c = 1 ∑ N w c E ∥ q j ( c ) − q j ∥ 2 ≤ ( j − 1 ) 3 η 4 k = 1 ∑ j − 1 ( C 1 M 2 E ∥ q k π − q k ∥ 2 + C 1 M 2 E ∥ q π − q ∥ 2 + C 2 ( k η ) 2 H ) . (24)
First, for j = 1 j=1 j = 1 , noting that q 1 ( c ) = q + p − η 2 ( ∇ f ( c ) ( q ) − ∇ f ( c ) ( q ) + ∇ f ( q ) ) q_{1}^{(c)}=q+p-\frac{\eta}{2}\left(\nabla f^{(c)}(q)-\nabla f^{(c)}(q)+\nabla f(q)\right) q 1 ( c ) = q + p − 2 η ( ∇ f ( c ) ( q ) − ∇ f ( c ) ( q ) + ∇ f ( q ) ) is constant for all c c c , thus
∑ c = 1 N w c E ∥ q j ( c ) − q j ∥ 2 = 0 , when j = 1. \sum_{c=1}^{N}w_{c}\mathbb{E}\|q_{j}^{(c)}-q_{j}\|^{2}=0,\qquad\text{when }j=1. c = 1 ∑ N w c E ∥ q j ( c ) − q j ∥ 2 = 0 , when j = 1.
Now, assume that (22) holds for j ≤ k j \le k j ≤ k . Next, we check it also holds for k + 1 k+1 k + 1 based on the assumption. By Lemma B.7, we have
∑ c = 1 N w c E ∥ q k + 1 ( c ) − q k + 1 ∥ 2 \sum_{c=1}^{N} w_c\mathbb{E}\lVert q_{k+1}^{(c)}-q_{k+1}\rVert^2 c = 1 ∑ N w c E ∥ q k + 1 ( c ) − q k + 1 ∥ 2
≤ 2 ( k + 1 ) 3 η 4 ∑ i = 1 k ( 4 M 2 ∑ c = 1 N w c E ∥ q i ( c ) − q i ∥ 2 + 4 M 2 E ∥ q i π − q i ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( i η ) 2 H ) \le2(k+1)^3\eta^4\sum_{i=1}^{k}\left(4M^2\sum_{c=1}^{N}w_c\mathbb{E}\lVert q_i^{(c)}-q_i\rVert^2+4M^2\mathbb{E}\lVert q_i^\pi-q_i\rVert^2+4M^2\mathbb{E}\lVert q^\pi-q\rVert^2+(i\eta)^2H\right) ≤ 2 ( k + 1 ) 3 η 4 i = 1 ∑ k ( 4 M 2 c = 1 ∑ N w c E ∥ q i ( c ) − q i ∥ 2 + 4 M 2 E ∥ q i π − q i ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( i η ) 2 H )
≤ 2 ( k + 1 ) 3 η 4 ∑ i = 1 k ( 4 M 2 i 3 η 4 ∑ j = 1 i − 1 ( C 1 M 2 E ∥ q j π − q j ∥ 2 + C 1 M 2 E ∥ q π − q ∥ 2 + C 2 ( j η ) 2 H ) ) \le2(k+1)^3\eta^4\sum_{i=1}^{k}\left(4M^2i^3\eta^4\sum_{j=1}^{i-1}\left(C_1M^2\mathbb{E}\lVert q_j^\pi-q_j\rVert^2+C_1M^2\mathbb{E}\lVert q^\pi-q\rVert^2+C_2(j\eta)^2H\right)\right) ≤ 2 ( k + 1 ) 3 η 4 i = 1 ∑ k ( 4 M 2 i 3 η 4 j = 1 ∑ i − 1 ( C 1 M 2 E ∥ q j π − q j ∥ 2 + C 1 M 2 E ∥ q π − q ∥ 2 + C 2 ( j η ) 2 H ) )
+ 2 ( k + 1 ) 3 η 4 ∑ i = 1 k ( 4 M 2 E ∥ q i π − q i ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( i η ) 2 H ) \qquad+2(k+1)^3\eta^4\sum_{i=1}^{k}\left(4M^2\mathbb{E}\lVert q_i^\pi-q_i\rVert^2+4M^2\mathbb{E}\lVert q^\pi-q\rVert^2+(i\eta)^2H\right) + 2 ( k + 1 ) 3 η 4 i = 1 ∑ k ( 4 M 2 E ∥ q i π − q i ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( i η ) 2 H )
where the second inequality is by our induction assumption for i ≤ k i\le k i ≤ k .
Noting that for any sequence { a j } \{a_j\} { a j } ,
∑ i = 1 k i 3 ∑ j = 1 i − 1 a j = ∑ j = 1 k − 1 ∑ i = j + 1 k i 3 a j ≤ ∑ j = 1 k − 1 k 4 a j \sum_{i=1}^{k}i^3\sum_{j=1}^{i-1}a_j=\sum_{j=1}^{k-1}\sum_{i=j+1}^{k}i^3a_j\le\sum_{j=1}^{k-1}k^4a_j i = 1 ∑ k i 3 j = 1 ∑ i − 1 a j = j = 1 ∑ k − 1 i = j + 1 ∑ k i 3 a j ≤ j = 1 ∑ k − 1 k 4 a j
Therefore, we further have
∑ c = 1 N w c E ∥ q k + 1 ( c ) − q k + 1 ∥ 2 ≤ ( k + 1 ) 3 η 4 ∑ j = 1 k ( ( 8 M 4 C 1 k 4 η 4 + 8 M 2 ) E ∥ q j π − q j ∥ 2 \sum_{c=1}^{N}w_c\mathbb{E}\lVert q_{k+1}^{(c)}-q_{k+1}\rVert^2\le(k+1)^3\eta^4\sum_{j=1}^{k}\left((8M^4C_1k^4\eta^4+8M^2)\mathbb{E}\lVert q_j^\pi-q_j\rVert^2
\right. c = 1 ∑ N w c E ∥ q k + 1 ( c ) − q k + 1 ∥ 2 ≤ ( k + 1 ) 3 η 4 j = 1 ∑ k ( ( 8 M 4 C 1 k 4 η 4 + 8 M 2 ) E ∥ q j π − q j ∥ 2
+ ( 8 M 4 C 1 k 4 η 4 + 8 M 2 ) E ∥ q π − q ∥ 2 + ( 8 M 2 C 2 k 4 η 4 + 2 ) H ) \left.
\qquad+(8M^4C_1k^4\eta^4+8M^2)\mathbb{E}\lVert q^\pi-q\rVert^2+(8M^2C_2k^4\eta^4+2)H\right) + ( 8 M 4 C 1 k 4 η 4 + 8 M 2 ) E ∥ q π − q ∥ 2 + ( 8 M 2 C 2 k 4 η 4 + 2 ) H )
By choosing C 1 , C 2 C_1,C_2 C 1 , C 2 such that
8 M 4 C 1 k 4 η 4 + 8 M 2 ≤ C 1 M 2 , 8 M 2 C 2 k 4 η 4 + 2 ≤ C 2 , 8M^4C_1k^4\eta^4+8M^2\le C_1M^2,\qquad8M^2C_2k^4\eta^4+2\le C_2, 8 M 4 C 1 k 4 η 4 + 8 M 2 ≤ C 1 M 2 , 8 M 2 C 2 k 4 η 4 + 2 ≤ C 2 ,
we can finish the induction. Recall that K η K\eta K η is set to be ≤ 1 / ( 2 M ) \le1/(2\sqrt{M}) ≤ 1/ ( 2 M ) . One choice is that C 1 = 16 , C 2 = 4 C_1=16,C_2=4 C 1 = 16 , C 2 = 4 . This finishes the proof.
Lemma B.7. Under the same notations and conditions of that of Lemma B.6,
∑ c = 1 N w c E ∥ q j ( c ) − q j ∥ 2 ≤ 2 j 3 η 4 ∑ k = 1 j − 1 ( 4 M 2 ∑ c = 1 N w c E ∥ q k ( c ) − q k ∥ 2 + 4 M 2 E ∥ q k π − q k ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( k η ) 2 H ) \sum_{c=1}^{N}w_c\mathbb{E}\lVert q_j^{(c)}-q_j\rVert^2\le2j^3\eta^4\sum_{k=1}^{j-1}\left(4M^2\sum_{c=1}^{N}w_c\mathbb{E}\lVert q_k^{(c)}-q_k\rVert^2+4M^2\mathbb{E}\lVert q_k^\pi-q_k\rVert^2+4M^2\mathbb{E}\lVert q^\pi-q\rVert^2+(k\eta)^2H\right) c = 1 ∑ N w c E ∥ q j ( c ) − q j ∥ 2 ≤ 2 j 3 η 4 k = 1 ∑ j − 1 ( 4 M 2 c = 1 ∑ N w c E ∥ q k ( c ) − q k ∥ 2 + 4 M 2 E ∥ q k π − q k ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( k η ) 2 H )
Proof. By definitions,
q j ( c ) − q j = q + j η p 0 − ( j η ) 2 2 ∇ f ( q ) − η 2 ∑ k = 1 j − 1 ∑ i = 1 k ( ∇ f ( c ) ( q i ( c ) ) − ∇ f ( c ) ( q ) ) q_j^{(c)}-q_j=q+j\eta p_0-\frac{(j\eta)^2}{2}\nabla f(q)-\eta^2\sum_{k=1}^{j-1}\sum_{i=1}^{k}\left(\nabla f^{(c)}(q_i^{(c)})-\nabla f^{(c)}(q)\right) q j ( c ) − q j = q + j η p 0 − 2 ( j η ) 2 ∇ f ( q ) − η 2 k = 1 ∑ j − 1 i = 1 ∑ k ( ∇ f ( c ) ( q i ( c ) ) − ∇ f ( c ) ( q ) )
− ∑ c = 1 N w c ( q + j η p 0 − ( j η ) 2 2 ∇ f ( q ) − η 2 ∑ k = 1 j − 1 ∑ i = 1 k ( ∇ f ( c ) ( q i ( c ) ) − ∇ f ( c ) ( q ) ) ) = η 2 ∑ k = 1 j − 1 ∑ i = 1 k ( ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) ) . \begin{aligned}
\qquad-\sum_{c=1}^{N}w_c\left(q+j\eta p_0-\frac{(j\eta)^2}{2}\nabla f(q)-\eta^2\sum_{k=1}^{j-1}\sum_{i=1}^{k}\left(\nabla f^{(c)}(q_i^{(c)})-\nabla f^{(c)}(q)\right)\right) \\
&=\eta^2\sum_{k=1}^{j-1}\sum_{i=1}^{k}\left(\sum_{\tilde c=1}^{N}w_{\tilde c}\left(\nabla f^{(\tilde c)}(q_i^{(\tilde c)})-\nabla f^{(\tilde c)}(q)\right)-\nabla f^{(c)}(q_i^{(c)})+\nabla f^{(c)}(q)\right).
\end{aligned} − c = 1 ∑ N w c ( q + j η p 0 − 2 ( j η ) 2 ∇ f ( q ) − η 2 k = 1 ∑ j − 1 i = 1 ∑ k ( ∇ f ( c ) ( q i ( c ) ) − ∇ f ( c ) ( q ) ) ) = η 2 k = 1 ∑ j − 1 i = 1 ∑ k ( c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) ) .
By Lemma B.12, we have
∥ q j ( c ) − q j ∥ 2 ≤ j ( j − 1 ) 2 ∑ k = 1 j − 1 ∑ i = 1 k η 2 ∑ c ~ = 1 N w c ~ ∥ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) ∥ 2 = j ( j − 1 ) 2 ∑ i = 1 j − 1 ∑ k = i j − 1 η 4 ∑ c ~ = 1 N w c ~ ∥ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) ∥ 2 (25) \begin{aligned}
\lVert q_j^{(c)}-q_j\rVert^2\le\frac{j(j-1)}{2}\sum_{k=1}^{j-1}\sum_{i=1}^{k}\eta^2\sum_{\tilde c=1}^{N}w_{\tilde c}\left\lVert\left(\nabla f^{(\tilde c)}(q_i^{(\tilde c)})-\nabla f^{(\tilde c)}(q)\right)-\nabla f^{(c)}(q_i^{(c)})+\nabla f^{(c)}(q)\right\rVert^2 \\
&=\frac{j(j-1)}{2}\sum_{i=1}^{j-1}\sum_{k=i}^{j-1}\eta^4\sum_{\tilde c=1}^{N}w_{\tilde c}\left\lVert\left(\nabla f^{(\tilde c)}(q_i^{(\tilde c)})-\nabla f^{(\tilde c)}(q)\right)-\nabla f^{(c)}(q_i^{(c)})+\nabla f^{(c)}(q)\right\rVert^2 \tag*{(25)}
\end{aligned} ∥ q j ( c ) − q j ∥ 2 ≤ 2 j ( j − 1 ) k = 1 ∑ j − 1 i = 1 ∑ k η 2 c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) 2 = 2 j ( j − 1 ) i = 1 ∑ j − 1 k = i ∑ j − 1 η 4 c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) 2 (25)
It follows that
∥ q j ( c ) − q j ∥ 2 ≤ j 3 η 4 2 ∑ i = 1 j − 1 ∥ ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) ∥ 2 . (26) \left\lVert q_j^{(c)}-q_j\right\rVert^2 \le\frac{j^3\eta^4}{2}\sum_{i=1}^{j-1}\left\lVert\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q)\right\rVert^2. \tag*{(26)} q j ( c ) − q j 2 ≤ 2 j 3 η 4 i = 1 ∑ j − 1 c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) 2 . (26)
The error ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) \sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q) ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) can be split into several part as follow
∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) = ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q i ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q i ) ⏟ discrete heterogeneity + ∇ f ( c ) ( q i π ) − ∇ f ( c ) ( q i ) + ∇ f ( q i ) − ∇ f ( q i π ) ⏟ convergence error + ∇ f ( c ) ( q ) − ∇ f ( c ) ( q π ) + ∇ f ( q π ) − ∇ f ( q ) ⏟ convergence error + ∇ f ( c ) ( q π ) − ∇ f ( c ) ( q i π ) + ∇ f ( q i π ) − ∇ f ( q π ) ⏟ oracle heterogeneity . \begin{aligned}
&\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q) \\
={}&\underbrace{\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q_i)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q_i)}_{\text{discrete heterogeneity}} \\
&+\underbrace{\nabla f^{(c)}(q_i^\pi)-\nabla f^{(c)}(q_i)+\nabla f(q_i)-\nabla f(q_i^\pi)}_{\text{convergence error}} \\
&+\underbrace{\nabla f^{(c)}(q)-\nabla f^{(c)}(q^\pi)+\nabla f(q^\pi)-\nabla f(q)}_{\text{convergence error}} \\
&+\underbrace{\nabla f^{(c)}(q^\pi)-\nabla f^{(c)}(q_i^\pi)+\nabla f(q_i^\pi)-\nabla f(q^\pi)}_{\text{oracle heterogeneity}}.
\end{aligned} = c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) discrete heterogeneity c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q i ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q i ) + convergence error ∇ f ( c ) ( q i π ) − ∇ f ( c ) ( q i ) + ∇ f ( q i ) − ∇ f ( q i π ) + convergence error ∇ f ( c ) ( q ) − ∇ f ( c ) ( q π ) + ∇ f ( q π ) − ∇ f ( q ) + oracle heterogeneity ∇ f ( c ) ( q π ) − ∇ f ( c ) ( q i π ) + ∇ f ( q i π ) − ∇ f ( q π ) .
Again, by Lemma B.12,
∥ ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) ∥ 2 ≤ 4 ( A ( c ) + B ( c ) + C ( c ) + D ( c ) ) (27) \left\lVert\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q)\right\rVert^2 \le4\left(A^{(c)}+B^{(c)}+C^{(c)}+D^{(c)}\right) \tag*{(27)} c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q ) 2 ≤ 4 ( A ( c ) + B ( c ) + C ( c ) + D ( c ) ) (27)
where
A ( c ) : = ∥ ∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q i ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q i ) ∥ 2 , A^{(c)}:=\left\lVert\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q_i)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q_i)\right\rVert^2, A ( c ) := c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q i ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q i ) 2 ,
B ( c ) : = ∥ ∇ f ( c ) ( q i π ) − ∇ f ( c ) ( q i ) + ∇ f ( q i ) − ∇ f ( q i π ) ∥ 2 B^{(c)}:=\left\lVert\nabla f^{(c)}(q_i^\pi)-\nabla f^{(c)}(q_i)+\nabla f(q_i)-\nabla f(q_i^\pi)\right\rVert^2 B ( c ) := ∇ f ( c ) ( q i π ) − ∇ f ( c ) ( q i ) + ∇ f ( q i ) − ∇ f ( q i π ) 2
C ( c ) : = ∥ ∇ f ( c ) ( q ) − ∇ f ( c ) ( q π ) + ∇ f ( q π ) − ∇ f ( q ) ∥ 2 , C^{(c)}:=\left\lVert\nabla f^{(c)}(q)-\nabla f^{(c)}(q^\pi)+\nabla f(q^\pi)-\nabla f(q)\right\rVert^2, C ( c ) := ∇ f ( c ) ( q ) − ∇ f ( c ) ( q π ) + ∇ f ( q π ) − ∇ f ( q ) 2 ,
D ( c ) : = ∥ ∇ f ( c ) ( q π ) − ∇ f ( c ) ( q i π ) + ∇ f ( q i π ) − ∇ f ( q π ) ∥ 2 . D^{(c)}:=\left\lVert\nabla f^{(c)}(q^\pi)-\nabla f^{(c)}(q_i^\pi)+\nabla f(q_i^\pi)-\nabla f(q^\pi)\right\rVert^2. D ( c ) := ∇ f ( c ) ( q π ) − ∇ f ( c ) ( q i π ) + ∇ f ( q i π ) − ∇ f ( q π ) 2 .
Consider A ( c ) A^{(c)} A ( c ) first, observe that
∑ c ~ = 1 N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q i ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q i ) = ∑ c ~ = 1 N w c ~ − I ( c ~ = c ) 2 ( 1 − w c ) ⋅ 2 ( 1 − w c ) ( ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) ) \begin{aligned}
&\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left(\nabla f^{(\tilde{c})}\left(q_i^{(\tilde{c})}\right)-\nabla f^{(\tilde{c})}(q_i)\right)-\nabla f^{(c)}\left(q_i^{(c)}\right)+\nabla f^{(c)}(q_i) \\
={}&\sum_{\tilde{c}=1}^{N}\frac{w_{\tilde{c}}-\mathbb{I}(\tilde{c}=c)}{2(1-w_c)}\cdot2(1-w_c)\left(\nabla f^{(\tilde{c})}\left(q_k^{(c)}\right)-\nabla f^{(\tilde{c})}(q_k)\right)
\end{aligned} = c ~ = 1 ∑ N w c ~ ( ∇ f ( c ~ ) ( q i ( c ~ ) ) − ∇ f ( c ~ ) ( q i ) ) − ∇ f ( c ) ( q i ( c ) ) + ∇ f ( c ) ( q i ) c ~ = 1 ∑ N 2 ( 1 − w c ) w c ~ − I ( c ~ = c ) ⋅ 2 ( 1 − w c ) ( ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) )
and that ∑ c ~ = 1 N ∣ w c ~ − I ( c ~ = c ) ∣ 2 ( 1 − w c ) = 1 \sum_{\tilde{c}=1}^{N}\frac{\left|w_{\tilde{c}}-\mathbb{I}(\tilde{c}=c)\right|}{2(1-w_c)}=1 ∑ c ~ = 1 N 2 ( 1 − w c ) ∣ w c ~ − I ( c ~ = c ) ∣ = 1 , by Lemma B.12
∑ c = 1 N w c A ( c ) ≤ ∑ c = 1 N w c ∑ c ~ = 1 N ∣ w c ~ − I ( c ~ = c ) ∣ 2 ( 1 − w c ) ∥ ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) ∥ 2 = 2 ∑ c ~ = 1 N w c ~ ∑ c ≠ c ~ N w c ( 1 − w c ) + ( 1 − w c ~ 2 ) ∥ ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) ∥ 2 ≤ 4 ∑ c ~ = 1 N w c ~ ∥ ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) ∥ 2 \begin{aligned}
\sum_{c=1}^{N}w_cA^{(c)}
&\le\sum_{c=1}^{N}w_c\sum_{\tilde{c}=1}^{N}\left|w_{\tilde{c}}-\mathbb{I}(\tilde{c}=c)\right|2(1-w_c)\left\lVert\nabla f^{(\tilde{c})}\left(q_k^{(c)}\right)-\nabla f^{(\tilde{c})}(q_k)\right\rVert^2 \\
&=2\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\sum_{c\ne\tilde{c}}^{N}w_c(1-w_c)+(1-w_{\tilde{c}}^2)\left\lVert\nabla f^{(\tilde{c})}\left(q_k^{(c)}\right)-\nabla f^{(\tilde{c})}(q_k)\right\rVert^2 \\
&\le4\sum_{\tilde{c}=1}^{N}w_{\tilde{c}}\left\lVert\nabla f^{(\tilde{c})}\left(q_k^{(c)}\right)-\nabla f^{(\tilde{c})}(q_k)\right\rVert^2
\end{aligned} c = 1 ∑ N w c A ( c ) ≤ c = 1 ∑ N w c c ~ = 1 ∑ N ∣ w c ~ − I ( c ~ = c ) ∣ 2 ( 1 − w c ) ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) 2 = 2 c ~ = 1 ∑ N w c ~ c = c ~ ∑ N w c ( 1 − w c ) + ( 1 − w c ~ 2 ) ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) 2 ≤ 4 c ~ = 1 ∑ N w c ~ ∇ f ( c ~ ) ( q k ( c ) ) − ∇ f ( c ~ ) ( q k ) 2
Further, by smoothness assumption,
∑ c = 1 N w c A ( c ) ≤ 4 ∑ c = 1 N w c M 2 ∥ q k ( c ) − q k ∥ 2 (28) \sum_{c=1}^{N} w_c A^{(c)} \le4\sum_{c=1}^{N} w_c M^2\lVert q_k^{(c)}-q_k\rVert^2 \tag*{(28)} c = 1 ∑ N w c A ( c ) ≤ 4 c = 1 ∑ N w c M 2 ∥ q k ( c ) − q k ∥ 2 (28)
Similarly, for B ( c ) B^{(c)} B ( c ) and C ( c ) C^{(c)} C ( c ) , we have
∑ c = 1 N w c B ( c ) ≤ 4 ∑ c = 1 N w c M 2 ∥ q k π − q k ∥ 2 = 4 M 2 ∥ q k π − q k ∥ 2 ∑ c = 1 N w c C ( c ) ≤ 4 ∑ c = 1 N w c M 2 ∥ q π − q ∥ 2 = 4 M 2 ∥ q π − q ∥ 2 (29) \begin{aligned}
\sum_{c=1}^{N}w_cB^{(c)}&\le4\sum_{c=1}^{N}w_cM^2\lVert q_k^\pi-q_k\rVert^2=4M^2\lVert q_k^\pi-q_k\rVert^2\\
\sum_{c=1}^{N}w_cC^{(c)}&\le4\sum_{c=1}^{N}w_cM^2\lVert q^\pi-q\rVert^2=4M^2\lVert q^\pi-q\rVert^2 \tag*{(29)}
\end{aligned} c = 1 ∑ N w c B ( c ) c = 1 ∑ N w c C ( c ) ≤ 4 c = 1 ∑ N w c M 2 ∥ q k π − q k ∥ 2 = 4 M 2 ∥ q k π − q k ∥ 2 ≤ 4 c = 1 ∑ N w c M 2 ∥ q π − q ∥ 2 = 4 M 2 ∥ q π − q ∥ 2 (29)
For D ( c ) D^{(c)} D ( c ) , by definitions, we directly have
∑ c = 1 N w c E D ( c ) ≤ ( k η ) 2 H (30) \sum_{c=1}^{N}w_c\mathbb{E}D^{(c)}\le(k\eta)^2H \tag*{(30)} c = 1 ∑ N w c E D ( c ) ≤ ( k η ) 2 H (30)
Combining (23)–(27), we have
∑ c = 1 N w c E ∥ q j ( c ) − q j ∥ 2 ≤ 2 j 3 η 4 ∑ k = 1 j − 1 ( 4 M 2 ∑ c = 1 N w c E ∥ q k ( c ) − q k ∥ 2 + 4 M 2 E ∥ q k π − q k ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( k η ) 2 H ) \sum_{c=1}^{N}w_c\mathbb{E}\lVert q_j^{(c)}-q_j\rVert^2\le2j^3\eta^4\sum_{k=1}^{j-1}\left(4M^2\sum_{c=1}^{N}w_c\mathbb{E}\lVert q_k^{(c)}-q_k\rVert^2+4M^2\mathbb{E}\lVert q_k^\pi-q_k\rVert^2+4M^2\mathbb{E}\lVert q^\pi-q\rVert^2+(k\eta)^2H\right) c = 1 ∑ N w c E ∥ q j ( c ) − q j ∥ 2 ≤ 2 j 3 η 4 k = 1 ∑ j − 1 ( 4 M 2 c = 1 ∑ N w c E ∥ q k ( c ) − q k ∥ 2 + 4 M 2 E ∥ q k π − q k ∥ 2 + 4 M 2 E ∥ q π − q ∥ 2 + ( k η ) 2 H )
This finishes the proof.
Lemma B.8 (0-th order Approximation Bound). Let q 0 , p 0 ∈ R d q_0,p_0\in\mathbb{R}^d q 0 , p 0 ∈ R d be two vectors. For any F ( ⋅ ) : R d ↦ R F(\cdot):\mathbb{R}^d\mapsto\mathbb{R} F ( ⋅ ) : R d ↦ R satisfying smoothness Assumption 4.2, then q K = h ~ L F ( F , q 0 , ∇ f ( q 0 ) , p 0 , η , k ) q_K=\widetilde{h}_{\mathrm{LF}}(F,q_0,\nabla f(q_0),p_0,\eta,k) q K = h LF ( F , q 0 , ∇ f ( q 0 ) , p 0 , η , k ) satisfies
∥ q k − q 0 ∥ 2 ≤ 2 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 M 2 ∥ q 0 − θ ∗ ∥ 2 (31) \lVert q_k-q_0\rVert^2\le2(k\eta)^2\lVert p_0\rVert^2+(k\eta)^4M^2\lVert q_0-\theta^*\rVert^2 \tag*{(31)} ∥ q k − q 0 ∥ 2 ≤ 2 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 M 2 ∥ q 0 − θ ∗ ∥ 2 (31) ∥ ∇ F ( q k ) − ∇ F ( q 0 ) ∥ 2 ≤ 2 M 2 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 M 4 ∥ q 0 − θ ∗ ∥ 2 (32) \lVert\nabla F(q_k)-\nabla F(q_0)\rVert^2\le2M^2(k\eta)^2\lVert p_0\rVert^2+(k\eta)^4M^4\lVert q_0-\theta^*\rVert^2 \tag*{(32)} ∥ ∇ F ( q k ) − ∇ F ( q 0 ) ∥ 2 ≤ 2 M 2 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 M 4 ∥ q 0 − θ ∗ ∥ 2 (32)
Note that we actually prove 30, which is an interesting result in the sense that the k k k -th leapfrog step can be bounded by the shift vector ∇ f ( q 0 ) \nabla f(q_0) ∇ f ( q 0 ) rather than ∇ F ( q 0 ) \nabla F(q_0) ∇ F ( q 0 ) .
Proof. We are going to prove
∥ q k − q 0 ∥ 2 ≤ 2 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 . (33) \lVert q_k-q_0\rVert^2\le2(k\eta)^2\lVert p_0\rVert^2+(k\eta)^4\lVert\nabla f(q_0)\rVert^2. \tag*{(33)} ∥ q k − q 0 ∥ 2 ≤ 2 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 . (33)
We prove claim (30) by induction. Then the claim (28) and (29) follows directly from (30) and M M M -smoothness Assumption 4.2 applied with ∇ f ( θ ∗ ) = 0 \nabla f(\theta^*)=0 ∇ f ( θ ∗ ) = 0 .
First, according to the definitions and Algorithm 1, we can write the full expression of q k q_k q k as follow
q k = q 0 + k η p 0 − ( k η ) 2 2 ∇ f ( q 0 ) − η 2 ∑ j = 1 k − 1 ( k − j ) ( ∇ F ( q j ) − ∇ F ( q 0 ) ) q_k=q_0+k\eta p_0-\frac{(k\eta)^2}{2}\nabla f(q_0)-\eta^2\sum_{j=1}^{k-1}(k-j)(\nabla F(q_j)-\nabla F(q_0)) q k = q 0 + k η p 0 − 2 ( k η ) 2 ∇ f ( q 0 ) − η 2 j = 1 ∑ k − 1 ( k − j ) ( ∇ F ( q j ) − ∇ F ( q 0 ))
which is proved by Lemma B.9.
For claim (30) with k = 1 k=1 k = 1 , by Cauchy–Schwarz inequality, we have that
∥ q 1 − q 0 ∥ 2 = ∥ η p 0 − η 2 2 ∇ f ( q 0 ) ∥ 2 ≤ 2 ∥ η p 0 ∥ 2 + 2 ∥ η 2 2 ∇ f ( q 0 ) ∥ 2 \lVert q_1-q_0\rVert^2=\left\lVert\eta p_0-\frac{\eta^2}{2}\nabla f(q_0)\right\rVert^2\le2\lVert\eta p_0\rVert^2+2\left\lVert\frac{\eta^2}{2}\nabla f(q_0)\right\rVert^2 ∥ q 1 − q 0 ∥ 2 = η p 0 − 2 η 2 ∇ f ( q 0 ) 2 ≤ 2 ∥ η p 0 ∥ 2 + 2 2 η 2 ∇ f ( q 0 ) 2
Next, we assume that the claim (30) holds for j = 1 , 2 , … , k − 1 j=1,2,\ldots,k-1 j = 1 , 2 , … , k − 1 . By direct calculations, for any c 1 , c 2 , c 3 > 0 c_1,c_2,c_3>0 c 1 , c 2 , c 3 > 0 such that ∑ i c i = 1 \sum_i c_i=1 ∑ i c i = 1 we have
∥ q k − q 0 ∥ 2 ≤ 1 c 1 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 4 c 2 ∥ ∇ f ( q 0 ) ∥ 2 + ∑ j = 1 k − 1 ( k − j ) η 4 k 3 6 j c 3 ∥ ∇ F ( q j ) − ∇ F ( q 0 ) ∥ 2 ≤ 1 c 1 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 4 c 2 ∥ ∇ f ( q 0 ) ∥ 2 + ∑ j = 1 k − 1 ( k − j ) η 4 k 3 M 2 6 j c 3 ∥ q j − q 0 ∥ 2 ≤ 1 c 1 ( k η ) 2 ∥ p 0 ∥ 2 + ( k η ) 4 4 c 2 ∥ ∇ f ( q 0 ) ∥ 2 + ∑ j = 1 k − 1 ( k − j ) η 4 k 3 M 2 6 j c 3 ⋅ ( 2 ( j η ) 2 ∥ p 0 ∥ 2 + ( j η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 ) ≤ ( 1 c 1 + M 2 6 c 3 2 ( k η ) 4 6 ) ( k η ) 2 ∥ p 0 ∥ 2 + ( 1 4 c 2 + M 2 6 c 3 ( k η ) 4 20 ) ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 . \begin{aligned}
\lVert q_k-q_0\rVert^2
&\le\frac{1}{c_1}(k\eta)^2\lVert p_0\rVert^2+\frac{(k\eta)^4}{4c_2}\lVert\nabla f(q_0)\rVert^2+\sum_{j=1}^{k-1}\frac{(k-j)\eta^4 k^3}{6jc_3}\lVert\nabla F(q_j)-\nabla F(q_0)\rVert^2\\
&\le\frac{1}{c_1}(k\eta)^2\lVert p_0\rVert^2+\frac{(k\eta)^4}{4c_2}\lVert\nabla f(q_0)\rVert^2+\sum_{j=1}^{k-1}\frac{(k-j)\eta^4 k^3M^2}{6jc_3}\lVert q_j-q_0\rVert^2\\
&\le\frac{1}{c_1}(k\eta)^2\lVert p_0\rVert^2+\frac{(k\eta)^4}{4c_2}\lVert\nabla f(q_0)\rVert^2+\sum_{j=1}^{k-1}\frac{(k-j)\eta^4 k^3M^2}{6jc_3}\cdot\left(2(j\eta)^2\lVert p_0\rVert^2+(j\eta)^4\lVert\nabla f(q_0)\rVert^2\right)\\
&\le\left(\frac{1}{c_1}+\frac{M^2}{6c_3}\frac{2(k\eta)^4}{6}\right)(k\eta)^2\lVert p_0\rVert^2+\left(\frac{1}{4c_2}+\frac{M^2}{6c_3}\frac{(k\eta)^4}{20}\right)(k\eta)^4\lVert\nabla f(q_0)\rVert^2.
\end{aligned} ∥ q k − q 0 ∥ 2 ≤ c 1 1 ( k η ) 2 ∥ p 0 ∥ 2 + 4 c 2 ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 + j = 1 ∑ k − 1 6 j c 3 ( k − j ) η 4 k 3 ∥ ∇ F ( q j ) − ∇ F ( q 0 ) ∥ 2 ≤ c 1 1 ( k η ) 2 ∥ p 0 ∥ 2 + 4 c 2 ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 + j = 1 ∑ k − 1 6 j c 3 ( k − j ) η 4 k 3 M 2 ∥ q j − q 0 ∥ 2 ≤ c 1 1 ( k η ) 2 ∥ p 0 ∥ 2 + 4 c 2 ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 + j = 1 ∑ k − 1 6 j c 3 ( k − j ) η 4 k 3 M 2 ⋅ ( 2 ( j η ) 2 ∥ p 0 ∥ 2 + ( j η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 ) ≤ ( c 1 1 + 6 c 3 M 2 6 2 ( k η ) 4 ) ( k η ) 2 ∥ p 0 ∥ 2 + ( 4 c 2 1 + 6 c 3 M 2 20 ( k η ) 4 ) ( k η ) 4 ∥ ∇ f ( q 0 ) ∥ 2 .
where the first inequality is due to Lemma B.12 and noting that c 1 + c 2 + ∑ j = 1 k − 1 ( k − j ) j ( k 3 − k ) / 6 c 3 = 1 c_1+c_2+\frac{\sum_{j=1}^{k-1}(k-j)j}{(k^3-k)/6}c_3=1 c 1 + c 2 + ( k 3 − k ) /6 ∑ j = 1 k − 1 ( k − j ) j c 3 = 1 ; the second inequality is due to smoothness Assumption 4.2; the third inequality holds by the induction assumption; the fourth inequality is by ∑ j = 1 k − 1 ( k − j ) j = k 3 − k 6 ≤ k 3 6 \sum_{j=1}^{k-1}(k-j)j=\frac{k^3-k}{6}\le\frac{k^3}{6} ∑ j = 1 k − 1 ( k − j ) j = 6 k 3 − k ≤ 6 k 3 and ∑ j = 1 k − 1 ( k − j ) j 3 = k 5 20 − k 3 12 + k 20 ≤ k 5 20 \sum_{j=1}^{k-1}(k-j)j^3=\frac{k^5}{20}-\frac{k^3}{12}+\frac{k}{20}\le\frac{k^5}{20} ∑ j = 1 k − 1 ( k − j ) j 3 = 20 k 5 − 12 k 3 + 20 k ≤ 20 k 5 . The completion of the induction follows by step size assumption K η ≤ 1 / M K\eta\le1/\sqrt{M} K η ≤ 1/ M and setting ( c 1 , c 2 , c 3 ) = ( 3 5 , 1 3 , 1 15 ) (c_1,c_2,c_3)=\left(\frac{3}{5},\frac{1}{3},\frac{1}{15}\right) ( c 1 , c 2 , c 3 ) = ( 5 3 , 3 1 , 15 1 ) in the last inequality. Therefore, we conclude the proof of (30). □ \square □
Lemma B.9. For q k = h ~ L F ( F , q 0 , ∇ f ( q 0 ) , p 0 , η , k ) q_k=\widetilde h_{\mathrm{LF}}(F,q_0,\nabla f(q_0),p_0,\eta,k) q k = h LF ( F , q 0 , ∇ f ( q 0 ) , p 0 , η , k ) and p k = p k − 1 − η ( ∇ F ( q k − 1 ) + ∇ F ( q k ) ) / 2 + η ( ∇ F ( q 0 ) − ∇ f ( q 0 ) ) p_k=p_{k-1}-\eta(\nabla F(q_{k-1})+\nabla F(q_k))/2+\eta(\nabla F(q_0)-\nabla f(q_0)) p k = p k − 1 − η ( ∇ F ( q k − 1 ) + ∇ F ( q k )) /2 + η ( ∇ F ( q 0 ) − ∇ f ( q 0 )) , we can rewrite as
q k = q 0 + k η p 0 − ( k η ) 2 2 ∇ f ( q 0 ) − η 2 ∑ j = 1 k − 1 ( k − j ) ( ∇ F ( q j ) − ∇ F ( q 0 ) ) (34) q_k=q_0+k\eta p_0-\frac{(k\eta)^2}{2}\nabla f(q_0)-\eta^2\sum_{j=1}^{k-1}(k-j)(\nabla F(q_j)-\nabla F(q_0)) \tag*{(34)} q k = q 0 + k η p 0 − 2 ( k η ) 2 ∇ f ( q 0 ) − η 2 j = 1 ∑ k − 1 ( k − j ) ( ∇ F ( q j ) − ∇ F ( q 0 )) (34) p k = p 0 − k η ∇ f ( q 0 ) − η ∑ j = 1 k − 1 ( ∇ F ( q j ) − ∇ F ( q 0 ) ) − η 2 ( ∇ F ( q k ) − ∇ F ( q 0 ) ) . (35) p_k=p_0-k\eta\nabla f(q_0)-\eta\sum_{j=1}^{k-1}(\nabla F(q_j)-\nabla F(q_0))-\frac{\eta}{2}(\nabla F(q_k)-\nabla F(q_0)). \tag*{(35)} p k = p 0 − k η ∇ f ( q 0 ) − η j = 1 ∑ k − 1 ( ∇ F ( q j ) − ∇ F ( q 0 )) − 2 η ( ∇ F ( q k ) − ∇ F ( q 0 )) . (35)
Proof. For simplicity of notations, we use f ~ ( ⋅ ) : = F ( ⋅ ) − F ( q 0 ) + f ( q 0 ) \widetilde f(\cdot):=F(\cdot)-F(q_0)+f(q_0) f ( ⋅ ) := F ( ⋅ ) − F ( q 0 ) + f ( q 0 ) . According to Algorithm 1,
q k = q k − 1 + η p k − 1 − η 2 2 ∇ f ~ ( q k − 1 ) , p k = p k − 1 − η ( ∇ f ~ ( q k − 1 ) + ∇ f ~ ( q k ) ) / 2 (36) q_k=q_{k-1}+\eta p_{k-1}-\frac{\eta^2}{2}\nabla\widetilde f(q_{k-1}),\qquad p_k=p_{k-1}-\eta(\nabla\widetilde f(q_{k-1})+\nabla\widetilde f(q_k))/2 \tag*{(36)} q k = q k − 1 + η p k − 1 − 2 η 2 ∇ f ( q k − 1 ) , p k = p k − 1 − η ( ∇ f ( q k − 1 ) + ∇ f ( q k )) /2 (36)
Summing from k = 1 , … , k k=1,\ldots,k k = 1 , … , k on both side of the second equation of (33), we can get
p k = p 0 − η 2 ∇ f ~ ( q 0 ) − η ∑ j = 1 k − 1 ∇ f ~ ( q j ) − η 2 ∇ f ~ ( q k ) . p_k=p_0-\frac{\eta}{2}\nabla\widetilde f(q_0)-\eta\sum_{j=1}^{k-1}\nabla\widetilde f(q_j)-\frac{\eta}{2}\nabla\widetilde f(q_k). p k = p 0 − 2 η ∇ f ( q 0 ) − η j = 1 ∑ k − 1 ∇ f ( q j ) − 2 η ∇ f ( q k ) .
This proves (32). Inserting this into the first equality of (33), we can get
q k = q k − 1 + p 0 − η 2 2 ∇ f ~ ( q 0 ) − η 2 ∑ j = 1 k − 1 ∇ f ~ ( q j ) q_k=q_{k-1}+p_0-\frac{\eta^2}{2}\nabla\widetilde f(q_0)-\eta^2\sum_{j=1}^{k-1}\nabla\widetilde f(q_j) q k = q k − 1 + p 0 − 2 η 2 ∇ f ( q 0 ) − η 2 j = 1 ∑ k − 1 ∇ f ( q j )
Summing from k = 1 , … , k k=1,\ldots,k k = 1 , … , k on both side yields
q k = q 0 + k η p 0 − ( k η ) 2 2 ∇ f ( q 0 ) − η 2 ∑ j = 1 k − 1 ( k − j ) ( ∇ F ( q j ) − ∇ F ( q 0 ) ) , q_k=q_0+k\eta p_0-\frac{(k\eta)^2}{2}\nabla f(q_0)-\eta^2\sum_{j=1}^{k-1}(k-j)(\nabla F(q_j)-\nabla F(q_0)), q k = q 0 + k η p 0 − 2 ( k η ) 2 ∇ f ( q 0 ) − η 2 j = 1 ∑ k − 1 ( k − j ) ( ∇ F ( q j ) − ∇ F ( q 0 )) ,
which proves (31).
Lemma B.10. Under the same notations of Theorem 4.3 and Assumption 4.2, for K η ≤ 1 / ( 2 M ) K\eta\le1/(2\sqrt{M}) K η ≤ 1/ ( 2 M ) , we have
∥ p t , k ∥ 2 ≤ 5 ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 ∥ θ t − θ ∗ ∥ 2 \lVert p_{t,k}\rVert^2 \le5\lVert p_t\rVert^2 + 5M^2(k\eta)^2\lVert\theta_t-\theta^*\rVert^2 ∥ p t , k ∥ 2 ≤ 5 ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 ∥ θ t − θ ∗ ∥ 2 ∥ θ t , k − θ ∗ ∥ 2 ≤ 4 ( k η ) 2 ∥ p t ∥ 2 + 3 ∥ θ t − θ ∗ ∥ 2 . \lVert\theta_{t,k}-\theta^*\rVert^2 \le4(k\eta)^2\lVert p_t\rVert^2 + 3\lVert\theta_t-\theta^*\rVert^2. ∥ θ t , k − θ ∗ ∥ 2 ≤ 4 ( k η ) 2 ∥ p t ∥ 2 + 3 ∥ θ t − θ ∗ ∥ 2 .
Proof. Recall that p t , k : = ∑ c = 1 N w c p t , k ( c ) p_{t,k} := \sum_{c=1}^{N} w_c p_{t,k}^{(c)} p t , k := ∑ c = 1 N w c p t , k ( c ) , and note that by Lemma B.11 that ∥ p t , k ( c ) ∥ 2 ≤ 5 ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 ∥ θ t − θ ∗ ∥ 2 \lVert p_{t,k}^{(c)}\rVert^2 \le5\lVert p_t\rVert^2 + 5M^2(k\eta)^2\lVert\theta_t-\theta^*\rVert^2 ∥ p t , k ( c ) ∥ 2 ≤ 5 ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 ∥ θ t − θ ∗ ∥ 2 , we have
∥ p t , k ∥ 2 ≤ ∑ c = 1 N w c ∥ p t , k ( c ) ∥ 2 ≤ 5 ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 ∥ θ t − θ ∗ ∥ 2 . \lVert p_{t,k}\rVert^2 \le\sum_{c=1}^{N} w_c\lVert p_{t,k}^{(c)}\rVert^2 \le5\lVert p_t\rVert^2 + 5M^2(k\eta)^2\lVert\theta_t-\theta^*\rVert^2. ∥ p t , k ∥ 2 ≤ c = 1 ∑ N w c ∥ p t , k ( c ) ∥ 2 ≤ 5 ∥ p t ∥ 2 + 5 M 2 ( k η ) 2 ∥ θ t − θ ∗ ∥ 2 .
This proves the first claim.
For the second claim, first, by convexity of ∥ ⋅ ∥ 2 \lVert\cdot\rVert^2 ∥ ⋅ ∥ 2 and Lemma B.12
∥ θ t , k − θ ∗ ∥ 2 ≤ 2 ∥ θ t , k − θ t ∥ 2 + 2 ∥ θ t − θ ∗ ∥ 2 ≤ ∑ c = 1 N w c 2 ∥ θ t , k ( c ) − θ t ∥ 2 + 2 ∥ θ t − θ ∗ ∥ 2 . \lVert\theta_{t,k}-\theta^*\rVert^2 \le2\lVert\theta_{t,k}-\theta_t\rVert^2 + 2\lVert\theta_t-\theta^*\rVert^2 \le\sum_{c=1}^{N} w_c 2\lVert\theta_{t,k}^{(c)}-\theta_t\rVert^2 + 2\lVert\theta_t-\theta^*\rVert^2. ∥ θ t , k − θ ∗ ∥ 2 ≤ 2 ∥ θ t , k − θ t ∥ 2 + 2 ∥ θ t − θ ∗ ∥ 2 ≤ c = 1 ∑ N w c 2 ∥ θ t , k ( c ) − θ t ∥ 2 + 2 ∥ θ t − θ ∗ ∥ 2 .
At the same time, for ∥ θ t , k ( c ) − θ t ∥ 2 \lVert\theta_{t,k}^{(c)}-\theta_t\rVert^2 ∥ θ t , k ( c ) − θ t ∥ 2 , Lemma B.8 states that ∥ θ t , k ( c ) − θ t ∥ 2 ≤ 2 ( k η ) 2 ∥ p t ∥ 2 + ( k η ) 4 M 2 ∥ θ t − θ ∗ ∥ 2 \lVert\theta_{t,k}^{(c)}-\theta_t\rVert^2 \le2(k\eta)^2\lVert p_t\rVert^2 + (k\eta)^4M^2\lVert\theta_t-\theta^*\rVert^2 ∥ θ t , k ( c ) − θ t ∥ 2 ≤ 2 ( k η ) 2 ∥ p t ∥ 2 + ( k η ) 4 M 2 ∥ θ t − θ ∗ ∥ 2 . And so
∥ θ t , k − θ ∗ ∥ 2 ≤ 4 ( k η ) 2 ∥ p t ∥ 2 + ( 2 + 2 ( k η ) 4 M 2 ) ∥ θ t − θ ∗ ∥ 2 ≤ 4 ( k η ) 2 ∥ p t ∥ 2 + 3 ∥ θ t − θ ∗ ∥ 2 \lVert\theta_{t,k}-\theta^*\rVert^2 \le4(k\eta)^2\lVert p_t\rVert^2 + (2+2(k\eta)^4M^2)\lVert\theta_t-\theta^*\rVert^2 \le4(k\eta)^2\lVert p_t\rVert^2 + 3\lVert\theta_t-\theta^*\rVert^2 ∥ θ t , k − θ ∗ ∥ 2 ≤ 4 ( k η ) 2 ∥ p t ∥ 2 + ( 2 + 2 ( k η ) 4 M 2 ) ∥ θ t − θ ∗ ∥ 2 ≤ 4 ( k η ) 2 ∥ p t ∥ 2 + 3 ∥ θ t − θ ∗ ∥ 2
where the last inequality is due to k η ≤ 1 / ( 2 M ) k\eta\le1/(2\sqrt{M}) k η ≤ 1/ ( 2 M ) . This finishes the proof. □
Lemma B.11. Suppose q k = h ~ L F ( F , q 0 , ∇ f ( q 0 ) , p 0 , η , k ) q_k = \tilde{h}_{\mathrm{LF}}(F,q_0,\nabla f(q_0),p_0,\eta,k) q k = h ~ LF ( F , q 0 , ∇ f ( q 0 ) , p 0 , η , k ) and p k = p k − 1 − η ( ∇ F ( q k − 1 ) + ∇ F ( q k ) ) / 2 + η ( ∇ F ( q 0 ) − ∇ f ( q 0 ) ) p_k = p_{k-1} - \eta(\nabla F(q_{k-1})+\nabla F(q_k))/2 + \eta(\nabla F(q_0)-\nabla f(q_0)) p k = p k − 1 − η ( ∇ F ( q k − 1 ) + ∇ F ( q k )) /2 + η ( ∇ F ( q 0 ) − ∇ f ( q 0 )) . Under Assumption 4.2, for K η ≤ 1 / ( 2 M ) K\eta\le1/(2\sqrt{M}) K η ≤ 1/ ( 2 M ) , we have
∥ p j ∥ 2 ≤ 5 ∥ p 0 ∥ 2 + 5 M 2 ( j η ) 2 ∥ q 0 − θ ∗ ∥ 2 . \lVert p_j\rVert^2 \le5\lVert p_0\rVert^2 + 5M^2(j\eta)^2\lVert q_0-\theta^*\rVert^2. ∥ p j ∥ 2 ≤ 5 ∥ p 0 ∥ 2 + 5 M 2 ( j η ) 2 ∥ q 0 − θ ∗ ∥ 2 .
Proof. By definitions and Algorithm 1, we have
p k = p 0 − k η ∇ f ( q 0 ) − η ∑ j = 1 k − 1 ( ∇ F ( q j ) − ∇ F ( q 0 ) ) − η 2 ( ∇ F ( q k ) − ∇ F ( q 0 ) ) p_k = p_0-k\eta\nabla f(q_0)-\eta\sum_{j=1}^{k-1}\left(\nabla F(q_j)-\nabla F(q_0)\right)-\frac{\eta}{2}\left(\nabla F(q_k)-\nabla F(q_0)\right) p k = p 0 − k η ∇ f ( q 0 ) − η j = 1 ∑ k − 1 ( ∇ F ( q j ) − ∇ F ( q 0 ) ) − 2 η ( ∇ F ( q k ) − ∇ F ( q 0 ) )
By Cauchy–Schwarz inequality and M M M -smoothness assumption,
∥ p k ∥ 2 ≤ 4 ∥ p 0 ∥ 2 + 4 ∥ k η ∇ f ( q 0 ) ∥ 2 + 4 ∥ η ∑ j = 1 k − 1 ( ∇ F ( q j ) − ∇ F ( q 0 ) ) ∥ 2 + 4 ∥ η 2 ( ∇ F ( q k ) − ∇ F ( q 0 ) ) ∥ 2 \lVert p_k\rVert^2 \le4\lVert p_0\rVert^2+4\lVert k\eta\nabla f(q_0)\rVert^2+4\left\lVert\eta\sum_{j=1}^{k-1}\left(\nabla F(q_j)-\nabla F(q_0)\right)\right\rVert^2+4\left\lVert\frac{\eta}{2}\left(\nabla F(q_k)-\nabla F(q_0)\right)\right\rVert^2 ∥ p k ∥ 2 ≤ 4 ∥ p 0 ∥ 2 + 4 ∥ k η ∇ f ( q 0 ) ∥ 2 + 4 η j = 1 ∑ k − 1 ( ∇ F ( q j ) − ∇ F ( q 0 ) ) 2 + 4 2 η ( ∇ F ( q k ) − ∇ F ( q 0 ) ) 2
≤ 4 ∥ p 0 ∥ 2 + 4 ∥ k η ∇ f ( q 0 ) ∥ 2 + 4 ( k − 1 ) ∑ j = 1 k − 1 η 2 ∥ ∇ F ( q j ) − ∇ F ( q 0 ) ∥ 2 + 4 ∥ η 2 ( ∇ F ( q k ) − ∇ F ( q 0 ) ) ∥ 2 \le4\lVert p_0\rVert^2+4\lVert k\eta\nabla f(q_0)\rVert^2+4(k-1)\sum_{j=1}^{k-1}\eta^2\lVert\nabla F(q_j)-\nabla F(q_0)\rVert^2+4\left\lVert\frac{\eta}{2}\left(\nabla F(q_k)-\nabla F(q_0)\right)\right\rVert^2 ≤ 4 ∥ p 0 ∥ 2 + 4 ∥ k η ∇ f ( q 0 ) ∥ 2 + 4 ( k − 1 ) j = 1 ∑ k − 1 η 2 ∥ ∇ F ( q j ) − ∇ F ( q 0 ) ∥ 2 + 4 2 η ( ∇ F ( q k ) − ∇ F ( q 0 ) ) 2
≤ 4 ∥ p 0 ∥ 2 + 4 ( k η ) 2 ∥ ∇ f ( q 0 ) ∥ 2 + 4 ( k − 1 ) ∑ j = 1 k − 1 η 2 M 2 ∥ q j − q 0 ∥ 2 + η 2 M 2 ∥ q k − q 0 ∥ 2 \le4\lVert p_0\rVert^2+4(k\eta)^2\lVert\nabla f(q_0)\rVert^2+4(k-1)\sum_{j=1}^{k-1}\eta^2M^2\lVert q_j-q_0\rVert^2+\eta^2M^2\lVert q_k-q_0\rVert^2 ≤ 4 ∥ p 0 ∥ 2 + 4 ( k η ) 2 ∥ ∇ f ( q 0 ) ∥ 2 + 4 ( k − 1 ) j = 1 ∑ k − 1 η 2 M 2 ∥ q j − q 0 ∥ 2 + η 2 M 2 ∥ q k − q 0 ∥ 2
≤ 4 ∥ p 0 ∥ 2 + 4 ( k η ) 2 ∥ ∇ f ( q 0 ) ∥ 2 + 4 ( k η ) 2 M 2 max j ≤ k ∥ q j − q 0 ∥ 2 \le4\lVert p_0\rVert^2+4(k\eta)^2\lVert\nabla f(q_0)\rVert^2+4(k\eta)^2M^2\max_{j\le k}\lVert q_j-q_0\rVert^2 ≤ 4 ∥ p 0 ∥ 2 + 4 ( k η ) 2 ∥ ∇ f ( q 0 ) ∥ 2 + 4 ( k η ) 2 M 2 j ≤ k max ∥ q j − q 0 ∥ 2
where the first two inequalities are by Lemma B.12 and the third inequality is by M M M -smoothness assumption.
Note that Lemma B.8 gives that ∥ q j − q 0 ∥ 2 ≤ 2 ( j η ) 2 ∥ p 0 ∥ 2 + ( j η ) 4 M 2 ∥ q 0 − θ ∗ ∥ 2 \lVert q_j-q_0\rVert^2 \le2(j\eta)^2\lVert p_0\rVert^2+(j\eta)^4M^2\lVert q_0-\theta^*\rVert^2 ∥ q j − q 0 ∥ 2 ≤ 2 ( j η ) 2 ∥ p 0 ∥ 2 + ( j η ) 4 M 2 ∥ q 0 − θ ∗ ∥ 2 . Inserting this into the above inequality yields
∥ p k ∥ 2 ≤ 4 ( 1 + 2 ( k η ) 4 M 2 ) ∥ p 0 ∥ 2 + 4 ( k η ) 2 ( 1 + M 2 ( k η ) 4 ) M 2 ∥ q 0 − θ ∗ ∥ 2 . \lVert p_k\rVert^2 \le4(1+2(k\eta)^4M^2)\lVert p_0\rVert^2+4(k\eta)^2(1+M^2(k\eta)^4)M^2\lVert q_0-\theta^*\rVert^2. ∥ p k ∥ 2 ≤ 4 ( 1 + 2 ( k η ) 4 M 2 ) ∥ p 0 ∥ 2 + 4 ( k η ) 2 ( 1 + M 2 ( k η ) 4 ) M 2 ∥ q 0 − θ ∗ ∥ 2 .
The second claim follows by noting that k η ≤ 1 / ( 2 M ) k\eta\le1/(2\sqrt{M}) k η ≤ 1/ ( 2 M ) . □
Lemma B.12 (Jensen’s inequality). For any vectors { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n and positive constants { λ i } i = 1 n \{\lambda_i\}_{i=1}^{n} { λ i } i = 1 n with ∑ i λ i = 1 \sum_i \lambda_i=1 ∑ i λ i = 1 , due to the convexity of ∥ ⋅ ∥ 2 \lVert\cdot\rVert^2 ∥ ⋅ ∥ 2 , we have
∥ ∑ i λ i x i ∥ 2 ≤ ∑ i λ i ∥ x i ∥ 2 ; \left\lVert\sum_i\lambda_i x_i\right\rVert^2\leq\sum_i\lambda_i\lVert x_i\rVert^2; i ∑ λ i x i 2 ≤ i ∑ λ i ∥ x i ∥ 2 ; ∥ ∑ i x i ∥ 2 ≤ ∑ i λ i ∥ x i / λ i ∥ 2 = ∑ i 1 λ i ∥ x i ∥ 2 . \left\lVert\sum_i x_i\right\rVert^2\leq\sum_i\lambda_i\left\lVert x_i/\lambda_i\right\rVert^2=\sum_i\frac{1}{\lambda_i}\lVert x_i\rVert^2. i ∑ x i 2 ≤ i ∑ λ i ∥ x i / λ i ∥ 2 = i ∑ λ i 1 ∥ x i ∥ 2 . For any vector-value function x ( t ) x(t) x ( t ) and non-negative integrable function λ ( t ) \lambda(t) λ ( t ) ,
∥ ∫ λ ( t ) x ( t ) d t ∥ 2 ≤ ∫ λ ( t ) d t ∫ λ ( t ) ∥ x ( t ) ∥ 2 d t . \left\lVert\int\lambda(t)x(t)\mathrm{d}t\right\rVert^2\leq\int\lambda(t)\mathrm{d}t\int\lambda(t)\lVert x(t)\rVert^2\mathrm{d}t. ∫ λ ( t ) x ( t ) d t 2 ≤ ∫ λ ( t ) d t ∫ λ ( t ) ∥ x ( t ) ∥ 2 d t . ∥ ∫ λ ( t ) x ( t ) d t ∥ 2 ≤ ∫ λ ( t ) ∥ x ( t ) ∥ 2 d t , if ∫ λ ( t ) d t = 1. \left\lVert\int\lambda(t)x(t)\mathrm{d}t\right\rVert^2\leq\int\lambda(t)\lVert x(t)\rVert^2\mathrm{d}t,\quad\text{if }\int\lambda(t)\mathrm{d}t=1. ∫ λ ( t ) x ( t ) d t 2 ≤ ∫ λ ( t ) ∥ x ( t ) ∥ 2 d t , if ∫ λ ( t ) d t = 1.
Study on heterogeneity metric H H H
Bound on H H H
Recall that H : = max i ≤ K ∑ c = 1 N w c E ∥ 1 i η ( ∇ f ( c ) ( H ~ η i ( θ π ) ) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H ~ η i ( θ π ) ) ) ∥ 2 H:=\max_{i\leq K}\sum_{c=1}^{N}w_c\mathbb{E}\left\lVert\frac{1}{\mathrm{i}\eta}\left(\nabla f^{(c)}(\widetilde{\mathcal{H}}_{\eta}^{i}(\theta^\pi))-\nabla f^{(c)}(\theta^\pi)+\nabla f(\theta^\pi)-\nabla f(\widetilde{\mathcal{H}}_{\eta}^{i}(\theta^\pi))\right)\right\rVert^2 H := max i ≤ K ∑ c = 1 N w c E i η 1 ( ∇ f ( c ) ( H η i ( θ π )) − ∇ f ( c ) ( θ π ) + ∇ f ( θ π ) − ∇ f ( H η i ( θ π )) ) 2 . By the M M M -Lipschitz condition,
H ≤ 4 max 1 ≤ i ≤ K ∑ c = 1 N w c E ∥ M i η ( H ~ η i ( θ π ) − θ π ) ∥ 2 . H\leq4\max_{1\leq i\leq K}\sum_{c=1}^{N}w_c\mathbb{E}\left\lVert\frac{M}{\mathrm{i}\eta}\left(\widetilde{\mathcal{H}}_{\eta}^{i}(\theta^\pi)-\theta^\pi\right)\right\rVert^2. H ≤ 4 1 ≤ i ≤ K max c = 1 ∑ N w c E i η M ( H η i ( θ π ) − θ π ) 2 .
Moreover,
H ~ η i ( θ π ) − θ π = ∫ 0 i η p ( t ) d t . \widetilde{\mathcal{H}}_{\eta}^{i}(\theta^\pi)-\theta^\pi=\int_0^{i\eta}p(t)\,\mathrm{d}t. H η i ( θ π ) − θ π = ∫ 0 i η p ( t ) d t .
where p ( t ) p(t) p ( t ) has a stationary marginal multivariate normal distribution. Overall, we can obtain that
for some absolute constant C C C .
Solutions of H H H on Gaussian examples
Give normal clients with same covariance structure (e.g., N ( 1 , I ) N(1,I) N ( 1 , I ) and N ( − 1 , I ) N(-1,I) N ( − 1 , I ) , and the global is N ( 0 , I ) N(0,I) N ( 0 , I ) ), then
∇ f ( c ) ( θ 2 ) − ∇ f ( c ) ( θ 1 ) + ∇ f ( θ 1 ) − ∇ f ( θ 2 ) ≡ 0 , \nabla f^{(c)}(\theta_2)-\nabla f^{(c)}(\theta_1)+\nabla f(\theta_1)-\nabla f(\theta_2)\equiv0, ∇ f ( c ) ( θ 2 ) − ∇ f ( c ) ( θ 1 ) + ∇ f ( θ 1 ) − ∇ f ( θ 2 ) ≡ 0 ,
meaning that H = 0 H=0 H = 0 always.
For non-equal covariance case, e.g., N ( 0 , 3 I / 4 ) N(0,3I/4) N ( 0 , 3 I /4 ) and N ( 0 , 3 I / 2 ) N(0,3I/2) N ( 0 , 3 I /2 ) , and the global is N ( 0 , I ) N(0,I) N ( 0 , I ) , the HMC trajectory for the global has a closed form, i.e., θ t = θ 0 cos ( t ) + p 0 sin ( t ) \theta_t=\theta_0\cos(t)+p_0\sin(t) θ t = θ 0 cos ( t ) + p 0 sin ( t ) elementwisely. The calculation of H H H eventually reduces to
d × sup t E θ , p ∼ N ( 0 , I 2 ) ∣ θ ( 1 − cos ( t ) ) − p sin ( t ) t ∣ 2 / 9 = 2 d 9 × sup t 1 − cos ( t ) t 2 = d 9 . d\times\sup_t\mathbb{E}_{\theta,p\sim N(0,I^2)}\left|\frac{\theta(1-\cos(t))-p\sin(t)}{t}\right|^2/9=\frac{2d}{9}\times\sup_t\frac{1-\cos(t)}{t^2}=\frac{d}{9}. d × t sup E θ , p ∼ N ( 0 , I 2 ) t θ ( 1 − cos ( t )) − p sin ( t ) 2 /9 = 9 2 d × t sup t 2 1 − cos ( t ) = 9 d .
Experimental Details
Additional Details for Figure 2
Table 2 reports the stepsize and leapfrog grids used for the simulated Bayesian logistic regression experiment in Figure 2 . The same grid is used for both panels. FA-LD uses T = 10 T=10 T = 10 and K = 1 K=1 K = 1 for every stepsize. FA-HMC uses T = 10 T=10 T = 10 and the K K K values listed in the table. AFHMC uses the candidate leapfrog counts K A ∈ K H M C ( η ) ∪ 10 K H M C ( η ) K_A\in\mathcal{K}_{\mathrm{HMC}}(\eta)\cup10\mathcal{K}_{\mathrm{HMC}}(\eta) K A ∈ K HMC ( η ) ∪ 10 K HMC ( η ) . For each (algorithm, η \eta η ) pair, Figure 2 reports the best-performing K K K from this grid.
Table 2: Candidate grid for the simulated Bayesian logistic regression experiment. Here K H M C ( η ) K_{\mathrm{HMC}}(\eta) K HMC ( η ) denotes the FA-HMC leapfrog grid at stepsize η \eta η ; the AFHMC grid is K H M C ( η ) ∪ 10 K H M C ( η ) K_{\mathrm{HMC}}(\eta) \cup10K_{\mathrm{HMC}}(\eta) K HMC ( η ) ∪ 10 K HMC ( η ) .
Table 2.
Additional Details for the Gaussian Dimension-Scaling Experiments
Low-heterogeneity target. For each dimension d d d and each of the N = 10 N=10 N = 10 clients, we draw 10 5 10^5 1 0 5 samples from N ( 16.21 d , 1.6 I d ) \mathcal{N}(16.21d,1.6I_d) N ( 16.21 d , 1.6 I d ) and set the local target of client c c c to N ( μ ^ c , σ ^ c 2 I d ) \mathcal{N}(\hat{\mu}_c,\hat{\sigma}_c^2I_d) N ( μ ^ c , σ ^ c 2 I d ) , where μ ^ c \hat{\mu}_c μ ^ c is the sample mean and σ ^ c 2 \hat{\sigma}_c^2 σ ^ c 2 is the coordinate-averaged sample variance. The global target is fitted in the same way to the samples pooled over all clients, and W 2 2 W_2^2 W 2 2 is computed as in the heterogeneous experiment. The heterogeneity therefore only comes from sampling error: across all dimensions and seeds, the root-mean-square deviation of the client means from the global mean is between 3.6 × 10 − 3 3.6 \times10^{-3} 3.6 × 1 0 − 3 and 4.5 × 10 − 3 4.5 \times10^{-3} 4.5 × 1 0 − 3 per coordinate, compared with 11.1 11.1 11.1 in the heterogeneous experiment, where the client means are 20 20 20 and 1 1 1 and the global mean is 16.2 16.2 16.2 . AFHMC runs one trajectory of K ( d ) K(d) K ( d ) surrogate leapfrog steps per round and uses the stopping rule of § 5 (W 2 2 < 0.1 W_2^2 < 0.1 W 2 2 < 0.1 for 20 consecutive checks, at most 1000 rounds). The random seed controls both the client samples and the HMC noise. Table 3 reports the first-crossing rounds for every seed.
Table 3: First communication round at which AFHMC reaches W 2 2 < 0.1 W_2^2 < 0.1 W 2 2 < 0.1 on the low-heterogeneity Gaussian target, with K ( d ) = ⌊ 50 ( d / 100 ) 1 / 2 ⌉ K(d)=\lfloor50(d/100)^{1/2}\rceil K ( d ) = ⌊ 50 ( d /100 ) 1/2 ⌉ and η ( d ) = 0.006 ( d / 100 ) − 1 / 2 \eta(d)=0.006(d/100)^{-1/2} η ( d ) = 0.006 ( d /100 ) − 1/2 .
Table 3.
FA-HMC baselines at an equal number of server exchanges. Theorem 4.1 of Liang et al. [26 ] shows that, under strong convexity, Hessian smoothness and bounded stochastic-gradient variance, FA-HMC attains W 2 ≤ ϵ W_2 \le\epsilon W 2 ≤ ϵ when
η 2 = C min { 1 K 2 L , ϵ K 2 d T , ϵ 2 K 2 d T 2 ( 1 − ρ ) N ′ , ϵ 2 K d ∑ c = 1 N w c 2 σ g 2 } . \eta^2 = C\min\left\{\frac{1}{K^2L},\frac{\epsilon}{K^2\sqrt{d}T},\frac{\epsilon^2}{K^2dT^2(1-\rho)N'},\frac{\epsilon^2}{Kd\sum_{c=1}^{N}w_c^2\sigma_g^2}\right\}. η 2 = C min { K 2 L 1 , K 2 d T ϵ , K 2 d T 2 ( 1 − ρ ) N ′ ϵ 2 , K d ∑ c = 1 N w c 2 σ g 2 ϵ 2 } .
In our Gaussian experiment all clients share the momentum, so ρ = 1 \rho=1 ρ = 1 , and the gradients are exact, so σ g 2 = 0 \sigma_g^2=0 σ g 2 = 0 ; the last two terms therefore impose no constraint. The remaining dimension-dependent term gives η ∝ ( K T d 1 / 4 ) − 1 \eta\propto(K\sqrt{T}d^{1/4})^{-1} η ∝ ( K T d 1/4 ) − 1 . With T = 10 T=10 T = 10 and K F ( d ) = max { 1 , ⌊ K ( d ) / 10 ⌋ } ∝ d 1 / 3 K_{\mathrm{F}}(d)=\max\{1,\lfloor K(d)/10\rfloor\}\propto d^{1/3} K F ( d ) = max { 1 , ⌊ K ( d ) /10 ⌋} ∝ d 1/3 , this yields η ( d ) ∝ d − 7 / 12 \eta(d)\propto d^{-7/12} η ( d ) ∝ d − 7/12 , which we anchor at d = 100 d=100 d = 100 as η ( d ) = 0.006 ( d / 100 ) − 7 / 12 \eta(d)=0.006(d/100)^{-7/12} η ( d ) = 0.006 ( d /100 ) − 7/12 . The second schedule is the dimension-scaling setting of Liang et al. [26 ] , K F = 5 K_{\mathrm{F}}=5 K F = 5 , T = 10 T=10 T = 10 and η ( d ) = 0.02 d − 1 / 4 \eta(d)=0.02d^{-1/4} η ( d ) = 0.02 d − 1/4 .
Figure 5. Additional predictive-quality metrics for Bayesian logistic regression on heterogeneous FMNIST against the number of server exchanges (one per round for FA-LD and FA-HMC, two per round for AFHMC). Left: Brier score. Right: negative log-likelihood. The data are partitioned across N = 10 N = 10 N = 10 clients using a label-skewed Dirichlet split with concentration parameter α = 0.1 \alpha= 0.1 α = 0.1 .
Both schedules are run for 2 R ( d ) 2R(d) 2 R ( d ) rounds, where R ( d ) R(d) R ( d ) is the AFHMC first-crossing round, so that FA-HMC uses the same number of server exchanges as AFHMC. Table 4 reports the resulting errors together with the original matched-budget setting. These schedules are theory-guided choices rather than an exhaustive search over ( η , K , T ) (\eta, K, T) ( η , K , T ) , and each setting is run once.
Table 4. FA-HMC W 2 2 W_2^2 W 2 2 on the heterogeneous Gaussian target. R ( d ) R(d) R ( d ) is the AFHMC first-crossing round for W 2 2 < 0.1 W_2^2 < 0.1 W 2 2 < 0.1 . The original setting uses the AFHMC stepsize for R ( d ) R(d) R ( d ) rounds; the two FA-HMC-specific schedules are run for 2 R ( d ) 2R(d) 2 R ( d ) rounds. All settings use T = 10 T = 10 T = 10 ; the original and Theorem-4.1 settings use K F ( d ) K_F(d) K F ( d ) , and the second setting uses K F = 5 K_F = 5 K F = 5 .
Additional Details for MNIST Logistic Regression
To create heterogeneous federated learning scenario, the FMNIST training set is partitioned across N = 10 N = 10 N = 10 clients using a label-skewed Dirichlet split. Specifically, for each class c c c , we sample a client-proportion vector
p c ∼ Dirichlet ( α 1 N ) , α = 0.1 , p_c \sim\operatorname{Dirichlet}(\alpha\mathbf{1}_N), \qquad\alpha= 0.1, p c ∼ Dirichlet ( α 1 N ) , α = 0.1 ,
and distribute the examples of class c c c across clients according to p c p_c p c . This produces heterogeneous clients with different label distributions.
Each configuration is repeated over five random seeds. The reported values in Table 5 are the final mean and standard error (SE) across seeds at 3600 server exchanges, i.e., at round 3600 for FA-LD and FA-HMC and at round 1800 for AFHMC. Since the stepsize is tuned separately for each metric, the selected stepsize may differ between Accuracy, Brier score, and NLL for the same method and K K K . Table 6 reports the accuracy at intermediate budgets. At 3600 server exchanges, AFHMC with K ∈ { 10 , 100 } K \in\{10, 100\} K ∈ { 10 , 100 } attains the highest accuracy and the lowest NLL, and ties with FA-HMC (K = 100 K = 100 K = 100 ) in Brier score; FA-HMC with K = 50 K = 50 K = 50 has lower Brier score and NLL at intermediate budgets.
Table 5: Final performance on heterogeneous FMNIST at 3600 server exchanges. Entries are mean ± \pm ± standard error over five random seeds.
Table 5.
Table 6: Test accuracy on heterogeneous FMNIST at an equal number of server exchanges (AFHMC at round x / 2 x/2 x /2 , FA-LD and FA-HMC at round x x x ). Entries are means over five random seeds; stepsizes as in Table 5.
Table 6.
Computational cost. Between two synchronizations, each client performs 50 leapfrog steps in FA-LD and FA-HMC, i.e., 100 mini-batch gradient evaluations per round, and K K K leapfrog steps plus one gradient evaluation for the drift correction in AFHMC, i.e., 2 K + 1 2K + 1 2 K + 1 evaluations per round. At 3600 server exchanges, AFHMC with K = 10 K = 10 K = 10 therefore uses 1800 × 21 = 37,800 1800 \times21 = 37{,}800 1800 × 21 = 37 , 800 gradient evaluations per client, compared with 3600 × 100 = 360,000 3600 \times100 = 360{,}000 3600 × 100 = 360 , 000 for FA-HMC.