In statistical learning and analysis from shared data, which is increasingly widely adopted in platforms such as federated learning and meta-learning, there are two major concerns: privacy and robustness. Each participating individual should be able to contribute without the fear of leaking one's sensitive information. At the same time, the system should be robust in the presence of malicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable to the other.

In recent centralized nonconvex distributed learning and federated learning, local methods are one of the promising approaches to reduce communication time. However, existing work has mainly focused on studying first-order optimality guarantees. On the other side, second-order optimality guaranteed algorithms, i.e., algorithms escaping saddle points, have been extensively studied in the nondistributed optimization literature. In this paper, we study a new local algorithm called Bias-Variance Reduced Local Perturbed SGD (BVR-L-PSGD), that combines the existing bias-variance reduced gradient estimator with parameter perturbation to find second-order optimal points in centralized nonconvex distributed optimization. BVR-L-PSGD enjoys second-order optimality with nearly the same communication complexity as the best known one of BVR-L-SGD to find first-order optimality. Particularly, the communication complexity is better than non-local methods when the local datasets heterogeneity is smaller than the smoothness of the local loss. In an extreme case, the communication complexity approaches to eΘ(1)when the local datasets heterogeneity goes to zero.

In this section, we provide further intuition about the proposed AdaQN method. As shown in Figure 5, in AdaQN we need to ensure that the approximate solution of the ERM problem with m samples denoted by wm is within the superlinear convergence neighborhood of BFGS for the ERM problem with n = 2msamples. Here, w m and w n are the optimal solutions of the risks Rm and Rn corresponding to the sets Sm and Sn with mand nsamples, respectively, where Sm Sn. The statistical accuracy region of Rm is denoted by a blue circle, the statistical accuracy region of Rn is denoted by a red circle, and the superlinear convergence neighborhood of BFGS for Rn is denoted by a dotted purple circle. As we observe, any point within the statistical accuracy of w m is within the superlinear convergence neighborhood of BFGS for Rn.