論文の概要: STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals
- arxiv url: http://arxiv.org/abs/2505.22422v1
- Date: Wed, 28 May 2025 14:48:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-29 17:35:50.660645
- Title: STaR-Bets: Sequential Target-Recalculating Bets for Tighter Confidence Intervals
- Title（参考訳）: STaR-Bets:Tighter Confidence Intervalsのためのシーケンシャルターゲット再計算ベット
- Authors: Václav Voráček, Francesco Orabona,
- Abstract要約: 提案アルゴリズムは, 競合相手に対して実験的に優れる信頼区間を計算し, ベッティングに基づくアルゴリズムを提案する。
私たちの戦略はすべてのステップで最適な戦略を使用しますが、標準的な賭け方法は事前に一定の戦略を選択します。
また、信頼区間の幅は、$n$で減少する1+o(1)$因子まで最適であることを示す。
- 参考スコア（独自算出の注目度）: 9.319818839579137
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The construction of confidence intervals for the mean of a bounded random variable is a classical problem in statistics with numerous applications in machine learning and virtually all scientific fields. In particular, obtaining the tightest possible confidence intervals is vital every time the sampling of the random variables is expensive. The current state-of-the-art method to construct confidence intervals is by using betting algorithms. This is a very successful approach for deriving optimal confidence sequences, even matching the rate of law of iterated logarithms. However, in the fixed horizon setting, these approaches are either sub-optimal or based on heuristic solutions with strong empirical performance but without a finite-time guarantee. Hence, no betting-based algorithm guaranteeing the optimal $\mathcal{O}(\sqrt{\frac{\sigma^2\log\frac1\delta}{n}})$ width of the confidence intervals are known. This work bridges this gap. We propose a betting-based algorithm to compute confidence intervals that empirically outperforms the competitors. Our betting strategy uses the optimal strategy in every step (in a certain sense), whereas the standard betting methods choose a constant strategy in advance. Leveraging this fact results in strict improvements even for classical concentration inequalities, such as the ones of Hoeffding or Bernstein. Moreover, we also prove that the width of our confidence intervals is optimal up to an $1+o(1)$ factor diminishing with $n$. The code is available on~https://github.com/vvoracek/STaR-bets-confidence-interval.
- Abstract（参考訳）: 有界確率変数の平均に対する信頼区間の構成は、統計学において古典的な問題であり、機械学習やほぼすべての科学分野において多くの応用がある。
特に、確率変数のサンプリングが高価になるたびに、最も厳密な信頼区間を得ることが不可欠である。
信頼区間を構築するための現在の最先端手法は、ベッティングアルゴリズムを用いている。
これは、反復対数の法則に合致する最適な自信列を導出するための非常に成功したアプローチである。
しかし、固定地平線設定では、これらのアプローチは準最適か、強い経験的性能を持つヒューリスティック解に基づいているが、有限時間保証はない。
したがって、最適な $\mathcal{O}(\sqrt {\frac {\sigma^2\log\frac1\delta}{n}}) を保証するベッティングベースのアルゴリズムは知られていない。
この仕事はこのギャップを埋める。
提案アルゴリズムは, 競合相手に対して実験的に優れる信頼区間を計算し, ベッティングに基づくアルゴリズムを提案する。
私たちの賭け戦略は、(ある意味で)すべてのステップで最適な戦略を使用しますが、標準的な賭け方法は、事前に一定の戦略を選択します。
この事実を活用することで、ホーフディングやベルンシュタインのような古典的な濃度の不等式に対しても厳格な改善がもたらされる。
さらに、信頼区間の幅は、$n$で減少する1+o(1)$因子まで最適であることを示す。
コードはhttps://github.com/vvoracek/STaR-bets-confidence-intervalで公開されている。
関連論文リスト
- Tighter Confidence Bounds for Sequential Kernel Regression [3.683202928838613]
我々は、シーケンシャルカーネル回帰のための新しい信頼境界を確立するために、マーチンゲールテール不等式を使用する。
私たちの信頼境界は円錐プログラムを解くことで計算できるが、この素バージョンはすぐに非現実的になる。
信頼性境界が既存のものを置き換えると、KernelUCBアルゴリズムはより優れた経験的性能、最悪のパフォーマンス保証、それに匹敵する計算コストが得られます。
論文 参考訳（メタデータ） (2024-03-19T13:47:35Z) - High Confidence Level Inference is Almost Free using Parallel Stochastic
Optimization [16.38026811561888]
本稿では,高効率計算と高速収束による信頼区間構築に焦点をあてた新しい推論手法を提案する。
提案手法は,推定値の標準的な更新を超える最小限の計算量とメモリを必要とするため,推論処理はほとんどコストがかからない。
論文 参考訳（メタデータ） (2024-01-17T17:11:45Z) - Show Your Work with Confidence: Confidence Bands for Tuning Curves [51.12106543561089]
チューニング作業の関数としての曲線プロット検証性能。
そこで我々は,曲線のチューニングに有効な信頼帯域を構築するための最初の方法を提案する。
提案手法と比較し,提案手法の有効性を検証し,サンプルサイズの影響を解析し,モデルの比較に関するガイダンスを提供する。
論文 参考訳（メタデータ） (2023-11-16T00:50:37Z) - Huber-Robust Confidence Sequences [37.16361789841549]
信頼シーケンスは、逐次追跡可能な信頼区間であり、任意のデータ依存の停止時間で有効である。
非逐次的設定で達成された最適幅を達成するために,結果の信頼性シーケンスが得られたことを示す。
信頼シーケンスは、A/B/nテストやバンドイットで使用される一般的なツールであるため、これらの結果は、外れ値や敵の腐敗に対して堅牢なシーケンシャルな実験への扉を開く。
論文 参考訳（メタデータ） (2023-01-23T17:29:26Z) - Tight Concentrations and Confidence Sequences from the Regret of
Universal Portfolio [30.750408480772027]
Jun と Orabona [COLT'19] はオンライン賭けアルゴリズムの後悔の保証を時間的一様濃度の不等式に簡単に変換する方法を示した。
ミニマックスベッティングアルゴリズムの後悔は、新しい暗黙的な経験的時間一様集中を引き起こすことを示す。
論文 参考訳（メタデータ） (2021-10-27T00:44:32Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
敵対的レジリエントな分散最適化。
機械は独立して勾配を計算し 協力することができます
私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。
それは非常に実用的です:それはないときすべての前の方法の性能を改善します。
セッティングマシンがあります。
論文 参考訳（メタデータ） (2020-12-28T17:19:32Z) - CoinDICE: Off-Policy Confidence Interval Estimation [107.86876722777535]
強化学習における高信頼行動非依存のオフ政治評価について検討する。
様々なベンチマークにおいて、信頼区間推定が既存の手法よりも厳密で精度が高いことが示されている。
論文 参考訳（メタデータ） (2020-10-22T12:39:11Z) - Near-Optimal Confidence Sequences for Bounded Random Variables [5.901337162013615]
オンライン推論の根本的な問題は、成長する無限小サンプルサイズに対して均一に有効である信頼区間のシーケンスを提供することである。
我々は,ベンツクスの濃度値を利用して,有界確率変数のほぼ最適確率列を提供する。
得られた信頼性シーケンスは、合成カバレッジ問題と適応停止アルゴリズムへの応用の両方において好適であることが確認された。
論文 参考訳（メタデータ） (2020-06-09T02:50:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。