論文の概要: Coresets for Wasserstein Distributionally Robust Optimization Problems
- arxiv url: http://arxiv.org/abs/2210.04260v1
- Date: Sun, 9 Oct 2022 13:24:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-11 18:42:14.453824
- Title: Coresets for Wasserstein Distributionally Robust Optimization Problems
- Title(参考訳): Wasserstein分布ロバスト最適化問題に対するコアセット
- Authors: Ruomin Huang, Jiawei Huang, Wenjie Liu and Hu Ding
- Abstract要約: Wassersteinの分散ロバスト最適化(textsfWDRO)は、曖昧なデータによる機械学習のロバスト性を高める一般的なモデルである。
本稿では,一般的なtextsfWDRO問題に対する$epsilon$-coresetを構築するための統一フレームワークを提案する。
テキストfWDROの強い双対性特性を用いて「双対コアセット」を計算可能であることを示す。
- 参考スコア(独自算出の注目度): 23.292883776685326
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Wasserstein distributionally robust optimization (\textsf{WDRO}) is a popular
model to enhance the robustness of machine learning with ambiguous data.
However, the complexity of \textsf{WDRO} can be prohibitive in practice since
solving its ``minimax'' formulation requires a great amount of computation.
Recently, several fast \textsf{WDRO} training algorithms for some specific
machine learning tasks (e.g., logistic regression) have been developed.
However, the research on designing efficient algorithms for general large-scale
\textsf{WDRO}s is still quite limited, to the best of our knowledge.
\textit{Coreset} is an important tool for compressing large dataset, and thus
it has been widely applied to reduce the computational complexities for many
optimization problems. In this paper, we introduce a unified framework to
construct the $\epsilon$-coreset for the general \textsf{WDRO} problems. Though
it is challenging to obtain a conventional coreset for \textsf{WDRO} due to the
uncertainty issue of ambiguous data, we show that we can compute a ``dual
coreset'' by using the strong duality property of \textsf{WDRO}. Also, the
error introduced by the dual coreset can be theoretically guaranteed for the
original \textsf{WDRO} objective. To construct the dual coreset, we propose a
novel grid sampling approach that is particularly suitable for the dual
formulation of \textsf{WDRO}. Finally, we implement our coreset approach and
illustrate its effectiveness for several \textsf{WDRO} problems in the
experiments.
- Abstract(参考訳): Wassersteinの分散ロバスト最適化(\textsf{WDRO})は、曖昧なデータによる機械学習のロバスト性を高めるための一般的なモデルである。
しかし、'minimax'' の定式化を解くには大量の計算を必要とするため、実際には‘textsf{WDRO} の複雑さは禁じられる。
近年、特定の機械学習タスク(ロジスティック回帰など)のための高速 \textsf{wdro} トレーニングアルゴリズムが開発されている。
しかし、一般の大規模 \textsf{WDRO} に対する効率的なアルゴリズムの設計に関する研究は、我々の知る限り、まだ非常に限られている。
\textit{Coreset} は大規模なデータセットを圧縮するための重要なツールであり、多くの最適化問題に対する計算複雑性の低減に広く応用されている。
本稿では,一般的な textsf{WDRO} 問題に対する$\epsilon$-coreset を構築するための統一フレームワークを提案する。
あいまいなデータの不確実性のため,従来の「textsf{WDRO}」のコアセットを得るのは難しいが,「dual coreset'」を「textsf{WDRO}」の強い双対性を用いて計算できることが示されている。
また、デュアルコアセットによって導入された誤差は、元の \textsf{WDRO} の目的に対して理論的に保証することができる。
双対コアセットを構築するために,新しいグリッドサンプリング手法を提案し,この手法は,特に textsf{WDRO} の双対定式化に適している。
最後に、コアセットアプローチを実装し、実験におけるいくつかの \textsf{WDRO} 問題に対するその有効性を示す。
関連論文リスト
- Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization [23.029511473335145]
本稿では、その性能のロバスト性を明確に評価した制約付きDROに焦点を当てる。
各$chi2$-divergencesポイント$におけるアルゴリズムの複雑さは、データセットサイズが独立しているため、大規模アプリケーションに適している。
論文 参考訳(メタデータ) (2024-04-01T15:56:58Z) - FedDRO: Federated Compositional Optimization for Distributionally Robust
Learning [11.70892315284039]
大規模かつ分散的なデータ利用には,効率的なフェデレート学習勾配アルゴリズムの開発が必要である。
FL設定における非線形合成勾配を解くための効率的なFedAvg型アルゴリズムを提案する。
我々の研究の重要な新規性は、大規模なバッチ評価を必要としない解の精度非依存のアルゴリズムを開発することである。
論文 参考訳(メタデータ) (2023-11-21T14:53:39Z) - AutoCoreset: An Automatic Practical Coreset Construction Framework [65.37876706107764]
コアセットは入力セットの小さな重み付き部分集合であり、損失関数によく似ている。
本稿では,ユーザからの入力データと所望のコスト関数のみを必要とするコアセット構築のための自動フレームワークを提案する。
この集合は有限であるが、コア集合は極めて一般であることを示す。
論文 参考訳(メタデータ) (2023-05-19T19:59:52Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳(メタデータ) (2023-02-08T01:42:45Z) - Coresets for Relational Data and The Applications [8.573878018370547]
coresetは、元の入力データセットの構造を保存できる小さなセットである。
我々は、クラスタリング、ロジスティック回帰、SVMといった機械学習タスクにコアセットアプローチを適用することができることを示す。
論文 参考訳(メタデータ) (2022-10-09T12:46:27Z) - Robust Coreset for Continuous-and-Bounded Learning (with Outliers) [30.91741925182613]
本研究では,エム連続有界学習問題に対する新しいロバストなコアセット法を提案する。
私たちの堅牢なコアセットは、完全にダイナミックな環境で効率的に維持できます。
論文 参考訳(メタデータ) (2021-06-30T19:24:20Z) - DORO: Distributional and Outlier Robust Optimization [98.44757325531631]
本稿では,分散ロバスト最適化のためのDOROのフレームワークを提案する。
このアプローチのコアとなるのは、DROがオーバーフィットして潜在的な外れ値に収まらないような、洗練されたリスク関数である。
提案手法の有効性を理論的に証明し, DOROがDROの性能と安定性を向上することを示す。
論文 参考訳(メタデータ) (2021-06-11T02:59:54Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳(メタデータ) (2020-07-13T16:30:47Z) - An Online Method for A Class of Distributionally Robust Optimization
with Non-Convex Objectives [54.29001037565384]
本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。
本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
論文 参考訳(メタデータ) (2020-06-17T20:19:25Z) - Faster Secure Data Mining via Distributed Homomorphic Encryption [108.77460689459247]
ホモモルフィック暗号化(HE)は、最近、暗号化されたフィールド上で計算を行う能力により、ますます注目を集めている。
本稿では,スケーリング問題の解決に向けて,新しい分散HEベースのデータマイニングフレームワークを提案する。
各種データマイニングアルゴリズムとベンチマークデータセットを用いて,新しいフレームワークの有効性と有効性を検証する。
論文 参考訳(メタデータ) (2020-06-17T18:14:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。