論文の概要: 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のよりよい適用可能性を示している。

関連論文リスト

• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  本稿では,両者の時間的分離を必要とせずに,意思決定とIS分布を共同で更新する反復型アルゴリズムを提案する。 本手法は,IS分布系に対する目的的,軽度な仮定の凸性の下で,最小の変数分散を達成し,大域収束を保証する。
  論文  参考訳（メタデータ） (2025-04-04T16:10:18Z)
• Sharpness-Aware Minimization: General Analysis and Improved Rates [10.11126899274029]
  Sharpness-Aware Minimization (SAM) は機械学習モデルの一般化を改善する強力な方法として登場した。 本稿では,SAMとその非正規化変動規則(USAM)を1回の更新で解析する。 我々は、より自然に緩和された仮定の下で、新しいサイズの結果を示す。
  論文  参考訳（メタデータ） (2025-03-04T03:04:06Z)
• Sample Complexity of the Sign-Perturbed Sums Method [0.0]
  Sign-Perturbed Sums (SPS) 法は真のシステムパラメータに対して正確で漸近的でない信頼領域を構成する。 一般線形回帰問題に対するSPSのサンプル複雑性について検討する。 SPS信頼領域の理論的境界と経験的サイズの違いを実験的に検討した。
  論文  参考訳（メタデータ） (2024-09-02T13:18:53Z)
• Sample Complexity of the Sign-Perturbed Sums Identification Method: Scalar Case [0.0]
  Sign-Perturbed Sum (SPS) は強力な有限サンプルシステム同定アルゴリズムである。 本稿では,SPS信頼区間の挙動について検討する。
  論文  参考訳（メタデータ） (2024-01-28T22:44:41Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  冗長な手法を排除し、単純で効率的なシェープリー推定器SimSHAPを提案する。 既存手法の解析において、推定器は特徴部分集合からランダムに要約された値の線形変換として統一可能であることを観察する。 実験により,SimSHAPの有効性が検証され,精度の高いShapley値の計算が大幅に高速化された。
  論文  参考訳（メタデータ） (2023-11-02T06:09:24Z)
• 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)
• Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
  この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。 提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
  論文  参考訳（メタデータ） (2020-06-22T17:58:54Z)
• $\gamma$-ABC: Outlier-Robust Approximate Bayesian Computation Based on a Robust Divergence Estimator [95.71091446753414]
  最寄りの$gamma$-divergence推定器をデータ差分尺度として用いることを提案する。 本手法は既存の不一致対策よりも高いロバスト性を実現する。
  論文  参考訳（メタデータ） (2020-06-13T06:09:27Z)
• Decidability of Sample Complexity of PAC Learning in finite setting [1.8130068086063333]
  様々な概念のPAC機械学習は、モデルとして考慮された確率測度の支持がa-プリオリ境界を満たすとき、正確に決定できる。 この結果は、最近発見された有限支持確率に対するZFC内のEMXの不決定性とは対照的である。
  論文  参考訳（メタデータ） (2020-02-26T14:27:36Z)
• Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenters [2.3025186469300434]
  機械学習と最適化のコミュニティには、凸リスク問題、すなわち最小化近似(SA)とサンプル平均近似(SAA)の2つの主要なアプローチがある。 ワッサーシュタイン・バリセンタ問題に対して、この優越性は逆転可能であることを示す。 最適輸送距離とエントロピー規則化された最適輸送距離に関して定義されたバリセンタを計算するSAおよびSAA実装の複雑さ境界を述べることで、詳細な比較を行う。
  論文  参考訳（メタデータ） (2020-01-21T18:54:39Z)

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

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