Quantization Avoids Saddle Points in Distributed Optimization
Distributed nonconvex optimization underpins key functionalities of numerous distributed systems, ranging from power systems, smart buildings, cooperative robots, vehicle networks to sensor networks. Recently, it has also merged as a promising solution to handle the enormous growth in data and model sizes in deep learning. A fundamental problem in distributed nonconvex optimization is avoiding convergence to saddle points, which significantly degrade optimization accuracy. We discover that the process of quantization, which is necessary for all digital communications, can be exploited to enable saddle-point avoidance. More specifically, we propose a stochastic quantization scheme and prove that it can effectively escape saddle points and ensure convergence to a second-order stationary point in distributed nonconvex optimization. With an easily adjustable quantization granularity, the approach allows a user to control the number of bits sent per iteration and, hence, to aggressively reduce the communication overhead. Numerical experimental results using distributed optimization and learning problems on benchmark datasets confirm the effectiveness of the approach.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationQuantizationSimilar Papers 제목 키워드 기반
Accelerated Multiplicative Weights Update Avoids Saddle Points almost always
We consider non-convex optimization problems with constraint that is a product of simplices. A commonly used algorithm in solving this type of problem is the Multiplicative Weights Update (MWU), an algorithm that is wide…
Efficiently avoiding saddle points with zero order methods: No gradients required
We consider the case of derivative-free algorithms for non-convex optimization, also known as zero order algorithms, that use only function evaluations rather than gradients. For a wide variety of gradient approximators …
Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resilience
The problem of saddle-point avoidance for non-convex optimization is quite challenging in large scale distributed learning frameworks, such as Federated Learning, especially in the presence of Byzantine workers. The cele…
Federated LearningConvergence rate of sign stochastic gradient descent for non-convex functions
The sign stochastic gradient descent method (signSGD) utilizes only the sign of the stochastic gradient in its updates. Since signSGD carries out one-bit quantization of the gradients, it is extremely practical for distr…
Distributed OptimizationQuantizationIntuitive Analysis of the Quantization-based Optimization: From Stochastic and Quantum Mechanical Perspective
In this paper, we present an intuitive analysis of the optimization technique based on the quantization of an objective function. Quantization of an objective function is an effective optimization methodology that decrea…
global-optimizationQuantization