Fugu-MT 論文翻訳(概要): Tight bounds for minimum l1-norm interpolation of noisy data

論文の概要: Tight bounds for minimum l1-norm interpolation of noisy data

arxiv url: http://arxiv.org/abs/2111.05987v1
Date: Wed, 10 Nov 2021 23:30:47 GMT
ステータス: 処理完了
システム内更新日: 2021-11-12 14:08:45.481335
Title: Tight bounds for minimum l1-norm interpolation of noisy data
Title（参考訳）: 雑音データの最小l1ノルム補間のためのタイト境界
Authors: Guillaume Wang, Konstantin Donhauser, Fanny Yang
Abstract要約: 我々は、等方的特徴とスパース基底真理に対するノイズ最小ノルムフィッティングの一貫性を示唆する。我々の研究は、最小$ell$-normの「良性オーバーフィッティング」に関する文献を補完します。
参考スコア（独自算出の注目度）: 8.508198765617196
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We provide matching upper and lower bounds of order $\sigma^2/\log(d/n)$ for the prediction error of the minimum $\ell_1$-norm interpolator, a.k.a. basis pursuit. Our result is tight up to negligible terms when $d \gg n$, and is the first to imply asymptotic consistency of noisy minimum-norm interpolation for isotropic features and sparse ground truths. Our work complements the literature on "benign overfitting" for minimum $\ell_2$-norm interpolation, where asymptotic consistency can be achieved only when the features are effectively low-dimensional.
Abstract（参考訳）: 最小の$\ell_1$-norm補間器の予測誤差に対して、位数 $\sigma^2/\log(d/n)$ の上限と下限を一致させる。我々の結果は、$d \gg n$ のときに無視できない項に密着しており、等方的特徴とスパース基底真理に対するノイズの最小ノルム補間の漸近的一貫性を暗示する最初の例である。我々の研究は、少なくとも$\ell_2$-norm補間のための「良性過剰フィッティング」に関する文献を補完するものであり、その特徴が効果的に低次元である場合にのみ漸近的一貫性を達成することができる。

関連論文リスト

Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
固定学習率$eta$の勾配降下はスムーズな関数を表す局所最小値しか見つからないことを示す。また、$n$のデータポイントのサポートの厳密な内部で、$widetildeO(n-4/5)$のほぼ最適MSE境界を証明します。
論文参考訳（メタデータ） (2024-06-10T22:57:27Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文参考訳（メタデータ） (2023-01-10T20:43:29Z)
Tight bounds for maximum $\ell_1$-margin classifiers [10.055143995729415]
適応性は、標準的な識別的設定に対する最大$ell_$-margin分類器には適用されないことを示す。ノイズを補間すると、誤差は次数$frac1sqrtlog(d/n)$で消滅する。
論文参考訳（メタデータ） (2022-12-07T17:05:31Z)
Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文参考訳（メタデータ） (2022-09-30T04:15:44Z)
Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文参考訳（メタデータ） (2022-08-11T04:12:50Z)
Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
論文参考訳（メタデータ） (2022-06-17T06:10:20Z)
A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文参考訳（メタデータ） (2022-02-23T16:10:23Z)
Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文参考訳（メタデータ） (2020-10-16T08:10:02Z)
Escaping Saddle-Points Faster under Interpolation-like Conditions [19.9471360853892]
過度なパラメータ化の下では、いくつかの標準的な最適化アルゴリズムがサドルポイントを回避し、局所最小化器に収束する。本稿では、PSGDアルゴリズムの1次オラクル複雑性について論じ、$epsilon$ localminimizerに到達した。次に、Cubic-Regularized Newton (SCRN)アルゴリズムのアンダーライクな条件を分析し、局所最小化剤アンダーライクな条件に到達するためのオラクルの複雑さが$tildemathcalO (1/epsilon2.5)であることを示す。
論文参考訳（メタデータ） (2020-09-28T02:15:18Z)
On Uniform Convergence and Low-Norm Interpolation Learning [25.96459928769678]
経験的誤差と人口的誤差の差を均一に有界に表すことは,標準球における学習を全く示さないことを示す。我々は、最小限のノルム補間器の整合性は、わずかに弱いが標準的概念、つまり標準球におけるゼロエラー予測器の一様収束で説明できると主張している。
論文参考訳（メタデータ） (2020-06-10T16:49:28Z)

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