論文の概要: Efficient Algorithms for Empirical Group Distributional Robust
Optimization and Beyond
- arxiv url: http://arxiv.org/abs/2403.03562v1
- Date: Wed, 6 Mar 2024 09:14:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 15:33:33.652560
- Title: Efficient Algorithms for Empirical Group Distributional Robust
Optimization and Beyond
- Title（参考訳）: 経験的群分布ロバスト最適化のための効率的なアルゴリズム
- Authors: Dingzhi Yu, Yunuo Cai, Wei Jiang, Lijun Zhang
- Abstract要約: 経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。
我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。
注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
- 参考スコア（独自算出の注目度）: 15.664414751701718
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the empirical counterpart of group distributionally robust
optimization (GDRO), which aims to minimize the maximal empirical risk across
$m$ distinct groups. We formulate empirical GDRO as a $\textit{two-level}$
finite-sum convex-concave minimax optimization problem and develop a stochastic
variance reduced mirror prox algorithm. Unlike existing methods, we construct
the stochastic gradient by per-group sampling technique and perform variance
reduction for all groups, which fully exploits the $\textit{two-level}$
finite-sum structure of empirical GDRO. Furthermore, we compute the snapshot
and mirror snapshot point by a one-index-shifted weighted average, which
distinguishes us from the naive ergodic average. Our algorithm also supports
non-constant learning rates, which is different from existing literature. We
establish convergence guarantees both in expectation and with high probability,
demonstrating a complexity of
$\mathcal{O}\left(\frac{m\sqrt{\bar{n}\ln{m}}}{\varepsilon}\right)$, where
$\bar n$ is the average number of samples among $m$ groups. Remarkably, our
approach outperforms the state-of-the-art method by a factor of $\sqrt{m}$.
Furthermore, we extend our methodology to deal with the empirical minimax
excess risk optimization (MERO) problem and manage to give the expectation
bound and the high probability bound, accordingly. The complexity of our
empirical MERO algorithm matches that of empirical GDRO at
$\mathcal{O}\left(\frac{m\sqrt{\bar{n}\ln{m}}}{\varepsilon}\right)$,
significantly surpassing the bounds of existing methods.
- Abstract（参考訳）: グループ分散ロバスト最適化 (GDRO) の実証的対応について検討し, グループ間における最大経験的リスクを最小化することを目的とした。
我々は、経験的GDROを$\textit{two-level}$ finite-sum convex-concave minimax Optimization問題として定式化し、確率分散還元ミラープロキシアルゴリズムを開発した。
既存の手法とは異なり、群ごとのサンプリング手法により確率勾配を構築し、すべての群に対して分散還元を行い、経験的 GDRO の $\textit{two-level}$ finite-sum 構造を完全に活用する。
さらに、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。
本アルゴリズムは,既存の文献とは異なる非定常学習率もサポートする。
ここで、$\bar n$ は $m$ 群のサンプルの平均数である、$\mathcal{o}\left(\frac{m\sqrt{\bar{n}\ln{m}}}{\varepsilon}\right)$ の複雑さを示す。
注目すべきは、我々の手法が最先端の手法を$\sqrt{m}$で上回ることである。
さらに,実証的なミニマックス超過リスク最適化(MERO)問題に対処するために方法論を拡張し,予測境界と高い確率境界を与える。
経験的メロアルゴリズムの複雑さは、既存の手法の境界を大幅に上回る$\mathcal{o}\left(\frac{m\sqrt{\bar{n}\ln{m}}}{\varepsilon}\right)$における経験的gdroのそれと一致する。
関連論文リスト
- Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL [6.996002801232415]
生成モデルを用いてマルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを求める際のサンプル複雑性について検討した。
我々は,知識を必要とせず,最適なスパンベース複雑性に適合するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2025-02-16T19:10:55Z) - Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsity [14.396304498754688]
私たちは、$(lambda, beta)$-sparsityをダブした、空白という新しい概念を示します。
つまり、少なくとも$theta$のリスクが他のグループのリスクよりも少なくとも$lambda$であるような、少なくとも$beta$グループのセットがあります。
計算効率のよい手法により,次元自由な半適応サンプルの複雑性を得る方法を示す。
論文 参考訳（メタデータ） (2024-10-01T13:45:55Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。
状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-13T17:18:11Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。