StochaLM: a Stochastic alternate Linearization Method for distributed optimization
We present the Stochastic alternate Linearization Method (StochaLM), a token-based method for distributed optimization. This algorithm finds the solution of a consensus optimization problem by solving a sequence of subproblems where some components of the cost are linearized around specific anchor points. StochaLM can be interpreted as a dual block coordinate ascent method whose block components are selected using the state of an ergodic Markov chain. This sampling process is neither essentially cyclic nor independent over time, preventing us from using proofs of convergence of dual block coordinate ascent methods done in previous works. The proof of convergence of our method is, therefore, also novel. We show that, if the cost is strongly convex and the network is fully connected, then, with probability one, the primal sequence generated by StochaLM converges to the solution. Our method is application-friendly, as it has no global hyperparameters to tune; any hyperparameters can be tuned locally by the agents, using information regarding their private cost and neighbourhood. Our method is, therefore, decentralized in the truest sense. Numerical experiments evidence that our method converges to the solution faster than other token-based methods, even when these methods' hyperparameters are tuned for optimal performance.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationFederated LearningSimilar Papers 제목 키워드 기반
Optimizing Non-decomposable Performance Measures: A Tale of Two Classes
Modern classification problems frequently present mild to severe label imbalance as well as specific requirements on classification characteristics, and require optimizing performance measures that are non-decomposable o…
General ClassificationVocal Bursts Valence PredictionStochastic Variational Inference with Gradient Linearization
Variational inference has experienced a recent surge in popularity owing to stochastic approaches, which have yielded practical tools for a wide range of model classes. A key benefit is that stochastic variational infere…
DenoisingOptical Flow EstimationSurface ReconstructionVariational InferenceEvaluation and Optimization of Gradient Compression for Distributed Deep Learning
To accelerate distributed training, many gradient compression methods have been proposed to alleviate the communication bottleneck in synchronous stochastic gradient descent (S-SGD), but their efficacy in real-world appl…
Deep LearningGPUQuantizationMoment Propagation of Polynomial Systems Through Carleman Linearization for Probabilistic Safety Analysis
We develop a method to approximate the moments of a discrete-time stochastic polynomial system. Our method is built upon Carleman linearization with truncation. Specifically, we take a stochastic polynomial system with f…
Optimal Complexity in Byzantine-Robust Distributed Stochastic Optimization with Data Heterogeneity
In this paper, we establish tight lower bounds for Byzantine-robust distributed first-order stochastic optimization methods in both strongly convex and non-convex stochastic optimization. We reveal that when the distribu…
Stochastic Optimization