論文の概要: Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization

• arxiv url: http://arxiv.org/abs/2606.17215v1
• Date: Mon, 15 Jun 2026 18:56:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-17 17:15:32.109132
• Title: Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization
• Title（参考訳）: ロバスト・ハーフスペース学習における重み付きヒンジ法における正方形の重み付き障壁:クリストッフェル・ファンクションによる評価
• Authors: Xiaoyu Li,
• Abstract要約: 不正なデータを削除した証明書は、その低度な瞬間を通じてのみデータを見ることができる。 我々はこれを、悪意のある雑音の下で$$$marginのハーフスペースを堅牢に学習する、再重み付けアプローチの組織原理に転換する。
• 参考スコア（独自算出の注目度）: 5.232247961914376
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A certificate that removes outliers sees the data only through its low-degree moments, and an adversary exploits exactly this, hiding corruption where the clean data already looks typical, in the blind spot no bounded-degree test resolves. That blind spot turns out to have an exact size: the Christoffel function of the clean marginal, the very quantity modern data analysis thresholds to detect outliers, here read from the adversary's side as the corruption a bounded-degree certificate cannot remove. We turn this inversion into the organizing principle of the reweighted-hinge approach to robustly learning $γ$-margin halfspaces under malicious noise (Shen, 2025; Zeng and Shen, 2025): the governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center $c$ from a degree-$2t$ certificate is exactly the Christoffel function $λ_{t+1}(c)$ of the clean marginal. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error $ε$ costs SoS degree $Ω(\log(1/ε))$ or margin $Ω(\sqrt{\log(1/ε)}/\sqrt{d})$, explaining why the $\log(1/ε)$ margin Shen (2025) records is forced, with a weighted-Chebyshev reduction making the threshold $2t=Θ((|c|/s)^2)$ tight modulo one classical weighted-extremal estimate. A degree-$2$ outlier barrier: the resolution principle realized as an explicit instance on which degree $2$ is stuck at $η^{1/2}$ while degree $4$ escapes, locating the method's small breakdown rate in the degree, not the analysis. And a degree-$2t$ algorithm tracing the frontier $η^{1-1/2t}$ (recovering Shen (2025) at $t=1$), whose gain is an explicit constant, capped by the pancake density and shown unimprovable by the degree-$2$ barrier.
• Abstract（参考訳）: 外乱を除去する証明書は、その低度モーメントを通してのみデータを見るが、敵はまさにこれを悪用し、クリーンなデータがすでに典型的に見えるような汚職を隠す。 清潔な限界のクリストッフェル関数、異常値を検出するための非常に量の近代的なデータ分析しきい値、ここでは敵側から読めば、境界度証明書の破損は取り除けない。 我々はこの逆転を、悪意のある雑音下での$γ$-margin半空間の堅牢な学習(Shen, 2025; Zeng and Shen, 2025): 支配資源は、外周除去証明書のSquares次数であり、解決原理は、ある中心に2t$証明書から隠せる最大汚職質量は、正確にはChristoffel関数$λ_{t+1}(c)$である、と述べている。 3つの結果が従うが、いずれも証明法(情報理論ではない)に反する。 余分なトレードオフ: 過度なパンケーキをエラーに認定する ε$ Cost SoS degree $Ω(\log(1/ε))$ or margin $Ω(\sqrt{\log(1/ε)}/\sqrt{d})$ は、なぜ$\log(1/ε)$ margin Shen (2025) レコードが強制されるのかを説明し、重み付きチェビシェフの値が閾値2t=*((|c|/s)^2)$ tight modulo one classical weighted-extremal estimates(英語版)である。 次数 2$ 外れの障壁: 解法原理は、2$ が $η^{1/2}$ で固定されるような明示的なインスタンスとして実現され、次数 4$ がエスケープされ、解析ではなく、その度合いでメソッドの小さな分解速度が特定される。 また、フロンティア$η^{1-1/2t}$(2025年のシェン(英語版)を$t=1$で回収する)をトレースする次数$2tのアルゴリズムは、そのゲインは明示定数であり、パンケーキ密度に制限され、次数$2$の障壁によって証明不可能である。

関連論文リスト

• The Security Budget of Code-LLM Prompt Hardening: Provable Limits Under Pass-Only Acceptance [0.0]
  本稿では,emphTri-Audit Protocolとしてフロアを運用する。このプロトコルは,プロンプト側推論レジストリ属性をモデル側実証ログから分離する2軸レポーティングプロトコルである。 CodeLlama-7B, Qwen2.5-Coder-7B/1.5B and DeepSeek-Coder-6.7B at $n=164$ yields the emphCross-Model Tri-Audit Invariance: of 28 pass-serving rows, 12-changed-of-record learned-can
  論文  参考訳（メタデータ） (2026-06-02T08:22:14Z)
• Hidden-State Privacy Has an Empty Middle [51.56484100374058]
  すべてのフルランクガウス解放を$O(1)$ Fisher utility で表すと、マハラノビス信号が隠れた幅で直線的に成長する方向を認める。 スクラッチからトレーニングされたスプリットメモリトランスフォーマーは、[20, 33]$90MでG_mathrmMahに達し、固定言語損失ペナルティにおいて、30Mから1Bまでの同じ予算のGPTベースラインに対して6ドル～24ドルという優位性を維持する。
  論文  参考訳（メタデータ） (2026-05-21T20:12:09Z)
• Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
  実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。 本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。 また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
  論文  参考訳（メタデータ） (2026-05-13T15:41:30Z)
• On the Sparsifiability of Correlation Clustering: Approximation Guarantees under Edge Sampling [6.908972852063454]
  相関クラスタリング(CC)は基本的な教師なし学習プリミティブである。 LPベースの保証を維持するためには,どの程度のエッジ情報が必要であるかを検討する。 ヤオのミニマックス原理を通して、擬距離構造がなければ、任意のアルゴリズムが$o(n)$一様ランダムエッジを観測すると近似比が生じることを示す。
  論文  参考訳（メタデータ） (2026-02-14T09:12:15Z)
• On Traceability in $\ell_p$ Stochastic Convex Optimization [34.23960368886818]
  学習アルゴリズムが$m$-traceableであるとは、そのアウトプットを分析することで、トレーニングサンプルの少なくとも$m$を識別できるということである。 我々の主な成果は、SCOにおけるトレーサビリティと過剰リスクの根本的なトレードオフを明らかにすることである。
  論文  参考訳（メタデータ） (2025-02-24T18:10:06Z)
• Corruption-Robust Offline Reinforcement Learning with General Function Approximation [60.91257031278004]
  一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。 我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
  論文  参考訳（メタデータ） (2023-10-23T04:07:26Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
  SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。 本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。 1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
  論文  参考訳（メタデータ） (2021-10-13T17:50:46Z)

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

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