Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence

• URL: http://arxiv.org/abs/2210.07703v2
• Date: Wed, 4 Sep 2024 17:45:51 GMT
• Title: Hybrid Decentralized Optimization: Leveraging Both First- and Zeroth-Order Optimizers for Faster Convergence
• Authors: Matin Ansaripour, Shayan Talaei, Giorgi Nadiradze, Dan Alistarh,
• Abstract summary: We show that a distributed system can withstand noisier zeroth-order agents but can even benefit from such agents into the optimization process. Our results hold both convex and non-zero-th order optimization objectives while they could still contribute to joint optimization tasks.
• Score: 31.59453616577858
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Distributed optimization is the standard way of speeding up machine learning training, and most of the research in the area focuses on distributed first-order, gradient-based methods. Yet, there are settings where some computationally-bounded nodes may not be able to implement first-order, gradient-based optimization, while they could still contribute to joint optimization tasks. In this paper, we initiate the study of hybrid decentralized optimization, studying settings where nodes with zeroth-order and first-order optimization capabilities co-exist in a distributed system, and attempt to jointly solve an optimization task over some data distribution. We essentially show that, under reasonable parameter settings, such a system can not only withstand noisier zeroth-order agents but can even benefit from integrating such agents into the optimization process, rather than ignoring their information. At the core of our approach is a new analysis of distributed optimization with noisy and possibly-biased gradient estimators, which may be of independent interest. Our results hold for both convex and non-convex objectives. Experimental results on standard optimization tasks confirm our analysis, showing that hybrid first-zeroth order optimization can be practical, even when training deep neural networks.

Related papers

• Understanding Optimization in Deep Learning with Central Flows [53.66160508990508]
  We show that an RMS's implicit behavior can be explicitly captured by a "central flow:" a differential equation. We show that these flows can empirically predict long-term optimization trajectories of generic neural networks.
  arXiv  Detail & Related papers  (2024-10-31T17:58:13Z)
• Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization [8.670873561640903]
  We investigate the finite-time analysis of finding ($delta,,ilon$)-stationary points for nonsmooth nonsmooth objectives in decentralized settings. $O is the first finite-time guarantee for decentralized nonsmooth optimization.
  arXiv  Detail & Related papers  (2024-06-03T16:09:34Z)
• A Continuous Relaxation for Discrete Bayesian Optimization [17.312618575552]
  We show that inference and optimization can be computationally tractable. We consider in particular the optimization domain where very few observations and strict budgets exist. We show that the resulting acquisition function can be optimized with both continuous or discrete optimization algorithms.
  arXiv  Detail & Related papers  (2024-04-26T14:47:40Z)
• Localized Zeroth-Order Prompt Optimization [54.964765668688806]
  We propose a novel algorithm, namely localized zeroth-order prompt optimization (ZOPO) ZOPO incorporates a Neural Tangent Kernel-based derived Gaussian process into standard zeroth-order optimization for an efficient search of well-performing local optima in prompt optimization. Remarkably, ZOPO outperforms existing baselines in terms of both the optimization performance and the query efficiency.
  arXiv  Detail & Related papers  (2024-03-05T14:18:15Z)
• SGD with Partial Hessian for Deep Neural Networks Optimization [18.78728272603732]
  We propose a compound, which is a combination of a second-order with a precise partial Hessian matrix for updating channel-wise parameters and the first-order gradient descent (SGD) algorithms for updating the other parameters. Compared with first-orders, it adopts a certain amount of information from the Hessian matrix to assist optimization, while compared with the existing second-order generalizations, it keeps the good performance of first-order generalizations imprecise.
  arXiv  Detail & Related papers  (2024-03-05T06:10:21Z)
• Optimistic Optimization of Gaussian Process Samples [30.226274682578172]
  A competing, computationally more efficient, global optimization framework is optimistic optimization, which exploits prior knowledge about the geometry of the search space in form of a dissimilarity function. We argue that there is a new research domain between geometric and probabilistic search, i.e. methods that run drastically faster than traditional Bayesian optimization, while retaining some of the crucial functionality of Bayesian optimization.
  arXiv  Detail & Related papers  (2022-09-02T09:06:24Z)
• Optimizer Amalgamation [124.33523126363728]
  We are motivated to study a new problem named Amalgamation: how can we best combine a pool of "teacher" amalgamations into a single "student" that can have stronger problem-specific performance? First, we define three differentiable mechanisms to amalgamate a pool of analyticals by gradient descent. In order to reduce variance of the process, we also explore methods to stabilize the process by perturbing the target.
  arXiv  Detail & Related papers  (2022-03-12T16:07:57Z)
• An Efficient Batch Constrained Bayesian Optimization Approach for Analog Circuit Synthesis via Multi-objective Acquisition Ensemble [11.64233949999656]
  We propose an efficient parallelizable Bayesian optimization algorithm via Multi-objective ACquisition function Ensemble (MACE) Our proposed algorithm can reduce the overall simulation time by up to 74 times compared to differential evolution (DE) for the unconstrained optimization problem when the batch size is 15. For the constrained optimization problem, our proposed algorithm can speed up the optimization process by up to 15 times compared to the weighted expected improvement based Bayesian optimization (WEIBO) approach, when the batch size is 15.
  arXiv  Detail & Related papers  (2021-06-28T13:21:28Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• A Primer on Zeroth-Order Optimization in Signal Processing and Machine Learning [95.85269649177336]
  ZO optimization iteratively performs three major steps: gradient estimation, descent direction, and solution update. We demonstrate promising applications of ZO optimization, such as evaluating and generating explanations from black-box deep learning models, and efficient online sensor management.
  arXiv  Detail & Related papers  (2020-06-11T06:50:35Z)
• Global Optimization of Gaussian processes [52.77024349608834]
  We propose a reduced-space formulation with trained Gaussian processes trained on few data points. The approach also leads to significantly smaller and computationally cheaper sub solver for lower bounding. In total, we reduce time convergence by orders of orders of the proposed method.
  arXiv  Detail & Related papers  (2020-05-21T20:59:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.