論文の概要: Super fast rates in structured prediction

• arxiv url: http://arxiv.org/abs/2102.00760v1
• Date: Mon, 1 Feb 2021 10:50:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-03 07:00:59.583050
• Title: Super fast rates in structured prediction
• Title（参考訳）: 構造予測における超高速速度
• Authors: Vivien Cabannes and Alessandro Rudi and Francis Bach
• Abstract要約: 連続的な問題が連続的な値を予測しているときに、離散的な問題が本質的に離散的なアウトプットを予測しているという事実を活用する方法を示す。 まず、近接する隣人に基づく予測器について説明し、二項分類で知られている確率を、構造的予測の枠組み内の任意の離散問題に一般化する。 次に、カーネルリッジの回帰について検討し、問題の硬さを特徴付けるパラメータによって、n-1/4$の既知のレートを任意に高速化する。
• 参考スコア（独自算出の注目度）: 88.99819200562784
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Discrete supervised learning problems such as classification are often tackled by introducing a continuous surrogate problem akin to regression. Bounding the original error, between estimate and solution, by the surrogate error endows discrete problems with convergence rates already shown for continuous instances. Yet, current approaches do not leverage the fact that discrete problems are essentially predicting a discrete output when continuous problems are predicting a continuous value. In this paper, we tackle this issue for general structured prediction problems, opening the way to "super fast" rates, that is, convergence rates for the excess risk faster than $n^{-1}$, where $n$ is the number of observations, with even exponential rates with the strongest assumptions. We first illustrate it for predictors based on nearest neighbors, generalizing rates known for binary classification to any discrete problem within the framework of structured prediction. We then consider kernel ridge regression where we improve known rates in $n^{-1/4}$ to arbitrarily fast rates, depending on a parameter characterizing the hardness of the problem, thus allowing, under smoothness assumptions, to bypass the curse of dimensionality.
• Abstract（参考訳）: 分類のような離散的教師付き学習問題は、回帰に類似した連続的な代理問題を導入することでしばしば取り組まれる。 サロゲート誤差による推定と解の間の元の誤差の境界は、連続インスタンスに対して既に示されている収束率で離散的な問題を内包する。 しかし、現在のアプローチでは、連続的な問題が連続的な値を予測するとき、離散的な問題は本質的に離散的な出力を予測しているという事実を活用できない。 本稿では、一般的な構造化された予測問題についてこの問題に取り組み、過度のリスクに対する収束率が$n^{-1}$よりも速く、$n$が観測数であり、最も強い仮定で指数関数的なレートも含む「超高速」率への道を開く。 まず,近接近傍に基づく予測器について説明を行い,構造化予測の枠組み内の任意の離散問題に対してバイナリ分類で知られている確率を一般化する。 次に,n^{-1/4}$の既知の速度を任意に高速化するカーネルリッジ回帰を,問題の硬さを特徴付けるパラメータによって検討し,スムーズな仮定の下で,次元性の呪いを回避できるようにする。

関連論文リスト

• On the tightness of information-theoretic bounds on generalization error of learning algorithms [5.081241420920605]
  まず、平方根が必ずしもスローレートを含まないことを示し、この境界を用いて高速な速度結果が得られることを示す。 高速一般化誤差に必要な臨界条件を同定し,$(eta,c)$-central条件と呼ぶ。
  論文  参考訳（メタデータ） (2023-03-26T08:59:05Z)
• Boosting the Confidence of Generalization for $L_2$-Stable Randomized Learning Algorithms [41.082982732100696]
  適切に設計されたサブバッグプロセスは、データとアルゴリズムの両方にほぼ28の指数関数的一般化バウンダリをもたらすことを示す。 さらに、自然減衰学習率を持つ凸問題や非重み付き問題に対する高確率一般化境界を改善するために、総合的な結果を導出する。
  論文  参考訳（メタデータ） (2022-06-08T12:14:01Z)
• Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence [69.65563161962245]
  ニュートン法を用いて,滑らかで強凸な目的関数を考える。 最適段階において局所収束に遷移する普遍重み付き平均化スキームが存在することを示す。
  論文  参考訳（メタデータ） (2022-04-20T07:14:21Z)
• Benign Underfitting of Stochastic Gradient Descent [72.38051710389732]
  本研究では,適切な学習データを得ることで,一般化性能を実現する「従来型」学習ルールとして,勾配降下度(SGD)がどの程度理解されるかを検討する。 類似現象が起こらない近縁な交換SGDを解析し、その集団リスクが実際に最適な速度で収束することを証明する。
  論文  参考訳（メタデータ） (2022-02-27T13:25:01Z)
• Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification [16.0817847880416]
  ヒルベルト空間上の様々な線形予測問題を含む統一的なフレームワークを提供する。 誤特定レベル $epsilon$ に対して、これらの推定器は、文献で最もよく知られたレートと一致する、$O(maxleft|mathcalO|1/2n-1/2, |mathcalI|1/2n-1 right+epsilon)$ の誤差率を達成する。
  論文  参考訳（メタデータ） (2022-01-06T08:51:08Z)
• SLOE: A Faster Method for Statistical Inference in High-Dimensional Logistic Regression [68.66245730450915]
  実用データセットに対する予測の偏見を回避し、頻繁な不確実性を推定する改善された手法を開発している。 私たちの主な貢献は、推定と推論の計算時間をマグニチュードの順序で短縮する収束保証付き信号強度の推定器SLOEです。
  論文  参考訳（メタデータ） (2021-03-23T17:48:56Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  帰納バイアスは 経験的に過剰フィットを防げる中心的存在です この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。 我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
  論文  参考訳（メタデータ） (2021-03-23T17:15:53Z)
• Fast Rates for the Regret of Offline Reinforcement Learning [82.49300293077583]
  無限水平割引マルコフ決定過程(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)
• Estimating means of bounded random variables by betting [39.98103047898974]
  本稿では、境界観測から未知の平均を推定する古典的な問題に対して、信頼区間(CI)と時間一様信頼シーケンス(CS)を導出する。 本稿では,Chernoff法を一般化し改良したものと考えられる濃度境界を導出する一般手法を提案する。 我々は、これらのアイデアを、置換せずにサンプリングに拡張する方法を示し、また、非常に研究された問題である。
  論文  参考訳（メタデータ） (2020-10-19T17:22:03Z)

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

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