論文の概要: Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique

• arxiv url: http://arxiv.org/abs/2210.05618v1
• Date: Tue, 11 Oct 2022 17:04:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 17:33:05.278808
• Title: Zero-Order One-Point Estimate with Distributed Stochastic Gradient-Tracking Technique
• Title（参考訳）: 分散確率勾配追従法によるゼロ次一点推定
• Authors: Elissa Mhanna and Mohamad Assaad
• Abstract要約: 本研究では,各エージェントが滑らかで凸な局所目的関数を持つ分散マルチエージェント最適化問題を考える。 分散勾配追跡法を,勾配推定のない帯域設定に拡張する。 近似ツールを用いた滑らかで凸な目的のための新しい手法の収束解析を行う。
• 参考スコア（独自算出の注目度）: 23.63073074337495
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we consider a distributed multi-agent stochastic optimization problem, where each agent holds a local objective function that is smooth and convex, and that is subject to a stochastic process. The goal is for all agents to collaborate to find a common solution that optimizes the sum of these local functions. With the practical assumption that agents can only obtain noisy numerical function queries at exactly one point at a time, we extend the distributed stochastic gradient-tracking method to the bandit setting where we don't have an estimate of the gradient, and we introduce a zero-order (ZO) one-point estimate (1P-DSGT). We analyze the convergence of this novel technique for smooth and convex objectives using stochastic approximation tools, and we prove that it converges almost surely to the optimum. We then study the convergence rate for when the objectives are additionally strongly convex. We obtain a rate of $O(\frac{1}{\sqrt{k}})$ after a sufficient number of iterations $k > K_2$ which is usually optimal for techniques utilizing one-point estimators. We also provide a regret bound of $O(\sqrt{k})$, which is exceptionally good compared to the aforementioned techniques. We further illustrate the usefulness of the proposed technique using numerical experiments.
• Abstract（参考訳）: 本研究では,分散マルチエージェント確率最適化問題について考察し,各エージェントが滑らかで凸な局所的目的関数を持ち,確率過程を考慮に入れた。 目標は、すべてのエージェントが協力して、これらのローカル関数の合計を最適化する共通ソリューションを見つけることだ。 エージェントが正確に1つの時点でしかノイズの多い数値関数クエリしか取得できないという現実的な仮定により、分散確率勾配追跡法を、勾配の見積もりを持たないバンディット設定に拡張し、ゼロオーダー(ZO)1点推定(1P-DSGT)を導入する。 確率的近似ツールを用いて, 滑らかで凸な目的のための新しい手法の収束を解析し, ほぼ確実に最適に収束することを示す。 次に、目的がさらに強い凸である場合の収束率について検討する。 我々は,1点推定器を用いた手法に最適である,十分な数の反復の後に,$O(\frac{1}{\sqrt{k}})$を得る。 また、上記の手法と比較して非常に良い$O(\sqrt{k})$の後悔境界も提供する。 さらに,数値実験による提案手法の有用性について述べる。

関連論文リスト

• Single Point-Based Distributed Zeroth-Order Optimization with a Non-Convex Stochastic Objective Function [14.986031916712108]
  勾配追跡手法の一点推定に基づくゼロ階分散最適化手法を提案する。 我々は,この手法が雑音条件下で数値関数と収束することを証明した。
  論文  参考訳（メタデータ） (2024-10-08T11:45:45Z)
• Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions [26.543628010637036]
  非函数に対して$mathcalO(log T)$の最適収束率を達成する新しい適応還元法を導入する。 また、提案手法を拡張して、合成最適化のために$mathcalO(log T)$と同じ最適率を得る。
  論文  参考訳（メタデータ） (2024-06-04T04:39:51Z)
• CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
  本稿では,通信制限条件下で分散最適化問題を解くことを検討する。 CEDASと呼ばれる圧縮精密拡散法について述べる。 特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
  論文  参考訳（メタデータ） (2023-01-14T09:49:15Z)
• 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)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  この作業は、一階情報を必要としない零次最適化(ZO)の反復である。 座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
  論文  参考訳（メタデータ） (2020-12-21T17:29:58Z)
• Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic Approach [2.538209532048867]
  ホモトピック法は、ラッソ型推定器で使われる$ell_1$ペナルティを近似するために用いられる。 ラッソ型推定器の計算における既存の手法よりも高速な数値収束率を示す。
  論文  参考訳（メタデータ） (2020-10-26T22:37:49Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。