論文の概要: Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization

• arxiv url: http://arxiv.org/abs/2406.19475v1
• Date: Thu, 27 Jun 2024 18:38:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-01 18:41:35.475746
• Title: Stochastic First-Order Methods with Non-smooth and Non-Euclidean Proximal Terms for Nonconvex High-Dimensional Stochastic Optimization
• Title（参考訳）: 非凸高次元確率最適化のための非滑らかおよび非ユークリッド近位項をもつ確率的一階法
• Authors: Yue Xie, Jiawen Bi, Hongcheng Liu,
• Abstract要約: 非問題が非問題である場合、一階法のサンプルは問題次元に線形に依存することがあるが、望ましくない問題に対するものである。 我々のアルゴリズムは距離を使って複雑さを見積もることができる。 MathO (log d) / EuM4。 DISFOM は $mathO (log d) / EuM4 を用いて分散を鋭くすることができることを示す。
• 参考スコア（独自算出の注目度）: 2.0657831823662574
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When the nonconvex problem is complicated by stochasticity, the sample complexity of stochastic first-order methods may depend linearly on the problem dimension, which is undesirable for large-scale problems. In this work, we propose dimension-insensitive stochastic first-order methods (DISFOMs) to address nonconvex optimization with expected-valued objective function. Our algorithms allow for non-Euclidean and non-smooth distance functions as the proximal terms. Under mild assumptions, we show that DISFOM using minibatches to estimate the gradient enjoys sample complexity of $ \mathcal{O} ( (\log d) / \epsilon^4 ) $ to obtain an $\epsilon$-stationary point. Furthermore, we prove that DISFOM employing variance reduction can sharpen this bound to $\mathcal{O} ( (\log d)^{2/3}/\epsilon^{10/3} )$, which perhaps leads to the best-known sample complexity result in terms of $d$. We provide two choices of the non-smooth distance functions, both of which allow for closed-form solutions to the proximal step. Numerical experiments are conducted to illustrate the dimension insensitive property of the proposed frameworks.
• Abstract（参考訳）: 非凸問題が確率性によって複雑になるとき、確率的一階法のサンプル複雑性は問題次元に線形に依存することがあるが、これは大規模問題では望ましくない。 本研究では,非凸最適化のための次元非感性確率的一階法(DISFOMs)を提案する。 我々のアルゴリズムは、近距離項として非ユークリッドおよび非滑らか距離関数を許容する。 軽度の仮定では、勾配を推定するためにミニバッチを使用する DISFOM は、$ \mathcal{O} ( (\log d) / \epsilon^4 ) $ のサンプル複雑性を楽しみ、$\epsilon$-定常点を得る。 さらに、分散還元を用いた DisFOM がこの境界を $\mathcal{O} ( (\log d)^{2/3}/\epsilon^{10/3} )$ とし、おそらく最もよく知られたサンプルの複雑さを$d$ で表す。 非滑らか距離関数の2つの選択肢を提供し、どちらも近位ステップに対する閉形式解を可能にする。 提案手法の寸法不感性を示す数値実験を行った。

関連論文リスト

• 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)
• Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
  楽観的勾配法はミニマックス最適化問題に対処するのに有用である。 従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
  論文  参考訳（メタデータ） (2024-01-26T01:16:59Z)
• 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)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
  2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。 我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
  論文  参考訳（メタデータ） (2022-07-12T17:21:45Z)
• Stochastic Zeroth order Descent with Structured Directions [10.604744518360464]
  我々は, 有限差分法であるStructured Zeroth Order Descent (SSZD)を導入・解析し, 集合 $lleq d 方向の勾配を近似し, $d は周囲空間の次元である。 凸凸に対して、すべての$c1/2$に対して$O( (d/l) k-c1/2$)$ 上の関数の収束はほぼ確実に証明する。
  論文  参考訳（メタデータ） (2022-06-10T14:00:06Z)
• 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)
• Mean-Square Analysis with An Application to Optimal Dimension Dependence of Langevin Monte Carlo [60.785586069299356]
  この研究は、2-ワッサーシュタイン距離におけるサンプリング誤差の非同相解析のための一般的な枠組みを提供する。 我々の理論解析は数値実験によってさらに検証される。
  論文  参考訳（メタデータ） (2021-09-08T18:00:05Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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