論文の概要: Approximating Pandora's Box with Correlations
- arxiv url: http://arxiv.org/abs/2108.12976v1
- Date: Mon, 30 Aug 2021 03:32:16 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-31 14:21:14.605335
- Title: Approximating Pandora's Box with Correlations
- Title（参考訳）: Pandoraのボックスを相関で近似する
- Authors: Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, Christos Tzamos
- Abstract要約: PandoraのBoxのよりシンプルなバージョンへの一般的な還元を示します。
本研究では,サポート$m$が明示的に与えられた分布の場合と,製品分布が$m$の混合の場合の2つの相関関係について検討する。
- 参考スコア（独自算出の注目度）: 13.672870739536231
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Pandora's Box problem asks to find a search strategy over $n$
alternatives given stochastic information about their values, aiming to
minimize the sum of the search cost and the value of the chosen alternative.
Even though the case of independently distributed values is well understood,
our algorithmic understanding of the problem is very limited once the
independence assumption is dropped.
Our work aims to characterize the complexity of approximating the Pandora's
Box problem under correlated value distributions. To that end, we present a
general reduction to a simpler version of Pandora's Box, that only asks to find
a value below a certain threshold, and eliminates the need to reason about
future values that will arise during the search. Using this general tool, we
study two cases of correlation; the case of explicitly given distributions of
support $m$ and the case of mixtures of $m$ product distributions.
$\bullet$ In the first case, we connect Pandora's Box to the well studied
problem of Optimal Decision Tree, obtaining an $O(\log m)$ approximation but
also showing that the problem is strictly easier as it is equivalent (up to
constant factors) to the Uniform Decision Tree problem.
$\bullet$ In the case of mixtures of product distributions, the problem is
again related to the noisy variant of Optimal Decision Tree which is
significantly more challenging. We give a constant-factor approximation that
runs in time $n^{ \tilde O( m^2/\varepsilon^2 ) }$ for $m$ mixture components
whose marginals on every alternative are either identical or separated in TV
distance by $\varepsilon$.
- Abstract（参考訳）: pandoraのボックス問題は、それらの値に関する確率的な情報から、n$以上の代替品の探索戦略を見つけ、検索コストと選択された代替品の値の合計を最小化することを目的としている。
独立分散値の場合にはよく理解されているが、独立性仮定を落とせば、問題のアルゴリズム的な理解は非常に限定される。
本研究は,pandoraのボックス問題を相関値分布下で近似する複雑さを特徴付けることを目的としている。
そのために我々は,pandoraのボックスの単純なバージョンに対して,特定のしきい値未満の値を求めるだけで,検索中に発生する将来の値について判断する必要をなくす,汎用的な還元を提案する。
この汎用ツールを用いて,サポート$m$の明示的な分布の場合と製品分布$m$の混合の場合の2つの相関関係について検討した。
第一のケースでは、pandoraのボックスを最適決定木のよく研究された問題に結びつけ、o(\log m)$の近似を得るが、一様決定木問題と同値である(定数係数まで)ので、問題は厳密に容易であることを示す。
$\bullet$ 製品分布の混合の場合、問題は、非常に難しい最適決定木(Optimal Decision Tree)のうるさい変種(noisy variant)に再び関係している。
n^{ \tilde o(m^2/\varepsilon^2 ) }$ for $m$ mixed components 任意の選択肢の辺数が同じか、テレビの間隔で$\varepsilon$ で区切られるかのいずれかである。
関連論文リスト
- Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Robust Distribution Learning with Local and Global Adversarial Corruptions [17.22168727622332]
誤差を$sqrtvarepsilon k + rho + tildeO(dsqrtkn-1/(k lor2)$で有界な共分散を持つ場合、効率的な有限サンプルアルゴリズムを開発する。
我々の効率的な手順は、理想的だが難解な2-ワッサーシュタイン射影推定器の新たなトレースノルム近似に依存する。
論文 参考訳（メタデータ） (2024-06-10T17:48:36Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。
これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文 参考訳（メタデータ） (2023-10-13T03:08:59Z) - Privately Estimating a Gaussian: Efficient, Robust and Optimal [6.901744415870126]
純微分プライバシー(DP)モデルと近似微分プライバシー(DP)モデルの両方において、ガウス分布をプライベートに推定する効率的なアルゴリズムを提供する。
純粋なDP設定では、未知の$d$次元ガウス分布を任意の全変分誤差まで推定する効率的なアルゴリズムを与える。
平均推定の特別な場合、我々のアルゴリズムは$widetilde O(d1.5)$の最適なサンプル複雑性を達成し、以前の作業から$widetilde O(d1.5)$のバウンドを改善する。
論文 参考訳（メタデータ） (2022-12-15T18:27:39Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Bandit Algorithms for Prophet Inequality and Pandora's Box [13.709418181148148]
マルチアーメッド・バンディットモデルにおける預言不等式とPandoraのボックス問題について検討した。
我々の結果は、予言の不平等とPandoraのBoxの両面で、ほぼ最適の$tildeO(mathsfpoly(n)sqrtT)$トータル後悔アルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-11-16T00:10:35Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - The Bethe and Sinkhorn Permanents of Low Rank Matrices and Implications
for Profile Maximum Likelihood [33.51964370430905]
我々はベーテとシンクホーンの永久体の近似の質に関する新しい限界を提供する。
先行研究における凸緩和とベーテ近似とシンクホーン近似との驚くべき関係を確立する。
論文 参考訳（メタデータ） (2020-04-06T06:40:03Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。