論文の概要: List-Decodable Regression via Expander Sketching

• arxiv url: http://arxiv.org/abs/2511.22524v1
• Date: Thu, 27 Nov 2025 15:04:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-01 19:47:55.619156
• Title: List-Decodable Regression via Expander Sketching
• Title（参考訳）: Expander SketchingによるList-Decodable Regression
• Authors: Herbod Pourali, Sajjad Hashemian, Ebrahim Ardeshir-Larijani,
• Abstract要約: 本稿では,サンプルの複雑さを$tildeO((d+log1)/)$, list size $O (1/)$, and near input-sparsity running time $tildeO(mathrmnnz(X)+d3/)$を実現するリストデコダブル線形回帰のための拡張処理フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce an expander-sketching framework for list-decodable linear regression that achieves sample complexity $\tilde{O}((d+\log(1/δ))/α)$, list size $O(1/α)$, and near input-sparsity running time $\tilde{O}(\mathrm{nnz}(X)+d^{3}/α)$ under standard sub-Gaussian assumptions. Our method uses lossless expanders to synthesize lightly contaminated batches, enabling robust aggregation and a short spectral filtering stage that matches the best known efficient guarantees while avoiding SoS machinery and explicit batch structure.
• Abstract（参考訳）: 我々は、サンプル複雑性を達成できるリストデコダブル線形回帰のための拡張処理フレームワーク、$\tilde{O}((d+\log(1/δ))/α)$, list size $O(1/α)$, and near input-sparsity running time $\tilde{O}(\mathrm{nnz}(X)+d^{3}/α)$を提供する。 提案手法では, 損失のない拡張器を用いて光汚染されたバッチを合成し, 堅牢なアグリゲーションと, SoS 機械や明示的なバッチ構造を回避しつつ, 既知の効率的な保証に適合する短いスペクトルフィルタリングステージを実現する。

関連論文リスト

• Robust learning of halfspaces under log-concave marginals [6.852292115526837]
  線形しきい値関数を学習し、境界体積$O(r+varepsilon)$の分類子を半径摂動$r$で返すアルゴリズムを与える。 dtildeO(1/varepsilon2)$の時間とサンプルの複雑さはブール回帰の複雑さと一致する。
  論文  参考訳（メタデータ） (2025-05-19T20:12:16Z)
• Batch List-Decodable Linear Regression via Higher Moments [39.32851434877865]
  バッチを用いたリスト復号化線形回帰の課題について検討する。 バッチは、未知の線形回帰分布からのi.d.サンプルからなる場合、クリーンと呼ばれる。
  論文  参考訳（メタデータ） (2025-03-12T20:11:07Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  SignSGD with Majority Votingは,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappaka ppakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappakappa -1right,Kappakappakappa-1right,Kappakappakappa-1right,Kappakappappapa-1right,Kappaを用いて,複雑性の全範囲で堅牢に動作することを示す。
  論文  参考訳（メタデータ） (2025-02-11T19:54:11Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Stochastic Halpern iteration in normed spaces and applications to reinforcement learning [0.30693357740321775]
  我々は,Halpern反復のオラクル複雑性をミニバッチで解析する。 我々は,平均値と割引値の報酬MDPに対する新しいモデルフリーアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-19T01:07:35Z)
• Efficient List-Decodable Regression using Batches [33.300073775123835]
  バッチを用いたリスト復号化線形回帰の研究を始める。 この設定では、バッチの$alpha in (0,1]$分しか真ではない。 それぞれの真のバッチは、共通の未知の分布から$ge n$ i.i.dのサンプルを含み、残りのバッチは、任意の、あるいは、敵対的なサンプルを含むことができる。
  論文  参考訳（メタデータ） (2022-11-23T07:08:00Z)
• Settling the Sample Complexity of Model-Based Offline Reinforcement Learning [50.5790774201146]
  オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。 事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。 モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
  論文  参考訳（メタデータ） (2022-04-11T17:26:19Z)
• 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)

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

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