論文の概要: Optimal Methods for Risk Averse Distributed Optimization
- arxiv url: http://arxiv.org/abs/2203.05117v1
- Date: Thu, 10 Mar 2022 02:27:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-11 15:30:02.228999
- Title: Optimal Methods for Risk Averse Distributed Optimization
- Title（参考訳）: リスク逆分散最適化のための最適手法
- Authors: Gaunghui Lan, Zhe Zhang
- Abstract要約: ネットワーク上でのリスク逆最適化の通信複雑性について検討する。
本稿では,分散リスク逆最適化(DRAO)と分散リスク逆最適化(DRAO-S)の2つのアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 6.022808618190239
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper studies the communication complexity of risk averse optimization
over a network. The problem generalizes the well-studied risk-neutral
finite-sum distributed optimization problem and its importance stems from the
need to handle risk in an uncertain environment. For algorithms in the
literature, there exists a gap in communication complexities for solving
risk-averse and risk-neutral problems. We propose two distributed algorithms,
namely the distributed risk averse optimization (DRAO) method and the
distributed risk averse optimization with sliding (DRAO-S) method, to close the
gap. Specifically, the DRAO method achieves the optimal communication
complexity by assuming a certain saddle point subproblem can be easily solved
in the server node. The DRAO-S method removes the strong assumption by
introducing a novel saddle point sliding subroutine which only requires the
projection over the ambiguity set $P$. We observe that the number of
$P$-projections performed by DRAO-S is optimal. Moreover, we develop matching
lower complexity bounds to show that communication complexities of both DRAO
and DRAO-S are not improvable. Numerical experiments are conducted to
demonstrate the encouraging empirical performance of the DRAO-S method.
- Abstract（参考訳）: 本稿では,ネットワーク上のリスク回避最適化の通信複雑性について検討する。
この問題は、よく研究されたリスク中立な有限サム分散最適化問題を一般化し、その重要性は不確定な環境でリスクを扱う必要性に起因する。
文献におけるアルゴリズムには、リスク逆問題とリスクニュートラル問題を解くための通信複雑性のギャップが存在する。
本研究では,分散リスク逆最適化法(drao法)と分散リスク逆最適化法(drao-s法)という2つの分散アルゴリズムを提案する。
具体的には、サーバノードにおいて、特定のサドルポイント部分問題を容易に解決できると仮定して、最適な通信複雑性を達成する。
DRAO-S法は、曖昧性集合を射影することだけを必要とする新しいサドル点スライディングサブルーチンを導入することで、強い仮定を取り除く。
DRAO-Sによって実行される$P$-プロジェクションの数は最適である。
さらに, DRAO と DRAO-S の通信複雑度が即効しないことを示すために, 一致した低複雑性境界を開発する。
数値実験により, DRAO-S法の性能向上を実証した。
関連論文リスト
- Stabilized Proximal-Point Methods for Federated Optimization [20.30761752651984]
非加速アルゴリズムの通信複雑性は、分散近位点アルゴリズムであるDANEによって達成される。
ハイブリッド投影近点法に着想を得て,新しい分散アルゴリズムS-DANEを提案する。
S-DANEは、S-DANEとして良好な局所計算効率を保ちながら、通信の複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2024-07-09T17:56:29Z) - Spectral-Risk Safe Reinforcement Learning with Convergence Guarantees [13.470544618339506]
本稿では、スペクトルリスク尺度制約付きRLアルゴリズム、スペクトルリスク制約付きポリシー最適化(SRCPO)を提案する。
双レベル最適化構造では、外部問題はリスク測度から導出される双対変数を最適化することであり、内部問題は最適ポリシーを見つけることである。
提案手法は連続制御タスク上で評価され,制約を満たす他のRCRLアルゴリズムの中で最高の性能を示した。
論文 参考訳（メタデータ） (2024-05-29T02:17:25Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳（メタデータ） (2023-12-19T13:17:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Federated Distributionally Robust Optimization with Non-Convex
Objectives: Algorithm and Analysis [24.64654924173679]
Asynchronous Single-looP alternatIve gRadient projEction という非同期分散アルゴリズムを提案する。
新しい不確実性集合、すなわち制約付きD-ノルムの不確実性集合は、以前の分布を利用し、強靭性の度合いを柔軟に制御するために開発される。
実世界のデータセットに関する実証研究は、提案手法が高速収束を達成できるだけでなく、悪意のある攻撃だけでなく、データに対する堅牢性も維持できることを示した。
論文 参考訳（メタデータ） (2023-07-25T01:56:57Z) - Distributed Distributionally Robust Optimization with Non-Convex
Objectives [24.64654924173679]
Asynchronous Single-looP alternatIve gRadient projEction という非同期分散アルゴリズムを提案する。
新しい不確実性集合、すなわち制約付きD-ノルムの不確実性集合は、以前の分布を利用し、強靭性の度合いを柔軟に制御するために開発される。
実世界のデータセットに関する実証研究は、提案手法が高速収束を達成できるだけでなく、悪意のある攻撃だけでなく、データに対する堅牢性も維持できることを示した。
論文 参考訳（メタデータ） (2022-10-14T07:39:13Z) - Efficient Risk-Averse Reinforcement Learning [79.61412643761034]
リスク逆強化学習(RL)では、リターンのリスク測定を最適化することが目標である。
特定の条件下では、これは必然的に局所最適障壁につながることを証明し、それを回避するためのソフトリスク機構を提案する。
迷路ナビゲーション,自律運転,資源配分ベンチマークにおいて,リスク回避の改善を示す。
論文 参考訳（メタデータ） (2022-05-10T19:40:52Z) - Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD
for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
ローカル手法は通信時間を短縮する有望なアプローチの1つである。
局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-02-12T15:12:17Z) - Federated Distributionally Robust Optimization for Phase Configuration
of RISs [106.4688072667105]
我々は、教師付き学習環境において、多種多様なRISタイプ上での堅牢な再構成可能なインテリジェントサーフェス(RIS)支援ダウンリンク通信の問題について検討する。
異種RIS設計上のダウンリンク通信を分散的に位相構成を最適化する方法を学ぶ異なる労働者としてモデル化することにより、分散学習問題を解決することができる。
提案アルゴリズムは, 競合するベースラインと比較して, 最悪の分布精度を実現するために, 通信ラウンドを少なくする必要がある。
論文 参考訳（メタデータ） (2021-08-20T07:07:45Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。