論文の概要: 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つの用語が再びインスタンス依存的な意味で改善できないことを示す下界を定式化する。 この特徴付けの具体的な結果は、この問題の最適近似係数が普遍定数よりもはるかに大きいことである。 本稿では,線形関数近似を用いた政策評価問題に対する時間差学習手法の誤差を正確に特徴付けし,その最適性を確立した。

関連論文リスト

• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• On Bellman equations for continuous-time policy evaluation I: discretization and approximation [3.704688279256839]
  本研究では,連続時間拡散過程の離散的に観測された軌道から値関数を計算する問題について検討する。 離散時間強化学習と互換性のある,容易に実装可能な数値スキームに基づく新しいアルゴリズムのクラスを開発する。
  論文  参考訳（メタデータ） (2024-07-08T14:05:03Z)
• A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization [0.0]
  本稿では, 基底乱ベクトルの非線形関数の期待値と, 基底乱ベクトルに依存する他の関数の条件付き期待値を含む最適化問題を考察する。 本研究では, 外部関数が滑らかで, 内部関数が異なる非制約学習問題に対して, 特殊な単一スケール法を提案する。
  論文  参考訳（メタデータ） (2024-05-17T14:35:50Z)
• 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)
• 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)

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

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