論文の概要: Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence

• arxiv url: http://arxiv.org/abs/2202.12183v1
• Date: Thu, 24 Feb 2022 16:37:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-25 16:36:46.819168
• Title: Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence
• Title（参考訳）: 確率収束型ディープラーニングのためのNDCGサロゲートの大規模確率最適化
• Authors: Zi-Hao Qiu, Quanqi Hu, Yongjian Zhong, Lijun Zhang, Tianbao Yang
• Abstract要約: 正規化カウント累積ゲイン(英: Normalized Discounted Cumulative Gain)は、情報検索と機械学習におけるランキング指標である。 本稿では,NDCGを最適化する原理的手法を提案する。 我々の知る限りでは、NDCGを証明可能な収束保証で最適化するアルゴリズムが提案されたのはこれが初めてである。
• 参考スコア（独自算出の注目度）: 41.20916144991216
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: NDCG, namely Normalized Discounted Cumulative Gain, is a widely used ranking metric in information retrieval and machine learning. However, efficient and provable stochastic methods for maximizing NDCG are still lacking, especially for deep models. In this paper, we propose a principled approach to optimize NDCG and its top-$K$ variant. First, we formulate a novel compositional optimization problem for optimizing the NDCG surrogate, and a novel bilevel compositional optimization problem for optimizing the top-$K$ NDCG surrogate. Then, we develop efficient stochastic algorithms with provable convergence guarantees for the non-convex objectives. Different from existing NDCG optimization methods, the per-iteration complexity of our algorithms scales with the mini-batch size instead of the number of total items. To improve the effectiveness for deep learning, we further propose practical strategies by using initial warm-up and stop gradient operator. Experimental results on multiple datasets demonstrate that our methods outperform prior ranking approaches in terms of NDCG. To the best of our knowledge, this is the first time that stochastic algorithms are proposed to optimize NDCG with a provable convergence guarantee.
• Abstract（参考訳）: NDCG(英: Normalized Discounted Cumulative Gain)は、情報検索と機械学習において広く使われているランキング指標である。 しかし、NDCGの最大化のための効率的かつ証明可能な確率的手法は、特に深層モデルでは、まだ不足している。 本稿では,NDCGとそのトップ$K$の変種を最適化する原理的アプローチを提案する。 まず、NDCGサロゲートを最適化するための新しい構成最適化問題と、上位K$NDCGサロゲートを最適化するための新しい2レベル構成最適化問題を定式化する。 そこで我々は,非凸目的に対して,効率の良い収束保証付き確率的アルゴリズムを開発した。 既存の NDCG 最適化手法とは異なり,アルゴリズムの項目毎の複雑性は,総項目数ではなく,ミニバッチサイズでスケールする。 深層学習の有効性を向上させるために,初期ウォームアップと停止勾配演算子を用いた実践的戦略を提案する。 複数のデータセットに対する実験結果から,提案手法がNDCGの手法よりも優れていることが示された。 我々の知る限りでは、証明可能な収束保証でNDCGを最適化する確率的アルゴリズムが提案されたのはこれが初めてである。

関連論文リスト

• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  勾配に基づくアルゴリズムはバイレベル最適化に広く用いられている。 本研究では,より高速な収束率を実現する非置換サンプリングに基づくアルゴリズムを提案する。 合成および実世界の両方のアプリケーションに対してアルゴリズムを検証する。
  論文  参考訳（メタデータ） (2024-11-07T17:05:31Z)
• A Pure Quantum Approximate Optimization Algorithm Based on CNR Operation [0.0]
  汎用的な純粋量子近似最適化アルゴリズムを提案する。 このアルゴリズムは$p$レベルの分割・対数構造に構成されている。 2つの最適化問題の必要なキュービット数が10である場合、アルゴリズムの性能を詳細に示す。
  論文  参考訳（メタデータ） (2023-10-27T06:54:39Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Optimizing NOTEARS Objectives via Topological Swaps [41.18829644248979]
  本稿では,候補アルゴリズムの集合に有効な手法を提案する。 内部レベルでは、対象が与えられた場合、オフ・ザ・アート制約を利用する。 提案手法は,他のアルゴリズムのスコアを大幅に改善する。
  論文  参考訳（メタデータ） (2023-05-26T21:49:37Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Genetically Modified Wolf Optimization with Stochastic Gradient Descent for Optimising Deep Neural Networks [0.0]
  本研究の目的は、人口ベースメタヒューリスティックアルゴリズムを用いて、ニューラルネットワーク(NN)重み付けを最適化するための代替アプローチを分析することである。 Grey Wolf (GWO) と Genetic Modified Algorithms (GA) のハイブリッドをグラディエント・Descent (SGD) と組み合わせて検討した。 このアルゴリズムは、高次元性の問題にも対処しながら、エクスプロイトと探索の組み合わせを可能にする。
  論文  参考訳（メタデータ） (2023-01-21T13:22:09Z)
• An Empirical Evaluation of Zeroth-Order Optimization Methods on AI-driven Molecule Optimization [78.36413169647408]
  分子目的を最適化するための様々なZO最適化手法の有効性について検討する。 ZO符号に基づく勾配降下(ZO-signGD)の利点を示す。 本稿では,Guurcamol スイートから広く使用されているベンチマークタスクに対して,ZO 最適化手法の有効性を示す。
  論文  参考訳（メタデータ） (2022-10-27T01:58:10Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  このアルゴリズムは指数勾配と$p$-normアルゴリズムの組み合わせと解釈できる。 彼らはシーケンス依存の後悔の上界を達成し、スパース目標決定変数の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-08-08T11:29:55Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)

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

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