論文の概要: Momentum Accelerates the Convergence of Stochastic AUPRC Maximization

• arxiv url: http://arxiv.org/abs/2107.01173v1
• Date: Fri, 2 Jul 2021 16:21:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-05 14:45:19.476082
• Title: Momentum Accelerates the Convergence of Stochastic AUPRC Maximization
• Title（参考訳）: モーメントは確率的AUPRC最大化の収束を加速する
• Authors: Guanghui Wang, Ming Yang, Lijun Zhang, Tianbao Yang
• Abstract要約: 高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
• 参考スコア（独自算出の注目度）: 80.8226518642952
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study stochastic optimization of areas under precision-recall curves (AUPRC), which is widely used for combating imbalanced classification tasks. Although a few methods have been proposed for maximizing AUPRC, stochastic optimization of AUPRC with convergence guarantee remains an undeveloped territory. A recent work [42] has proposed a promising approach towards AUPRC based on maximizing a surrogate loss for the average precision, and proved an $O(1/\epsilon^5)$ complexity for finding an $\epsilon$-stationary solution of the non-convex objective. In this paper, we further improve the stochastic optimization of AURPC by (i) developing novel stochastic momentum methods with a better iteration complexity of $O(1/\epsilon^4)$ for finding an $\epsilon$-stationary solution; and (ii) designing a novel family of stochastic adaptive methods with the same iteration complexity of $O(1/\epsilon^4)$, which enjoy faster convergence in practice. To this end, we propose two innovative techniques that are critical for improving the convergence: (i) the biased estimators for tracking individual ranking scores are updated in a randomized coordinate-wise manner; and (ii) a momentum update is used on top of the stochastic gradient estimator for tracking the gradient of the objective. Extensive experiments on various data sets demonstrate the effectiveness of the proposed algorithms. Of independent interest, the proposed stochastic momentum and adaptive algorithms are also applicable to a class of two-level stochastic dependent compositional optimization problems.
• Abstract（参考訳）: 本稿では,不均衡な分類課題に対処するために広く用いられている精度リコール曲線(auprc)下の領域の確率的最適化について検討する。 AUPRCの最大化にはいくつかの方法が提案されているが、収束保証付きAUPRCの確率的最適化は未開発領域のままである。 最近の研究[42]では、平均精度のサロゲート損失を最大化することに基づく AUPRC に対する有望なアプローチを提案し、非凸目的の$O(1/\epsilon^5)$複雑性を証明した。 本稿では, (i)$O(1/\epsilon^4)$の反復複雑性を向上した新しい確率運動量法を開発し, (ii)$O(1/\epsilon^4)$と同じ反復複雑性を持つ新しい確率適応手法のファミリーを設計し, 実際により高速な収束を享受することで, AURPCの確率的最適化をさらに改善する。 そこで本研究では,コンバージェンス改善に不可欠な2つの革新的手法を提案する。 (i) 個々のランキングスコアを追跡するバイアス付き推定器をランダムに座標的に更新する, (ii) 目標の勾配を追跡する確率的勾配推定器の上に運動量更新を用いる。 様々なデータセットに対する実験により,提案アルゴリズムの有効性が示された。 独立性において、提案された確率運動量と適応アルゴリズムは、2段階確率依存構成最適化問題にも適用できる。

関連論文リスト

• Near-Optimal High-Probability Convergence for Non-Convex Stochastic Optimization with Variance Reduction [17.408563601880253]
  大規模分散における非還元最適化のための新しいアルゴリズムを提案する。 我々のアルゴリズムは$(T$delta)/分散の速度で収束することを示す。 これは最高の結果を得るための最初の高い確率のイテレーションです。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。 IRLの多くのアルゴリズムは本質的にネスト構造を持つ。 我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T17:13:45Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Minibatch and Momentum Model-based Methods for Stochastic Non-smooth Non-convex Optimization [3.4809730725241597]
  モデルベース手法に対する2つの重要な拡張を行う。 まず,各イテレーションのモデル関数を近似するために,サンプルの集合を用いる新しいミニバッチを提案する。 第二に、運動量法の成功により、新しい凸モデルを提案する。
  論文  参考訳（メタデータ） (2021-06-06T05:31:57Z)
• On Stochastic Moving-Average Estimators for Non-Convex Optimization [105.22760323075008]
  本稿では,移動平均(SEMA)問題に基づく広く利用されている推定器のパワーを実証する。 これらすべてのアートな結果に対して、これらのアートな問題に対する結果も提示します。
  論文  参考訳（メタデータ） (2021-04-30T08:50:24Z)
• An Efficient Algorithm for Deep Stochastic Contextual Bandits [10.298368632706817]
  コンテキスト境界の問題では、エージェントは特定の観察されたコンテキストに基づいてアクションを選択し、反復よりも報酬を最大化します。 近年、ディープニューラルネットワーク(DNN)を用いて行動に対する期待される報酬を予測する研究がいくつか行われ、勾配に基づく手法で訓練されている。
  論文  参考訳（メタデータ） (2021-04-12T16:34:43Z)
• Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
  バイレベル最適化は多くの機械学習問題に対するツールである。 Stoc-BiO という新しい確率効率勾配推定器を提案する。
  論文  参考訳（メタデータ） (2020-10-15T18:09:48Z)

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

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