論文の概要: Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity

• arxiv url: http://arxiv.org/abs/2006.04429v3
• Date: Fri, 17 Jun 2022 09:38:48 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-24 02:37:17.016770
• Title: Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity
• Title（参考訳）: 確率近似における最悪の場合解析を超えて:モーメント推定はインスタンス複雑性を改善する
• Authors: Jingzhao Zhang, Hongzhou Lin, Subhro Das, Suvrit Sra, Ali Jadbabaie
• Abstract要約: 近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
• 参考スコア（独自算出の注目度）: 58.70807593332932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study oracle complexity of gradient based methods for stochastic approximation problems. Though in many settings optimal algorithms and tight lower bounds are known for such problems, these optimal algorithms do not achieve the best performance when used in practice. We address this theory-practice gap by focusing on instance-dependent complexity instead of worst case complexity. In particular, we first summarize known instance-dependent complexity results and categorize them into three levels. We identify the domination relation between different levels and propose a fourth instance-dependent bound that dominates existing ones. We then provide a sufficient condition according to which an adaptive algorithm with moment estimation can achieve the proposed bound without knowledge of noise levels. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation as it achieves improved instance complexity.
• Abstract（参考訳）: 確率近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 多くの設定において、最適アルゴリズムと厳密な下限はそのような問題で知られているが、これらの最適アルゴリズムは実際に使用される際に最高の性能を達成できない。 最悪の場合の複雑性ではなく、インスタンス依存の複雑性に焦点を当てることで、この理論と実践的なギャップに対処する。 特に、既知のインスタンス依存の複雑性結果をまず要約し、3つのレベルに分類する。 異なるレベル間の支配関係を特定し、既存のレベルを支配する4番目のインスタンス依存境界を提案する。 次に、雑音レベルを知らずに、モーメント推定を伴う適応アルゴリズムが提案した境界を達成できる十分な条件を提供する。 提案するアルゴリズムとその解析は、インスタンスの複雑さを改善するためにモーメント推定の成功を理論的に正当化する。

関連論文リスト

• Instance-Optimality in Interactive Decision Making: Toward a Non-Asymptotic Theory [30.061707627742766]
  適応性の強い概念であるインスタンス最適化を目指しており、どの問題の場合であっても、検討中のアルゴリズムは全ての一貫したアルゴリズムより優れていると主張する。 本稿では,一般関数近似を用いたインスタンス最適決定の非漸近的理論の開発に向けて第一歩を踏み出す。
  論文  参考訳（メタデータ） (2023-04-24T21:51:58Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Beyond No Regret: Instance-Dependent PAC Reinforcement Learning [29.552894877883883]
  低後悔を達成し、インスタンス最適率で$epsilon$-optimal Policyを特定できるというトレードオフが存在することを示す。 本稿では,このサンプル複雑性を実現する新しい計画ベースアルゴリズムの提案と解析を行う。 我々のアルゴリズムは最小限の最適値であり、いくつかの例では、インスタンス依存のサンプル複雑性は最悪のケース境界よりも大幅に改善されている。
  論文  参考訳（メタデータ） (2021-08-05T16:34:17Z)
• Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
  プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。 我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
  論文  参考訳（メタデータ） (2021-05-13T18:24:30Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective [104.67295710363679]
  古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。 我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。 次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
  論文  参考訳（メタデータ） (2020-10-07T01:33:06Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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