論文の概要: New Sample Complexity Bounds for (Regularized) Sample Average
Approximation in Several Heavy-Tailed, Non-Lipschitzian, and High-Dimensional
Cases
- arxiv url: http://arxiv.org/abs/2401.00664v1
- Date: Mon, 1 Jan 2024 04:35:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-03 16:19:19.452217
- Title: New Sample Complexity Bounds for (Regularized) Sample Average
Approximation in Several Heavy-Tailed, Non-Lipschitzian, and High-Dimensional
Cases
- Title(参考訳): 重機, 非リプシッツ, 高次元における(正規化)サンプル平均近似のための新しい試料複雑度境界
- Authors: Hongcheng Liu and Jindong Tong
- Abstract要約: 目的関数が必ずしもリプシッツでなくても(R)SAAが有効であることを示す。
必要なサンプルサイズは、3つの構造的仮定のいずれかの下で$mathcal Oleft(p d2/pright)$より悪い速度で成長することを示す。
- 参考スコア(独自算出の注目度): 0.8158530638728501
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the sample complexity of sample average approximation (SAA) and its
simple variations, referred to as the regularized SAA (RSAA), in solving convex
and strongly convex stochastic programming (SP) problems under
heavy-tailed-ness, non-Lipschitz-ness, and/or high dimensionality. The presence
of such irregularities underscores critical vacua in the literature. In
response, this paper presents three sets of results: First, we show that the
(R)SAA is effective even if the objective function is not necessarily Lipschitz
and the underlying distribution admits some bounded central moments only at
(near-)optimal solutions. Second, when the SP's objective function is the sum
of a smooth term and a Lipschitz term, we prove that the (R)SAA's sample
complexity is completely independent from any complexity measures (e.g., the
covering number) of the feasible region. Third, we explicate the (R)SAA's
sample complexities with regard to the dependence on dimensionality $d$: When
some $p$th ($p\geq 2$) central moment of the underlying distribution is
bounded, we show that the required sample size grows at a rate no worse than
$\mathcal O\left(p d^{2/p}\right)$ under any one of the three structural
assumptions: (i) strong convexity w.r.t. the $q$-norm ($q\geq 1$); (ii) the
combination of restricted strong convexity and sparsity; and (iii) a
dimension-insensitive $q$-norm of an optimal solution. In both cases of (i) and
(iii), it is further required that $p\leq q/(q-1)$. As a direct implication,
the (R)SAA's complexity becomes (poly-)logarithmic in $d$, whenever $p\geq
c\cdot \ln d$ is admissible for some constant $c>0$. These new results deviate
from the SAA's typical sample complexities that grow polynomially with $d$.
Part of our proof is based on the average-replace-one (RO) stability, which
appears to be novel for the (R)SAA's analyses.
- Abstract(参考訳): 本研究では, サンプル平均近似 (SAA) のサンプル複雑性と, 正規化SAA (RSAA) と呼ばれる, 重み付き, 非リプシッツ性, および/または高次元性の下での凸および強凸確率計画 (SP) 問題の解法について検討した。
このような不規則さの存在は、文学における重要な空白を浮き彫りにする。
第一に、目的関数が必ずしもリプシッツでなくても(R)SAAが有効であることを示し、基礎となる分布は(近傍)最適解においてのみ有界な中心モーメントを許容する。
第二に、SP の目的関数が滑らかな項とリプシッツ項の和であるとき、(R)SAA のサンプルの複雑さが実現可能な領域の任意の複雑性測度(例えば被覆数)から完全に独立であることを証明する。
第3に、次元への依存に関して、(r)saa のサンプル複雑性を次のように説明する: 基礎となる分布の中央モーメントの p$th (p\geq 2$) が有界であるとき、必要なサンプルサイズが$\mathcal o\left(p d^{2/p}\right)$ 以下の3つの構造的仮定のいずれかの下でも増加することを示す。
(i)強い凸性 w.r.t. the $q$-norm (q\geq 1$);
(ii)制限された強い凸性とスパース性の組み合わせ
(iii)最適解の次元非感受性$q$ノルム。
どちらの場合も
(i)および
(iii)$p\leq q/(q-1)$をさらに要求する。
直接的な意味として、 (R)SAA の複雑性は (poly-)logarithmic in $d$ となり、ある定数 $c>0$ に対して $p\geq c\cdot \ln d$ が許容される。
これらの新しい結果は、$d$で多項式的に成長するSAAの典型的なサンプル複雑度から逸脱する。
我々の証明の一部は、(R)SAAの分析において新しいものと思われる平均交換1(RO)安定性に基づいている。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - The Sample Complexity Of ERMs In Stochastic Convex Optimization [13.896417716930687]
実際に$tildeO(fracdepsilon+frac1epsilon2)$データポイントも十分であることを示す。
さらに、この結果を一般化し、全ての凸体に対して同様の上界が成り立つことを示す。
論文 参考訳(メタデータ) (2023-11-09T14:29:25Z) - Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。
これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文 参考訳(メタデータ) (2023-10-13T03:08:59Z) - A Finite Sample Complexity Bound for Distributionally Robust Q-learning [16.88062487980405]
我々は,展開環境が訓練環境と異なる強化学習環境を考える。
ロバストなマルコフ決定プロセスの定式化を適用することで、Liuらで研究されている分布的にロバストな$Q$ラーニングフレームワークを拡張します。
これはモデルのないロバストなRL問題に対する最初のサンプル複雑性結果である。
論文 参考訳(メタデータ) (2023-02-26T01:15:32Z) - Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic
Shortest Path [106.37656068276902]
本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。
学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。
我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
論文 参考訳(メタデータ) (2022-10-10T18:34:32Z) - Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates
of Linear Stochastic Approximation [22.51165277694864]
本稿では,線形近似 (LSA) アルゴリズムの有限時間解析を行う。
LSAは$d$次元線形系の近似解を計算するために用いられる。
論文 参考訳(メタデータ) (2022-07-10T14:36:04Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z) - 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) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳(メタデータ) (2020-07-15T03:25:24Z) - Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。
$n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。