論文の概要: Super-Universal Regularized Newton Method

• arxiv url: http://arxiv.org/abs/2208.05888v1
• Date: Thu, 11 Aug 2022 15:44:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-12 13:40:32.520719
• Title: Super-Universal Regularized Newton Method
• Title（参考訳）: 超普遍正規化ニュートン法
• Authors: Nikita Doikov, Konstantin Mishchenko, Yurii Nesterov
• Abstract要約: 第二導関数あるいは第三導関数のH"古い連続性によって特徴づけられる問題クラスの族を導入する。 本稿では,問題クラスに最適な大域的複雑性境界を持つ自動調整を行うための,簡単な適応探索手法を提案する。
• 参考スコア（独自算出の注目度）: 14.670197265564196
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the performance of a variant of Newton method with quadratic regularization for solving composite convex minimization problems. At each step of our method, we choose regularization parameter proportional to a certain power of the gradient norm at the current point. We introduce a family of problem classes characterized by H\"older continuity of either the second or third derivative. Then we present the method with a simple adaptive search procedure allowing an automatic adjustment to the problem class with the best global complexity bounds, without knowing specific parameters of the problem. In particular, for the class of functions with Lipschitz continuous third derivative, we get the global $O(1/k^3)$ rate, which was previously attributed to third-order tensor methods. When the objective function is uniformly convex, we justify an automatic acceleration of our scheme, resulting in a faster global rate and local superlinear convergence. The switching between the different rates (sublinear, linear, and superlinear) is automatic. Again, for that, no a priori knowledge of parameters is needed.
• Abstract（参考訳）: 複合凸最小化問題の解法として2次正規化を用いたニュートン法の性能解析を行った。 提案手法の各ステップでは,現在点における勾配ノルムの一定のパワーに比例する正規化パラメータを選択する。 第二導関数あるいは第三導関数の H より古い連続性によって特徴づけられる問題クラスの族を導入する。 そこで本研究では,問題のパラメータを特定せずに,最適な大域的複雑性境界を持つ問題クラスを自動調整する,簡単な適応探索手法を提案する。 特に、リプシッツ連続三階微分を持つ函数のクラスに対しては、以前は三階テンソル法に起因していた大域$O(1/k^3)$レートを得る。 目的関数が一様凸である場合、我々のスキームの自動加速度を正当化し、より高速な大域率と局所超線型収束をもたらす。 異なるレート(サブリニア、リニア、スーパーリニア)の切り替えは自動的に行われる。 そのため、パラメータの事前知識は必要ありません。

関連論文リスト

• Efficient Low-rank Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization [8.879403568685499]
  パラメータの平滑化に適応的な更新戦略を導入する。 この振る舞いは、アルゴリズムを数回繰り返した後に、効果的に問題を解決するものに変えます。 すべてのイテレーションが重要なものであることを保証し、グローバルに提案された実験を証明します。
  論文  参考訳（メタデータ） (2024-06-22T02:37:13Z)
• First and zeroth-order implementations of the regularized Newton method with lazy approximated Hessians [4.62316736194615]
  我々は一般の非自由$ノルムフリー問題のリップオーダー(ヘシアン-O)とゼロオーダー(微分自由)の実装を開発する。 また、アルゴリズムに遅延バウンダリ更新を加えて、これまで計算されたヘッセン近似行列を数回繰り返し再利用する。
  論文  参考訳（メタデータ） (2023-09-05T17:40:54Z)
• Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method [4.62316736194615]
  準自己調和平滑成分を用いた複合凸最適化問題について検討する。 この問題クラスは、古典的な自己調和函数とリプシッツ連続ヘッセン函数の間に自然に補間する。 準自己協和関数を最小化するためには、グラディエント正規化を伴う基本ニュートン法を用いることができる。
  論文  参考訳（メタデータ） (2023-08-28T17:43:04Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  等式制約付き非線形非IBS最適化問題に対する適応的不正確なニュートン法を開発した。 ベンチマーク非線形問題,LVMのデータによる制約付きロジスティック回帰,PDE制約問題において,本手法の優れた性能を示す。
  論文  参考訳（メタデータ） (2023-05-28T06:33:37Z)
• Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron [49.45105570960104]
  ランダム勾配降下のグローバル収束を$Oleft(T-3right)$ rateで証明する。 これら2つの境界は、収束率の正確な特徴づけを与える。 このポテンシャル関数は緩やかに収束し、損失関数の緩やかな収束率を示す。
  論文  参考訳（メタデータ） (2023-02-20T15:33:26Z)
• Second-order optimization with lazy Hessians [55.51077907483634]
  一般の非線形最適化問題を解くためにニュートンの遅延ヘッセン更新を解析する。 我々は、メソッドの各ステップで新しい勾配を計算しながら、これまで見られたヘッセン反復を再利用する。
  論文  参考訳（メタデータ） (2022-12-01T18:58:26Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Implicit differentiation for fast hyperparameter selection in non-smooth convex learning [87.60600646105696]
  内部最適化問題が凸であるが非滑らかである場合の一階法を研究する。 本研究では, ヤコビアンの近位勾配降下と近位座標降下収率列の前方モード微分が, 正確なヤコビアンに向かって収束していることを示す。
  論文  参考訳（メタデータ） (2021-05-04T17:31:28Z)
• Optimizing generalization on the train set: a novel gradient-based framework to train parameters and hyperparameters simultaneously [0.0]
  一般化は機械学習における中心的な問題である。 本稿では,新たなリスク尺度に基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-06-11T18:04:36Z)
• Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
  我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。 我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。 論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-12T16:44:27Z)
• First Order Methods take Exponential Time to Converge to Global Minimizers of Non-Convex Functions [28.776950569604026]
  本研究では、非凸函数の基本硬度に関する境界を与える。 パラメータ推定問題は家族識別の問題と等価であることを示す。
  論文  参考訳（メタデータ） (2020-02-28T18:28:43Z)

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

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