論文の概要: Avoiding strict saddle points of nonconvex regularized problems

• arxiv url: http://arxiv.org/abs/2401.09274v3
• Date: Thu, 18 Jul 2024 08:59:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-19 21:41:25.905621
• Title: Avoiding strict saddle points of nonconvex regularized problems
• Title（参考訳）: 非凸正規化問題の厳密なサドル点を回避する
• Authors: Luwei Bai, Yaohua Hu, Hao Wang, Xiaoqi Yang,
• Abstract要約: 第二項最適性条件は定常点の零点にのみ依存することを示す。 本稿では,反復再重み付き$ell_1$を含む2つの繰り返し重み付きアルゴリズムを提案する。 これらのアルゴリズムは、サドル点の性質が仮定されるときのみランダムに局所的なサドラーに収束することを示す。
• 参考スコア（独自算出の注目度）: 3.92625489118339
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider a class of non-convex and non-smooth sparse optimization problems, which encompass most existing nonconvex sparsity-inducing terms. We show the second-order optimality conditions only depend on the nonzeros of the stationary points. We propose two damped iterative reweighted algorithms including the iteratively reweighted $\ell_1$ algorithm (DIRL$_1$) and the iteratively reweighted $\ell_2$ (DIRL$_2$) algorithm, to solve these problems. For DIRL$_1$, we show the reweighted $\ell_1$ subproblem has support identification property so that DIRL$_1$ locally reverts to a gradient descent algorithm around a stationary point. For DIRL$_2$, we show the solution map of the reweighted $\ell_2$ subproblem is differentiable and Lipschitz continuous everywhere. Therefore, the map of DIRL$_1$ and DIRL$_2$ and their inverse are Lipschitz continuous, and the strict saddle points are their unstable fixed points. By applying the stable manifold theorem, these algorithms are shown to converge only to local minimizers with randomly initialization when the strictly saddle point property is assumed.
• Abstract（参考訳）: 本稿では,非凸・非滑らかなスパース最適化問題のクラスについて考察する。 2階最適条件は定常点の零点にのみ依存することを示す。 本稿では,反復再重み付き$\ell_1$アルゴリズム(DIRL$_1$)と反復再重み付き$\ell_2$(DIRL$_2$)アルゴリズム(DIRL$)の2つの繰り返し重み付き再重み付きアルゴリズムを提案する。 DIRL$_1$の場合、再重み付き$\ell_1$ subproblemは、DIRL$_1$が定常点付近の勾配降下アルゴリズムに局所的に復帰するように、サポート識別特性を持つことを示す。 DIRL$_2$ に対し、reweighted $\ell_2$ subproblem is differentiable and Lipschitz continuous everywhere の解写像を示す。 したがって、DIRL$_1$とDIRL$_2$とそれらの逆写像はリプシッツ連続であり、厳密なサドル点は不安定な不動点である。 安定多様体の定理を適用することにより、これらのアルゴリズムは厳密なサドル点の性質が仮定されるとき、ランダムに初期化される局所最小化にのみ収束することが示される。

関連論文リスト

• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• A Cubic-regularized Policy Newton Algorithm for Reinforcement Learning [9.628032156001073]
  立方正則化を取り入れた2つのポリシーニュートンアルゴリズムを提案する。 どちらのアルゴリズムも確率比法を用いて値関数の勾配とヘシアンを推定する。 特に、我々のアルゴリズムのサンプル複雑さが$epsilon$-SOSPを見つけるのに$O(epsilon-3.5)$であり、これは最先端のサンプル複雑性の$O(epsilon-4.5)$よりも改善されている。
  論文  参考訳（メタデータ） (2023-04-21T13:43:06Z)
• Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap [12.446156563700482]
  凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。 また、安定性と精度の間には根本的なトレードオフがあることも示している。
  論文  参考訳（メタデータ） (2023-02-24T21:50:02Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• A gradient estimator via L1-randomization for online zero-order optimization with two point feedback [93.57603470949266]
  2つの関数評価とランダム化に基づく新しい勾配推定器を提案する。 ゼロ次オラクルの雑音に対する仮定は,ノイズのキャンセルと逆方向雑音の2種類について考察する。 我々は、問題の全てのパラメータに適応する、いつでも完全にデータ駆動のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-05-27T11:23:57Z)
• A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization [12.096252285460814]
  合成最適化のためのプロジェクションフリー条件付き勾配型アルゴリズムを提案する。 提案アルゴリズムで要求されるオラクルの数と線形最小化オラクルは,それぞれ$mathcalO_T(epsilon-2)$と$mathcalO_T(epsilon-3)$である。
  論文  参考訳（メタデータ） (2022-02-09T06:05:38Z)
• A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
  凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。 主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
  論文  参考訳（メタデータ） (2021-10-28T14:19:30Z)
• The Complexity of Nonconvex-Strongly-Concave Minimax Optimization [43.07732143522183]
  本稿では,非強凹型(nc-sc)滑らかなミニマックス問題の近似定常点を求めるための複雑さを確立する。 提案された$Omega-strong$lyconcaveサブ2問題を一般複雑性と平均複雑性の両方で展開する。 提案する有限和設定では,提案するアルゴリズムは条件数にほぼ依存している。
  論文  参考訳（メタデータ） (2021-03-29T18:53:57Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms [0.0]
  主な結果は、非滑らか関数に対する$epsilon$-approximate Local minimumの新たな特徴に基づいている。 標準的な仮定では、摂動近位点、摂動近位勾配、摂動近位線形アルゴリズムは非滑らかな凸関数に対して$epsilon$-approximate局所最小値を求める。
  論文  参考訳（メタデータ） (2021-02-04T19:17:13Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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