ZO-JADE: Zeroth-order Curvature-Aware Multi-Agent Convex Optimization

Abstract

In this work we address the problem of convex optimization in a multi-agent setting where the objective is to minimize the mean of local cost functions whose derivatives are not available (e.g. black-box models). Moreover agents can only communicate with local neighbors according to a connected network topology. Zeroth-order (ZO) optimization has recently gained increasing attention in federated learning and multi-agent scenarios exploiting finite-difference approximations of the gradient using from $2$ (directional gradient) to $2d$ (central difference full gradient) evaluations of the cost functions, where $d$ is the dimension of the problem. The contribution of this work is to extend ZO distributed optimization by estimating the curvature of the local cost functions via finite-difference approximations. In particular, we propose a novel algorithm named ZO-JADE, that by adding just one extra point, i.e. $2d+1$ in total, allows to simultaneously estimate the gradient and the diagonal of the local Hessian, which are then combined via average tracking consensus to obtain an approximated Jacobi descent. Guarantees of semi-global exponential stability are established via separation of time-scales. Extensive numerical experiments on real-world data confirm the efficiency and superiority of our algorithm with respect to several other distributed zeroth-order methods available in the literature based on only gradient estimates.

References in corpus (8)

• Lyapunov Theory for Discrete Time Systems
• Zeroth Order Nonconvex Multi-Agent Optimization over Networks
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• ZO-JADE: Zeroth-order Curvature-Aware Multi-Agent Convex Optimization
• Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points
• Distributed Zero-Order Optimization under Adversarial Noise
• Hessian Inverse Approximation as Covariance for Random Perturbation in Black-Box Problems
• Zeroth-Order Stochastic Coordinate Methods for Decentralized Non-convex Optimization

Cited by in corpus (1)

• ZO-JADE: Zeroth-order Curvature-Aware Multi-Agent Convex Optimization