論文の概要: Tractability from overparametrization: The example of the negative
perceptron
- arxiv url: http://arxiv.org/abs/2110.15824v1
- Date: Thu, 28 Oct 2021 01:00:13 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-01 15:32:25.416809
- Title: Tractability from overparametrization: The example of the negative
perceptron
- Title（参考訳）: 過パラメータ化からの導出性:負のパーセプトロンの例
- Authors: Andrea Montanari, Yiqiao Zhong, Kangjie Zhou
- Abstract要約: 我々は線形プログラミングアルゴリズムを解析し、対応するしきい値である$delta_textlin(kappa)$を特徴付ける。
閾値$delta_textlin(kappa)$間のギャップを観察し、他のアルゴリズムの振る舞いに関する疑問を提起する。
- 参考スコア（独自算出の注目度）: 13.299431908881425
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the negative perceptron problem we are given $n$ data points
$({\boldsymbol x}_i,y_i)$, where ${\boldsymbol x}_i$ is a $d$-dimensional
vector and $y_i\in\{+1,-1\}$ is a binary label. The data are not linearly
separable and hence we content ourselves to find a linear classifier with the
largest possible \emph{negative} margin. In other words, we want to find a unit
norm vector ${\boldsymbol \theta}$ that maximizes $\min_{i\le n}y_i\langle
{\boldsymbol \theta},{\boldsymbol x}_i\rangle$. This is a non-convex
optimization problem (it is equivalent to finding a maximum norm vector in a
polytope), and we study its typical properties under two random models for the
data.
We consider the proportional asymptotics in which $n,d\to \infty$ with
$n/d\to\delta$, and prove upper and lower bounds on the maximum margin
$\kappa_{\text{s}}(\delta)$ or -- equivalently -- on its inverse function
$\delta_{\text{s}}(\kappa)$. In other words, $\delta_{\text{s}}(\kappa)$ is the
overparametrization threshold: for $n/d\le
\delta_{\text{s}}(\kappa)-\varepsilon$ a classifier achieving vanishing
training error exists with high probability, while for $n/d\ge
\delta_{\text{s}}(\kappa)+\varepsilon$ it does not. Our bounds on
$\delta_{\text{s}}(\kappa)$ match to the leading order as $\kappa\to -\infty$.
We then analyze a linear programming algorithm to find a solution, and
characterize the corresponding threshold $\delta_{\text{lin}}(\kappa)$. We
observe a gap between the interpolation threshold $\delta_{\text{s}}(\kappa)$
and the linear programming threshold $\delta_{\text{lin}}(\kappa)$, raising the
question of the behavior of other algorithms.
- Abstract（参考訳）: 負のパーセプトロン問題では、$n$ data points $({\boldsymbol x}_i,y_i)$、ただし${\boldsymbol x}_i$は$d$-dimensional vector、$y_i\in\{+1,-1\}$はバイナリラベルである。
データは線形分離可能ではなく、従って、最大の可能な 'emph{ negative} マージンを持つ線形分類器を見つけるのに満足する。
言い換えれば、単位ノルムベクトル ${\boldsymbol \theta}$ を見つけて、$\min_{i\le n}y_i\langle {\boldsymbol \theta},{\boldsymbol x}_i\rangle$ を最大化する。
これは非凸最適化問題(ポリトープ内の最大ノルムベクトルを見つけるのと同値)であり、データに対する2つのランダムモデルの下でその典型的な性質を調べる。
我々は、$n,d\to \infty$と$n/d\to\delta$の比例漸近を考慮し、その逆関数 $\delta_{\text{s}}(\kappa)$ の最大辺 $\kappa_{\text{s}}(\delta)$ あるいは -- 等価に) の上と下の境界を証明している。
言い換えると、$\delta_{\text{s}}(\kappa)$はオーバーパラメトリゼーションしきい値である: for $n/d\le \delta_{\text{s}}(\kappa)-\varepsilon$ a classifier 消滅するトレーニングエラーを達成することは高い確率で存在し、$n/d\ge \delta_{\text{s}}(\kappa)+\varepsilon$はそうではない。
我々の$\delta_{\text{s}}(\kappa)$は、先頭の順序に$\kappa\to -\infty$と一致します。
次に線形計画アルゴリズムを解析して解を見つけ、対応するしきい値 $\delta_{\text{lin}}(\kappa)$ を特徴付ける。
我々は補間しきい値 $\delta_{\text{s}}(\kappa)$ と線形計画しきい値 $\delta_{\text{lin}}(\kappa)$ の間のギャップを観察し、他のアルゴリズムの振る舞いの問題を提起する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳（メタデータ） (2023-07-11T08:51:53Z) - A spectral least-squares-type method for heavy-tailed corrupted
regression with unknown covariance \& heterogeneous noise [2.019622939313173]
重み付き最小二乗線形回帰は、少なくとも$epsilon n$ arbitrary outliersの$n$のラベル特徴サンプルを破損させたと仮定して再検討する。
本稿では,$(Sigma,Xi) や $Xi$ の演算ノルムに関する知識を前提に,電力法に基づくほぼ最適に計算可能な推定器を提案する。
論文 参考訳（メタデータ） (2022-09-06T23:37:31Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Self-training Converts Weak Learners to Strong Learners in Mixture
Models [86.7137362125503]
擬似ラベルの $boldsymbolbeta_mathrmpl$ が,最大$C_mathrmerr$ の分類誤差を達成可能であることを示す。
さらに、ロジスティックな損失に対して勾配降下を実行することで、ラベル付き例のみを使用して、分類誤差が$C_mathrmerr$で擬ラベルの $boldsymbolbeta_mathrmpl$ が得られることを示す。
論文 参考訳（メタデータ） (2021-06-25T17:59:16Z) - Infinite-Horizon Offline Reinforcement Learning with Linear Function
Approximation: Curse of Dimensionality and Algorithm [46.36534144138337]
本稿では,オフライン強化学習におけるポリシー評価のサンプル複雑さについて検討する。
低分布シフトの仮定の下では、最大$oleft(maxleft fracleftvert thetapirightvert _24varepsilon4logfracddelta,frac1varepsilon2left(d+logfrac1deltaright)right right)$サンプルを必要とするアルゴリズムがあることを示す。
論文 参考訳（メタデータ） (2021-03-17T18:18:57Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳（メタデータ） (2020-08-15T11:06:45Z) - Fast Differentiable Clipping-Aware Normalization and Rescaling [22.320256458354137]
最適再スケーリングは高速かつ微分可能なアルゴリズムを用いて解析的に見つけることができることを示す。
我々のアルゴリズムは任意のp-ノルムに対して有効であり、摂動に正規化された入力でニューラルネットワークを訓練するのに使うことができる。
論文 参考訳（メタデータ） (2020-07-15T13:43:22Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。