論文の概要: Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent
- arxiv url: http://arxiv.org/abs/2603.10184v1
- Date: Tue, 10 Mar 2026 19:27:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-12 16:22:32.665992
- Title: Stability and Robustness via Regularization: Bandit Inference via Regularized Stochastic Mirror Descent
- Title（参考訳）: 規則化による安定性とロバスト性:正規化確率鏡による帯域推定
- Authors: Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury, Koulik Khamaru,
- Abstract要約: 最近の研究で、安定性は適応性の下での有効な推論に十分な条件であると認識されている。
本稿では,ミラー降下に基づく帯域幅アルゴリズムの安定性の体系的理論を考案する。
正規化されたEXP3の変種は、敵の腐敗がある場合でも経験的アームの正常性を維持する。
- 参考スコア（独自算出の注目度）: 2.0999222360659613
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Statistical inference with bandit data presents fundamental challenges due to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability as a sufficient condition for valid inference under adaptivity. This paper develops a systematic theory of stability for bandit algorithms based on stochastic mirror descent, a broad algorithmic framework that includes the widely-used EXP3 algorithm as a special case. Our contributions are threefold. First, we establish a general stability criterion: if the average iterates of a stochastic mirror descent algorithm converge in ratio to a non-random probability vector, then the induced bandit algorithm is stable. This result provides a unified lens for analyzing stability across diverse algorithmic instantiations. Second, we introduce a family of regularized-EXP3 algorithms employing a log-barrier regularizer with appropriately tuned parameters. We prove that these algorithms satisfy our stability criterion and, as an immediate corollary, that Wald-type confidence intervals for linear functionals of the mean parameter achieve nominal coverage. Notably, we show that the same algorithms attain minimax-optimal regret guarantees up to logarithmic factors, demonstrating that inference-enabling stability and learning efficiency are compatible objectives within the mirror descent framework. Third, we establish robustness to corruption: a modified variant of regularized-EXP3 maintains asymptotic normality of empirical arm means even in the presence of $o(T^{1/2})$ adversarial corruptions. This stands in sharp contrast to other stable algorithms such as UCB, which suffer linear regret even under logarithmic levels of corruption.
- Abstract（参考訳）: バンディットデータによる統計的推測は、古典的漸近理論に基づく独立性の仮定に反する適応サンプリングによる根本的な問題を示す。
最近の研究で、安定性は適応性の下での有効な推論に十分な条件であると認識されている。
本稿では,広範に使用されているEXP3アルゴリズムを特殊なケースとして含む,確率的ミラー降下に基づく帯域幅アルゴリズムの安定性の体系的理論を開発する。
私たちの貢献は3倍です。
まず、確率ミラー降下アルゴリズムの平均的な反復が非ランダム確率ベクトルに比例するならば、誘導帯域幅アルゴリズムは安定である。
この結果は、多様なアルゴリズムのインスタンス化における安定性を解析するための統一レンズを提供する。
第2に、適切に調整されたパラメータを持つログバリア正規化器を用いた正規化EXP3アルゴリズムのファミリーを導入する。
我々はこれらのアルゴリズムが我々の安定性基準を満たすことを証明し、即ち、平均パラメータの線形汎関数に対するウォルド型信頼区間が名目的カバレッジを達成することを証明した。
特に,同アルゴリズムが最小最適後悔を達成し,対数的要因まで保証できることを示し,鏡下降フレームワーク内での推論応答の安定性と学習効率が相反することを示す。
第3に、汚職に対する堅牢性を確立する:正規化-EXP3の修正版は、$o(T^{1/2})$逆汚職が存在する場合でも、経験的アームの漸近正規性を維持する。
これは、UDBのような他の安定なアルゴリズムとは対照的であり、対数レベルの汚職でも線形後悔に苦しむ。
関連論文リスト
- Efficient Inference after Directionally Stable Adaptive Experiments [47.32051320630248]
本稿では,帯域幅などの適応データ収集後の経路微分可能な対象の推測について検討する。
本稿では,従来の目標パラメトリック安定性条件よりも厳格に弱い,新たな目標固有条件である指向性安定性を導入する。
論文 参考訳（メタデータ） (2026-02-25T01:09:18Z) - Avoiding the Price of Adaptivity: Inference in Linear Contextual Bandits via Stability [2.5782420501870296]
安定性と統計的効率は、単一の文脈的帯域幅法で共存することができると論じる。
本アルゴリズムは,対数的因子に最適化された最小限の誤差保証を実現する。
論文 参考訳（メタデータ） (2025-12-23T13:53:53Z) - Statistical Inference under Adaptive Sampling with LinUCB [15.167069362020426]
線形帯域に対する線形上信頼境界(LinUCB)アルゴリズムは安定性という特性を満たすことを示す。
我々は、LinUCBアルゴリズムの中央極限定理を確立し、推定誤差の極限分布の正規性を確立する。
論文 参考訳（メタデータ） (2025-11-28T21:48:18Z) - On Instability of Minimax Optimal Optimism-Based Bandit Algorithms [2.5782420501870296]
マルチアーム・バンディット(MAB)アルゴリズムは適応的で非i.d.な性質のため困難である。
楽観主義原理に基づく広帯域アルゴリズムの安定性特性を解析する。
MOSS, Anytime-MOSS, Vanilla-MOSS, ADA-UCB, OC-UCB, KL-MOSS, KL-UCB-SWITCH, Anytime KL-UCB-SWITCH などのミニマックス最適UPB型アルゴリズムが不安定であることを示す。
論文 参考訳（メタデータ） (2025-11-24T04:23:26Z) - The Relative Instability of Model Comparison with Cross-validation [65.90853456199493]
クロスバリデーションは、安定した機械学習アルゴリズムのテストエラーに対する信頼区間を提供するために使用できる。
相対安定性は、単純なアルゴリズムであっても、既存の安定性の結果から容易に導き出すことはできない。
ソフトスレッディングまたはラッソを用いた場合、試験誤差差に対するCV信頼区間の無効性を実証的に確認する。
論文 参考訳（メタデータ） (2025-08-06T12:54:56Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Stability and Generalization for Stochastic Recursive Momentum-based Algorithms for (Strongly-)Convex One to $K$-Level Stochastic Optimizations [20.809499420384256]
STORMベースのアルゴリズムは、K$レベル(K geq 3$)の最適化問題を解決するために広く開発されている。
本稿では,STORMに基づく3つの代表的なアルゴリズムを包括的に分析する。
論文 参考訳（メタデータ） (2024-07-07T07:07:04Z) - Exploring the Algorithm-Dependent Generalization of AUPRC Optimization
with List Stability [107.65337427333064]
AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。
本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。
3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
論文 参考訳（メタデータ） (2022-09-27T09:06:37Z) - Private Robust Estimation by Stabilizing Convex Relaxations [22.513117502159922]
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
$(epsilon, delta)$-differentially private (DP)
論文 参考訳（メタデータ） (2021-12-07T07:47:37Z) - Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses [52.039438701530905]
任意のリプシッツ非平滑凸損失に対して,数種類の勾配勾配降下(SGD)に対して,鋭い上下境界を与える。
我々の限界は、極端に過剰な集団リスクを伴う、微分的にプライベートな非平滑凸最適化のための新しいアルゴリズムを導出することを可能にする。
論文 参考訳（メタデータ） (2020-06-12T02:45:21Z) - Distributionally Robust Bayesian Optimization [121.71766171427433]
そこで本研究では,ゼロ次雑音最適化のための分散ロバストなベイズ最適化アルゴリズム(DRBO)を提案する。
提案アルゴリズムは, 種々の設定において, 線形に頑健な後悔を確実に得る。
提案手法は, 実世界のベンチマークと実世界のベンチマークの両方において, 頑健な性能を示す。
論文 参考訳（メタデータ） (2020-02-20T22:04:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。