論文の概要: Active Bipartite Ranking with Smooth Posterior Distributions
- arxiv url: http://arxiv.org/abs/2602.24263v1
- Date: Fri, 27 Feb 2026 18:32:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-02 19:48:24.562072
- Title: Active Bipartite Ranking with Smooth Posterior Distributions
- Title（参考訳）: Smooth Posterior Distributions を用いたActive Bipartite Ranking
- Authors: James Cheshire, Stephan Clémençon,
- Abstract要約: 双部格付けは、多くのアプリケーションにかかわる統計的学習問題であり、受動的文脈において広く研究されている。
本研究では,推定ランキングルールのROC曲線と$sup$ノルムの最適値との距離を最小化することを目的とした,スムーズランクと呼ばれる新しいアルゴリズムを提案する。
本研究では,スムーズランクのサンプリング時間に依存する問題と,任意のPAC$(,)$アルゴリズムのサンプリング時間に依存する問題を確立する。
- 参考スコア（独自算出の注目度）: 1.9838140219494644
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this article, bipartite ranking, a statistical learning problem involved in many applications and widely studied in the passive context, is approached in a much more general \textit{active setting} than the discrete one previously considered in the literature. While the latter assumes that the conditional distribution is piece wise constant, the framework we develop permits in contrast to deal with continuous conditional distributions, provided that they fulfill a Hölder smoothness constraint. We first show that a naive approach based on discretisation at a uniform level, fixed \textit{a priori} and consisting in applying next the active strategy designed for the discrete setting generally fails. Instead, we propose a novel algorithm, referred to as smooth-rank and designed for the continuous setting, which aims to minimise the distance between the ROC curve of the estimated ranking rule and the optimal one w.r.t. the $\sup$ norm. We show that, for a fixed confidence level $ε>0$ and probability $δ\in (0,1)$, smooth-rank is PAC$(ε,δ)$. In addition, we provide a problem dependent upper bound on the expected sampling time of smooth-rank and establish a problem dependent lower bound on the expected sampling time of any PAC$(ε,δ)$ algorithm. Beyond the theoretical analysis carried out, numerical results are presented, providing solid empirical evidence of the performance of the algorithm proposed, which compares favorably with alternative approaches.
- Abstract（参考訳）: 本稿では、多くのアプリケーションにかかわる統計的学習問題であり、受動的文脈において広く研究されている二部類ランキングについて、これまで文献で考えられてきた離散的なものよりもずっと一般的な「textit{active setting}」でアプローチする。
後者は条件分布が断片的定数であると仮定するが、我々が開発するフレームワークは、ヘルダー滑らか性制約を満たすことを条件として、連続条件分布を扱うことを許容する。
まず、一様レベルでの離散化に基づく自然なアプローチ、固定された \textit{a priori} を示し、次に離散的な設定のために設計されたアクティブな戦略を適用することは一般的に失敗する。
このアルゴリズムは,推定されたランキングルールのROC曲線と$\sup$ノルムの最適値との距離を最小化することを目的としている。
固定信頼度 $ε>0$ と確率 $δ\in (0,1)$ に対して、滑らかなランクは PAC$(ε,δ)$ であることを示す。
さらに、スムーズランクの期待サンプリング時間に依存する問題依存上界を提供し、任意のPAC$(ε,δ)$アルゴリズムの期待サンプリング時間に依存する問題依存下界を確立する。
理論的解析の他に、数値的な結果が提示され、提案アルゴリズムの性能に関する確固たる実証的な証拠が得られ、これは代替手法と好意的に比較できる。
関連論文リスト
- On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
単一ループ近似インプリシト差分法(SSAID)アルゴリズムの洗練された収束解析を行う。
i) 最適な$mathcalO(-2)$最先端のマルチループメソッドのレートと一致し、 (ii) $-dependenceの最初の明示的できめ細かい特徴を提供する。
論文 参考訳（メタデータ） (2026-02-27T03:12:08Z) - Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。
クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。
我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
論文 参考訳（メタデータ） (2026-02-05T14:16:47Z) - EVaR-Optimal Arm Identification in Bandits [7.340828059560291]
The fixed-confidence best arm identification problem in the multiarmed bandit (MAB) framework under the Entropic Value-at-Risk criterion。
論文 参考訳（メタデータ） (2025-10-06T11:49:56Z) - Minimax Optimal Two-Stage Algorithm For Moment Estimation Under Covariate Shift [10.35788775775647]
ソースとターゲットの分布が分かっている場合,問題の最小境界について検討する。
具体的には、まず、ソース分布の下で関数の最適推定器を訓練し、その後、モーメント推定器を校正する確率比再重み付け手順を使用する。
この問題を解決するために、二重ロバスト性を確保し、対応する上界を与える推定器の切り離されたバージョンを提案する。
論文 参考訳（メタデータ） (2025-06-30T01:32:36Z) - Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。
我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
論文 参考訳（メタデータ） (2025-06-03T02:56:26Z) - Wasserstein Distributionally Robust Bayesian Optimization with Continuous Context [5.4147994801415145]
我々は,文脈分布の不確実性の下での逐次的データ駆動意思決定の課題に対処する。
We propose a novel algorithm for Wasserstein Distributionally Robust Bayesian Optimization。
我々の理論解析はヒルベルト空間における自己正規化濃度と分布的ロバストな最適化のための有限サンプル境界の最近の結果を組み合わせたものである。
論文 参考訳（メタデータ） (2025-03-26T09:11:17Z) - Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
我々は$f$-divergence-regularized offline policy learningを分析する。
逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。
これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
論文 参考訳（メタデータ） (2025-02-09T22:14:45Z) - Strictly Low Rank Constraint Optimization -- An Asymptotically
$\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。
我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
論文 参考訳（メタデータ） (2023-07-04T16:55:41Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳（メタデータ） (2022-01-21T02:46:57Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。
我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
論文 参考訳（メタデータ） (2020-03-16T17:15:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。