論文の概要: Near-optimal Swap Regret Minimization for Convex Losses
- arxiv url: http://arxiv.org/abs/2602.08862v1
- Date: Mon, 09 Feb 2026 16:26:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-10 20:26:25.357943
- Title: Near-optimal Swap Regret Minimization for Convex Losses
- Title（参考訳）: 凸損失に対する近接最適スワップレグレット最小化
- Authors: Lunjia Hu, Jon Schneider, Yifan Wu,
- Abstract要約: 我々は、ほぼ最適の$widetilde O(sqrt T)$期待スワップリミスを保証するランダム化されたオンラインアルゴリズムを、単位区間において適応的に選択されたLipschitz凸損失の任意の列に対して与える。
- 参考スコア（独自算出の注目度）: 21.006993033547708
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a randomized online algorithm that guarantees near-optimal $\widetilde O(\sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $\widetilde O(T^{2/3})$ and answers an open question of Fishelson et al. [2025b]. In addition, our algorithm is efficient: it runs in $\mathsf{poly}(T)$ time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first $\widetilde O(\sqrt T)$ calibration error guarantee.
- Abstract（参考訳）: 我々は、ほぼ最適の$\widetilde O(\sqrt T)$期待スワップ後悔を保証するランダム化されたオンラインアルゴリズムを提供する。
これにより、以前の$\widetilde O(T^{2/3})$のベストバウンドを改善し、Fielson et al [2025b] のオープンな疑問に答える。
さらに、我々のアルゴリズムは効率的で、$\mathsf{poly}(T)$ timeで動作する。
この結果を得るための重要な技術的アイデアは、単位間隔を複数の粒度でビンに離散化し、同時にすべてのスケールを用いてランダム化予測を行うことである。
提案手法は, 一般照会性に対する校正誤差を最小化するための効率的なオンラインアルゴリズムである。
この結果は、事前の作業で必要とされる識別関数のリプシッツネスの仮定を必要とせず、中央値のキャリブレーションに適用し、最初の$\widetilde O(\sqrt T)$キャリブレーション誤差を保証する。
関連論文リスト
- Online Conformal Prediction with Efficiency Guarantees [2.0305676256390934]
新たなオンラインフレームワークにおける共形予測の問題について検討する。
この問題では、ターゲットの誤発見率$alpha > 0$と時間軸$T$が与えられる。
論文 参考訳（メタデータ） (2025-07-03T10:00:50Z) - Improved Bounds for Swap Multicalibration and Swap Omniprediction [31.959887895880765]
我々は,有界線型関数に対する$O(sqrtT)$ $ell_2$-swap多重校正誤差を効率よく実現できることを示す。
また、凸関数とリプシッツ関数のクラスに対して、$varepsilon$-swap omnipredictorを効率的に学習する、$O(varepsilon -3)$サンプル複雑性も確立する。
論文 参考訳（メタデータ） (2025-05-27T08:29:35Z) - High dimensional online calibration in polynomial time [17.45683822446751]
オンライン(シークエンシャル)キャリブレーションでは、予測器は有限結果空間上の確率分布を予測し、T$dayのシーケンス上で$[d]$を予測する。
最もよく知られたアルゴリズムは、非自明なキャリブレーションを達成するのに$exp(d)$dayが必要である。
本稿では,複数のラウンドの後に,非自明なアルゴリズムキャリブレーションを保証する第1のキャリブレーション戦略を提案する。
論文 参考訳（メタデータ） (2025-04-12T06:28:05Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。