論文の概要: 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)安定性に基づいている。

関連論文リスト

• Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case [0.0]
  Sign-Perturbed Sum (SPS) は強力な有限サンプルシステム同定アルゴリズムである。 本稿では,SPS信頼区間の挙動について検討する。
  論文  参考訳（メタデータ） (2024-01-28T22:44:41Z)
• SA-Solver: Stochastic Adams Solver for Fast Sampling of Diffusion Models [66.67616086310662]
  拡散確率モデル(DPM)は生成タスクでかなりの成功を収めた。 DPM からのサンプリングは、時間を要する拡散 SDE や ODE の解法と等価であるため、改良された微分方程式解法に基づく多数の高速サンプリング手法が提案されている。 拡散SDEを解くための効率の良いAdams法であるSA-of-rを提案する。
  論文  参考訳（メタデータ） (2023-09-10T12:44:54Z)
• The Curse of Memory in Stochastic Approximation: Extended Version [1.534667887016089]
  適応制御の初期から、制御システムコミュニティ内で近似の理論と応用が成長してきた。 近年の結果, (十分小さい) ステップサイズ$alpha>0$のSAの顕著な性能が確認されている。
  論文  参考訳（メタデータ） (2023-09-06T12:22:32Z)
• The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model [61.87673435273466]
  本稿では,強化学習(RL)におけるモデルロバスト性を検討した。 我々は,デプロイ環境が,名目MDPに規定された不確実性に陥る場合に,最悪の場合のパフォーマンスを最適化する政策を学習することを目的とした,分布的に堅牢なマルコフ決定プロセス(RMDP)の枠組みを採用する。
  論文  参考訳（メタデータ） (2023-05-26T02:32:03Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• Amortized Conditional Normalized Maximum Likelihood: Reliable Out of Distribution Uncertainty Estimation [99.92568326314667]
  本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。 提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。 我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
  論文  参考訳（メタデータ） (2020-11-05T08:04:34Z)
• Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
  本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。 次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。 市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
  論文  参考訳（メタデータ） (2020-08-28T02:07:08Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。 本手法は既存の不一致対策よりも高いロバスト性を実現する。
  論文  参考訳（メタデータ） (2020-06-13T06:09:27Z)
• Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenters [2.3025186469300434]
  機械学習と最適化のコミュニティには、凸リスク問題、すなわち最小化近似(SA)とサンプル平均近似(SAA)の2つの主要なアプローチがある。 ワッサーシュタイン・バリセンタ問題に対して、この優越性は逆転可能であることを示す。 最適輸送距離とエントロピー規則化された最適輸送距離に関して定義されたバリセンタを計算するSAおよびSAA実装の複雑さ境界を述べることで、詳細な比較を行う。
  論文  参考訳（メタデータ） (2020-01-21T18:54:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。