論文の概要: 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) - Stochastic Ratios Tracking Algorithm for Large Scale Machine Learning
Problems [0.7614628596146599]
古典的なSGDフレームワークにおける適応的なステップ長選択のための新しいアルゴリズムを提案する。
妥当な条件下では、アルゴリズムは十分に確立された理論的な要件に従ってステップ長を生成する。
このアルゴリズムは,手動チューニングから得られる最良ステップ長に匹敵するステップ長を生成することができることを示す。
論文 参考訳(メタデータ) (2023-05-17T06:22:11Z) - A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。
どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。
特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
論文 参考訳(メタデータ) (2023-04-21T13:43:06Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-21T00:17:24Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-31T19:14:30Z) - 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) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳(メタデータ) (2020-12-13T04:47:37Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳(メタデータ) (2020-07-06T15:20:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。