論文の概要: Reconciling Universal and Uniform Learning with $Q$-Aggregation

• arxiv url: http://arxiv.org/abs/2609.05041v1
• Date: Fri, 04 Sep 2026 12:02:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-07 18:15:24.029158
• Title: Reconciling Universal and Uniform Learning with $Q$-Aggregation
• Title（参考訳）: Q$-Aggregationによるユニバーサルとユニフォーマルラーニングの再構築
• Abstract要約: 余剰平均二乗誤差の観点から、有界応答下での回帰について検討する。 Q$-aggregation 推定器が指数的普遍率を達成することを示す。 また、二乗損失を伴う学習における普遍的な学習率に関するいくつかの構造的結果も証明した。
• 参考スコア（独自算出の注目度）: 13.815063206114713
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study regression under bounded responses in terms of excess mean squared error. When the comparator class is finite, this setting is known as model selection aggregation, and achieving minimax excess risk requires improper learning algorithms. Contrary to this, in the universal learning framework no improperness is needed, as simple empirical risk minimization achieves the best-possible exponential learning rate. Hence, the two frameworks suggest different optimal algorithmic principles. This poses the question of best-of-both-worlds guarantees: Are minimax and universal exponential rates achievable by the same algorithm? For finite hypothesis classes, we answer this question in the affirmative by showing that the $Q$-aggregation estimator - which is known to achieve minimax optimal tails - achieves exponential universal rates. A wide range of other estimators and algorithmic principles (ERM, sequential averaging, pruning, and star estimation) do not achieve both. For countably infinite hypothesis classes, we answer the question in the negative by showing that there is an inherent trade-off between achieving exponential universal and minimax uniform rates. This trade-off is exactly traced by combining optimal algorithms from each world using $Q$-aggregation. Besides these results, we prove several additional structural results about universal rates in learning with squared loss.
• Abstract（参考訳）: 余剰平均二乗誤差の観点から、有界応答下での回帰について検討する。 コンパレータクラスが有限の場合、この設定はモデル選択アグリゲーションと呼ばれ、最小極超過リスクを達成するには不適切な学習アルゴリズムが必要である。 これとは対照的に、単純な経験的リスク最小化が最良の指数的学習率を達成するため、普遍的な学習フレームワークでは不適切さは不要である。 したがって、2つのフレームワークは異なる最適なアルゴリズム原理を提案する。 ミニマックスと普遍指数率は同じアルゴリズムで達成できるのか? 有限仮説クラスに対しては、$Q$-aggregation 推定器(ミニマックス最適尾根を達成することが知られている)が指数的普遍率を達成することを示して、この疑問に肯定的に答える。 他の幅広い推定器やアルゴリズムの原理(ERM、逐次平均化、プルーニング、スター推定)は両方を達成できない。 数え切れないほど無限の仮説クラスに対して、指数的普遍性(英語版)とミニマックス均一性(英語版)の達成の間に固有のトレードオフが存在することを示すことによって、負の質問に答える。 このトレードオフは、Q$-aggregationを使って、各世界の最適なアルゴリズムを組み合わせることによって、正確に追跡される。 これらの結果に加えて、二乗損失を伴う学習における普遍率に関するいくつかの構造的結果が証明された。

関連論文リスト

• The Sample Complexity of Multiclass and Sparse Contextual Bandits [106.74652380822778]
  我々は,包括的フィードバックに基づいて,与えられたクラスからほぼ最適なポリシーを特定することを目的とする。 ゼロ・ワンの報酬を伴うバンド型マルチクラス分類に動機付けられ、emph$s$-sparse設定に焦点をあてる。 我々は、$s$-sparseの報酬で、誘導モデルクラスは、$s$でスケールするシャープなDEC境界を認め、直接最適なレートを得ることを示す。
  論文  参考訳（メタデータ） (2026-05-28T09:12:20Z)
• On the Learning Curves of Revenue Maximization [62.087200798198786]
  学習曲線は、トレーニングサンプル数の関数として、固定された基礎分布に対するアルゴリズムの誤差の減衰をプロットする。 収益を最大化する学習アルゴリズムに関する先行研究は、学習理論におけるPAC学習フレームワークと並行して、分散のない視点を採用する。 ベイズ一貫性アルゴリズムが存在し、任意の評価分布に対して学習曲線が0に収束することを示す。
  論文  参考訳（メタデータ） (2026-04-29T17:38:25Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Turing-Universal Learners with Optimal Scaling Laws [2.7485183218472016]
  我々は,全ての学習アルゴリズムにおいて,最適な分布依存率を実現する「ユニバーサル学習者」アルゴリズムの存在を観察する。 構成そのものは、レヴィンの普遍探索の単純な拡張である(Levin, 1973)
  論文  参考訳（メタデータ） (2021-11-09T18:44:35Z)
• Localization, Convexity, and Star Aggregation [0.0]
  オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。 統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-19T00:47:59Z)
• Differentiable Linear Bandit Algorithm [6.849358422233866]
  アッパー信頼境界は、線形多腕バンディット問題の最も一般的な方法である。 勾配上昇による信頼度を学習できる勾配推定器を導入する。 提案アルゴリズムは,腕の特徴の次元を$d$で,信頼度を$hatbeta$で学習したサイズを$tildemathcalO(hatbetasqrtdT)$上限とする。
  論文  参考訳（メタデータ） (2020-06-04T16:43:55Z)

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

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