論文の概要: 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補間のための「良性過剰フィッティング」に関する文献を補完するものであり、その特徴が効果的に低次元である場合にのみ漸近的一貫性を達成することができる。
関連論文リスト
- 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 [77.8485863487028]
本稿では、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) - Private optimization in the interpolation regime: faster rates and
hardness results [9.405458160620533]
プライベートでない凸最適化では、勾配法は非補間法よりも、全てのサンプル損失を同時に最小化する解が存在するという問題にはるかに早く収束する。
プライベートサンプルの複雑さは指数関数的に改善した(近辺)。
論文 参考訳(メタデータ) (2022-10-31T05:18:27Z) - 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) - Optimal and instance-dependent guarantees for Markovian linear
stochastic approximation [77.84027086542827]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳(メタデータ) (2021-12-23T18:47:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。