論文の概要: Online Estimation via Offline Estimation: An Information-Theoretic Framework
- arxiv url: http://arxiv.org/abs/2404.10122v1
- Date: Mon, 15 Apr 2024 20:19:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-17 18:51:25.417777
- Title: Online Estimation via Offline Estimation: An Information-Theoretic Framework
- Title（参考訳）: オフライン推定によるオンライン推定:情報理論フレームワーク
- Authors: Dylan J. Foster, Yanjun Han, Jian Qian, Alexander Rakhlin,
- Abstract要約: オフライン推定アルゴリズムをオンライン推定アルゴリズムに変換することは可能か?
我々はOracle-Efficient Online Estimation (OEOE)という新しいフレームワークを導入し,学習者はストリーム上で動作しているブラックボックスアルゴリズムによって生成されたオフライン推定器のシーケンスを通じて,データストリームと間接的にのみ対話することができる。
- 参考スコア（独自算出の注目度）: 75.80823630681323
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: $ $The classical theory of statistical estimation aims to estimate a parameter of interest under data generated from a fixed design ("offline estimation"), while the contemporary theory of online learning provides algorithms for estimation under adaptively chosen covariates ("online estimation"). Motivated by connections between estimation and interactive decision making, we ask: is it possible to convert offline estimation algorithms into online estimation algorithms in a black-box fashion? We investigate this question from an information-theoretic perspective by introducing a new framework, Oracle-Efficient Online Estimation (OEOE), where the learner can only interact with the data stream indirectly through a sequence of offline estimators produced by a black-box algorithm operating on the stream. Our main results settle the statistical and computational complexity of online estimation in this framework. $\bullet$ Statistical complexity. We show that information-theoretically, there exist algorithms that achieve near-optimal online estimation error via black-box offline estimation oracles, and give a nearly-tight characterization for minimax rates in the OEOE framework. $\bullet$ Computational complexity. We show that the guarantees above cannot be achieved in a computationally efficient fashion in general, but give a refined characterization for the special case of conditional density estimation: computationally efficient online estimation via black-box offline estimation is possible whenever it is possible via unrestricted algorithms. Finally, we apply our results to give offline oracle-efficient algorithms for interactive decision making.
- Abstract（参考訳）: オンライン学習の現代的な理論は、適応的に選択された共変量(オンライン推定)に基づく推定のためのアルゴリズムを提供する。
オフライン推定アルゴリズムをブラックボックス方式でオンライン推定アルゴリズムに変換することは可能か?
我々は,新たなフレームワークであるOracle-Efficient Online Estimation (OEOE)を導入することで,この疑問を情報理論の観点から検討する。
本研究の主な成果は,本フレームワークにおけるオンライン推定の統計的・計算的複雑さについて考察することである。
$\bullet$ 統計複雑性。
情報理論上,ブラックボックスのオフライン推定オラクルを用いてほぼ最適のオンライン推定誤差を実現するアルゴリズムが存在することを示し,OEOEフレームワークにおける最小値のほぼ8つの特徴を与える。
$\bullet$Computational complexity。
上記の保証は一般に計算効率のよい方法では達成できないが、条件密度推定の特別な場合について、洗練された特徴を与える: ブラックボックスによる計算効率の良いオンライン推定は、制限のないアルゴリズムで可能であれば可能である。
最後に,この結果を用いて,対話型意思決定のためのオフラインオラクル効率アルゴリズムを提案する。
関連論文リスト
- Online Distributional Regression [0.0]
大規模ストリーミングデータは、現代の機械学習アプリケーションで一般的である。
サプライチェーン管理、気象学、気象学など多くの分野が確率論的予測を用いている。
本稿では,正規化線形分布モデルのオンライン推定手法を提案する。
論文 参考訳（メタデータ） (2024-06-26T16:04:49Z) - Online non-parametric likelihood-ratio estimation by Pearson-divergence
functional minimization [55.98760097296213]
iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。
本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
論文 参考訳（メタデータ） (2023-11-03T13:20:11Z) - Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
半可観測マルコフ決定過程におけるオフライン強化学習(RL)について検討する。
本稿では,UnderlineProxy変数 underlinePessimistic UnderlinePolicy UnderlineOptimization (textttP3O)アルゴリズムを提案する。
textttP3Oは、確立されたデータセットを持つPOMDPのための証明可能な最初のオフラインRLアルゴリズムである。
論文 参考訳（メタデータ） (2022-05-26T19:13:55Z) - Scalable computation of prediction intervals for neural networks via
matrix sketching [79.44177623781043]
既存の不確実性推定アルゴリズムでは、モデルアーキテクチャとトレーニング手順を変更する必要がある。
本研究では、与えられたトレーニングされたニューラルネットワークに適用し、近似予測間隔を生成できる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-06T13:18:31Z) - Spatially Adaptive Online Prediction of Piecewise Regular Functions [12.18340575383456]
オンライン環境における部分的正規関数推定の問題点を考察する。
我々は、最近開発された睡眠専門家集約アルゴリズムと呼ばれるオンライン学習アルゴリズムの修正版を提案する。
論文 参考訳（メタデータ） (2022-03-30T18:15:56Z) - Grouped Variable Selection with Discrete Optimization: Computational and
Statistical Perspectives [9.593208961737572]
本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。
本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。
提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
論文 参考訳（メタデータ） (2021-04-14T19:21:59Z) - COMBO: Conservative Offline Model-Based Policy Optimization [120.55713363569845]
ディープニューラルネットワークのような複雑なモデルによる不確実性推定は困難であり、信頼性が低い。
我々は,サポート外状態動作の値関数を正規化するモデルベースオフラインRLアルゴリズムCOMBOを開発した。
従来のオフラインモデルフリーメソッドやモデルベースメソッドと比べて、comboは一貫してパフォーマンスが良いことが分かりました。
論文 参考訳（メタデータ） (2021-02-16T18:50:32Z) - Statistical Inference for Online Decision Making via Stochastic Gradient
Descent [31.103438051597887]
我々は、決定を下し、決定ルールをオンラインで更新するオンラインアルゴリズムを提案する。
効率的だけでなく、あらゆる種類のパラメトリック報酬モデルもサポートしている。
提案アルゴリズムと理論的結果は,ニュース記事レコメンデーションへのシミュレーションおよび実データ応用によって検証される。
論文 参考訳（メタデータ） (2020-10-14T18:25:18Z) - Probabilistic Case-based Reasoning for Open-World Knowledge Graph
Completion [59.549664231655726]
ケースベース推論(CBR)システムは,与えられた問題に類似した事例を検索することで,新たな問題を解決する。
本稿では,知識ベース(KB)の推論において,そのようなシステムが実現可能であることを示す。
提案手法は,KB内の類似エンティティからの推論パスを収集することにより,エンティティの属性を予測する。
論文 参考訳（メタデータ） (2020-10-07T17:48:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。