論文の概要: Learning with Simulators: No Regret in a Computationally Bounded World
- arxiv url: http://arxiv.org/abs/2606.13576v1
- Date: Thu, 11 Jun 2026 17:02:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-12 15:55:27.934988
- Title: Learning with Simulators: No Regret in a Computationally Bounded World
- Title（参考訳）: シミュレータによる学習 - 計算的に境界付けられた世界でのレジスト
- Authors: Sasha Voitovych, Abhishek Shetty, Noah Golowich, Alexander Rakhlin,
- Abstract要約: そこでは,学習者がデータを生成する分布を近似するシミュレータにアクセスできるようにする。
私たちは、従来の独立したデータ、すなわちVCに依存するエラー境界で、学習保証を回復できることを示します。
- 参考スコア（独自算出の注目度）: 65.78002253798827
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.
- Abstract（参考訳）: 一般化に必要な最小の仮定を理解することは、学習理論の基本的な問題である。
残念なことに、ほとんどの結果はデータ生成プロセスの独立性(あるいはそのプロキシ)に大きく依存しています。
このギャップに対処するために、学習者がデータを生成する分布(これは任意に複雑で依存的なプロセスかもしれない)を近似するシミュレータにアクセス可能な、シミュラブルプロセスのフレームワークを導入する。
驚いたことに、そのようなシミュレーターにアクセスすると、従来の独立したデータ、すなわちVC次元に依存するエラー境界を用いて、学習保証を回復できることが示される。
さらに,この枠組みを用いて条件付きサンプリングのパワーを調べ,厳密な統計的・計算的優位性を示す。
我々のフレームワークのハイライトとして、時間境界のコルモゴロフ複雑性によって制御される後悔を伴う、すべてのプロセスでサンプリング可能な任意のVCクラスを同時に学習する1つのアルゴリズムを示す。
これにより、古典的なPACモデルが大幅に拡張される。
関連論文リスト
- Learning-Augmented Moment Estimation on Time-Decay Models [55.06256430461023]
私たちは、多くの基本的な問題に対して学習強化アルゴリズムを提供するために、データセットのヘビーヒッターにオラクルを使用します。
提案手法は,実データおよび合成データセット上でのアルゴリズムの実用的効率を実証する実験的な評価によって理論的結果を補完するものである。
論文 参考訳（メタデータ） (2026-03-03T00:42:34Z) - Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。
一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。
一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
論文 参考訳（メタデータ） (2026-02-24T06:15:59Z) - Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
ハーフスペースの交叉学習は計算学習理論における中心的な問題である。
たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。
本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-11-13T00:28:24Z) - Efficient Machine Unlearning via Influence Approximation [75.31015485113993]
インフルエンサーベースのアンラーニングは、個別のトレーニングサンプルがモデルパラメータに与える影響を再トレーニングせずに推定する顕著なアプローチとして現れてきた。
本稿では,暗記(増分学習)と忘れ(未学習)の理論的関連性を確立する。
本稿では、インフルエンス近似アンラーニングアルゴリズムを導入し、インクリメンタルな視点から効率的なマシンアンラーニングを行う。
論文 参考訳（メタデータ） (2025-07-31T05:34:27Z) - Collaborative Learning with Different Labeling Functions [7.228285747845779]
我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。
データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
論文 参考訳（メタデータ） (2024-02-16T04:32:22Z) - Bootstrap aggregation and confidence measures to improve time series
causal discovery [0.0]
本稿では,時間的依存関係とラグ構造を保存する時系列因果発見のための新しいブートストラップ手法を提案する。
我々は、この手法を、最先端の条件付き独立性に基づくアルゴリズムPCMCI+と組み合わせる。
論文 参考訳（メタデータ） (2023-06-15T08:37:16Z) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳（メタデータ） (2022-02-08T16:39:57Z) - A Theory of Universal Learning [26.51949485387526]
普遍的な学習の確率は3つしかないことを示す。
任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
論文 参考訳（メタデータ） (2020-11-09T15:10:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。