論文の概要: Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming

• arxiv url: http://arxiv.org/abs/2401.00664v4
• Date: Wed, 25 Sep 2024 02:47:56 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-09 05:28:28.250602
• Title: Metric Entropy-Free Sample Complexity Bounds for Sample Average Approximation in Convex Stochastic Programming
• Title（参考訳）: 凸確率計画における平均平均近似のための計量エントロピー自由サンプル複素境界
• Authors: Hongcheng Liu, Jindong Tong,
• Abstract要約: 本稿では,凸問題や強凸プログラミング(SP)問題におけるサンプル平均近似(SAA)について検討する。 SAAのサンプルの複雑さは、計量エントロピーの定量化から完全に解放されることを示している。
• 参考スコア（独自算出の注目度）: 0.6906005491572401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies sample average approximation (SAA) in solving convex or strongly convex stochastic programming (SP) problems. Under some common regularity conditions, we show -- perhaps for the first time -- that SAA's sample complexity can be completely free from any quantification of metric entropy (such as the logarithm of the covering number), leading to a significantly more efficient rate with dimensionality $d$ than most existing results. From the newly established complexity bounds, an important revelation is that SAA and the canonical stochastic mirror descent (SMD) method, two mainstream solution approaches to SP, entail almost identical rates of sample efficiency, rectifying a persistent theoretical discrepancy of SAA from SMD by the order of $O(d)$. Furthermore, this paper explores non-Lipschitzian scenarios where SAA maintains provable efficacy but the corresponding results for SMD remain mostly unexplored, indicating the potential of SAA's better applicability in some irregular settings.
• Abstract（参考訳）: 本稿では、凸あるいは強凸確率計画(SP)問題の解法におけるサンプル平均近似(SAA)について検討する。 いくつかの共通正規性条件の下では、SAAのサンプルの複雑さは(被覆数の対数のような)計量エントロピーの量子化から完全に解放され、既存のほとんどの結果よりも次元$d$のかなり効率的な速度が得られることを示す。 新たに確立された複雑性境界から、SAAと正準確率ミラー降下(SMD)法は、SPに対する2つの主流解法であり、サンプル効率のほぼ同じ率を伴い、$O(d)$の順序でSAAの永続的理論的相違をSMDから修正する。 さらに,SAAが証明可能な有効性を維持している非リプシッツ的シナリオについて検討するが,SMDの対応する結果はほとんど探索されていないままであり,不規則な条件下でのSAAのよりよい適用可能性を示している。

関連論文リスト

• 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)

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

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