A Low Complexity Approximation of Gradient Descent for Learning over Single and Multi-Agent Systems
Mohammad H. Nassralla, Naeem Akl, Amr Mahmoud Salem Mohamed, Zaher Dawy · 2023
Gradient descent (GD) is an iterative optimization method to minimize a differentiable cost function. A main drawback of GD is its use of the entire dataset to perform a parameter update per learning step, which is cost-prohibitive for large-scale problems. Variants of GD such as mini-batch GD and stochastic GD compute the update direction with respect to a randomly sampled selection of the training dataset per iteration. This reduces the computational burden at the cost of adding jitters to the learning direction. Alternatively, we propose an iterative optimization algorithm that performs cheap parameter updates at minimal perturbation of the GD direction. The new method computes a deterministic summary of the training dataset, and then computes the learning direction per iteration with respect to the summary. We provide a convergence analysis for the proposed method and show that the thoroughness of the summary can be tweaked to optimize the trade-off between computational complexity and convergence rate. Simulation results are illustrated numerically for single and multi-agent systems.