論文の概要: Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

• arxiv url: http://arxiv.org/abs/2407.00966v1
• Date: Mon, 1 Jul 2024 04:58:36 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-04 00:46:07.613876
• Title: Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension
• Title（参考訳）: 低内在次元学習概念の平滑化解析
• Authors: Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos,
• Abstract要約: 教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。 学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。 時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 17.485243410774814
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In traditional models of supervised learning, the goal of a learner -- given examples from an arbitrary joint distribution on $\mathbb{R}^d \times \{\pm 1\}$ -- is to output a hypothesis that is competitive (to within $\epsilon$) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of $k$-halfspaces in time $k^{poly(\frac{\log k}{\epsilon \gamma}) }$ where $\gamma$ is the margin parameter. Before our work, the best-known runtime was exponential in $k$ (Arriaga and Vempala, 1999).
• Abstract（参考訳）: 教師付き学習の伝統的なモデルでは、学習者のゴール(例えば$\mathbb{R}^d \times \{\pm 1\}$)は、あるクラスから最も適した概念の競合する仮説($\epsilon$)を出力することである。 単純な概念クラスを学習する際の強硬度結果を回避するために,学習者が小さなランダムなガウス摂動に頑健な最高の分類器とのみ競合するスムーズな分析フレームワークを導入する。 この微妙な変化により、(1)は低次元部分空間(いわゆるマルチインデックスモデル)に依存し、(2)は有界ガウス曲面を持つという概念に対して幅広い学習結果が得られる。 このクラスはハーフ空間と(低次元)凸集合の関数を含み、ガウスのような高度に構造化された分布に関して非滑らかな設定でのみ学習できることが知られている。 驚くべきことに、我々の分析は、マージンのある学習のような従来の非スムーズなフレームワークに新しい結果をもたらす。 特に、$k$-半空間の交叉を時間$k^{poly(\frac{\log k}{\epsilon \gamma}) }$ ここで、$\gamma$はマージンパラメータである。 我々の研究以前には、最もよく知られたランタイムは$k$(Arriaga and Vempala, 1999)で指数関数であった。

関連論文リスト

• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  アンサンブル学習(英: Ensemble learning)は、弱い学習者を利用して強力な学習者を生み出す方法である。 我々は、マージンの概念を活かした滑らかで凸な目的関数を設計し、強力な学習者がより差別的になるようにした。 そして、我々のアルゴリズムを、多数のデータセットの10倍の大きさのランダムな森林や他の古典的な手法と比較する。
  論文  参考訳（メタデータ） (2024-08-06T03:42:38Z)
• 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)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• Testable Learning with Distribution Shift [9.036777309376697]
  分散シフトを伴うテスト可能学習と呼ばれる新しいモデルを定義する。 テスト分布上の分類器の性能を証明可能なアルゴリズムを得る。 ハーフスペースやハーフスペースの交点,決定木といった概念クラスを学ぶ上で,いくつかの肯定的な結果が得られる。
  論文  参考訳（メタデータ） (2023-11-25T23:57:45Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• Testing distributional assumptions of learning algorithms [5.204779946147061]
  テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。 データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
  論文  参考訳（メタデータ） (2022-04-14T19:10:53Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。 我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。 また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
  論文  参考訳（メタデータ） (2020-06-08T17:59:11Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)

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

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