論文の概要: Resolution Limits of Non-Adaptive 20 Questions Search for a Moving Target

• arxiv url: http://arxiv.org/abs/2206.08884v1
• Date: Tue, 14 Jun 2022 02:20:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-26 12:17:12.791300
• Title: Resolution Limits of Non-Adaptive 20 Questions Search for a Moving Target
• Title（参考訳）: 非適応20問の解答限界 : 移動対象の探索
• Authors: Lin Zhou and Alfred Hero
• Abstract要約: 本研究では,初期位置と速度の不明な単位立方体上での移動対象の非適応探索戦略を,一様定速度モデルの下で検討する。 非漸近的および有界性を導出することにより、最適な非適応的クエリ手順の最小解を有限個のクエリで特徴付ける。 この結果を証明するために、チャネル符号化、有限ブロック長情報理論からのアイデアの借用、および量子化された対象軌道の数に基づく構成境界について、現状の問題点を考察する。
• 参考スコア（独自算出の注目度）: 8.767398758618793
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Using the 20 questions estimation framework with query-dependent noise, we study non-adaptive search strategies for a moving target over the unit cube with unknown initial location and velocities under a piecewise constant velocity model. In this search problem, there is an oracle who knows the instantaneous location of the target at any time. Our task is to query the oracle as few times as possible to accurately estimate the location of the target at any specified time. We first study the case where the oracle's answer to each query is corrupted by discrete noise and then generalize our results to the case of additive white Gaussian noise. In our formulation, the performance criterion is the resolution, which is defined as the maximal $L_\infty$ distance between the true locations and estimated locations. We characterize the minimal resolution of an optimal non-adaptive query procedure with a finite number of queries by deriving non-asymptotic and asymptotic bounds. Our bounds are tight in the first-order asymptotic sense when the number of queries satisfies a certain condition and our bounds are tight in the stronger second-order asymptotic sense when the target moves with a constant velocity. To prove our results, we relate the current problem to channel coding, borrow ideas from finite blocklength information theory and construct bounds on the number of possible quantized target trajectories.
• Abstract（参考訳）: 問合せ依存雑音を伴う20問推定フレームワークを用いて,未知の初期位置と速度を有する単位立方体上の移動対象の非適応探索戦略を区分的定数速度モデルを用いて検討する。 この検索問題では、ターゲットの即時位置をいつでも知っているオラクルがいます。 我々のタスクは、特定の時間にターゲットの位置を正確に推定するために、できるだけ数回オラクルに問い合わせることです。 まず,各クエリに対するオラクルの回答が離散ノイズによって損なわれるケースを調査し,その結果を白色ガウスノイズに一般化した。 我々の定式化では、性能基準は解像度であり、真の位置と推定位置の間の最大$l_\infty$距離として定義される。 非漸近的および漸近的境界を導出することにより、有限数のクエリで最適な非適応的クエリ手順の最小解法を特徴付ける。 私たちの境界は、クエリ数が一定の条件を満たす場合の1次漸近的な感覚と、目標が一定の速度で移動する場合のより強い2次漸近的な感覚とが密接である。 この結果を証明するために、チャネル符号化、有限ブロック長情報理論からのアイデアの借用、および量子化された対象軌道の数に基づく構成境界について、現状の問題点を考察する。

関連論文リスト

• A Finite-Horizon Approach to Active Level Set Estimation [0.7366405857677227]
  レベルセット推定(LSE)における空間サンプリングの文脈におけるアクティブラーニングの問題点について考察する。 1次元でLSEを行うための有限水平探索法を提案するが、最終的な推定誤差と一定数のサンプルの移動距離のバランスは最適である。 結果の最適化問題をクローズドな方法で解き、その結果のポリシーが既存のアプローチを一般化することを示す。
  論文  参考訳（メタデータ） (2023-10-18T14:11:41Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  本研究では,スムーズな損失関数に対する期待値である非バッチ最適化問題について検討する。 我々の研究は、学習率と運動量パラメータを適応的に設定する新しいアプローチとともに、STORMアルゴリズムの上に構築されている。
  論文  参考訳（メタデータ） (2021-11-01T15:43:36Z)
• An Automated Approach to Causal Inference in Discrete Settings [8.242194776558895]
  本稿では,効率的な二重緩和法と空間分岐結合法を用いて因果効果を自動的に結合するアルゴリズムを提案する。 このアルゴリズムは、許容可能なデータ生成プロセスを探索し、利用可能な情報と最も正確な範囲を出力する。 これは、不完全境界を特徴付ける$epsilon$-sharpnessと呼ばれる追加の保証を提供する。
  論文  参考訳（メタデータ） (2021-09-28T03:55:32Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Optimal Sequential Detection of Signals with Unknown Appearance and Disappearance Points in Time [64.26593350748401]
  本論文は、変化の期間が有限で未知であると仮定して、逐次的な変化点検出問題に対処する。 我々は、所定の時間(または空間)ウィンドウにおける最小検出確率を最大化する信頼性の高い最大変更検出基準に焦点を当てる。 FMAアルゴリズムは、光学画像中の衛星のかすかなストリークを検出するために応用される。
  論文  参考訳（メタデータ） (2021-02-02T04:58:57Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Query Complexity of k-NN based Mode Estimation [4.821253146561989]
  与えられた n 個の点のデータセットに対して、その点を最小の k 番目の近傍距離で同定する問題について検討する。 本研究では,信頼区間のアイデアに基づく逐次学習アルゴリズムを設計し,どのクエリをオラクルに送信するかを適応的に決定し,高い確率で問題を正しく解けるようにした。
  論文  参考訳（メタデータ） (2020-10-26T11:32:08Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic Approximation with Markov Noise: Analysis and applications in reinforcement learning [0.0]
  マルコフ雑音によって駆動される2つの時間スケール近似の収束解析を初めて提示する。 両方の時間スケールにおける差分包摂を限定することで、フレームワークの挙動を分析する。 ポリシ評価アルゴリズムの関数近似における最初の情報的誤差境界を求める。
  論文  参考訳（メタデータ） (2020-04-08T03:59:21Z)

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

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