論文の概要: Polynomial Preconditioning for Gradient Methods

• arxiv url: http://arxiv.org/abs/2301.13194v1
• Date: Mon, 30 Jan 2023 18:55:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-31 13:11:02.118037
• Title: Polynomial Preconditioning for Gradient Methods
• Title（参考訳）: 勾配法における多項式プレコンディショニング
• Authors: Nikita Doikov, Anton Rodomanov
• Abstract要約: 対称性によって生成される新しいプレコンディショナー群を提案する。 条件番号の証明可能な改善を施した一階最適化手法を提供する。 グラディエントおよびファストグラディエントメソッドにプレコンディショニングを組み込む方法を示し、それに対応するグローバルな複雑性を確立する。
• 参考スコア（独自算出の注目度）: 9.13755431537592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study first-order methods with preconditioning for solving structured nonlinear convex optimization problems. We propose a new family of preconditioners generated by symmetric polynomials. They provide first-order optimization methods with a provable improvement of the condition number, cutting the gaps between highest eigenvalues, without explicit knowledge of the actual spectrum. We give a stochastic interpretation of this preconditioning in terms of coordinate volume sampling and compare it with other classical approaches, including the Chebyshev polynomials. We show how to incorporate a polynomial preconditioning into the Gradient and Fast Gradient Methods and establish the corresponding global complexity bounds. Finally, we propose a simple adaptive search procedure that automatically chooses the best possible polynomial preconditioning for the Gradient Method, minimizing the objective along a low-dimensional Krylov subspace. Numerical experiments confirm the efficiency of our preconditioning strategies for solving various machine learning problems.
• Abstract（参考訳）: 構造付き非線形凸最適化問題に対する事前条件付き一階法について検討する。 対称多項式によって生成される新しいプレコンディショナー群を提案する。 彼らは条件番号の証明可能な改善を施した一階最適化手法を提供し、実際のスペクトルを明示的に知ることなく、最高固有値間のギャップを減らした。 この事前条件を座標体積サンプリングの観点から確率論的に解釈し、チェビシェフ多項式を含む他の古典的アプローチと比較する。 グラディエントおよびファストグラディエントメソッドに多項式プレコンディショニングを組み込む方法を示し、対応する大域的複雑性境界を確立する。 最後に,低次元クリロフ部分空間に沿って目的を最小化し,最適多項式プレコンディショニングを自動的に選択する簡単な適応探索手法を提案する。 数値実験により,機械学習問題に対するプレコンディショニング手法の有効性が検証された。

関連論文リスト

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• A conditional gradient homotopy method with applications to Semidefinite Programming [1.6369790794838281]
  ホモトピーに基づく条件勾配法による凸最適化問題の解法。 我々の理論的複雑さは、最先端のSDPに直面すると競合し、安価なプロジェクションフリーの決定的な利点がある。
  論文  参考訳（メタデータ） (2022-07-07T05:48:27Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples [0.0]
  低ランク行列補完のための反復アルゴリズムを提案する。 ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
  論文  参考訳（メタデータ） (2021-06-03T20:31:00Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)
• Complexity Guarantees for Polyak Steps with Momentum [76.97851351276165]
  そこでは,この知識を最適な値である$f_*$で置き換える。 まず、Polyak ステップによる単純な勾配勾配の古典的な場合よりも若干改善された収束境界を示し、その後、収束保証とともに、Polyak ステップと運動量を持つ加速勾配法を導出する。
  論文  参考訳（メタデータ） (2020-02-03T17:50:28Z)

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

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