Fugu-MT 論文翻訳(概要): Second-Order Min-Max Optimization with Lazy Hessians

論文の概要: Second-Order Min-Max Optimization with Lazy Hessians

arxiv url: http://arxiv.org/abs/2410.09568v1
Date: Sat, 12 Oct 2024 15:30:17 GMT
ステータス: 処理完了
システム内更新日: 2024-10-30 13:45:15.628576
Title: Second-Order Min-Max Optimization with Lazy Hessians
Title（参考訳）: Lazy Hessianを用いた2次Min-Max最適化
Authors: Lesi Chen, Chengchang Liu, Jingzhao Zhang,
Abstract要約: 本稿では,凸凹型最小値最適化のための2次法について検討する。計算コストは反復的にヘッセンによって削減できることを示す。
参考スコア（独自算出の注目度）: 17.17389531402505
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This paper studies second-order methods for convex-concave minimax optimization. Monteiro and Svaiter (2012) proposed a method to solve the problem with an optimal iteration complexity of $\mathcal{O}(\epsilon^{-3/2})$ to find an $\epsilon$-saddle point. However, it is unclear whether the computational complexity, $\mathcal{O}((N+ d^2) d \epsilon^{-2/3})$, can be improved. In the above, we follow Doikov et al. (2023) and assume the complexity of obtaining a first-order oracle as $N$ and the complexity of obtaining a second-order oracle as $dN$. In this paper, we show that the computation cost can be reduced by reusing Hessian across iterations. Our methods take the overall computational complexity of $ \tilde{\mathcal{O}}( (N+d^2)(d+ d^{2/3}\epsilon^{-2/3}))$, which improves those of previous methods by a factor of $d^{1/3}$. Furthermore, we generalize our method to strongly-convex-strongly-concave minimax problems and establish the complexity of $\tilde{\mathcal{O}}((N+d^2) (d + d^{2/3} \kappa^{2/3}) )$ when the condition number of the problem is $\kappa$, enjoying a similar speedup upon the state-of-the-art method. Numerical experiments on both real and synthetic datasets also verify the efficiency of our method.
Abstract（参考訳）: 本稿では,凸凹型最小値最適化のための2次法について検討する。 Monteiro and Svaiter (2012) は、$\epsilon$-saddle 点を求めるために$\mathcal{O}(\epsilon^{-3/2})$の最適反復複雑性で問題を解く方法を提案した。しかし、計算複雑性$\mathcal{O}((N+ d^2) d \epsilon^{-2/3})$が改善できるかどうかは不明である。上記の例では、Doikov et al (2023) に従い、一階のオラクルを得る複雑さを$N$、二階のオラクルを得る複雑さを$dN$と仮定する。本稿では,Hessianを反復的に再利用することで,計算コストを削減可能であることを示す。我々の手法は、$ \tilde{\mathcal{O}}((N+d^2)(d+d^{2/3}\epsilon^{-2/3}))$の計算複雑性を、d^{1/3}$の係数で改善する。さらに,本手法を強凸・強凸最小値問題に一般化し,問題の条件数が$\kappa$である場合の$$\tilde{\mathcal{O}}((N+d^2)(d + d^{2/3} \kappa^{2/3})の複雑性を確立する。実データと合成データの両方に関する数値実験により,本手法の有効性が検証された。

関連論文リスト

Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文参考訳（メタデータ） (2024-10-03T15:04:01Z)
Efficient Continual Finite-Sum Minimization [52.5238287567572]
連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
論文参考訳（メタデータ） (2024-06-07T08:26:31Z)
Accelerated Variance-Reduced Forward-Reflected Methods for Root-Finding Problems [8.0153031008486]
そこで本研究では,Nesterovの高速前方反射法と分散還元法を新たに提案し,根絶問題の解法を提案する。我々のアルゴリズムは単ループであり、ルートフィリング問題に特化して設計された非バイアス分散還元推定器の新たなファミリーを利用する。
論文参考訳（メタデータ） (2024-06-04T15:23:29Z)
Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文参考訳（メタデータ） (2023-11-18T23:55:59Z)
Accelerating Inexact HyperGradient Descent for Bilevel Optimization [84.00488779515206]
本稿では,一般的な非コンケーブ二段階最適化問題の解法を提案する。また,非コンケーブ問題における2次定常点を求める際の既存の複雑性も改善した。
論文参考訳（メタデータ） (2023-06-30T20:36:44Z)
A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文参考訳（メタデータ） (2023-01-10T20:43:29Z)
Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文参考訳（メタデータ） (2022-08-07T20:53:42Z)
The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文参考訳（メタデータ） (2022-05-19T16:04:40Z)
Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss [41.17536985461902]
オラクルの複雑さを$Omega(Nepsilon-2/3)$として証明し、N$への依存が多対数因子に最適であることを示す。非滑らかな場合、$tildeO(Nepsilon-2/3 + sqrtNepsilon-8/3)$と$tildeO(Nepsilon-2/3 + sqrtNepsilon-1)$の複雑さ境界を改善した手法を開発する。
論文参考訳（メタデータ） (2021-05-04T21:49:15Z)
Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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