論文の概要: Optimal oracle inequalities for solving projected fixed-point equations
- arxiv url: http://arxiv.org/abs/2012.05299v1
- Date: Wed, 9 Dec 2020 20:19:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-16 02:06:37.436639
- Title: Optimal oracle inequalities for solving projected fixed-point equations
- Title(参考訳): 射影不動点方程式を解くための最適オラクル不等式
- Authors: Wenlong Mou, Ashwin Pananjady, Martin J. Wainwright
- Abstract要約: ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
- 参考スコア(独自算出の注目度): 53.31620399640334
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear fixed point equations in Hilbert spaces arise in a variety of
settings, including reinforcement learning, and computational methods for
solving differential and integral equations. We study methods that use a
collection of random observations to compute approximate solutions by searching
over a known low-dimensional subspace of the Hilbert space. First, we prove an
instance-dependent upper bound on the mean-squared error for a linear
stochastic approximation scheme that exploits Polyak--Ruppert averaging. This
bound consists of two terms: an approximation error term with an
instance-dependent approximation factor, and a statistical error term that
captures the instance-specific complexity of the noise when projected onto the
low-dimensional subspace. Using information theoretic methods, we also
establish lower bounds showing that both of these terms cannot be improved,
again in an instance-dependent sense. A concrete consequence of our
characterization is that the optimal approximation factor in this problem can
be much larger than a universal constant. We show how our results precisely
characterize the error of a class of temporal difference learning methods for
the policy evaluation problem with linear function approximation, establishing
their optimality.
- Abstract(参考訳): ヒルベルト空間における線形不動点方程式は、強化学習や微分方程式と積分方程式の解法を含む様々な設定で生じる。
ヒルベルト空間の既知の低次元部分空間を探索することにより、ランダムな観測の集合を用いて近似解を計算する方法を検討する。
まず,polyak-ruppert平均化を利用した線形確率近似スキームにおける平均二乗誤差のインスタンス依存上界を証明した。
この境界は、インスタンス依存近似係数を持つ近似誤差項と、低次元部分空間に投影されたときの雑音のインスタンス固有の複雑さを捉える統計的誤差項の2つの項からなる。
また,情報理論的な手法を用いて,これら2つの用語が再びインスタンス依存的な意味で改善できないことを示す下界を定式化する。
この特徴付けの具体的な結果は、この問題の最適近似係数が普遍定数よりもはるかに大きいことである。
本稿では,線形関数近似を用いた政策評価問題に対する時間差学習手法の誤差を正確に特徴付けし,その最適性を確立した。
関連論文リスト
- Approximation Theory, Computing, and Deep Learning on the Wasserstein
Space [0.6445605125467574]
有限標本から無限次元空間における近似関数の挑戦について検討する。
我々の特に焦点はワッサーシュタイン距離関数(英語版)(Wasserstein distance function)に集中しており、これは関連する例である。
数値的な実装では,ニューラルネットワークをベース関数として適切に設計し,基礎関数として機能する。
論文 参考訳(メタデータ) (2023-10-30T13:59:47Z) - Multistage Stochastic Optimization via Kernels [3.7565501074323224]
我々は,多段階最適化問題に対する非パラメトリック,データ駆動,トラクタブルアプローチを開発した。
本稿では,提案手法が最適に近い平均性能で決定ルールを生成することを示す。
論文 参考訳(メタデータ) (2023-03-11T23:19:32Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳(メタデータ) (2023-01-16T02:57:37Z) - Compressive Fourier collocation methods for high-dimensional diffusion
equations with periodic boundary conditions [7.80387197350208]
高次元偏微分方程式(英: High-dimensional partial Differential Equations, PDE)は、ファイナンスから計算化学まで多岐にわたる数学モデリングツールである。
これらのPDEを解くための標準的な数値技術は、典型的には次元の呪いの影響を受けている。
高次元におけるスパース関数近似の最近の進歩に触発されて、圧縮フーリエコロケーションと呼ばれる新しい手法を提案する。
論文 参考訳(メタデータ) (2022-06-02T19:11:27Z) - Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
ガウスのプロセスはデータセットのサイズとともに違法にスケールする。
多くの近似法が開発されており、必然的に近似誤差を導入している。
この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。
本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
論文 参考訳(メタデータ) (2022-05-30T22:16:25Z) - Experimental Design for Linear Functionals in Reproducing Kernel Hilbert
Spaces [102.08678737900541]
線形汎関数に対するバイアス認識設計のためのアルゴリズムを提供する。
準ガウス雑音下での固定および適応設計に対する漸近的でない信頼集合を導出する。
論文 参考訳(メタデータ) (2022-05-26T20:56:25Z) - On efficient algorithms for computing near-best polynomial
approximations to high-dimensional, Hilbert-valued functions from limited
samples [1.0650780147044159]
スパース近似は、限られたサンプルから滑らかで高次元の関数を近似するのに欠かせないものとなっている。
本稿では,指数的あるいは代数的収束率を主張するアルゴリズムと理論的保証と,サンプリング,アルゴリズム的,物理的離散化誤差に対する頑健性を紹介する。
論文 参考訳(メタデータ) (2022-03-25T20:56:07Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳(メタデータ) (2022-01-21T02:46:57Z) - Accelerated and instance-optimal policy evaluation with linear function
approximation [17.995515643150657]
既存のアルゴリズムはこれらの下界の少なくとも1つと一致しない。
我々は,両下界を同時に一致させる高速時間差分アルゴリズムを開発し,インスタンス最適性という強い概念を実現する。
論文 参考訳(メタデータ) (2021-12-24T17:21:04Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳(メタデータ) (2020-07-07T21:26:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。