論文の概要: Robustly Reliable Learning for Regression

• arxiv url: http://arxiv.org/abs/2610.17381v1
• Date: Mon, 12 Oct 2026 20:39:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-17 19:12:03.718492
• Title: Robustly Reliable Learning for Regression
• Title（参考訳）: 回帰のためのロバストな信頼性のある学習
• Abstract要約: 最適予測範囲 $I*_x_test(S, b)$ for any $L$-Lipschitz predictor with all but at $b$ points in $S$。 最も厳密な範囲である$I*_x_test(S, b)$の計算における正当性を証明する。 次に、データセット$Sがもはや$L$-Lipschitz一貫性のない一般的なシナリオに対処する。
• 参考スコア（独自算出の注目度）: 8.051890847211078
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the problem of robustly reliable learning for the regression setting in adversarial environments. Given a test point $x_{test}$, a training dataset $S$ of $n$ data points, a corruption budget $b \ll n$, and a real-valued hypothesis class $\mathcal H$, our goal is to output the optimal prediction range $I^*_{x_{test}}(S, b)$, such that any $L$-Lipschitz predictor consistent with all but at most $b$ points in $S$ must predict a value $h(x_{test}) \in I$. We then instantiate the analysis for $L$-Lipschitz hypothesis classes, a natural and widely studied class in the regression setting, focusing on two key scenarios. First, for the restricted case where the corrupted dataset is guaranteed to be $L$-Lipschitz consistent, we propose a simple and efficient $b^{th}$-best heuristic algorithm and prove its correctness in computing the tightest possible range $I^*_{x_{test}}(S, b)$. We then establish its computational complexity of $O(n)$ and show that it is computationally optimal in this scenario. Building on this foundation, we address the general scenario where the dataset $S$ is no longer $L$-Lipschitz consistent. We demonstrate that computing the optimal range in this setting reduces to analyzing a violation graph, which models the pairwise $L$-Lipschitz violations among data points. By leveraging the structural properties of this graph's kernel, we propose a Fixed-Parameter Tractable (FPT) algorithm that computes the exact optimal range in $O(n^2 + b^4)$ time. Furthermore, under the Strong Exponential Time Hypothesis (SETH), we establish a computational lower bound of $Ω(n^{2 - o(1)})$, proving that our algorithm is computationally optimal. Finally, we discuss open directions for the problem of robustly reliable learning for regression.
• Abstract（参考訳）: 対戦環境における回帰設定に対する頑健な信頼性学習の課題について紹介する。 テストポイント $x_{test}$, トレーニングデータセット $S$ of $n$ データポイント, 汚職予算 $b \ll n$, 実数値仮説クラス $\mathcal H$ が与えられた場合、我々のゴールは最適な予測範囲 $I^*_{x_{test}}(S, b)$ を出力することである。 次に、回帰設定における自然で広く研究されているクラスである$L$-Lipschitz仮説クラスの解析を2つの主要なシナリオに焦点をあててインスタンス化する。 まず、破損したデータセットが$L$-Lipschitz整合性を保証する制限された場合、単純で効率的な$b^{th}$-bestヒューリスティックアルゴリズムを提案し、最も厳密な範囲である$I^*_{x_{test}}(S, b)$の計算におけるその正当性を証明した。 次に、計算複雑性を$O(n)$と定め、このシナリオで計算的に最適であることを示す。 この基盤に基づいて、データセット$S$がもはや$L$-Lipschitz一貫性のない一般的なシナリオに対処する。 この設定における最適範囲の計算は、データポイント間のペアの$L$-Lipschitz違反をモデル化する違反グラフの解析に還元されることを示す。 このグラフのカーネルの構造特性を活用することにより, 正確な最適範囲を$O(n^2 + b^4)$時間で計算する固定パラメータトラクタ(FPT)アルゴリズムを提案する。 さらに、Strong Exponential Time hypothesis (SETH) の下で、計算の下限を$Ω(n^{2 - o(1)})$と定め、アルゴリズムが計算的に最適であることを証明した。 最後に,レグレッションのための堅牢な学習の問題に対するオープンな方向性について論じる。

関連論文リスト

• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
  論文  参考訳（メタデータ） (2025-10-12T15:42:44Z)
• Nearly Optimal Differentially Private ReLU Regression [18.599299269974498]
  微分プライバシ(DP)モデルにおいて、最も基本的な非学習問題の1つ、ReLU回帰について検討する。 我々は,1パスのミニバッチ一般化モデルパーセプトロンアルゴリズムを提案し,解析することで,$epsilon$と公開データの要求を緩和する。
  論文  参考訳（メタデータ） (2025-03-08T02:09:47Z)
• Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
  誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。 我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
  論文  参考訳（メタデータ） (2024-06-10T17:48:36Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• 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)
• 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)

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

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