論文の概要: Omnipredictors for Regression and the Approximate Rank of Convex Functions

• arxiv url: http://arxiv.org/abs/2401.14645v1
• Date: Fri, 26 Jan 2024 04:29:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-29 15:49:36.810848
• Title: Omnipredictors for Regression and the Approximate Rank of Convex Functions
• Title（参考訳）: 回帰に関する大域的予測と凸関数の近似ランク
• Authors: Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, Mihir Singhal
• Abstract要約: クラス $mathcal L$ の損失関数とクラス $mathcal C$ の損失予測器は、$mathcal L$ の損失毎に $mathcal C$ の最良の仮説よりも予想される損失が少ない予測器である。
• 参考スコア（独自算出の注目度）: 7.549720420141907
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Consider the supervised learning setting where the goal is to learn to predict labels $\mathbf y$ given points $\mathbf x$ from a distribution. An \textit{omnipredictor} for a class $\mathcal L$ of loss functions and a class $\mathcal C$ of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in $\mathcal C$ for every loss in $\mathcal L$. Since the work of [GKR+21] that introduced the notion, there has been a large body of work in the setting of binary labels where $\mathbf y \in \{0, 1\}$, but much less is known about the regression setting where $\mathbf y \in [0,1]$ can be continuous. Our main conceptual contribution is the notion of \textit{sufficient statistics} for loss minimization over a family of loss functions: these are a set of statistics about a distribution such that knowing them allows one to take actions that minimize the expected loss for any loss in the family. The notion of sufficient statistics relates directly to the approximate rank of the family of loss functions. Our key technical contribution is a bound of $O(1/\varepsilon^{2/3})$ on the $\epsilon$-approximate rank of convex, Lipschitz functions on the interval $[0,1]$, which we show is tight up to a factor of $\mathrm{polylog} (1/\epsilon)$. This yields improved runtimes for learning omnipredictors for the class of all convex, Lipschitz loss functions under weak learnability assumptions about the class $\mathcal C$. We also give efficient omnipredictors when the loss families have low-degree polynomial approximations, or arise from generalized linear models (GLMs). This translation from sufficient statistics to faster omnipredictors is made possible by lifting the technique of loss outcome indistinguishability introduced by [GKH+23] for Boolean labels to the regression setting.
• Abstract（参考訳）: 分布から$\mathbf y$ 与えられた点 $\mathbf x$ を予測することを目標とする教師付き学習集合を考える。 損失関数のクラス $\mathcal L$ と、損失関数のクラス $\mathcal C$ に対する \textit{omnipredictor} は、予想される損失が $\mathcal L$ のすべての損失に対する $\mathcal C$ の最良の仮説よりも少ない予測子である。 この概念を導入した [gkr+21] の仕事以来、$\mathbf y \in \{0, 1\}$ というバイナリラベルの設定には多くの作業があったが、$\mathbf y \in [0,1]$ が連続であるような回帰設定についてはあまり知られていない。 我々の主要な概念的貢献は、損失関数の族に対する損失最小化のための「textit{sufficient statistics}」の概念である。 十分統計量の概念は、損失函数の族(英語版)の近似階数に直接関係している。 我々の主要な技術的貢献は、$O(1/\varepsilon^{2/3})$の値で、$\epsilon$-approximate rank of convex, Lipschitz function on the interval $[0,1]$, which show is tight up to a factor of $\mathrm{polylog} (1/\epsilon)$である。 これにより、すべての凸、リプシッツ損失関数のクラスに対して、$\mathcal C$に関する弱い可学習性仮定の下でのオムニプレクタ学習のランタイムが向上する。 また、損失族が低次多項式近似を持つとき、あるいは一般化線形モデル(glms)から生じるとき、効率的な全量予測子を与える。 ブールラベルの[gkh+23]による損失結果の識別可能性の技術を回帰設定へ持ち上げることにより、十分な統計量からより高速な全量予測器への変換が可能となる。

関連論文リスト

• Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation for the Square Loss [33.18537822803389]
  L2$ と $Psi_p$ の位相が我々の仮説クラス $mathscrF$, $mathscrF$ に同値であるときにいつでも、$mathscrF$ は弱準ガウス類であることを示す。 以上の結果から, 混合への直接的な依存は高次項に還元されるため, この問題は実現可能か否かを判断できる。
  論文  参考訳（メタデータ） (2024-02-08T18:57:42Z)
• Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
  我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。 スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。 また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
  論文  参考訳（メタデータ） (2023-04-05T07:24:19Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [43.0867217287089]
  ガウス分布の下で半空間を不可知的に学習する作業について検討する。 この課題に対して,ほぼ最適計算硬度を証明した。
  論文  参考訳（メタデータ） (2023-02-13T16:46:23Z)
• LegendreTron: Uprising Proper Multiclass Loss Learning [22.567234503869845]
  損失関数は教師付き学習の基盤として機能し、しばしばモデル開発の前に選択される。 最近の研究は、損失とモデルを共同で引き起こそうとしている。 sc LegendreTron は,多クラス問題に対するアンフォプロペラの正準損失と確率を共同で学習する,新規かつ実用的な方法である。
  論文  参考訳（メタデータ） (2023-01-27T13:10:45Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。 学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
  論文  参考訳（メタデータ） (2022-06-17T17:55:43Z)
• Omnipredictors [19.735769148626588]
  ロス最小化は機械学習において支配的なパラダイムである。 我々は家族の損失を最適化するために使用できる$mathcalL,mathcalC$)-omnipredictorの概念を紹介した。 このような「余分な知識」の学習は、多重校正とのつながりを通して実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-09-11T23:28:49Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
  我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。 最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
  論文  参考訳（メタデータ） (2020-03-04T07:36:38Z)

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

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