論文の概要: Regularization and Optimal Multiclass Learning
- arxiv url: http://arxiv.org/abs/2309.13692v1
- Date: Sun, 24 Sep 2023 16:49:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-26 18:14:21.253768
- Title: Regularization and Optimal Multiclass Learning
- Title（参考訳）: 正規化と最適マルチクラス学習
- Authors: Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan,
Shang-Hua Teng
- Abstract要約: この研究は、経験的リスク最小化が失敗する最も単純な設定における正規化の役割を特徴づけることである。
ワンインクルージョングラフ(OIG)を用いて、試行錯誤アルゴリズムの原理に相応しい最適な学習アルゴリズムを示す。
- 参考スコア（独自算出の注目度）: 10.909417433031454
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: The quintessential learning algorithm of empirical risk minimization (ERM) is
known to fail in various settings for which uniform convergence does not
characterize learning. It is therefore unsurprising that the practice of
machine learning is rife with considerably richer algorithmic techniques for
successfully controlling model capacity. Nevertheless, no such technique or
principle has broken away from the pack to characterize optimal learning in
these more general settings.
The purpose of this work is to characterize the role of regularization in
perhaps the simplest setting for which ERM fails: multiclass learning with
arbitrary label sets. Using one-inclusion graphs (OIGs), we exhibit optimal
learning algorithms that dovetail with tried-and-true algorithmic principles:
Occam's Razor as embodied by structural risk minimization (SRM), the principle
of maximum entropy, and Bayesian reasoning. Most notably, we introduce an
optimal learner which relaxes structural risk minimization on two dimensions:
it allows the regularization function to be "local" to datapoints, and uses an
unsupervised learning stage to learn this regularizer at the outset. We justify
these relaxations by showing that they are necessary: removing either dimension
fails to yield a near-optimal learner. We also extract from OIGs a
combinatorial sequence we term the Hall complexity, which is the first to
characterize a problem's transductive error rate exactly.
Lastly, we introduce a generalization of OIGs and the transductive learning
setting to the agnostic case, where we show that optimal orientations of
Hamming graphs -- judged using nodes' outdegrees minus a system of
node-dependent credits -- characterize optimal learners exactly. We demonstrate
that an agnostic version of the Hall complexity again characterizes error rates
exactly, and exhibit an optimal learner using maximum entropy programs.
- Abstract（参考訳）: 経験的リスク最小化(ERM)の学習アルゴリズムは、一様収束が学習を特徴付けない様々な設定で失敗することが知られている。
したがって、機械学習の実践が、モデルキャパシティの制御を成功させるために、かなりリッチなアルゴリズム技術で波及していることは驚くにあたらない。
それでも、このようなテクニックや原則は、これらのより一般的な設定で最適な学習を特徴付けるために、パックから切り離されたものはない。
この研究の目的は、ermが失敗する最も単純な設定である任意のラベルセットによるマルチクラス学習において、正規化の役割を特徴づけることである。
構造的リスク最小化(srm)、最大エントロピーの原理、ベイズ的推論によって具現化されるoccamのカミソリ(razor)というアルゴリズムを試す。
特に,2次元の構造的リスク最小化を緩和する最適学習器を導入する。これは,正規化関数をデータポイントに「局所的」にすることを可能にし,教師なし学習段階を用いて,この正規化関数を最初から学習する。
いずれの次元も削除しても、ほぼ最適に近い学習者を生み出すことはできない。
また、OIGからホール複雑性と呼ばれる組合せ列を抽出し、問題の帰納的誤り率を正確に特徴づける最初の方法である。
最後に、oigの一般化とトランスダクティブ学習設定を不可知のケースに導入し、ハミンググラフの最適方向 -- ノードの外部度を用いて判断された -- ノード依存のクレジットのシステム -- が最適な学習者を正確に特徴付けることを示す。
ホール複雑性の非依存バージョンは誤り率を正確に特徴付けし、最大エントロピープログラムを用いて最適な学習者を示す。
関連論文リスト
- Probably Approximately Precision and Recall Learning [62.912015491907994]
精度とリコールは機械学習の基本的な指標である。
一方的なフィードバック – トレーニング中にのみ肯定的な例が観察される – は,多くの実践的な問題に固有のものだ。
PAC学習フレームワークでは,各仮説をグラフで表現し,エッジは肯定的な相互作用を示す。
論文 参考訳（メタデータ） (2024-11-20T04:21:07Z) - A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
我々は,現代のディープラーニングにおいて広く普及している一般的なメタ学習問題に対処する。
これらの問題は、しばしばBi-Level Optimizations (BLO)として定式化される。
我々は,与えられたBLO問題を,内部損失関数が滑らかな分布となり,外損失が内部分布に対する期待損失となるようなii最適化に変換することにより,新たな視点を導入する。
論文 参考訳（メタデータ） (2024-10-14T12:10:06Z) - GBM-based Bregman Proximal Algorithms for Constrained Learning [3.667453772837954]
我々はBregman近位アルゴリズムのフレームワーク内で制約付き学習タスクにGBMを適用する。
本稿では,学習対象関数が凸である場合に,大域的最適性を保証する新しいブレグマン法を提案する。
本稿では,Bregmanアルゴリズムフレームワークの有効性を示すための実験的な証拠を提供する。
論文 参考訳（メタデータ） (2023-08-21T14:56:51Z) - Active Learning in the Predict-then-Optimize Framework: A Margin-Based
Approach [5.371816551086118]
本研究では,ラベルのないデータストリームから特徴サンプルのラベルを要求するかどうかを逐次決定する学習手法を開発した。
我々の能動学習法は,予測パラメータによって引き起こされる決定誤差によって直接情報を得る最初の方法である。
論文 参考訳（メタデータ） (2023-05-11T05:44:36Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Neural Active Learning with Performance Guarantees [37.16062387461106]
非パラメトリックなレシエーションにおけるストリーミング環境におけるアクティブラーニングの問題について検討する。
我々は最近提案されたニューラル・タンジェント・カーネル(NTK)近似ツールを用いて、アルゴリズムが操作する特徴空間と学習したモデルを上から計算する適切なニューラル埋め込みを構築する。
論文 参考訳（メタデータ） (2021-06-06T20:44:23Z) - Smooth Bilevel Programming for Sparse Regularization [5.177947445379688]
反復再重み付き最小二乗法(IRLS)は、機械学習における空間的回帰問題を解くための一般的な手法である。
両レベルスキームが組み合わさって、IRLSの驚くほど再パラメータ化が、いかにスパーシティの上位化を実現するかを示す。
論文 参考訳（メタデータ） (2021-06-02T19:18:22Z) - Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning [36.015585972493575]
本稿では,一般値関数近似を用いたバッチ強化学習(RL)について考察する。
Empirical Risk Minimizer (ERM) の過剰リスクは、関数クラスの Rademacher 複雑性によって有界である。
高速統計率は局所ラデマッハ複雑性のツールを使用することで達成できる。
論文 参考訳（メタデータ） (2021-03-25T14:45:29Z) - Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
ガウスの下の半空間を不可知的に学習する問題を考察する。
我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
論文 参考訳（メタデータ） (2021-02-10T18:40:44Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。