論文の概要: Approximating Pandora's Box with Correlations
- arxiv url: http://arxiv.org/abs/2108.12976v4
- Date: Fri, 21 Jul 2023 18:16:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-26 01:40:48.311733
- Title: Approximating Pandora's Box with Correlations
- Title（参考訳）: Pandoraのボックスを相関で近似する
- Authors: Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, Christos Tzamos
- Abstract要約: 本稿では,次にどのボックスを訪問するかを適応的に選択できる最適ポリシーの近似の複雑さについて検討する。
本研究の主な成果は,一様決定木(UDT)問題に対するPBの近似保存等価性を確立することである。
また、より簡潔に値上の分布が$m$の積分布の混合として与えられる場合についても検討する。
- 参考スコア（独自算出の注目度）: 14.284880952600995
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the classic Pandora's Box (PB) problem under correlated
distributions on the box values. Recent work of arXiv:1911.01632 obtained
constant approximate algorithms for a restricted class of policies for the
problem that visit boxes in a fixed order. In this work, we study the
complexity of approximating the optimal policy which may adaptively choose
which box to visit next based on the values seen so far.
Our main result establishes an approximation-preserving equivalence of PB to
the well studied Uniform Decision Tree (UDT) problem from stochastic
optimization and a variant of the Min-Sum Set Cover ($\text{MSSC}_f$) problem.
For distributions of support $m$, UDT admits a $\log m$ approximation, and
while a constant factor approximation in polynomial time is a long-standing
open problem, constant factor approximations are achievable in subexponential
time (arXiv:1906.11385). Our main result implies that the same properties hold
for PB and $\text{MSSC}_f$.
We also study the case where the distribution over values is given more
succinctly as a mixture of $m$ product distributions. This problem is again
related to a noisy variant of the 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 ) }$ when the mixture components on every box
are either identical or separated in TV distance by $\varepsilon$.
- Abstract（参考訳）: 古典的なpandora's box (pb) 問題をボックス値の相関分布の下で再検討する。
arXiv:1911.01632の最近の研究は、ボックスを一定の順序で訪問する問題に対する制限されたポリシーのクラスに対して、一定の近似アルゴリズムを得た。
本研究では,これまで見てきた値に基づいて,次に訪れるボックスを適応的に選択できる最適ポリシーの近似の複雑さについて検討する。
本研究の主な成果は,確率的最適化による一様決定木(UDT)問題に対するPBの近似保存等価性を確立し,Min-Sum Set Cover(\text{MSSC}_f$)問題の変種を定式化することである。
サポート$m$の分布に対して、UDTは$\log m$近似を認め、多項式時間における定数係数近似は長年の開問題であるが、定数係数近似は半周期時間(arXiv:1906.11385)で達成可能である。
私たちの主な結果は、PBと$\text{MSSC}_f$のプロパティが同じであることを示している。
また、値の分布がより簡潔に$m$の製品分布の混合物として与えられる場合についても検討する。
この問題は、さらに困難である最適決定木(Optimal Decision Tree)のうるさい変種と再び関係している。
時間$n^{ \tilde O(m^2/\varepsilon^2 ) }$ 各ボックス上の混合成分が同一またはテレビ距離で$\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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。