論文の概要: Majorizing Measures, Sequential Complexities, and Online Learning
- arxiv url: http://arxiv.org/abs/2102.01729v1
- Date: Tue, 2 Feb 2021 19:52:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-05 03:52:59.665047
- Title: Majorizing Measures, Sequential Complexities, and Online Learning
- Title（参考訳）: メジャー化対策、シーケンス複雑性、オンライン学習
- Authors: Adam Block, Yuval Dagan, and Sasha Rakhlin
- Abstract要約: 本稿では, シーケンシャルなRademacher複雑性を制御するために, ジェネリックチェアリングと大規模化手法を導入する。
分数被覆数の概念は, 逐次スケール感応次元の点で支配的であることを示す。
我々は最悪のシーケンシャルなRademacher複雑性に対して、厳密な収縮不等式を確立する。
- 参考スコア（独自算出の注目度）: 2.1793134762413433
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce the technique of generic chaining and majorizing measures for
controlling sequential Rademacher complexity. We relate majorizing measures to
the notion of fractional covering numbers, which we show to be dominated in
terms of sequential scale-sensitive dimensions in a horizon-independent way,
and, under additional complexity assumptions establish a tight control on
worst-case sequential Rademacher complexity in terms of the integral of
sequential scale-sensitive dimension. Finally, we establish a tight contraction
inequality for worst-case sequential Rademacher complexity. The above
constitutes the resolution of a number of outstanding open problems in
extending the classical theory of empirical processes to the sequential case,
and, in turn, establishes sharp results for online learning.
- Abstract（参考訳）: 本稿では, シーケンシャルなRademacher複雑性を制御するために, ジェネリックチェアリングと大規模化手法を導入する。
本研究は,水平独立な方法での逐次スケールセンシティブな次元の観点で支配される分数被覆数の概念を大規模化することで,さらに複雑性の仮定により,逐次スケールセンシティブな次元の積分による最悪ケースシーケンシャルなラデマッハ複雑性の厳密な制御を確立する。
最後に、最悪ケースシーケンシャルなRademacher複雑性に対して、厳密な収縮不等式を確立する。
上記は、経験的過程の古典的理論を逐次ケースに拡張する上で顕著なオープン問題の数の解決を構成し、その結果、オンライン学習のための鋭い結果を確立します。
関連論文リスト
- A Survey on Complexity Measures of Pseudo-Random Sequences [2.6530332965939345]
1960年代に2進列のコルモゴロフ複雑性が導入されて以来、ランダムネス評価のための複雑性測定のトピックにおいて大きな進歩があった。
本調査は, 擬似ランダム列の線形, 二次, 最大次複雑度に関する過去40年間の顕著な研究をレビューする。
論文 参考訳（メタデータ） (2024-05-14T10:07:58Z) - Generalization Guarantees via Algorithm-dependent Rademacher Complexity [33.408679482592426]
本稿では,アルゴリズムおよびデータ依存仮説クラスの経験的ラデマッハ複雑性である一般化誤差を制御する尺度を提案する。
有限フラクタル次元に基づく新しい境界を得るが、これは (a) 従来のフラクタル型境界を連続的な仮説クラスから有限的な仮説クラスに拡張し、 (b) 相互情報項を避ける。
論文 参考訳（メタデータ） (2023-07-04T18:37:38Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Chaos and multifold complexity for an inverted harmonic oscillator [0.0]
複雑性は、交互にジグザグの順序で与えられた時間の組み合わせの最も長い置換に支配されていることを証明する。
多次複雑性の一般的な構造は、一般的な量子系に対して普遍的に真であるべきであると推測する。
論文 参考訳（メタデータ） (2022-11-06T14:19:48Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Algorithmic Regularization in Model-free Overparametrized Asymmetric
Matrix Factorization [16.325663190517773]
我々は、任意の過パラメータ化を持つ自然な非定式化の下で、非対称な分解問題を考察する。
観測された行列に対して最高の低ランク近似を生成する。
論文 参考訳（メタデータ） (2022-03-06T00:07:53Z) - On the Complexity of a Practical Primal-Dual Coordinate Method [63.899427212054995]
ランダム・座標降下法(PURE-CD)を用いた原始双対アルゴリズムの複雑性境界を証明した。
バイマックス性能問題を解くための優れた外挿が得られることが示されている。
論文 参考訳（メタデータ） (2022-01-19T16:14:27Z) - Parallelizing Contextual Linear Bandits [82.65675585004448]
並列な)コンテキスト線形バンディットアルゴリズムの族を提示し、その遺残はそれらの完全シーケンシャルなアルゴリズムとほぼ同一である。
また,これらの並列アルゴリズムについて,材料発見や生物配列設計の問題など,いくつかの領域で実証評価を行った。
論文 参考訳（メタデータ） (2021-05-21T22:22:02Z) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳（メタデータ） (2020-10-07T01:33:06Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - Adversarial Learning Guarantees for Linear Hypotheses and Neural
Networks [45.06091849856641]
線形仮説の対角的経験的ラデマチャー複雑性に対して, 上下境界を与える。
我々は解析を拡張し、1つのReLUユニットに対してRadecherの複雑性を下限と上限に設定する。
最後に、1つの隠蔽層を持つフィードフォワードニューラルネットワークに対して、逆ラデマチャー複雑性境界を与える。
論文 参考訳（メタデータ） (2020-04-28T15:55:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。