Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution

Abstract

Distributed optimization utilizes local computation and communication to realize a global aim of optimizing the sum of local objective functions. This article addresses a class of constrained distributed nonconvex optimization problems involving univariate objectives, aiming to achieve global optimization without requiring local evaluations of gradients at every iteration. We propose a novel algorithm named CPCA, exploiting the notion of combining Chebyshev polynomial approximation, average consensus, and polynomial optimization. The proposed algorithm is i) able to obtain $\epsilon$-globally optimal solutions for any arbitrarily small given accuracy $\epsilon$, ii) efficient in both zeroth-order queries (i.e., evaluations of function values) and inter-agent communication, and iii) distributed terminable when the specified precision requirement is met. The key insight is to use polynomial approximations to substitute for general local objectives, distribute these approximations via average consensus, and solve an easier approximate version of the original problem. Due to the nice analytic properties of polynomials, this approximation not only facilitates efficient global optimization, but also allows the design of gradient-free iterations to reduce cumulative costs of queries and achieve geometric convergence for solving nonconvex problems. We provide a comprehensive analysis of the accuracy and complexities of the proposed algorithm.

arXiv commentPublished in IEEE Transactions on Control of Network Systems

References in corpus (12)

• On Hyperparameter Optimization of Machine Learning Algorithms: Theory and Practice
• Constrained Consensus
• On the Linear Convergence of the ADMM in Decentralized Consensus Optimization
• Harnessing Smoothness to Accelerate Distributed Optimization
• An improved convergence analysis for decentralized online stochastic non-convex optimization
• Decentralized Frank-Wolfe Algorithm for Convex and Non-convex Problems
• Distributed Non-Convex First-Order Optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms
• DC-DistADMM: ADMM Algorithm for Constrained Distributed Optimization over Directed Graphs
• Polynomial methods in statistical inference: theory and practice
• An essentially decentralized interior point method for control
• Optimizing Large-Scale Hyperparameters via Automated Learning Algorithm
• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution

Cited by in corpus (1)

• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution