論文の概要: 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}$の既知の速度を任意に高速化するカーネルリッジ回帰を,問題の硬さを特徴付けるパラメータによって検討し,スムーズな仮定の下で,次元性の呪いを回避できるようにする。

関連論文リスト

• A Statistical Theory of Regularization-Based Continual Learning [10.899175512941053]
  線形回帰タスクの順序に基づく正規化に基づく連続学習の統計的解析を行う。 まず、全てのデータが同時に利用可能であるかのように得られたオラクル推定器の収束率を導出する。 理論解析の副産物は、早期停止と一般化された$ell$-regularizationの等価性である。
  論文  参考訳（メタデータ） (2024-06-10T12:25:13Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。 本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
  論文  参考訳（メタデータ） (2024-04-03T00:41:19Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds [12.699376765058137]
  勾配降下法(SGD)は、おそらく現代の機械学習において最も一般的な最適化法である。 SGDを交換せずにサンプリングするSGDが分析されたのはごく最近のことだ。 データマトリックスに依存し、既存の境界によって予測されるものよりも決して悪くない、きめ細かい複雑性境界を証明します。
  論文  参考訳（メタデータ） (2023-06-21T18:14:44Z)
• Instance-Dependent Generalization Bounds via Optimal Transport [51.71650746285469]
  既存の一般化境界は、現代のニューラルネットワークの一般化を促進する重要な要因を説明することができない。 データ空間における学習予測関数の局所リプシッツ正則性に依存するインスタンス依存の一般化境界を導出する。 ニューラルネットワークに対する一般化境界を実験的に解析し、有界値が有意義であることを示し、トレーニング中の一般的な正規化方法の効果を捉える。
  論文  参考訳（メタデータ） (2022-11-02T16:39:42Z)
• A Primal-Dual Approach to Solving Variational Inequalities with General Constraints [54.62996442406718]
  Yang et al. (2023) は最近、一般的な変分不等式を解決するために一階勾配法を使う方法を示した。 この方法の収束性を証明し、演算子が$L$-Lipschitz と monotone である場合、この手法の最後の繰り返しのギャップ関数が$O(frac1sqrtK)$で減少することを示す。
  論文  参考訳（メタデータ） (2022-10-27T17:59:09Z)
• 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)
• Fast Rates for the Regret of Offline Reinforcement Learning [69.23654172273085]
  無限水平割引決定プロセス(MDP)における固定行動ポリシーによって生成されたオフラインデータからの強化学習の後悔について検討する。 最適品質関数 $Q*$ に対する任意の推定が与えられたとき、定義するポリシーの後悔は、$Q*$-estimate の点収束率の指数によって与えられる速度で収束することを示す。
  論文  参考訳（メタデータ） (2021-01-31T16:17:56Z)

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

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