Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function

• URL: http://arxiv.org/abs/2410.05942v1
• Date: Tue, 8 Oct 2024 11:45:45 GMT
• Title: Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function
• Authors: Elissa Mhanna, Mohamad Assaad,
• Abstract summary: We introduce a zero-order distributed optimization method based on a one-point estimate of the gradient tracking technique. We prove that this new technique converges with a numerical function at a noisy setting.
• Score: 14.986031916712108
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Zero-order (ZO) optimization is a powerful tool for dealing with realistic constraints. On the other hand, the gradient-tracking (GT) technique proved to be an efficient method for distributed optimization aiming to achieve consensus. However, it is a first-order (FO) method that requires knowledge of the gradient, which is not always possible in practice. In this work, we introduce a zero-order distributed optimization method based on a one-point estimate of the gradient tracking technique. We prove that this new technique converges with a single noisy function query at a time in the non-convex setting. We then establish a convergence rate of $O(\frac{1}{\sqrt[3]{K}})$ after a number of iterations K, which competes with that of $O(\frac{1}{\sqrt[4]{K}})$ of its centralized counterparts. Finally, a numerical example validates our theoretical results.

Related papers

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions [26.543628010637036]
  We introduce a novel adaptive reduction method that achieves an optimal convergence rate of $mathcalO(log T)$ for non- functions. We also extend the proposed technique to obtain the same optimal rate of $mathcalO(log T)$ for compositional optimization.
  arXiv  Detail & Related papers  (2024-06-04T04:39:51Z)
• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  Variance reduction techniques are designed to decrease the sampling variance, thereby accelerating convergence rates of first-order (FO) and zeroth-order (ZO) optimization methods. In composite optimization problems, ZO methods encounter an additional variance called the coordinate-wise variance, which stems from the random estimation. This paper proposes the Zeroth-order Proximal Double Variance Reduction (ZPDVR) method, which utilizes the averaging trick to reduce both sampling and coordinate-wise variances.
  arXiv  Detail & Related papers  (2024-05-28T02:27:53Z)
• Mirror Natural Evolution Strategies [10.495496415022064]
  We focus on the theory of zeroth-order optimization which utilizes both the first-order and second-order information approximated by the zeroth-order queries. We show that the estimated covariance matrix of textttMiNES converges to the inverse of Hessian matrix of the objective function.
  arXiv  Detail & Related papers  (2023-08-01T11:45:24Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  Many real-world problems have complicated non functional constraints and use a large number of data points. Our proposed method outperforms an existing method with the previously best-known result.
  arXiv  Detail & Related papers  (2022-12-19T14:48:54Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique [23.63073074337495]
  We consider a distributed multi-agent optimization problem where each agent holds a local objective function that is smooth and convex. We extend the distributed gradient-tracking method to the bandit setting where we don't have an estimate of the gradient. We analyze the convergence of this novel technique for smooth and convex objectives using approximation tools.
  arXiv  Detail & Related papers  (2022-10-11T17:04:45Z)
• Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
  Existing methods either require two gradient calls or two projections in each iteration, which may costly in some applications. In this paper, we first show that a variant of the Optimistic Gradient (RGOG) has a rich set of non-comonrate min-max convergence rate problems. Our convergence rates hold for standard measures such as and the natural and the natural.
  arXiv  Detail & Related papers  (2022-10-06T17:50:42Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• 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)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  We study the problem of zero-order optimization of a strongly convex function. We consider a randomized approximation of the projected gradient descent algorithm. Our results imply that the zero-order algorithm is nearly optimal in terms of sample complexity and the problem parameters.
  arXiv  Detail & Related papers  (2020-06-14T10:42:23Z)

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.