論文の概要: Multi-block Min-max Bilevel Optimization with Applications in Multi-task
Deep AUC Maximization
- arxiv url: http://arxiv.org/abs/2206.00260v1
- Date: Wed, 1 Jun 2022 06:42:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-03 02:02:38.933079
- Title: Multi-block Min-max Bilevel Optimization with Applications in Multi-task
Deep AUC Maximization
- Title（参考訳）: マルチタスクディープAUC最適化におけるマルチブロックMin-maxバイレベル最適化と応用
- Authors: Quanqi Hu, Yongjian Zhong, Tianbao Yang
- Abstract要約: マルチブロックのmin-max双レベル最適化問題に対処するシングルループアルゴリズムを提案する。
我々のアルゴリズムは数百のタスクで問題に取り組むのに利用できることを示す。
- 参考スコア（独自算出の注目度）: 36.743632418094
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study multi-block min-max bilevel optimization problems,
where the upper level is non-convex strongly-concave minimax objective and the
lower level is a strongly convex objective, and there are multiple blocks of
dual variables and lower level problems. Due to the intertwined multi-block
min-max bilevel structure, the computational cost at each iteration could be
prohibitively high, especially with a large number of blocks. To tackle this
challenge, we present a single-loop randomized stochastic algorithm, which
requires updates for only a constant number of blocks at each iteration. Under
some mild assumptions on the problem, we establish its sample complexity of
$\mathcal{O}(1/\epsilon^4)$ for finding an $\epsilon$-stationary point. This
matches the optimal complexity for solving stochastic nonconvex optimization
under a general unbiased stochastic oracle model. Moreover, we provide two
applications of the proposed method in multi-task deep AUC (area under ROC
curve) maximization and multi-task deep partial AUC maximization. Experimental
results validate our theory and demonstrate the effectiveness of our method on
problems with hundreds of tasks.
- Abstract（参考訳）: 本稿では,上層レベルが非凸強凸ミニマックス目的であり,下層レベルが強凸目的であり,二重変数のブロックと下層レベル問題が存在するマルチブロックミニレベル最適化問題について検討する。
絡み合ったマルチブロックミニマックスの2レベル構造のため、各イテレーションでの計算コストは、特に多数のブロックにおいて、非常に高いものとなる。
この課題に対処するために,反復毎に一定数のブロックだけを更新する単一ループランダム化確率アルゴリズムを提案する。
この問題に関するいくつかの軽微な仮定の下で、$\epsilon$-定常点を見つけるために、そのサンプル複雑性を$\mathcal{O}(1/\epsilon^4)$とする。
これは一般の確率的オラクルモデルの下で確率的非凸最適化を解くのに最適な複雑さと一致する。
さらに,提案手法の2つの応用として,マルチタスク深部AUC(ROC曲線の下での領域)の最大化とマルチタスク深部AUCの最大化を提案する。
実験結果から,本手法の有効性を検証し,数百タスクの課題に対して検証した。
関連論文リスト
- A First-Order Multi-Gradient Algorithm for Multi-Objective Bi-Level Optimization [7.097069899573992]
マルチオブジェクト・バイ・レベル最適化(MOBLO)問題について検討する。
既存の勾配に基づくMOBLOアルゴリズムはヘッセン行列を計算する必要がある。
FORUMと呼ばれるMOBLOの高効率な1次多重勾配法を提案する。
論文 参考訳（メタデータ） (2024-01-17T15:03:37Z) - Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for
Multi-Block Bilevel Optimization [43.74656748515853]
非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。
a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
論文 参考訳（メタデータ） (2023-05-30T04:10:11Z) - A Lower Bound and a Near-Optimal Algorithm for Bilevel Empirical Risk
Minimization [23.401092942765196]
本稿では、SARAHアルゴリズムの2レベル拡張を提案する。
我々は、このアルゴリズムが$varepsilon$-stationarityを達成するために$mathcalO((n+m)frac12varepsilon-1)$ Oracleコールを必要とすることを示した。
両レベル問題の目的関数のほぼ定常点を得るのに必要なオラクル呼び出し数に対して、より低い境界を与える。
論文 参考訳（メタデータ） (2023-02-17T09:04:18Z) - Functional Constrained Optimization for Risk Aversion and Sparsity
Control [7.561780884831967]
リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。
本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。
提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
論文 参考訳（メタデータ） (2022-10-11T02:51:51Z) - Min-Max Bilevel Multi-objective Optimization with Applications in
Machine Learning [30.25074797092709]
本稿では,min-maxバイレベル多目的最適化フレームワークを提案する。
表現学習と超目的学習の応用を強調している。
論文 参考訳（メタデータ） (2022-03-03T18:56:13Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。