論文の概要: Exploiting the Surrogate Gap in Online Multiclass Classification

• arxiv url: http://arxiv.org/abs/2007.12618v2
• Date: Fri, 26 Feb 2021 11:51:23 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-07 06:33:10.919024
• Title: Exploiting the Surrogate Gap in Online Multiclass Classification
• Title（参考訳）: オンラインマルチクラス分類におけるサロゲートギャップの活用
• Authors: Dirk van der Hoeven
• Abstract要約: Gaptronは、オンラインのマルチクラス分類のためのランダム化された一階述語アルゴリズムである。 その結果,ロジスティックな損失,ヒンジの損失,スムーズなヒンジの損失に対して,常に後悔する結果が得られた。 ゼロワン損失とサロゲート損失のギャップを利用した新しい証明手法を提案する。
• 参考スコア（独自算出の注目度）: 13.452510519858995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present Gaptron, a randomized first-order algorithm for online multiclass classification. In the full information setting we show expected mistake bounds with respect to the logistic loss, hinge loss, and the smooth hinge loss with constant regret, where the expectation is with respect to the learner's randomness. In the bandit classification setting we show that Gaptron is the first linear time algorithm with $O(K\sqrt{T})$ expected regret, where $K$ is the number of classes. Additionally, the expected mistake bound of Gaptron does not depend on the dimension of the feature vector, contrary to previous algorithms with $O(K\sqrt{T})$ regret in the bandit classification setting. We present a new proof technique that exploits the gap between the zero-one loss and surrogate losses rather than exploiting properties such as exp-concavity or mixability, which are traditionally used to prove logarithmic or constant regret bounds.
• Abstract（参考訳）: オンライン多クラス分類のためのランダム化1次アルゴリズムであるGaptronを提案する。 完全な情報設定では,学習者のランダム性に対する期待値であるロジスティックな損失,ヒンジの損失,スムーズなヒンジの損失に対して,期待される誤り境界を示す。 バンドート分類設定では、gaptron は$o(k\sqrt{t})$ の期待後悔を持つ最初の線形時間アルゴリズムであり、ここで $k$ はクラスの数である。 さらに、gaptron の期待された誤り境界は特徴ベクトルの次元に依存しないが、以前のアルゴリズムではバンドイット分類設定に $o(k\sqrt{t})$ regret がある。 本稿では,従来,対数的あるいは一定残差の証明に用いられてきたexp-concavityやmixabilityといった特性を活用するのではなく,ゼロワン損失とサロゲート損失のギャップを利用する新しい証明手法を提案する。

関連論文リスト

• The Real Price of Bandit Information in Multiclass Classification [73.17969992976501]
  バンディットフィードバックを用いた複数クラス分類の古典的問題を再考する。 我々は, 後悔すべき$smashwidetildeO(|H|+sqrtT)$を保証する新しい帯域分類アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-16T12:11:09Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss [25.50155563108198]
  フルインフォメーションフィードバックを用いたオンライン構造化予測について検討する。 我々はエクスプロイト・ザ・サロゲート・ギャップ・フレームワークをemphFenchelによるオンライン構造化予測に拡張する。
  論文  参考訳（メタデータ） (2024-02-13T02:36:41Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Beyond Bandit Feedback in Online Multiclass Classification [17.07011090727996]
  学習者のフィードバックが任意の有向グラフによって決定されるような環境で,オンライン多クラス分類の問題について検討する。 任意のフィードバックグラフで動作する,初のオンラインマルチクラスアルゴリズムであるGappletronを紹介する。
  論文  参考訳（メタデータ） (2021-06-07T13:22:30Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• A Regret bound for Non-stationary Multi-Armed Bandits with Fairness Constraints [7.716156977428555]
  我々は,緩やかに変化する$k$-armed bandit問題を解くために,fair upper confidenceと呼ばれる新しいアルゴリズムとexploring fair-ucbeを提案する。 非定常ケースにおけるアルゴリズムの性能は,その定常ケースに近づくとゼロになりがちであることを示す。
  論文  参考訳（メタデータ） (2020-12-24T18:12:01Z)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
  論文  参考訳（メタデータ） (2020-06-10T01:59:34Z)

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

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