論文の概要: Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis
- arxiv url: http://arxiv.org/abs/2407.00916v1
- Date: Mon, 1 Jul 2024 02:42:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-04 00:55:54.714854
- Title: Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis
- Title（参考訳）: データ依存レギュレット解析によるメモリ制約を考慮したオンラインカーネル選択の学習可能性
- Authors: Junfan Li, Shizhong Liao,
- Abstract要約: 本稿では,カーネル選択とオンライン予測手順のメモリが固定予算に限定されたメモリ制約によるオンラインカーネル選択について検討する。
この結果から,2つのデータ複雑度が線形である場合,小さなメモリ制約内で学習が可能であることが示唆された。
- 参考スコア（独自算出の注目度）: 9.481945539928905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Online kernel selection is a fundamental problem of online kernel methods. In this paper, we study online kernel selection with memory constraint in which the memory of kernel selection and online prediction procedures is limited to a fixed budget. An essential question is what is the intrinsic relationship among online learnability, memory constraint and data complexity? To answer the question, it is necessary to show the trade-offs between regret bound and memory constraint. Previous work gives a worst-case lower bound depending on the data size,and shows learning is impossible within a small memory constraint. In contrast, we present a different result by providing data-dependent upper bounds depending on two data complexities, namely kernel alignment and the cumulative losses of competitive hypothesis. We propose an algorithmic framework giving data-dependent upper bounds for two types of loss functions. For the hinge loss function, our algorithm achieves an expected upper bound depending on kernel alignment. For smooth loss functions,our algorithm achieves a high-probability upper bound depending on the cumulative losses of competitive hypothesis. We also prove a matching lower bound for smooth loss functions. Our results show that if the two data complexities are sub-linear, then learning is possible within a small memory constraint. Our algorithmic framework depends on a new buffer maintaining framework and a reduction from online kernel selection to prediction with expert advice.Finally, we empirically verify the prediction performance of our algorithms on benchmark datasets.
- Abstract（参考訳）: オンラインカーネル選択は、オンラインカーネルメソッドの基本的な問題である。
本稿では,カーネル選択とオンライン予測手順のメモリが固定予算に制限されるメモリ制約によるオンラインカーネル選択について検討する。
重要な疑問は、オンライン学習性、メモリ制約、データ複雑さの内在的な関係は何か、ということです。
この問いに答えるためには、後悔の限界と記憶の制約の間のトレードオフを示す必要がある。
これまでの作業では、データサイズによって最悪の場合のバウンダリが低くなっており、小さなメモリ制約内では学習が不可能であることを示している。
対照的に、カーネルアライメントと競合仮説の累積損失という2つのデータ複雑度に依存するデータ依存上界を提供することにより、異なる結果が得られる。
本稿では,2種類の損失関数に対してデータ依存上界を与えるアルゴリズムフレームワークを提案する。
ヒンジ損失関数に対しては,カーネルのアライメントに応じて,提案アルゴリズムは期待上界を達成できる。
滑らかな損失関数に対しては、アルゴリズムは競合仮説の累積損失に依存する高確率上限を達成する。
また、滑らかな損失関数に対する一致した下界も証明する。
この結果から,2つのデータ複雑度が線形である場合,小さなメモリ制約内で学習が可能であることが示唆された。
アルゴリズムフレームワークは,新たなバッファ維持フレームワークと,オンラインカーネル選択から専門家のアドバイスによる予測への削減に依存し,ベンチマークデータセット上でアルゴリズムの予測性能を実証的に検証する。
関連論文リスト
- LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
敵は、学習者に未知の任意の数kの損失関数を破損させることで、外れ値を導入することができる。
我々は,任意の数kで損失関数を破損させることで,敵が外乱を発生させることができる,頑健なオンラインラウンド最適化フレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-12T17:08:31Z) - Kernel Alignment for Unsupervised Feature Selection via Matrix Factorization [8.020732438595905]
教師なしの特徴選択は、いわゆる次元の呪いを和らげるために有効であることが証明されている。
多くの既存行列分解に基づく教師なし特徴選択法は、サブスペース学習に基づいて構築されている。
本稿では,カーネル関数とカーネルアライメントを統合したモデルを構築する。
これにより、線形および非線形の類似情報を学習し、最適なカーネルを自動的に生成することができる。
論文 参考訳（メタデータ） (2024-03-13T20:35:44Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳（メタデータ） (2022-02-28T13:01:04Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Efficient First-Order Contextual Bandits: Prediction, Allocation, and
Triangular Discrimination [82.52105963476703]
統計的学習、オンライン学習、その他における繰り返しのテーマは、低騒音の問題に対してより速い収束率が可能であることである。
1次保証は統計的およびオンライン学習において比較的よく理解されている。
三角識別と呼ばれる対数損失と情報理論量が一階保証を得る上で基本的な役割を担っていることを示す。
論文 参考訳（メタデータ） (2021-07-05T19:20:34Z) - Lower Bounds on Cross-Entropy Loss in the Presence of Test-time
Adversaries [33.53470955144013]
本論文では,テストタイムの逆数の存在下でのクロスエントロピー損失の最適下限と,それに対応する最適分類出力を決定する。
また、この下界を効率的に計算するベスポークアルゴリズムの正しさの証明を提案し、提案する。
我々は,現在のロバストなトレーニング手法の有効性を判定するための診断ツールとして下限を用い,より大きな予算での最適性とのギャップを見出した。
論文 参考訳（メタデータ） (2021-04-16T21:41:28Z) - Online Limited Memory Neural-Linear Bandits with Likelihood Matching [53.18698496031658]
本研究では,探索学習と表現学習の両方が重要な役割を果たす課題を解決するために,ニューラルネットワークの帯域について検討する。
破滅的な忘れ込みに対して耐性があり、完全にオンラインである可能性の高いマッチングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-07T14:19:07Z) - Kernel k-Means, By All Means: Algorithms and Strong Consistency [21.013169939337583]
Kernel $k$クラスタリングは、非線形データの教師なし学習のための強力なツールである。
本稿では,最適化された局所解に対処するための一般的な手法を応用した結果を一般化する。
我々のアルゴリズムは、この非線形分離問題をよりよく解くために、Magricalization-minimization (MM) を利用している。
論文 参考訳（メタデータ） (2020-11-12T16:07:18Z) - Regularized ERM on random subspaces [18.541369654442796]
我々は、データのランダムなサブセットにまたがるデータ依存部分空間を、カーネルメソッドに対するNystr"omアプローチの特別なケースとして、リカバリする可能性があると考えている。
ランダムな部分空間を考えると自然に計算上の節約につながるが、問題は対応する学習精度が劣化するかどうかである。
論文 参考訳（メタデータ） (2020-06-17T17:21:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。