論文の概要: Robust learning of halfspaces under log-concave marginals
- arxiv url: http://arxiv.org/abs/2505.13708v1
- Date: Mon, 19 May 2025 20:12:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-21 14:49:52.513033
- Title: Robust learning of halfspaces under log-concave marginals
- Title（参考訳）: 対数圏境界の下でのハーフ空間のロバスト学習
- Authors: Jane Lange, Arsen Vasilyan,
- Abstract要約: 線形しきい値関数を学習し、境界体積$O(r+varepsilon)$の分類子を半径摂動$r$で返すアルゴリズムを与える。
dtildeO(1/varepsilon2)$の時間とサンプルの複雑さはブール回帰の複雑さと一致する。
- 参考スコア（独自算出の注目度）: 6.852292115526837
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We say that a classifier is \emph{adversarially robust} to perturbations of norm $r$ if, with high probability over a point $x$ drawn from the input distribution, there is no point within distance $\le r$ from $x$ that is classified differently. The \emph{boundary volume} is the probability that a point falls within distance $r$ of a point with a different label. This work studies the task of computationally efficient learning of hypotheses with small boundary volume, where the input is distributed as a subgaussian isotropic log-concave distribution over $\mathbb{R}^d$. Linear threshold functions are adversarially robust; they have boundary volume proportional to $r$. Such concept classes are efficiently learnable by polynomial regression, which produces a polynomial threshold function (PTF), but PTFs in general may have boundary volume $\Omega(1)$, even for $r \ll 1$. We give an algorithm that agnostically learns linear threshold functions and returns a classifier with boundary volume $O(r+\varepsilon)$ at radius of perturbation $r$. The time and sample complexity of $d^{\tilde{O}(1/\varepsilon^2)}$ matches the complexity of polynomial regression. Our algorithm augments the classic approach of polynomial regression with three additional steps: a) performing the $\ell_1$-error regression under noise sensitivity constraints, b) a structured partitioning and rounding step that returns a Boolean classifier with error $\textsf{opt} + O(\varepsilon)$ and noise sensitivity $O(r+\varepsilon)$ simultaneously, and c) a local corrector that ``smooths'' a function with low noise sensitivity into a function that is adversarially robust.
- Abstract（参考訳）: 分類器がノルム $r$ の摂動に対して \emph{adversarially robust} であるとは、入力分布から引き出された点 $x$ 上の高い確率を持つ場合、距離 $\le r$ から $x$ までの点が別々に分類される。
emph{boundary volume} は、ある点が異なるラベルを持つ点の距離$r$以内に落ちる確率である。
この研究は、入力が$\mathbb{R}^d$上の準ガウス的等方性対数凹分布として分配されるような、境界体積の小さい仮説を計算的に効率的に学習するタスクを研究する。
線形しきい値関数は逆向きに堅牢であり、境界体積は$r$に比例する。
このような概念クラスは多項式回帰によって効率的に学習可能であり、多項式しきい値関数(PTF)を生成するが、一般的には PTF は境界体積 $\Omega(1)$ を持ち、$r \ll 1$ である。
線形しきい値関数を不可知的に学習し、摂動半径$r$で境界体積$O(r+\varepsilon)$の分類子を返すアルゴリズムを与える。
d^{\tilde{O}(1/\varepsilon^2)}$の時間とサンプルの複雑さは多項式回帰の複雑さと一致する。
我々のアルゴリズムは、多項式回帰の古典的なアプローチを3つのステップで強化する。
a) ノイズ感度制約の下で$\ell_1$-errorレグレッションを実行すること。
b) エラー$\textsf{opt} + O(\varepsilon)$とノイズ感度$O(r+\varepsilon)$を同時に返す構造化パーティショニングとラウンドングステップ。
c) 「smooths」が雑音感度の低い関数を逆向きに堅牢な関数に限定する局所補正器
関連論文リスト
- Near-Optimal and Tractable Estimation under Shift-Invariance [0.21756081703275998]
そのような信号のクラスは、非常にリッチである:$mathbbCn$ 上のすべての指数振動を含み、合計$s$ である。
このクラスの統計複雑性は、$(delta)$-confidence $ell$-ballの半径2乗最小マックス周波数によって測定されるが、$s$-sparse信号のクラス、すなわち$Oleft(slog(en) + log(delta-1)right) cdot log(en/s)とほぼ同じであることを示す。
論文 参考訳（メタデータ） (2024-11-05T18:11:23Z) - A Proximal Modified Quasi-Newton Method for Nonsmooth Regularized Optimization [0.7373617024876725]
Lipschitz-of-$nabla f$
$mathcalS_k|p$。
$mathcalS_k|p$。
$nabla f$.
$mathcalS_k|p$。
論文 参考訳（メタデータ） (2024-09-28T18:16:32Z) - Iterative thresholding for non-linear learning in the strong $\varepsilon$-contamination model [3.309767076331365]
閾値降下を用いた単一ニューロンモデル学習のための近似境界を導出する。
線形回帰問題も研究し、$sigma(mathbfx) = mathbfx$ となる。
論文 参考訳（メタデータ） (2024-09-05T16:59:56Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - 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) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。