論文の概要: Non-Stochastic CDF Estimation Using Threshold Queries

• arxiv url: http://arxiv.org/abs/2301.05682v1
• Date: Fri, 13 Jan 2023 18:00:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-16 15:37:56.740622
• Title: Non-Stochastic CDF Estimation Using Threshold Queries
• Title（参考訳）: Threshold Queries を用いた非確率CDF推定
• Authors: Princewill Okoroafor, Vaishnavi Gupta, Robert Kleinberg, Eleanor Goh
• Abstract要約: 実験的な分布を2つの課題で推定する問題に取り組む。 まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。 第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
• 参考スコア（独自算出の注目度）: 3.6576781735746513
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Estimating the empirical distribution of a scalar-valued data set is a basic and fundamental task. In this paper, we tackle the problem of estimating an empirical distribution in a setting with two challenging features. First, the algorithm does not directly observe the data; instead, it only asks a limited number of threshold queries about each sample. Second, the data are not assumed to be independent and identically distributed; instead, we allow for an arbitrary process generating the samples, including an adaptive adversary. These considerations are relevant, for example, when modeling a seller experimenting with posted prices to estimate the distribution of consumers' willingness to pay for a product: offering a price and observing a consumer's purchase decision is equivalent to asking a single threshold query about their value, and the distribution of consumers' values may be non-stationary over time, as early adopters may differ markedly from late adopters. Our main result quantifies, to within a constant factor, the sample complexity of estimating the empirical CDF of a sequence of elements of $[n]$, up to $\varepsilon$ additive error, using one threshold query per sample. The complexity depends only logarithmically on $n$, and our result can be interpreted as extending the existing logarithmic-complexity results for noisy binary search to the more challenging setting where noise is non-stochastic. Along the way to designing our algorithm, we consider a more general model in which the algorithm is allowed to make a limited number of simultaneous threshold queries on each sample. We solve this problem using Blackwell's Approachability Theorem and the exponential weights method. As a side result of independent interest, we characterize the minimum number of simultaneous threshold queries required by deterministic CDF estimation algorithms.
• Abstract（参考訳）: スカラー値データセットの実証的分布の推定は、基本かつ基本的なタスクである。 本稿では,2つの難解な特徴をもつ実験的分布を推定する問題に取り組む。 まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。 第二に、データは独立で同一の分散を前提とせず、適応的敵を含む任意のプロセスでサンプルを生成することができる。 価格を提供し、消費者の購入判断を観察することは、その価値について単一のしきい値クエリを要求することと等価であり、初期採用者が後期採用者と著しく異なる可能性があるため、消費者の価値の分布は時間とともに非定常となる可能性がある。 我々の主な結果は、定数係数の範囲内で、サンプルあたりの1つのしきい値クエリを用いて、$[n]$、$\varepsilon$加法誤差までの要素列の経験CDFを推定する、サンプルの複雑さを定量化する。 この複雑性は、n$ に対数的にのみ依存し、この結果は、雑音の2次探索のための既存の対数-複雑度結果を、より困難な設定に拡張したものと解釈できる。 アルゴリズムの設計にあたっては、各サンプルに対して限られた数の同時しきい値クエリを行うことをアルゴリズムが許すより一般的なモデルを検討する。 この問題をブラックウェルのアプローチ可能性定理と指数重み法を用いて解く。 独立利害関係の副次として,決定論的CDF推定アルゴリズムで要求される同時しきい値クエリの最小数を特徴付ける。

関連論文リスト

• Efficiently learning and sampling multimodal distributions with data-based initialization [20.575122468674536]
  静止測度から少数のサンプルを与えられたマルコフ連鎖を用いて多重モーダル分布をサンプリングする問題を考察する。 マルコフ連鎖が$k$dのスペクトルギャップを持つ場合、静止分布からのサンプルは、静止測度からテレビ距離において$varepsilon$-closeの条件法則を持つサンプルを効率よく生成する。
  論文  参考訳（メタデータ） (2024-11-14T01:37:02Z)
• Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
  本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。 1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
  論文  参考訳（メタデータ） (2024-02-20T08:30:46Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Active Sampling of Multiple Sources for Sequential Estimation [92.37271004438406]
  本研究の目的は,パラメータを逐次推定するアクティブサンプリングアルゴリズムを設計し,信頼性の高い推定値を生成することである。 本稿では, エンフ条件推定コスト関数を導入し, 最近, トラクタブル解析を施した逐次推定手法を提案する。
  論文  参考訳（メタデータ） (2022-08-10T15:58:05Z)
• Convergence for score-based generative modeling with polynomial complexity [9.953088581242845]
  我々は、Scoreベースの生成モデルの背後にあるコアメカニックに対する最初の収束保証を証明した。 以前の作品と比較すると、時間的に指数関数的に増加するエラーや、次元の呪いに苦しむエラーは発生しない。 予測器・相関器はどちらの部分のみを使用するよりも収束性が高いことを示す。
  論文  参考訳（メタデータ） (2022-06-13T14:57:35Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Learning Entangled Single-Sample Distributions via Iterative Trimming [28.839136703139225]
  そこで本研究では, 反復トリミング標本に基づいて, 簡便かつ効率的な手法を解析し, トリミング標本集合上のパラメータを再推定する。 対数反復法では, 誤差が$lceil alpha n rceil$-th ノイズ点の雑音レベルにのみ依存する推定値が出力されることを示す。
  論文  参考訳（メタデータ） (2020-04-20T18:37:43Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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