論文の概要: Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health

• arxiv url: http://arxiv.org/abs/2402.01995v6
• Date: Sat, 19 Oct 2024 04:39:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:11:10.526178
• Title: Online Uniform Sampling: Randomized Learning-Augmented Approximation Algorithms with Application to Digital Health
• Title（参考訳）: オンライン一様サンプリング:ランダム化学習強化近似アルゴリズムとデジタルヘルスへの応用
• Authors: Xueqing Liu, Kyra Gan, Esmaeil Keyvanshokooh, Susan Murphy,
• Abstract要約: オンライン一様サンプリング(OUS)の新たな課題として,未知の意思決定時間に一様にサンプリング予算を分散させることが目的である。 OUS問題では、アルゴリズムは予算$b$とタイムホライズ$T$を与えられ、敵は[b,T]$の値$tau*を選択し、それをオンラインに公開する。 この問題に対して設計された最初のランダム化アルゴリズムを提示し、その後、学習拡張を組み込むように拡張する。
• 参考スコア（独自算出の注目度）: 3.534690532561709
• License:
• Abstract: Motivated by applications in digital health, this work studies the novel problem of online uniform sampling (OUS), where the goal is to distribute a sampling budget uniformly across unknown decision times. In the OUS problem, the algorithm is given a budget $b$ and a time horizon $T$, and an adversary then chooses a value $\tau^* \in [b,T]$, which is revealed to the algorithm online. At each decision time $i \in [\tau^*]$, the algorithm must determine a sampling probability that maximizes the budget spent throughout the horizon, respecting budget constraint $b$, while achieving as uniform a distribution as possible over $\tau^*$. We present the first randomized algorithm designed for this problem and subsequently extend it to incorporate learning augmentation. We provide worst-case approximation guarantees for both algorithms, and illustrate the utility of the algorithms through both synthetic experiments and a real-world case study involving the HeartSteps mobile application. Our numerical results show strong empirical average performance of our proposed randomized algorithms against previously proposed heuristic solutions.
• Abstract（参考訳）: 本研究は,デジタルヘルスの応用により,未知の意思決定時間に一様にサンプリング予算を分散することを目的とした,オンライン一様サンプリング(OUS)の新たな問題を研究する。 ous問題では、アルゴリズムに予算$b$と時間水平線$T$が与えられ、敵が$\tau^* \in [b,T]$を選択し、それをオンラインに公開する。 i \in [\tau^*]$ の決定時間毎に、アルゴリズムは、$\tau^*$ 以上の分布を均一に達成しつつ、水平線全体にわたって費やされた予算を最大化するサンプリング確率を決定する必要がある。 この問題に対して設計された最初のランダム化アルゴリズムを提示し、その後、学習拡張を組み込むように拡張する。 両アルゴリズムの最悪の近似保証を提供し、人工実験とHeartStepsモバイルアプリケーションを含む実世界のケーススタディの両方を通して、アルゴリズムの有用性を説明する。 提案手法は,従来提案されていたヒューリスティック解に対して,ランダム化アルゴリズムの強い経験的平均性能を示す。

関連論文リスト

• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• On Private Online Convex Optimization: Optimal Algorithms in $\ell_p$-Geometry and High Dimensional Contextual Bandits [9.798304879986604]
  本研究では,分散分布からサンプリングしたストリーミングデータを用いてDPの凸最適化問題について検討し,逐次到着する。 また、プライベート情報に関連するパラメータを更新し、新しいデータ(しばしばオンラインアルゴリズム)に基づいてリリースする連続リリースモデルについても検討する。 提案アルゴリズムは,1pleq 2$のときの最適余剰リスクと,2pleqinfty$のときの非プライベートな場合の最先端の余剰リスクを線形時間で達成する。
  論文  参考訳（メタデータ） (2022-06-16T12:09:47Z)
• An optimal scheduled learning rate for a randomized Kaczmarz algorithm [1.2183405753834562]
  そこで本研究では,Ax 近似 b + varepsilon$ を解くため,学習速度が無作為化 Kaczmarz アルゴリズムの性能にどのように影響するかを検討する。
  論文  参考訳（メタデータ） (2022-02-24T17:38:24Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs [0.0]
  これは、基本層のすべての可能な成層集合から最適成層を探索するサンプル問題である。 それぞれのソリューションのコストを評価するのに 費用がかかります 上記のアルゴリズムと最近の3つのアルゴリズムの多段階組み合わせを比較し、ソリューションコスト、評価時間、トレーニング時間を報告する。
  論文  参考訳（メタデータ） (2021-08-18T08:41:58Z)
• A PAC algorithm in relative precision for bandit problem with costly sampling [0.0]
  本稿ではまず,この離散最適化問題に対して,相対的精度でほぼ正解(PAC)を得るための単純帯域幅アルゴリズムを提案する。 また、同一の保証付きPACソリューションを提供する適応的帯域幅アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-30T09:22:25Z)
• Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
  生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。 我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。 標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
  論文  参考訳（メタデータ） (2020-07-06T15:20:17Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。 マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
  論文  参考訳（メタデータ） (2020-03-06T16:17:24Z)

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

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