A0411
Title: Generalization analysis of federated zeroth-order optimization
Authors: Hong Chen - Huazhong Agricultural University (China) [presenting]
Abstract: The federated zeroth-order optimization (FedZO) algorithm enjoys the advantages of both zeroth-order optimization and federated learning and has shown exceptional performance on black-box attack and softmax regression tasks. However, there is little generalization analysis for FedZO, and its analysis on computing convergence rate is slower than the corresponding first-order optimization setting. The aim is to establish systematic theoretical assessments of FedZO by developing an analysis technique for on-average model stability. The first generalization error bound of FedZO is established under the Lipschitz continuity and smoothness conditions. Then, refined generalization and optimization bounds are provided by replacing bounded gradient with heavy-tailed gradient noise and utilizing the second-order Taylor expansion for gradient approximation. With the help of a new error decomposition strategy, the theoretical analysis is also extended to the asynchronous case. For FedZO, the fine-grained analysis fills the theoretical gap in the generalization guarantees and polishes the convergence characterization of the computing algorithm.
