論文の概要: Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds

• arxiv url: http://arxiv.org/abs/2404.02364v2
• Date: Mon, 20 May 2024 18:25:35 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-22 18:12:24.564375
• Title: Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
• Title（参考訳）: 分布シフトを伴うハーフスペースの学習:改良アルゴリズムとSQ下界
• Authors: Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan,
• Abstract要約: Klivans、Stavropoulos、Vasilyanは、分散シフトを伴うテスト可能な学習の研究を始めた。 それらのモデルは、$mathcalD'$に仮定されないという点で、以前のすべての作業から逸脱している。
• 参考スコア（独自算出の注目度）: 9.036777309376697
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), where a learner is given labeled samples from training distribution $\mathcal{D}$, unlabeled samples from test distribution $\mathcal{D}'$, and the goal is to output a classifier with low error on $\mathcal{D}'$ whenever the training samples pass a corresponding test. Their model deviates from all prior work in that no assumptions are made on $\mathcal{D}'$. Instead, the test must accept (with high probability) when the marginals of the training and test distributions are equal. Here we focus on the fundamental case of intersections of halfspaces with respect to Gaussian training distributions and prove a variety of new upper bounds including a $2^{(k/\epsilon)^{O(1)}} \mathsf{poly}(d)$-time algorithm for TDS learning intersections of $k$ homogeneous halfspaces to accuracy $\epsilon$ (prior work achieved $d^{(k/\epsilon)^{O(1)}}$). We work under the mild assumption that the Gaussian training distribution contains at least an $\epsilon$ fraction of both positive and negative examples ($\epsilon$-balanced). We also prove the first set of SQ lower-bounds for any TDS learning problem and show (1) the $\epsilon$-balanced assumption is necessary for $\mathsf{poly}(d,1/\epsilon)$-time TDS learning for a single halfspace and (2) a $d^{\tilde{\Omega}(\log 1/\epsilon)}$ lower bound for the intersection of two general halfspaces, even with the $\epsilon$-balanced assumption. Our techniques significantly expand the toolkit for TDS learning. We use dimension reduction and coverings to give efficient algorithms for computing a localized version of discrepancy distance, a key metric from the domain adaptation literature.
• Abstract（参考訳）: Klivans, Stavropoulos, Vasilyanの最近の研究は、分散シフトによるテスト可能な学習(TDS学習)の研究を開始した。そこでは、学習者にトレーニング分布からラベル付きサンプルを付与する$\mathcal{D}$、テスト分布からラベル付けされていないサンプルを$\mathcal{D}'$、トレーニングサンプルが対応するテストを通過するたびに$\mathcal{D}'$で低エラーの分類器を出力することを目的としている。 それらのモデルは、$\mathcal{D}'$に仮定されることはないという点で、以前のすべての作業から逸脱する。 代わりに、トレーニングとテストの分布の限界が等しい場合、テストは(高い確率で)受け入れなければならない。 ここでは、ガウスの訓練分布に関するハーフ空間の交叉の基本的なケースに注目し、$k$同質半空間のTDS学習交叉に対する2$(k/\epsilon)^{O(1)}} \mathsf{poly}(d)$-timeアルゴリズムを含む様々な新しい上限を証明している。 ガウスのトレーニング分布は、正と負の両方の例(\epsilon$- Balanced)の少なくとも$\epsilon$分を含むという軽微な仮定の下で作業する。 また、任意のTDS学習問題に対するSQの下界の最初の集合を証明し、(1) 1 つの半空間に対する $\mathsf{poly}(d,1/\epsilon)$-time TDS 学習に$\epsilon$- Balanced 仮定が必要であること、(2) a $d^{\tilde{\Omega}(\log 1/\epsilon)$ 2 つの一般半空間の交叉に対する$$\epsilon$- Balanced 仮定においても$\epsilon$- Balanced 仮定は必要であることを示す。 我々の技術は、TDS学習のツールキットを著しく拡張します。 我々は次元の縮小と被覆を用いて、領域適応文学の重要な指標である離散距離の局所化バージョンを計算するための効率的なアルゴリズムを提供する。

関連論文リスト

• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• Efficient Testable Learning of Halfspaces with Adversarial Label Noise [44.32410859776227]
  最近導入されたテスト可能な学習モデルでは、データがテスタを通過すると、データに対する堅牢な学習者の出力を信頼するように、テスタ-ラーナーを作成する必要がある。 テストラナーは、時間$poly(d/eps)$を実行し、ミス分類エラー$O(opt)+eps$でハーフスペースを出力します。
  論文  参考訳（メタデータ） (2023-03-09T18:38:46Z)
• Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals [43.0867217287089]
  ガウス分布の下で半空間を不可知的に学習する作業について検討する。 この課題に対して,ほぼ最適計算硬度を証明した。
  論文  参考訳（メタデータ） (2023-02-13T16:46:23Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。 我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
  論文  参考訳（メタデータ） (2022-12-01T15:57:58Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
  有限混合系における非パラメトリック分布の学習問題について検討する。 このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
  論文  参考訳（メタデータ） (2022-03-28T23:53:48Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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