論文の概要: Approximate Function Evaluation via Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2203.10124v1
• Date: Fri, 18 Mar 2022 18:50:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-22 17:19:48.548050
• Title: Approximate Function Evaluation via Multi-Armed Bandits
• Title（参考訳）: マルチアームバンディットによる近似関数評価
• Authors: Tavor Z. Baharav, Gary Cheng, Mert Pilanci, David Tse
• Abstract要約: 既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
• 参考スコア（独自算出の注目度）: 51.146684847667125
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of estimating the value of a known smooth function $f$ at an unknown point $\boldsymbol{\mu} \in \mathbb{R}^n$, where each component $\mu_i$ can be sampled via a noisy oracle. Sampling more frequently components of $\boldsymbol{\mu}$ corresponding to directions of the function with larger directional derivatives is more sample-efficient. However, as $\boldsymbol{\mu}$ is unknown, the optimal sampling frequencies are also unknown. We design an instance-adaptive algorithm that learns to sample according to the importance of each coordinate, and with probability at least $1-\delta$ returns an $\epsilon$ accurate estimate of $f(\boldsymbol{\mu})$. We generalize our algorithm to adapt to heteroskedastic noise, and prove asymptotic optimality when $f$ is linear. We corroborate our theoretical results with numerical experiments, showing the dramatic gains afforded by adaptivity.
• Abstract（参考訳）: 未知の点 $\boldsymbol{\mu} \in \mathbb{R}^n$ において、既知の滑らかな関数 $f$ の値を推定する問題について検討する。 より大きな方向微分を持つ関数の方向に対応する$\boldsymbol{\mu}$のより頻繁な成分のサンプリングは、よりサンプル効率が高い。 しかし、$\boldsymbol{\mu}$は未知であるため、最適なサンプリング周波数も未知である。 我々は各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-\delta$は$\epsilon$の正確な推定値である$f(\boldsymbol{\mu})$を返す。 我々はヘテロスケダスティックノイズに適応するアルゴリズムを一般化し、$f$が線形である場合に漸近的最適性を証明する。 数値実験で理論結果を相関させ,適応性による劇的な向上を示す。

関連論文リスト

• Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
  シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。 適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
  論文  参考訳（メタデータ） (2024-11-08T17:10:38Z)
• Weighted least-squares approximation with determinantal point processes and generalized volume sampling [33.33724208084121]
  与えられた$m$-次元空間$V_m$の要素によって、函数を$L2$から近似する問題を考える。 近似は、ほぼ確実に$H$-normで測定された最高の近似誤差によって境界づけられていることを示す。
  論文  参考訳（メタデータ） (2023-12-21T17:34:18Z)
• Sharper Bounds for $\ell_p$ Sensitivity Sampling [56.45770306797584]
  まず, $ell_p$ 部分空間埋め込みを $p に対して高感度サンプリングする。 また、ルートレバレッジスコアサンプリングアルゴリズムは1leq p2$に対して約$d$を達成し、レバレッジスコアと感度サンプリングの組み合わせにより、約$d2/pmathfrak S2-4/p$を2pinftyで改善することを示した。
  論文  参考訳（メタデータ） (2023-06-01T14:27:28Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Sharper Rates and Flexible Framework for Nonconvex SGD with Client and Data Sampling [64.31011847952006]
  我々は、平均$n$スムーズでおそらくは非カラー関数のほぼ定常点を求める問題を再考する。 我々は$smallsfcolorgreen$を一般化し、事実上あらゆるサンプリングメカニズムで確実に動作するようにします。 我々は、スムーズな非カラー状態における最適境界の最も一般的な、最も正確な解析を提供する。
  論文  参考訳（メタデータ） (2022-06-05T21:32:33Z)
• Structure Learning in Graphical Models from Indirect Observations [17.521712510832558]
  本稿では、パラメータ法と非パラメトリック法の両方を用いて、Rp$における$p$次元ランダムベクトル$Xのグラフィカル構造を学習する。 温和な条件下では、グラフ構造推定器が正しい構造を得ることができることを示す。
  論文  参考訳（メタデータ） (2022-05-06T19:24:44Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Pareto Active Learning with Gaussian Processes and Adaptive Discretization [12.179548969182573]
  GPサンプリング関数の滑らかさと$(cal X,d)$の構造を利用して高速に学習するアルゴリズムを提案する。 本質的に、Adaptive $boldsymbolepsilon$-PALは木に基づく適応離散化技術を用いて、$boldsymbolepsilon$-accurate Paretoの設計セットを特定する。
  論文  参考訳（メタデータ） (2020-06-24T21:27:27Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)

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

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