Such independent samples can be obtained by querying the SO at (x, y) for three times. A.2 Technical Lemmas for Lipschitz Properties and Hessian Inverse Estimation We first restate Lemmas 2.2 of (Ghadimi and Wang, 2018) to characterize the smoothness properties of y Lemma A.1 Suppose Assumptions 3.3 and 3.4 hold. Throughout this section, we assume Assumptions 3.1, 3.2, 3.3, and 3.4 hold and the step-sizes follow (5) that q q Therefore, under Assumption 3.3, for all t apple T, for all 1 apple j apple b, we have E[ku B.2 Lemma B.2 and Its Proof We quantify the convergence behavior of consensus errors under the choices of step-sizes (5) and (6) as follows. Lemma B.2 Suppose Assumptions 3.1, 3.2, 3.3, and 3.4 hold and the step-sizes satisfy Lemma B.3 Suppose Assumptions 3.1, 3.2, 3.3, and 3.4 hold. B.7 Proof of Theorem 5.1 Proof: We start our analysis by considering the term kȳ Throughout this subsection, we assume Assumptions 3.1, 3.2, 3.3, 3.4, and 5.2 hold. C.1 Lemma C.1 and Its Proof Lemma C.1 Suppose Assumptions 3.1, 3.2, 3.3, 3.4, and 5.2 hold and the objective F satisfies µ-PL Assumption 5.2 in addition.

Federated Learning (FL), a distributed learning paradigm that scales on-device learning collaboratively, has emerged as a promising approach for decentralized AI applications. Local optimization methods such as Federated Averaging (FedAvg) are the most prominent methods for FL applications. Despite their simplicity and popularity, the theoretical understanding of local optimization methods is far from clear. This dissertation aims to advance the theoretical foundation of local methods in the following three directions. First, we establish sharp bounds for FedAvg, the most popular algorithm in Federated Learning. We demonstrate how FedAvg may suffer from a notion we call iterate bias, and how an additional third-order smoothness assumption may mitigate this effect and lead to better convergence rates. We explain this phenomenon from a Stochastic Differential Equation (SDE) perspective. Second, we propose Federated Accelerated Stochastic Gradient Descent (FedAc), the first principled acceleration of FedAvg, which provably improves the convergence rate and communication efficiency. Our technique uses on a potential-based perturbed iterate analysis, a novel stability analysis of generalized accelerated SGD, and a strategic tradeoff between acceleration and stability. Third, we study the Federated Composite Optimization problem, which extends the classic smooth setting by incorporating a shared non-smooth regularizer. We show that direct extensions of FedAvg may suffer from the "curse of primal averaging," resulting in slow convergence. As a solution, we propose a new primal-dual algorithm, Federated Dual Averaging, which overcomes the curse of primal averaging by employing a novel inter-client dual averaging procedure.