論文の概要: Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations

• arxiv url: http://arxiv.org/abs/2512.01213v1
• Date: Mon, 01 Dec 2025 02:52:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:34.651022
• Title: Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations
• Title（参考訳）: 部分的AUC最適化の近似ギャップの閉鎖:2つの定式化の物語
• Authors: Yangbangyan Jiang, Qianqian Xu, Huiyang Shao, Zhiyong Yang, Shilong Bao, Xiaochun Cao, Qingming Huang,
• Abstract要約: ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
• 参考スコア（独自算出の注目度）: 121.39938773554523
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As a variant of the Area Under the ROC Curve (AUC), the partial AUC (PAUC) focuses on a specific range of false positive rate (FPR) and/or true positive rate (TPR) in the ROC curve. It is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints. However, selecting instances within these constrained intervals during its calculation is NP-hard, and thus typically requires approximation techniques for practical resolution. Despite the progress made in PAUC optimization over the last few years, most existing methods still suffer from uncontrollable approximation errors or a limited scalability when optimizing the approximate PAUC objectives. In this paper, we close the approximation gap of PAUC optimization by presenting two simple instance-wise minimax reformulations: one with an asymptotically vanishing gap, the other with the unbiasedness at the cost of more variables. Our key idea is to first establish an equivalent instance-wise problem to lower the time complexity, simplify the complicated sample selection procedure by threshold learning, and then apply different smoothing techniques. Equipped with an efficient solver, the resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(ε^{-1/3})$ for typical one-way and two-way PAUCs. Moreover, we provide a tight generalization bound of our minimax reformulations. The result explicitly demonstrates the impact of the TPR/FPR constraints $α$/$β$ on the generalization and exhibits a sharp order of $\tilde{O}(α^{-1}\n_+^{-1} + β^{-1}\n_-^{-1})$. Finally, extensive experiments on several benchmark datasets validate the strength of our proposed methods.
• Abstract（参考訳）: ROC曲線下の領域(AUC)の変種として、部分的なAUC(PAUC)は、ROC曲線内の特定の偽陽性率(FPR)および/または真陽性率(TPR)の範囲に焦点を当てている。 これは、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 しかし、計算中のこれらの制約された区間内でのインスタンスの選択はNPハードであり、一般的には実際の解決のために近似技術を必要とする。 過去数年間のPAUC最適化の進歩にもかかわらず、ほとんどの既存手法はPAUCの目的を最適化する際に制御不能な近似誤差や拡張性に悩まされている。 本稿では,PAUC最適化の近似ギャップを,漸近的に消失するギャップと,より多くの変数のコストで不偏性を持つ2つの単純なインスタンスワイドの最小値再構成を提示することにより,近似ギャップを埋める。 我々のキーとなる考え方は、まず、時間的複雑さを減らし、しきい値学習による複雑なサンプル選択手順を単純化し、異なる平滑化手法を適用するために、等価なインスタンスワイズ問題を確立することである。 効率的な解法を備えたアルゴリズムは、典型的な一方方向と双方向のPAUCに対してサンプルサイズと収束率$O(ε^{-1/3})$の線形パーイテレーション計算複雑性を享受する。 さらに、ミニマックス修正の厳密な一般化バウンダリを提供する。 この結果は、一般化に対するTPR/FPR制約$α$/$β$の影響を明確に示し、$\tilde{O}(α^{-1}\n_+^{-1} + β^{-1}\n_-^{-1})$のシャープ順序を示す。 最後に、いくつかのベンチマークデータセットに関する広範な実験を行い、提案手法の強さを検証した。

関連論文リスト

• Double Variance Reduction: A Smoothing Trick for Composite Optimization Problems without First-Order Gradient [40.22217106270146]
  ばらつき低減技術はサンプリングのばらつきを低減し、一階法(FO)とゼロ階法(ZO)の収束率を向上するように設計されている。 複合最適化問題において、ZO法は、ランダム推定から導かれる座標ワイド分散と呼ばれる追加の分散に遭遇する。 本稿では,ZPDVR法とZPDVR法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T02:27:53Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Large-scale Optimization of Partial AUC in a Range of False Positive Rates [51.12047280149546]
  ROC曲線 (AUC) の下の領域は、機械学習において最も広く使われている分類モデルのパフォーマンス指標の1つである。 近年の封筒平滑化技術に基づく効率的な近似勾配降下法を開発した。 提案アルゴリズムは,効率のよい解法を欠くランク付けされた範囲損失の和を最小化するためにも利用できる。
  論文  参考訳（メタデータ） (2022-03-03T03:46:18Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。