論文の概要: Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization

• arxiv url: http://arxiv.org/abs/2412.04274v1
• Date: Thu, 05 Dec 2024 15:56:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-06 14:39:57.462011
• Title: Complexity of Vector-valued Prediction: From Linear Models to Stochastic Convex Optimization
• Title（参考訳）: ベクトル値予測の複雑さ:線形モデルから確率凸最適化へ
• Authors: Matan Schliserman, Tomer Koren,
• Abstract要約: 凸とリプシッツ損失関数の基本的な場合に焦点を当てる。 本稿では,この問題の複雑さと関連する学習モデルとの関連性に光を当てた,いくつかの新たな理論的結果を示す。 結果は,ベクトル値線形予測の設定を,広範に研究されている2つの異なる学習モデル間のブリッジングとして表現した。
• 参考スコア（独自算出の注目度）: 27.33243506775655
• License:
• Abstract: We study the problem of learning vector-valued linear predictors: these are prediction rules parameterized by a matrix that maps an $m$-dimensional feature vector to a $k$-dimensional target. We focus on the fundamental case with a convex and Lipschitz loss function, and show several new theoretical results that shed light on the complexity of this problem and its connection to related learning models. First, we give a tight characterization of the sample complexity of Empirical Risk Minimization (ERM) in this setting, establishing that $\smash{\widetilde{\Omega}}(k/\epsilon^2)$ examples are necessary for ERM to reach $\epsilon$ excess (population) risk; this provides for an exponential improvement over recent results by Magen and Shamir (2023) in terms of the dependence on the target dimension $k$, and matches a classical upper bound due to Maurer (2016). Second, we present a black-box conversion from general $d$-dimensional Stochastic Convex Optimization (SCO) to vector-valued linear prediction, showing that any SCO problem can be embedded as a prediction problem with $k=\Theta(d)$ outputs. These results portray the setting of vector-valued linear prediction as bridging between two extensively studied yet disparate learning models: linear models (corresponds to $k=1$) and general $d$-dimensional SCO (with $k=\Theta(d)$).
• Abstract（参考訳）: 本稿では,ベクトル値線形予測器の学習問題について考察する。これらは,$m$次元特徴ベクトルを$k$次元ターゲットにマッピングする行列によってパラメータ化される予測規則である。 我々は凸とリプシッツ損失関数の基本的なケースに注目し、この問題の複雑さと関連する学習モデルとの関係に光を当てる新しい理論的結果をいくつか示す。 まず、経験的リスク最小化(ERM)のサンプル複雑性をこの設定で厳密に評価し、例えば$\smash{\widetilde{\Omega}}(k/\epsilon^2)$例は、ERMが$\epsilon$過剰(人口)リスクに達するために必要であることを示す。 第二に、一般的な$d$次元確率凸最適化(SCO)からベクトル値線形予測へのブラックボックス変換を行い、任意のSCO問題を$k=\Theta(d)$出力で予測問題として埋め込むことができることを示す。 これらの結果から、ベクトル値線形予測は、線形モデル($k=1$に対応する)と一般的な$d$次元SCO($k=\Theta(d)$)の2つの広く研究されている異なる学習モデルの間のブリッジングとして表現される。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  我々は,モンテカルロサンプリングと反復線形解法を組み合わせた確率的アンローリングを導入し,行列逆転を回避した。 理論的解析により,解法の繰り返しによる解法の解法と逆転が最大値推定の勾配推定を高速化することを示した。 シミュレーションおよび実データ実験において、確率的アンロールは、モデル性能の損失を最小限に抑えながら、勾配EMよりも桁違いに高速な潜在ガウスモデルを学習することを示した。
  論文  参考訳（メタデータ） (2023-06-05T21:08:34Z)
• Restricted Strong Convexity of Deep Learning Models with Smooth Activations [31.003601717265006]
  本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。 Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。 深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
  論文  参考訳（メタデータ） (2022-09-29T21:24:26Z)
• KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal [70.15267479220691]
  モデル強化学習のサンプル複雑性を,生成的分散自由モデルを用いて検討・解析する。 我々の分析は、$varepsilon$が十分小さい場合、$varepsilon$-optimal Policyを見つけるのが、ほぼ最小の最適化であることを示している。
  論文  参考訳（メタデータ） (2022-05-27T19:39:24Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• A Precise Performance Analysis of Support Vector Regression [105.94855998235232]
  我々は,n$の線形測定に応用したハードおよびソフトサポートベクター回帰法について検討した。 得られた結果は、ハードおよびソフトサポートベクトル回帰アルゴリズムの設計に介入するパラメータを最適に調整するために使用される。
  論文  参考訳（メタデータ） (2021-05-21T14:26:28Z)
• Estimating Stochastic Linear Combination of Non-linear Regressions Efficiently and Scalably [23.372021234032363]
  サブサンプルサイズが大きくなると、推定誤差が過度に犠牲になることを示す。 私たちの知る限りでは、線形テキスト+確率モデルが保証される最初の研究です。
  論文  参考訳（メタデータ） (2020-10-19T07:15:38Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Asymptotic errors for convex penalized linear regression beyond Gaussian matrices [23.15629681360836]
  雑音線形観測から係数ベクトル$x_0$ in$RN$を学習する問題を考察する。 平均二乗誤差に対する明示的な式を厳密に導出する。 我々の予測は、非常に適度なサイズであっても、数値と非常によく一致していることを示す。
  論文  参考訳（メタデータ） (2020-02-11T13:43:32Z)
• Mixture model for designs in high dimensional regression and the LASSO [0.0]
  LASSOは、回帰モデル bean y & = & Xbeta + z, eean における変数選択の技法である。 本稿では,カラムの潜在的クラスタ化の性質を自然な方法で捉えることができる設計行列の混合モデルを提案する。
  論文  参考訳（メタデータ） (2012-10-17T15:10:39Z)

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

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