論文の概要: 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})$の後悔境界も提供する。
さらに,数値実験による提案手法の有用性について述べる。
関連論文リスト
- On diffusion-based generative models and their error bounds: The
log-concave case with full convergence estimates [3.8447306272420816]
我々は,強い対数空間データ分布を仮定して,拡散に基づく生成モデルの収束挙動を理論的に保証する。
我々は、モチベーションの例を通して、未知の平均を持つガウス分布からサンプリングし、我々のアプローチの強力さを実証する。
この手法はサンプリングアルゴリズムにおいて最もよく知られた収束率をもたらす。
論文 参考訳(メタデータ) (2023-11-22T18:40:45Z) - CEDAS: A Compressed Decentralized Stochastic Gradient Method with
Improved Convergence [10.770843226843418]
本稿では,通信制限条件下でのマルチエージェントネットワークの分散最適化問題について考察する。
提案手法は,CEDAS (Convexizes) を圧縮し,滑らかな凸関連ステップの適応的なステップを実現する。
論文 参考訳(メタデータ) (2023-01-14T09:49:15Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Stochastic Zeroth order Descent with Structured Directions [14.338969001937068]
有限差分法であるStructured Zeroth Order Descent (S-SZD) を導入・解析し、その場合、$d は周囲空間の次元である集合 $lleq d 方向の勾配を近似する。
凸に関して、収束境界と収束率はほぼ確実に証明し、各$c1/2$は、反復数に関してグラディエント Descent (SGD) の値に任意に近い。
論文 参考訳(メタデータ) (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) - Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order
Coordinate Method [3.860616339202303]
本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。
エージェントは問題を解くためにzo座標法を近似する。
論文 参考訳(メタデータ) (2021-03-24T03:07:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。