論文の概要: Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners

• arxiv url: http://arxiv.org/abs/2610.41961v1
• Date: Fri, 30 Oct 2026 16:12:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-02 22:05:31.80582
• Title: Robust Learning of Multi-Index Models under Logconcave Distributions via Weak Partial Learners
• Title（参考訳）: 弱部分学習者によるログコンケーブ分布下のマルチインデックスモデルのロバスト学習
• Abstract要約: ログコンケーブ分布下でBooleanの概念クラスを学習するための新しいアルゴリズムフレームワークを開発した。 我々のフレームワークは、マルチインデックスモデルの幅広いファミリーに適用され、以前よりもはるかに高速な堅牢な学習者が得られる。
• 参考スコア（独自算出の注目度）: 44.66700509667053
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop a new algorithmic framework for learning Boolean concept classes under logconcave distributions. Our framework applies to broad families of multi-index models and yields significantly faster robust learners than were previously known in these settings. It extends to partial classification and testable learning. Consequently, we obtain improved learners for several fundamental concept classes, including functions of halfspaces and multiclass linear classifiers, under logconcave marginals. Our starting point is a new boosting framework based on weak partial learners. Classical boosting approaches require often-intractable distribution-free weak learners or yield weak approximation guarantees. We show instead that weak learners for partial classification, where labels may be undefined on part of the domain, suffice for strong agnostic learning. The key challenge is that boosting requires a weak learner that succeeds under conditioned distributions that are not guaranteed to be logconcave. To address this, we develop a recursive moment-based partitioning procedure: given a logconcave distribution $X$ and a conditional version $X'$, we partition the space into polynomially many convex regions so that, on most regions, the low-degree moments of $X$ and $X'$ approximately agree. On each good region, a well-behaved multi-index model correlates with a low-degree polynomial, giving a weak hypothesis. Combining these hypotheses yields the required weak learner. A key ingredient of our approach is an efficient method for detecting moment discrepancy. Specifically, we show how to find a low-dimensional subspace that captures any non-trivial discrepancy between $X$ and $X'$, if one exists. Our approach combines spectral analysis of moment tensors with recent progress on isoperimetry for logconcave measures. This discrepancy-finding procedure may be of independent interest.
• Abstract（参考訳）: ログコンケーブ分布下でBooleanの概念クラスを学習するための新しいアルゴリズムフレームワークを開発した。 我々のフレームワークは、マルチインデックスモデルの幅広いファミリーに適用され、以前これらの設定で知られていたよりもはるかに高速な堅牢な学習者が得られる。 部分的な分類とテスト可能な学習に拡張する。 その結果,マルチクラス線形分類器とハーフスペースの関数を含むいくつかの基本概念クラスに対して,ログコンケーブ限界の下で改良された学習者を得ることができた。 私たちの出発点は、弱い部分学習者に基づく新しい強化フレームワークです。 古典的な強化アプローチは、しばしば難解な分布のない弱い学習者を必要とするか、弱い近似を保証する。 その代わりに、ラベルがドメインの一部で定義されていないような部分的分類のための弱い学習者は、強い不可知学習に十分であることを示す。 重要な課題は、ログコンケーブが保証されていない条件付きディストリビューションで成功する弱い学習者を必要とすることだ。 この問題に対処するために、再帰的なモーメントベースのパーティショニング手順を開発する: logconcave 分布 $X$ と条件付きバージョン $X'$ が与えられた場合、空間を多項式的に多くの凸領域に分割し、ほとんどの領域において、低次モーメント $X$ と $X'$ はほぼ一致する。 それぞれのよい領域において、よく定義された多重インデックスモデルは低次多項式と相関し、弱い仮説を与える。 これらの仮説を組み合わせることで、必要な弱い学習者が得られる。 提案手法の重要な要素は,モーメントの相違を検出する効率的な方法である。 具体的には、もし存在するなら、$X$ と $X'$ の間の非自明な相違を捕捉する低次元部分空間を見つける方法を示す。 提案手法は,モーメントテンソルのスペクトル解析と対数凹度測定の最近の進歩を組み合わせたものである。 この相違を補う手順は、独立した関心事であるかもしれない。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  アンサンブル学習(英: Ensemble learning)は、弱い学習者を利用して強力な学習者を生み出す方法である。 我々は、マージンの概念を活かした滑らかで凸な目的関数を設計し、強力な学習者がより差別的になるようにした。 そして、我々のアルゴリズムを、多数のデータセットの10倍の大きさのランダムな森林や他の古典的な手法と比較する。
  論文  参考訳（メタデータ） (2024-08-06T03:42:38Z)
• Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension [17.485243410774814]
  教師付き学習の伝統的なモデルでは、学習者の目標は、あるクラスから最も適した概念の競争的($epsilon$以内)な仮説を出力することである。 学習者が最高の無知としか競合しないスムーズな分析フレームワークを導入する。 時間内に$k$-halfspacesの交点を前向きに学習する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-01T04:58:36Z)
• Semi-Supervised Laplace Learning on Stiefel Manifolds [48.3427853588646]
  グラフベースで教師付きサンプルを低ラベルレートで作成するためのフレームワークSequential Subspaceを開発した。 我々の手法は極めて低いレートで、高いラベルレートで達成できる。
  論文  参考訳（メタデータ） (2023-07-31T20:19:36Z)
• An Upper Bound for the Distribution Overlap Index and Its Applications [22.92968284023414]
  本稿では,2つの確率分布間の重なり関数に対する計算容易な上限を提案する。 提案した境界は、一級分類と領域シフト解析においてその値を示す。 私たちの研究は、重複ベースのメトリクスの応用を拡大する大きな可能性を示しています。
  論文  参考訳（メタデータ） (2022-12-16T20:02:03Z)
• When are Local Queries Useful for Robust Learning? [25.832511407411637]
  本研究では,学習者が局所的なクエリを用いてより多くのパワーを与えられる学習モデルについて検討する。 我々は、ロバストな経験的リスク最小化を行う最初の分布自由アルゴリズムを与える。 我々は、0,1n$でハーフスペースに対してロバストな学習アルゴリズムを与え、その後、精度に縛られた敵に対して$mathbbRn$でハーフスペースに対してロバスト性を保証する。
  論文  参考訳（メタデータ） (2022-10-12T11:04:22Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)

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

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