On Linear Convergence of Adaptive Sign-based Gradient Descent
Kangchen He, Zhihai Qu, Xiuxian Li · 2024
This paper investigates a sign-based algorithm for unconstrained optimization problems, which leverages the sign of gradients rather than full gradients to reduce the communication cost in distributed optimization, and addresses the convergence failure of sign-based methods with nonadaptive step sizes. Specifically, the algorithm, called AS-GD, is demonstrated to be linearly convergent to a neighbourhood of the optimal value when the objective function is strongly convex, smooth or nonconvex, smooth but satisfies the Polyak-Łojasiewicz condition. Notably, AS-GD can further reduce or potentially eliminate the neighbourhood through appropriate adjustments to its hyperparameters. Synthetic and real-world numerical experiments are conducted respectively to validate the theoretical result.