論文の概要: Optimal randomized multilevel Monte Carlo for repeatedly nested expectations

• arxiv url: http://arxiv.org/abs/2301.04095v1
• Date: Tue, 10 Jan 2023 17:36:28 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-11 17:20:13.826124
• Title: Optimal randomized multilevel Monte Carlo for repeatedly nested expectations
• Title（参考訳）: 繰り返しネスト予測のための最適ランダム化マルチレベルモンテカルロ
• Authors: Yasa Syed, Guanyang Wang
• Abstract要約: 我々は「任意深さの帰納的推定」を意味する$mathsfREAD$と呼ばれるモンテカルロ推定器を提案する。 我々の推定器は最適計算コストが$mathcalO(varepsilon-2)$である。
• 参考スコア（独自算出の注目度）: 0.76146285961466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The estimation of repeatedly nested expectations is a challenging problem that arises in many real-world systems. However, existing methods generally suffer from high computational costs when the number of nestings becomes large. Fix any non-negative integer $D$ for the total number of nestings. Standard Monte Carlo methods typically cost at least $\mathcal{O}(\varepsilon^{-(2+D)})$ and sometimes $\mathcal{O}(\varepsilon^{-2(1+D)})$ to obtain an estimator up to $\varepsilon$-error. More advanced methods, such as multilevel Monte Carlo, currently only exist for $D = 1$. In this paper, we propose a novel Monte Carlo estimator called $\mathsf{READ}$, which stands for "Recursive Estimator for Arbitrary Depth.'' Our estimator has an optimal computational cost of $\mathcal{O}(\varepsilon^{-2})$ for every fixed $D$ under suitable assumptions, and a nearly optimal computational cost of $\mathcal{O}(\varepsilon^{-2(1 + \delta)})$ for any $0 < \delta < \frac12$ under much more general assumptions. Our estimator is also unbiased, which makes it easy to parallelize. The key ingredients in our construction are an observation of the problem's recursive structure and the recursive use of the randomized multilevel Monte Carlo method.
• Abstract（参考訳）: 繰り返しネストされた予測の推定は、多くの現実世界システムで発生する難しい問題である。 しかし,従来の手法ではネスト数が大きくなると計算コストが高くなるのが一般的である。 ネスティングの総数に対して、非負整数 $d$ を固定する。 標準モンテカルロ法は通常、少なくとも$\mathcal{o}(\varepsilon^{-(2+d)})$と$\mathcal{o}(\varepsilon^{-2(1+d)})$で、最大$\varepsilon$-errorの推定値を得る。 マルチレベルモンテカルロのようなより高度な手法は現在、$d = 1$ でのみ存在する。 本稿では, "任意の深さに対する再帰的推定子" を意味する "\mathsf{read}$" という新しいモンテカルロ推定器を提案する。 私たちの推定器は、適切な仮定の下で固定された$d$ に対して $\mathcal{o}(\varepsilon^{-2})$ の最適計算コストと、より一般的な仮定の下での任意の$0 < \delta < \frac12$ に対する$\mathcal{o}(\varepsilon^{-2(1 + \delta)}) のほぼ最適計算コストを持っています。 私たちの推定器もバイアスがなく、並列化が容易です。 我々の構築における重要な要素は、問題の再帰的構造とランダム化マルチレベルモンテカルロ法の再帰的利用の観察である。

関連論文リスト

• Second-Order Min-Max Optimization with Lazy Hessians [17.17389531402505]
  本稿では,凸凹型最小値最適化のための2次法について検討する。 計算コストは反復的にヘッセンによって削減できることを示す。
  論文  参考訳（メタデータ） (2024-10-12T15:30:17Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Universal Regular Conditional Distributions via Probability Measure-Valued Deep Neural Models [3.8073142980733]
  提案したフレームワークを用いて構築されたモデルはすべて、$C(mathcalX,mathcalP_1(mathcalY))$で密集している。 提案モデルはまた、ほとんどのランダム化された機械学習モデルに存在するアレラトリック不確かさを汎用的に表現できることも示している。
  論文  参考訳（メタデータ） (2021-05-17T11:34:09Z)
• Convergence of Sparse Variational Inference in Gaussian Processes Regression [29.636483122130027]
  計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
  論文  参考訳（メタデータ） (2020-08-01T19:23:34Z)
• Continuous Submodular Maximization: Beyond DR-Submodularity [48.04323002262095]
  最初に、バニラ座標の昇華の単純な変種を証明し、Coordinate-Ascent+ と呼ぶ。 次にCoordinate-Ascent++を提案し、同じ回数のイテレーションを実行しながら(1-1/e-varepsilon)$-approximationを保証する。 Coordinate-Ascent++の各ラウンドの計算は容易に並列化でき、マシン当たりの計算コストは$O(n/sqrtvarepsilon+nlog n)$である。
  論文  参考訳（メタデータ） (2020-06-21T06:57:59Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Moving Target Monte Carlo [0.0]
  我々は、移動目標モンテカルロ (MTMC) と呼ばれる新しい非マルコフサンプリングアルゴリズムを導入する。 後続分布$a_n(mathbfx)$の反復的に更新された近似を用いて、$n$-th繰り返しでの受け入れ率を構築する。 後続$p(mathbfx|mathbfd)$の真値は、候補$mathbfx$が受け入れられた場合にのみ計算される。
  論文  参考訳（メタデータ） (2020-03-10T17:38:36Z)

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

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