論文の概要: Stochastic Approximation Approaches to Group Distributionally Robust
Optimization
- arxiv url: http://arxiv.org/abs/2302.09267v4
- Date: Thu, 4 Jan 2024 03:42:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-05 17:58:05.536658
- Title: Stochastic Approximation Approaches to Group Distributionally Robust
Optimization
- Title(参考訳): 群分布ロバスト最適化に対する確率近似手法
- Authors: Lijun Zhang, Peng Zhao, Zhen-Hua Zhuang, Tianbao Yang, Zhi-Hua Zhou
- Abstract要約: 群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
- 参考スコア(独自算出の注目度): 96.26317627118912
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper investigates group distributionally robust optimization (GDRO),
with the purpose to learn a model that performs well over $m$ different
distributions. First, we formulate GDRO as a stochastic convex-concave
saddle-point problem, and demonstrate that stochastic mirror descent (SMD),
using $m$ samples in each iteration, achieves an $O(m (\log m)/\epsilon^2)$
sample complexity for finding an $\epsilon$-optimal solution, which matches the
$\Omega(m/\epsilon^2)$ lower bound up to a logarithmic factor. Then, we make
use of techniques from online learning to reduce the number of samples required
in each round from $m$ to $1$, keeping the same sample complexity.
Specifically, we cast GDRO as a two-players game where one player simply
performs SMD and the other executes an online algorithm for non-oblivious
multi-armed bandits. Next, we consider a more practical scenario where the
number of samples that can be drawn from each distribution is different, and
propose a novel formulation of weighted GDRO, which allows us to derive
distribution-dependent convergence rates. Denote by $n_i$ the sample budget for
the $i$-th distribution, and assume $n_1 \geq n_2 \geq \cdots \geq n_m$. In the
first approach, we incorporate non-uniform sampling into SMD such that the
sample budget is satisfied in expectation, and prove that the excess risk of
the $i$-th distribution decreases at an $O(\sqrt{n_1 \log m}/n_i)$ rate. In the
second approach, we use mini-batches to meet the budget exactly and also reduce
the variance in stochastic gradients, and then leverage stochastic mirror-prox
algorithm, which can exploit small variances, to optimize a carefully designed
weighted GDRO problem. Under appropriate conditions, it attains an $O((\log
m)/\sqrt{n_i})$ convergence rate, which almost matches the optimal
$O(\sqrt{1/n_i})$ rate of only learning from the $i$-th distribution with $n_i$
samples.
- Abstract(参考訳): 本稿では,群分布にロバストな最適化(gdro, group distributionally robust optimization)について検討する。
まず、GDROを確率的凸凹サドル点問題として定式化し、各反復において$m$のサンプルを用いて、$O(m)/\epsilon^2)$のサンプル複雑性を達成し、$Omega(m/\epsilon^2)$の対数係数に一致する$\epsilon$最適解を求める。
そして、オンライン学習の手法を使って、各ラウンドに必要なサンプル数を$m$から$$$に減らし、同じサンプルの複雑さを維持します。
具体的には、GDROを2人プレイヤゲームとして、一方のプレイヤーが単にSMDを実行し、他方のプレイヤーが非公開マルチアームバンディットのオンラインアルゴリズムを実行する。
次に,各分布から抽出できるサンプルの数が異なる,より実用的なシナリオを考察し,分布依存収束率の導出を可能にする重み付きGDROの新しい定式化を提案する。
n_i$ は$i$-th分布のサンプル予算を示し、$n_1 \geq n_2 \geq \cdots \geq n_m$ を仮定する。
最初のアプローチでは、サンプル予算が期待通りに満たされるように非一様サンプリングをsmdに組み込んで、$i$-th分布の過剰なリスクが$o(\sqrt{n_1 \log m}/n_i)$レートで減少することを証明する。
第2のアプローチでは、予算を正確に満たすためにミニバッチを使用し、確率勾配の分散を低減し、さらに小さな分散を活用可能な確率ミラープロキシアルゴリズムを利用して、慎重に設計された重み付きGDRO問題を最適化する。
適切な条件下では、$o((\log m)/\sqrt{n_i})$の収束率に達し、最適な$o(\sqrt{1/n_i})$の値にほぼ一致する。
関連論文リスト
- Efficient Algorithms for Empirical Group Distributional Robust
Optimization and Beyond [15.664414751701718]
経験的GDROを$textittwo-level$ finite-sum convex-concave minimax Optimization問題として定式化する。
我々は、スナップショットとミラースナップショットポイントを1インデックスシフトした重み付き平均で計算し、単純エルゴディック平均と区別する。
注目すべきは、我々の手法が最先端の手法よりも$sqrtm$で優れていることだ。
論文 参考訳(メタデータ) (2024-03-06T09:14:24Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳(メタデータ) (2023-02-20T23:29:43Z) - Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance
Estimation for Subgaussian Distributions [8.40077201352607]
我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。
我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
論文 参考訳(メタデータ) (2023-01-28T16:57:46Z) - Perfect Sampling from Pairwise Comparisons [26.396901523831534]
分散分布$mathcalD$の与えられたアクセスから最適なサンプルを効率よく取得する方法を,サポート対象の要素のペア比較に限定して検討する。
固定分布が$mathcalD$と一致するマルコフ連鎖を設計し、過去からの結合技術を用いて正確なサンプルを得るアルゴリズムを提供する。
論文 参考訳(メタデータ) (2022-11-23T11:20:30Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Optimal Sublinear Sampling of Spanning Trees and Determinantal Point
Processes via Average-Case Entropic Independence [3.9586758145580014]
強いレイリー分布から繰り返しサンプリングする高速アルゴリズムを設計する。
グラフ $G=(V, E)$ に対して、$G$ in $widetildeO(lvert Vrvert)$ time per sample から一様にランダムに散らばる木を概算する方法を示す。
$n$要素の基底集合の$k$のサブセット上の決定的点プロセスに対して、$widetildeO(komega)$ time の最初の $widetildeO(nk) の後に、$widetildeO(komega)$ time のサンプルを概算する方法を示す。
論文 参考訳(メタデータ) (2022-04-06T04:11:26Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳(メタデータ) (2020-07-16T06:44:44Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳(メタデータ) (2020-06-15T21:55:34Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳(メタデータ) (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。