論文の概要: Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method

• arxiv url: http://arxiv.org/abs/2308.14742v1
• Date: Mon, 28 Aug 2023 17:43:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-29 12:44:08.294760
• Title: Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method
• Title（参考訳）: ニュートン法の勾配正規化による準自己一致関数の最小化
• Authors: Nikita Doikov
• Abstract要約: 準自己調和平滑成分を用いた複合凸最適化問題について検討する。 この問題クラスは、古典的な自己調和函数とリプシッツ連続ヘッセン函数の間に自然に補間する。 準自己協和関数を最小化するためには、グラディエント正規化を伴う基本ニュートン法を用いることができる。
• 参考スコア（独自算出の注目度）: 4.62316736194615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.
• Abstract（参考訳）: 準自己共役滑らか成分を用いた複合凸最適化問題について検討した。 この問題は古典的自己協和函数とリプシッツ連続ヘッセン函数の間に自然に補間する。 これまで、この問題クラスにおける最善の複雑性境界は、信頼地域スキームとボール最小化オラクルの実装に関連付けられていた。 本稿では,準自己協和関数を最小化するために,勾配正規化を伴う基本ニュートン法を用いる。 制約のない最小化の場合、各ステップで単純な行列反転演算(線形系を解く)のみを含む。 我々は,信頼領域スキームの複雑性境界に適合する,このアルゴリズムの高速大域的線形率を証明したが,本手法は特に実装が容易である。 次に,2重ニュートン法を導入し,それに基づいてこの問題クラスに対して対応する高速化ニュートンスキームを開発し,基本手法の複雑さ係数をさらに向上させる。 本結果の直接的結果として,ロジスティック回帰,ソフトマックス,マトリックススケーリングなどの実用的問題に適用されたニュートン法の単純変種に対する高速な大域的線形速度を,目標目標に対する強凸性や均一凸性に関する追加の仮定を必要とせず確立した。

関連論文リスト

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization [12.84152722535866]
  目的関数が弱凸あるいは弱凸である非制約最適化問題を考える。 そこで本研究では,一階調律であり,実装が容易な段階的手法について考察する。
  論文  参考訳（メタデータ） (2023-01-30T22:13:14Z)
• Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization [88.0031283949404]
  多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。 提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2022-12-19T14:48:54Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Continuation Newton methods with deflation techniques for global optimization problems [3.705839280172101]
  最適化問題のグローバルな最小点はエンジニアリングである。 本稿では,この非線形大規模問題に対する新しいメメティックアルゴリズムについて考察する。 我々の数値実験によると、新しいアルゴリズムは制約のない未制約問題に対してうまく機能する。
  論文  参考訳（メタデータ） (2021-07-29T09:53:49Z)
• Complementary Composite Minimization, Small Gradients in General Norms, and Applications to Regression Problems [14.759688428864157]
  複合最小化は大規模凸最適化における強力なフレームワークである。 補完的複合最小化のための新しいアルゴリズムフレームワークを提案する。 我々は,フレームワークから得られるアルゴリズムが,ほとんどの標準最適化設定においてほぼ最適であることを証明した。
  論文  参考訳（メタデータ） (2021-01-26T19:21:28Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  定常点に収束する一般化外空間を提案する。 このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
  論文  参考訳（メタデータ） (2020-10-31T21:35:42Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)
• A Class of Linear Programs Solvable by Coordinate-Wise Minimization [0.0]
  座標最小化を正確に解く線形プログラムのクラスを示す。 いくつかのよく知られた最適化問題の2つのLP緩和がこのクラスにあることを示す。 我々の結果は理論的には非自明であり、将来的には新たな大規模最適化アルゴリズムがもたらされる可能性がある。
  論文  参考訳（メタデータ） (2020-01-28T17:14:47Z)

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

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