論文の概要: Constrained Learning with Universally Learnable Concept Classes

• arxiv url: http://arxiv.org/abs/2608.08414v1
• Date: Sun, 09 Aug 2026 02:13:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-11 19:16:36.815952
• Title: Constrained Learning with Universally Learnable Concept Classes
• Title（参考訳）: 普遍的に学習可能な概念クラスによる制約付き学習
• Abstract要約: 双対アルゴリズムの解の解の普遍的な PACC 学習性を確立する。 最適性は、凸性によって支配される普遍性と強ラグランジアン双対性の間に捕えられる。
• 参考スコア（独自算出の注目度）: 2.5998827435861633
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once. This strengthens near-PACC results, whose feasibility residual no amount of data can remove. Optimality is caught between generalization, governed by Rademacher complexity and favoring small classes, and strong Lagrangian duality, which rests on Lyapunov convexity for vector measures and needs decomposability, a demand pulling the other way. We reconcile the two by posing the population problem over a universal RKHS $\mathcal{H}_K$, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity $\mathfrak{T}^{\varepsilon}_{n}$, the least RKHS norm reaching an $\varepsilon$-optimal Lagrangian level set; we prove it finite, obtain exact learnability of the optimal value, and make the sample threshold explicit and polynomial in $1/\varepsilon$ under a source condition. Feasibility is harder: absent convexity the Lagrangian may not attain its infimum, and dual information pins down only an averaged constraint-risk vector, not the risks of any returned predictor. We introduce the closure-realization gap $\varepsilon^\star_\infty$, an index of how well $\mathcal{H}_K$ retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when $\varepsilon^\star_\infty=0$, in particular under dual differentiability, and near-PACC with residual exactly $\varepsilon^\star_\infty$ otherwise. Finally, no distribution-free threshold exists already in the unconstrained specialization, so universality is the canonical frame for dual algorithms over large hypothesis classes.
• Abstract（参考訳）: 完全非凸条件下での無限次元仮説クラスに対する制約付き統計的学習について検討し、双対アルゴリズムの解の普遍的なPACC学習性を確立する。 これにより、ほぼPACC結果が強化され、その実現可能性の残余は取り除けない。 ラデマッハ複雑性と小さなクラスに支配される一般化と、ベクトル測度に対するリャプノフ凸性(英語版)(Lyapunov convexity)に基づく強いラグランジアン双対性(英語版)(Lagrangian duality)との間には最適性があり、デコンポスタビリティ(英語版)(decomposability)を必要とする。 我々は、一般のRKHS$\mathcal{H}_K$で人口問題を提起し、分解可能なエンベロープに密着し、成長する半径のノルムボールについて学習することによって、この2つの問題を和らげる。 これにより、Tikhonov の複雑性 $\mathfrak{T}^{\varepsilon}_{n}$、最小の RKHS ノルムが$\varepsilon$-optimal Lagrangian レベルセットに達する。 ラグランジアンの凸性の欠如はその無限大に達しず、双対情報は平均的な制約リスクベクトルのみをピン留めし、返される予測子のリスクを下げる。 閉包実現ギャップ $\varepsilon^\star_\infty$ は、$\mathcal{H}_K$ が双対化から実現可能な解をいかにうまく取り出すかの指標である。 学習性は、特に双対微分可能性の下での$\varepsilon^\star_\infty=0$と、正確には$\varepsilon^\star_\infty$の残差を持つ準PACCの場合に正確である。 最後に、分布自由しきい値は既に制約のない特殊化の中に存在しないので、普遍性は大きな仮説クラス上の双対アルゴリズムの標準フレームである。

関連論文リスト

• Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter [3.6552781109515853]
  本研究では,一様損失下でのエントロピー最適輸送電位の実験的シンクホーン推定器について検討した。 固定正規化パラメータ $varepsilon>0$ に対して、漸近的でない統計レート $n-1/2$ を確立する。 鍵となる要件は、シンクホーン写像の残留安定度推定である。
  論文  参考訳（メタデータ） (2026-08-29T08:59:00Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Towards Fundamental Limits for Active Multi-distribution Learning [16.639855803241524]
  我々は,多分布学習のための新しいアルゴリズムを開発し,ラベルの複雑さを向上する。 実現可能な設定のバウンダリは情報理論的に最適であり、設定の$knu/varepsilon2$項は適切な学習者にとって基本的なものであることを示す。
  論文  参考訳（メタデータ） (2025-06-21T06:08:58Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Localization, Convexity, and Star Aggregation [0.0]
  オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。 統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-19T00:47:59Z)

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

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