論文の概要: Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient
- arxiv url: http://arxiv.org/abs/2206.01209v3
- Date: Mon, 10 Apr 2023 23:45:49 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-12 19:26:16.874017
- Title: Accelerated first-order methods for convex optimization with locally
Lipschitz continuous gradient
- Title（参考訳）: 局所リプシッツ連続勾配を用いた凸最適化の高速化一階法
- Authors: Zhaosong Lu and Sanyou Mei
- Abstract要約: まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。
提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。
提案手法の性能を実証するために,予備的な数値計算結果を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we develop accelerated first-order methods for convex
optimization with locally Lipschitz continuous gradient (LLCG), which is beyond
the well-studied class of convex optimization with Lipschitz continuous
gradient. In particular, we first consider unconstrained convex optimization
with LLCG and propose accelerated proximal gradient (APG) methods for solving
it. The proposed APG methods are equipped with a verifiable termination
criterion and enjoy an operation complexity of ${\cal O}(\varepsilon^{-1/2}\log
\varepsilon^{-1})$ and ${\cal O}(\log \varepsilon^{-1})$ for finding an
$\varepsilon$-residual solution of an unconstrained convex and strongly convex
optimization problem, respectively. We then consider constrained convex
optimization with LLCG and propose an first-order proximal augmented Lagrangian
method for solving it by applying one of our proposed APG methods to
approximately solve a sequence of proximal augmented Lagrangian subproblems.
The resulting method is equipped with a verifiable termination criterion and
enjoys an operation complexity of ${\cal O}(\varepsilon^{-1}\log
\varepsilon^{-1})$ and ${\cal O}(\varepsilon^{-1/2}\log \varepsilon^{-1})$ for
finding an $\varepsilon$-KKT solution of a constrained convex and strongly
convex optimization problem, respectively. All the proposed methods in this
paper are parameter-free or almost parameter-free except that the knowledge on
convexity parameter is required. In addition, preliminary numerical results are
presented to demonstrate the performance of our proposed methods. To the best
of our knowledge, no prior studies were conducted to investigate accelerated
first-order methods with complexity guarantees for convex optimization with
LLCG. All the complexity results obtained in this paper are new.
- Abstract（参考訳）: 本稿では,局所リプシッツ連続勾配 (llcg) を用いた凸最適化のための高速化一階法を開発した。
特に,まず非拘束凸最適化をLLCGで検討し,それを解決するための加速近位勾配(APG)法を提案する。
提案するapg法には検証可能な終端基準が与えられ、unconstrained convex と strong convex optimization problem の $\varepsilon$-residual solution を求めるために、${\cal o}(\varepsilon^{-1/2}\log \varepsilon^{-1})$ と ${\cal o}(\log \varepsilon^{-1})$ の演算複雑性が与えられる。
そこで本研究では,llgを用いた制約付き凸最適化について検討し,本提案手法の1つを適用し,それを解決するための一階の近位拡張ラグランジアン法を提案する。
得られた方法は検証可能な終了基準を備えており、拘束された凸と強い凸最適化問題の$\varepsilon$-kkt解を求めるための${\cal o}(\varepsilon^{-1}\log \varepsilon^{-1})$と${\cal o}(\varepsilon^{-1/2}\log \varepsilon^{-1})$の操作複雑性をそれぞれ享受する。
本論文では,凸度パラメータに関する知識が要求される以外,パラメータフリーあるいはほぼパラメータフリーである。
さらに,提案手法の性能を示すために,予備的な数値計算結果を示す。
私たちの知る限りでは、llcgによる凸最適化のための複雑性保証付き1次加速法について、先行研究は行われなかった。
この論文で得られた複雑さのすべては新しい。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - A simple uniformly optimal method without line search for convex optimization [9.280355951055865]
パラメータが優先されていない凸最適化問題の解法として最適収束率を得るには,線探索が過剰であることを示す。
滑らかな凸最適化のために最適な$mathcalO (1/k2)$収束率を達成できるAC-FGMと呼ばれる新しい勾配降下型アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-16T05:26:03Z) - Revisiting Subgradient Method: Complexity and Convergence Beyond Lipschitz Continuity [24.45688490844496]
次進法は非滑らかな最適化のための最も基本的なアルゴリズムスキームの1つである。
本研究では、まず、非Lipschitz凸と弱凸最小化をカバーするために、下次法の典型的な反復複雑性結果を拡張する。
論文 参考訳（メタデータ） (2023-05-23T15:26:36Z) - A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。
完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。
MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
論文 参考訳（メタデータ） (2023-01-26T05:34:21Z) - 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) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。