論文の概要: Efficient improper learning for online logistic regression

• arxiv url: http://arxiv.org/abs/2003.08109v3
• Date: Tue, 3 Nov 2020 08:01:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-22 09:50:35.427937
• Title: Efficient improper learning for online logistic regression
• Title（参考訳）: オンラインロジスティック回帰のための効率的な不適切な学習
• Authors: R\'emi J\'ez\'equel (SIERRA), Pierre Gaillard (SIERRA), Alessandro Rudi (SIERRA)
• Abstract要約: サンプル数 n の対数的後悔を持つ任意の正則アルゴリズムは、必然的に B の指数乗法定数を損なうことが知られている。 本研究では、対数的後悔を保ちながら、この指数定数を回避する効率的な不適切なアルゴリズムを設計する。 シュロゲート損失を伴う正規化経験的リスク最小化に基づく新しいアルゴリズムは、O(B log(Bn))として、オーダーO(d2)の1回あたりの時間複雑度で、後悔のスケーリングを満足させる。
• 参考スコア（独自算出の注目度）: 68.8204255655161
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the setting of online logistic regression and consider the regret with respect to the 2-ball of radius B. It is known (see [Hazan et al., 2014]) that any proper algorithm which has logarithmic regret in the number of samples (denoted n) necessarily suffers an exponential multiplicative constant in B. In this work, we design an efficient improper algorithm that avoids this exponential constant while preserving a logarithmic regret. Indeed, [Foster et al., 2018] showed that the lower bound does not apply to improper algorithms and proposed a strategy based on exponential weights with prohibitive computational complexity. Our new algorithm based on regularized empirical risk minimization with surrogate losses satisfies a regret scaling as O(B log(Bn)) with a per-round time-complexity of order O(d^2).
• Abstract（参考訳）: オンラインロジスティック回帰(英語版)(オンラインロジスティック回帰)の設定を考えると、半径 b の2次元球面に関する後悔を考える。 (hazan et al., 2014]) 標本数に対数的後悔を持つ任意の固有アルゴリズムは、必ず b の指数的乗算定数を被っていることが知られている。本研究では、この指数的定数を避けながら対数的後悔を保ちながら、効率的な不適切なアルゴリズムを設計する。 実際、[Foster et al., 2018] は、下限が不適切なアルゴリズムには適用されないことを示した。 本アルゴリズムは,o(b log(bn)) のオーダー o(d^2) の時間複雑度を満足するサロゲート損失を伴う正規化経験的リスク最小化に基づく。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• A Constrained BA Algorithm for Rate-Distortion and Distortion-Rate Functions [13.570794979535934]
  速度歪み関数に対するBlahut-Arimoto (BA)アルゴリズムの修正 修正アルゴリズムは、与えられた対象歪みに対してRD関数を直接計算する。
  論文  参考訳（メタデータ） (2023-05-04T08:41:03Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。 一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
  論文  参考訳（メタデータ） (2022-05-25T21:31:36Z)
• Mixability made efficient: Fast online multiclass logistic regression [68.8204255655161]
  我々は、混合性は最適な後悔を伴うアルゴリズムを得るための強力なツールであることを示した。 結果として得られる手法は、しばしば計算の複雑さに悩まされ、実用性が低下した。
  論文  参考訳（メタデータ） (2021-10-08T08:22:05Z)
• Screening for Sparse Online Learning [11.523471275501855]
  スパーシティ促進レギュラライザーは、低複素構造(例えば)を課すために広く使用されている。 l1-norm for sparsity) 教師付き学習の回帰係数に対する。 ほとんどのオンラインアルゴリズムは、ステップサイズと非消去の分散のためにプロパティを持っていません。 本稿では,オンラインアルゴリズムが生成するイテレートの不要な特徴を解消する方法を示し,有限なアクティビティ同定を強制する。
  論文  参考訳（メタデータ） (2021-01-18T10:40:47Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)
• Bandit algorithms: Letting go of logarithmic regret for statistical robustness [0.0]
  我々は,多武器の盗賊設定における後悔について研究し,アルゴリズムによる後悔と統計的堅牢性の間に基本的なトレードオフを確立する。 対数的後悔を伴う帯域学習アルゴリズムは常に矛盾しており、一貫した学習アルゴリズムは常に超対数的後悔に苦しむことを示す。
  論文  参考訳（メタデータ） (2020-06-22T07:18:47Z)

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

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