論文の概要: Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function
- arxiv url: http://arxiv.org/abs/2410.05942v1
- Date: Tue, 8 Oct 2024 11:45:45 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-01 12:00:27.538640
- Title: Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function
- Title(参考訳): 非凸確率目的関数を用いた単一点ベース分散ゼロ階最適化
- Authors: Elissa Mhanna, Mohamad Assaad,
- Abstract要約: 勾配追跡手法の一点推定に基づくゼロ階分散最適化手法を提案する。
我々は,この手法が雑音条件下で数値関数と収束することを証明した。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): ゼロオーダー最適化(ZO)は、現実的な制約を扱うための強力なツールである。
一方、勾配追跡(GT)技術は、コンセンサスの実現を目的とした分散最適化の効率的な手法であることが判明した。
しかし、これは勾配の知識を必要とする一階法(FO)であり、実際には必ずしも可能であるとは限らない。
本研究では,勾配追従手法の一点推定に基づくゼロ階分散最適化手法を提案する。
我々は,この手法が,非凸条件下で一度に1つのノイズ関数クエリと収束することを証明する。
次に、一連の反復 K の後に$O(\frac{1}{\sqrt[3]{K}})$の収束率を定め、これは集中化された K の$O(\frac{1}{\sqrt[4]{K}})$と競合する。
最後に、数値的な例は、我々の理論的結果を検証する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳(メタデータ) (2024-06-28T02:56:22Z) - Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions [26.543628010637036]
非函数に対して$mathcalO(log T)$の最適収束率を達成する新しい適応還元法を導入する。
また、提案手法を拡張して、合成最適化のために$mathcalO(log T)$と同じ最適率を得る。
論文 参考訳(メタデータ) (2024-06-04T04:39:51Z) - Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。
複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。
本稿では,ZPDVR法とZPDVR法を提案する。
論文 参考訳(メタデータ) (2024-05-28T02:27:53Z) - Mirror Natural Evolution Strategies [10.495496415022064]
我々は、ゼロ階探索で近似された一階情報と二階情報の両方を利用するゼロ階最適化理論に焦点をあてる。
我々は、textttMiNES の推定共分散行列が、目的関数のヘッセン行列の逆行列に収束することを示す。
論文 参考訳(メタデータ) (2023-08-01T11:45:24Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳(メタデータ) (2022-12-19T14:48:54Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Zero-Order One-Point Estimate with Distributed Stochastic
Gradient-Tracking Technique [23.63073074337495]
本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。
分散勾配追跡法を,勾配推定のない帯域設定に拡張する。
近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
論文 参考訳(メタデータ) (2022-10-11T17:04:45Z) - Accelerated Single-Call Methods for Constrained Min-Max Optimization [5.266784779001398]
既存の方法は、各イテレーションで2つのグラデーションコールか2つのプロジェクションを必要とする。
本稿では,RGOG(Optimistic Gradient)の変種が,非可換な min-max 収束率問題に富むことを示した。
私たちの収束率は、自然や自然のような標準の尺度に当てはまる。
論文 参考訳(メタデータ) (2022-10-06T17:50:42Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳(メタデータ) (2020-12-11T08:28:51Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-14T10:42:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。