論文の概要: Parameter-free Stochastic Optimization of Variationally Coherent Functions

• arxiv url: http://arxiv.org/abs/2102.00236v1
• Date: Sat, 30 Jan 2021 15:05:34 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-02 15:43:00.317413
• Title: Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Title（参考訳）: 変分コヒーレント関数のパラメータフリー確率最適化
• Authors: Francesco Orabona and D\'avid P\'al
• Abstract要約: 我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。 この2つを同時に実現したのは初めてである。
• 参考スコア（独自算出の注目度）: 19.468067110814808
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We design and analyze an algorithm for first-order stochastic optimization of a large class of functions on $\mathbb{R}^d$. In particular, we consider the \emph{variationally coherent} functions which can be convex or non-convex. The iterates of our algorithm on variationally coherent functions converge almost surely to the global minimizer $\boldsymbol{x}^*$. Additionally, the very same algorithm with the same hyperparameters, after $T$ iterations guarantees on convex functions that the expected suboptimality gap is bounded by $\widetilde{O}(\|\boldsymbol{x}^* - \boldsymbol{x}_0\| T^{-1/2+\epsilon})$ for any $\epsilon>0$. It is the first algorithm to achieve both these properties at the same time. Also, the rate for convex functions essentially matches the performance of parameter-free algorithms. Our algorithm is an instance of the Follow The Regularized Leader algorithm with the added twist of using \emph{rescaled gradients} and time-varying linearithmic regularizers.
• Abstract（参考訳）: 我々は $\mathbb{R}^d$ 上の関数の大規模クラスの一階確率最適化のためのアルゴリズムを設計・解析する。 特に、凸あるいは非凸となることができる \emph{variationally coherent} 関数を考える。 変分コヒーレント関数に対するアルゴリズムの反復は、大域的最小値 $\boldsymbol{x}^*$ にほぼ確実に収束する。 さらに、同じハイパーパラメータを持つ全く同じアルゴリズムは、t$の反復の後、期待される準最適ギャップが任意の$\epsilon>0$に対して$\widetilde{o}(\|\boldsymbol{x}^* - \boldsymbol{x}_0\| t^{-1/2+\epsilon})$であるような凸関数に対して保証する。 この2つの性質を同時に達成した最初のアルゴリズムである。 また、凸関数の速度はパラメータフリーなアルゴリズムの性能と本質的に一致する。 我々のアルゴリズムは、'emph{rescaled gradients} と時間変化線形正則化器を併用したFollow The Regularized Leaderアルゴリズムの例である。

関連論文リスト

• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Gradient-free optimization of highly smooth functions: improved analysis and a new algorithm [87.22224691317766]
  この研究は、目的関数が極めて滑らかであるという仮定の下で、ゼロ次ノイズオラクル情報による問題を研究する。 ゼロオーダー射影勾配勾配アルゴリズムを2種類検討する。
  論文  参考訳（メタデータ） (2023-06-03T17:05:13Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。 以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
  論文  参考訳（メタデータ） (2023-02-20T05:16:18Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  滑らかな凸凹凸結合型サドル点問題, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$ を考える。 漸進的勾配指数(AG-EG)降下指数アルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2022-06-17T06:10:20Z)
• Fast Stochastic Composite Minimization and an Accelerated Frank-Wolfe Algorithm under Parallelization [7.197233473373693]
  2つの凸関数の和を最小化する問題を考える。 1つはリプシッツ連続勾配を持ち、オークルを介してアクセスでき、もう1つは「単純」である。 我々は、$tildeO (1/ sqrtepsilon)$ iterationsで$epsilon$prialdual gap(期待して)を達成することができることを示す。
  論文  参考訳（メタデータ） (2022-05-25T13:01:09Z)
• Convergence rates of the stochastic alternating algorithm for bi-objective optimization [0.0]
  交互アルゴリズムは,強い凸性の下で$mathcalO (1/sqrtT)$のサブ線形収束率が得られることを示す。 重要なことに、各関数に適用されるステップの割合を変えることで、前方への近似を決定することができる。
  論文  参考訳（メタデータ） (2022-03-20T17:31:08Z)
• 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 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)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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