論文の概要: Efficient Methods for Online Multiclass Logistic Regression

• arxiv url: http://arxiv.org/abs/2110.03020v1
• Date: Wed, 6 Oct 2021 19:10:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-08 16:05:07.821912
• Title: Efficient Methods for Online Multiclass Logistic Regression
• Title（参考訳）: オンラインマルチクラスロジスティック回帰のための効率的な方法
• Authors: Naman Agarwal, Satyen Kale, Julian Zimmert
• Abstract要約: マルチクラスロジスティック回帰は、分類と強化に応用した機械学習の基本的なタスクである。 従来の研究は、オンラインマルチクラスロジスティック回帰問題において「高速」を達成するために不適切な予測器の重要性を強調してきた。 FOLKLOREという新しいアルゴリズムを開発し,Fosterら(2018)のアルゴリズムよりもはるかに高速に動作する問題について検討する。 提案アルゴリズムは,オンラインバンディット・マルチクラス予測とオンライン・マルチクラス・ブーピングに適用可能であることを示す。
• 参考スコア（独自算出の注目度）: 38.1260612507181
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multiclass logistic regression is a fundamental task in machine learning with applications in classification and boosting. Previous work (Foster et al., 2018) has highlighted the importance of improper predictors for achieving "fast rates" in the online multiclass logistic regression problem without suffering exponentially from secondary problem parameters, such as the norm of the predictors in the comparison class. While Foster et al. (2018) introduced a statistically optimal algorithm, it is in practice computationally intractable due to its run-time complexity being a large polynomial in the time horizon and dimension of input feature vectors. In this paper, we develop a new algorithm, FOLKLORE, for the problem which runs significantly faster than the algorithm of Foster et al.(2018) -- the running time per iteration scales quadratically in the dimension -- at the cost of a linear dependence on the norm of the predictors in the regret bound. This yields the first practical algorithm for online multiclass logistic regression, resolving an open problem of Foster et al.(2018). Furthermore, we show that our algorithm can be applied to online bandit multiclass prediction and online multiclass boosting, yielding more practical algorithms for both problems compared to the ones in Foster et al.(2018) with similar performance guarantees. Finally, we also provide an online-to-batch conversion result for our algorithm.
• Abstract（参考訳）: マルチクラスロジスティック回帰は、分類と強化における機械学習の基本的なタスクである。 先行研究(Foster et al., 2018)では、オンラインマルチクラスロジスティック回帰問題において、比較クラスの予測器のノルムのような二次問題パラメータに指数関数的に苦しむことなく、不適切な予測器が「高速」を達成することの重要性を強調している。 foster et al. (2018) は統計的に最適なアルゴリズムを導入したが、実行時の複雑性が時間軸の大きな多項式と入力特徴ベクトルの次元であるため、計算的に難解である。 本稿では,フォスターらのアルゴリズムよりも高速に動作する問題に対して,新しいアルゴリズムであるフォークロア(folklore)を開発した。 (2018) -- イテレーションごとの実行時間は次元で二乗的にスケールする -- 後悔の限界における予測者の規範に対する線形依存のコストで。 これにより、オンライン多クラスロジスティック回帰のための最初の実用的なアルゴリズムが得られ、Fosterらによって解決される。 (2018). さらに,本アルゴリズムをオンラインバンディットマルチクラス予測やオンラインマルチクラスブースティングに適用できることを示し,フォスターなどと比較して,両問題に対してより実用的なアルゴリズムを提供する。 (2018) 同様の性能保証。 最後に,提案アルゴリズムのオンライン・バッチ変換結果も提供する。

関連論文リスト

• Online Nonparametric Supervised Learning for Massive Data [0.0]
  本研究では,非パラメトリック分類器を大規模にリアルタイムに計算する高速アルゴリズムと,ストリーミングデータフレームワークを開発した。 提案手法は、リアルタイムな胎児の健康モニタリングによく使用される機械学習アルゴリズムと比較して評価・比較する。
  論文  参考訳（メタデータ） (2024-05-29T20:04:23Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Online Regenerative Learning [0.0]
  入力による目的関数を最大化するオンライン線形プログラミング(OLP)問題について検討する。 このタイプの OLP を解析する様々なアルゴリズムの性能は、入力が i.i.d 分布に従うとよく研究される。
  論文  参考訳（メタデータ） (2022-09-18T21:04:56Z)
• A Regression Approach to Learning-Augmented Online Algorithms [17.803569868141647]
  本論文では,本手法について紹介し,一般的なオンライン検索フレームワークの文脈で考察する。 この回帰問題におけるサンプルの複雑さにほぼ厳密な境界を示し、その結果を不可知的な設定にまで拡張する。 技術的観点から、回帰問題に対する損失関数の設計にオンライン最適化ベンチマークを組み込むことが重要であることを示す。
  論文  参考訳（メタデータ） (2022-05-18T04:29:14Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• OpReg-Boost: Learning to Accelerate Online Algorithms with Operator Regression [5.457279006229211]
  本稿では,オンライン最適化と学習アルゴリズムの収束性を高めるために,新たな正規化手法であるOpsReg-Boostを提案する。 本稿では,演算子の回帰問題を形式化し,計算効率の良いピースマン・ラフフォード解法を提案する。
  論文  参考訳（メタデータ） (2021-05-27T16:17:38Z)
• Boosting for Online Convex Optimization [64.15578413206715]
  多数の専門家とオンライン凸最適化の意思決定フレームワークを検討します。 弱学習アルゴリズムは、基本クラスの専門家に対するおよその後悔を保証するメカニズムとして定義します。 ベースクラスの凸船体に対するほぼ最適の後悔を保証する効率的なブースティングアルゴリズムを提供します。
  論文  参考訳（メタデータ） (2021-02-18T12:30:49Z)
• Online Orthogonal Matching Pursuit [6.6389732792316005]
  疎線形回帰のランダムな設計設定におけるオンラインサポート回復のための新しいオンラインアルゴリズム:オンライン直交マッチング法(OOMP)を提案する。 提案手法は,候補となる特徴にのみ必要なサンプルの割り当てと,回帰係数を推定するために選択した変数集合の最適化を逐次的に選択する。
  論文  参考訳（メタデータ） (2020-11-22T21:59:05Z)
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles [112.89548995091182]
  我々は、文脈的帯域幅からオンライン回帰への、初めての普遍的で最適な削減を提供する。 我々のアルゴリズムは、実現可能性以上の分布仮定は必要とせず、コンテキストが逆選択された場合でも機能する。
  論文  参考訳（メタデータ） (2020-02-12T11:33:46Z)

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

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