論文の概要: Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

• arxiv url: http://arxiv.org/abs/2602.20585v1
• Date: Tue, 24 Feb 2026 06:15:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-25 17:34:53.628403
• Title: Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness
• Title（参考訳）: 一般化スムースネスによる分散制約下でのオンライン・プライベート学習性の評価
• Authors: Moïse Blanchard, Abhishek Shetty, Alexander Rakhlin,
• Abstract要約: 本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。 一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。 一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
• 参考スコア（独自算出の注目度）: 63.833913892018536
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning theory, such as the VC theorem and Littlestone's characterization of online learnability, establish conditions on the hypothesis class that allow for learning under independent data and adversarial data, respectively. Building upon recent work bridging these extremes, we study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family $U$ and ask when such problems are learnable with sample complexity that behaves like the favorable independent case. We provide a near complete characterization of families $U$ that admit learnability in terms of a notion known as generalized smoothness i.e. a distribution family admits VC-dimension-dependent regret bounds for every finite-VC hypothesis class if and only if it is generalized smooth. Further, we give universal algorithms that achieve low regret under any generalized smooth adversary without explicit knowledge of $U$. Finally, when $U$ is known, we provide refined bounds in terms of a combinatorial parameter, the fragmentation number, that captures how many disjoint regions can carry nontrivial mass under $U$. These results provide a nearly complete understanding of learnability under distributional adversaries. In addition, building upon the surprising connection between online learning and differential privacy, we show that the generalized smoothness also characterizes private learnability under distributional constraints.
• Abstract（参考訳）: 学習と一般化を可能にする最小限の仮定を理解することは、おそらく学習理論の中心的な問題である。 VC定理(英語版)やリトルストーンによるオンライン学習可能性の評価(英語版)のような統計学習理論におけるいくつかの有望な結果が、それぞれ独立したデータと敵対的なデータの下での学習を可能にする仮説クラスの条件を確立する。 この極端を橋渡しする最近の研究に基づいて、固定されたファミリー$U$からデータ生成ディストリビューションを適応的に選択し、適切な独立ケースのように振る舞うサンプルの複雑さによって、そのような問題が学習可能かどうかを問う、分散敵の下でのシーケンシャルな意思決定について検討する。 一般化滑らか性(Generalized smoothness)と呼ばれる概念の観点で学習可能性を認めるファミリーのほぼ完全な特徴づけ、すなわち分布族は任意の有限VC仮説クラスに対してVC次元依存的後悔境界を認める。 さらに、任意の一般化された滑らかな逆数に対して、U$の明示的な知識を伴わずに、低後悔を達成する普遍的アルゴリズムを与える。 最後に、$U$が知られているとき、結合しない領域が$U$以下の非自明な質量を何個持てるかをキャプチャする、組合せパラメータ、フラグメンテーション数という観点で洗練された境界を与える。 これらの結果は、分布的敵の下での学習可能性のほぼ完全な理解を提供する。 また,オンライン学習と差分プライバシーの驚くべき結びつきを生かして,一般化されたスムーズさは,分布制約下での個人学習性も特徴付けることを示す。

関連論文リスト

• Distribution-Free Sequential Prediction with Abstentions [7.110627876507878]
  本研究では, 敵が任意の数の敵インスタンスを任意に注入することを許容する逐次予測問題について検討する。 各ラウンドにおいて、学習者はインスタンスが実際に破損した場合、ペナルティを発生させることなく予測を行うことも強調できる。 本稿では,弱い学習者の強化手順に基づくtextscAbstainBoostを提案する。
  論文  参考訳（メタデータ） (2026-02-20T00:28:27Z)
• Distributionally-Constrained Adversaries in Online Learning [7.903539618132857]
  より汎用的で柔軟な分布制約のある敵の枠組みを考察し、敵が選択した分布からインスタンスを抽出する。 本稿では,この文脈で学習可能な分布クラスの特性について述べる。
  論文  参考訳（メタデータ） (2025-06-12T02:11:10Z)
• Proper Learnability and the Role of Unlabeled Data [10.168670899305232]
  適切な学習可能性が論理的に決定不可能な問題、すなわちZFC公理に依存しない問題が存在することを示す。 そこで本研究では,PACモデルにおいて,適切な学習可能性の特性を損なう不確実性に関するすべての結果を示す。
  論文  参考訳（メタデータ） (2025-02-14T18:41:53Z)
• Symmetric Equilibrium Learning of VAEs [56.56929742714685]
  可変オートエンコーダ(VAE)をデコーダ-エンコーダペアとみなし,データ空間内の分布を潜在空間内の分布にマッピングする。 本研究では,エンコーダとデコーダに対して対称なナッシュ均衡学習手法を提案し,データと潜伏分布の両方がサンプリングによってのみアクセス可能な状況下でのVAEの学習を可能にする。
  論文  参考訳（メタデータ） (2023-07-19T10:27:34Z)
• Generalization Analysis for Contrastive Representation Learning [80.89690821916653]
  既存の一般化誤差境界は負の例の数$k$に線形に依存する。 対数項まで$k$に依存しないコントラスト学習のための新しい一般化境界を確立する。
  論文  参考訳（メタデータ） (2023-02-24T01:03:56Z)
• Differentially-Private Bayes Consistency [70.92545332158217]
  差分プライバシー(DP)を満たすベイズ一貫した学習ルールを構築する。 ほぼ最適なサンプル複雑性を持つ半教師付き環境で,任意のVCクラスをプライベートに学習できることを実証する。
  論文  参考訳（メタデータ） (2022-12-08T11:57:30Z)
• Learning versus Refutation in Noninteractive Local Differential Privacy [133.80204506727526]
  非対話的局所差分プライバシー(LDP)における2つの基本的な統計課題について検討する。 本研究の主な成果は,非対話型LDPプロトコルにおけるPAC学習の複雑さの完全な評価である。
  論文  参考訳（メタデータ） (2022-10-26T03:19:24Z)

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

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