論文の概要: Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality

• arxiv url: http://arxiv.org/abs/2105.07291v1
• Date: Sat, 15 May 2021 20:24:26 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-18 14:26:32.452999
• Title: Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality
• Title（参考訳）: Adaptive Newton Sketch:2次収束と有効ヘッセン次元を用いた線形時間最適化
• Authors: Jonathan Lacotte, Yifei Wang, Mert Pilanci
• Abstract要約: 自己整合性,複合性,強凸客観的関数を用いた凸最適化問題に対する二次収束率を有するランダム化アルゴリズムを提案する。 私たちの最初の貢献は、各イテレーションにおいて、埋め込み次元はヘッセン行列の有効次元と同じくらい小さくできることを示すことである。 この結果は、最先端のサブサンプリングニュートン法の古典線形-四次収束率を劇的に改善する。
• 参考スコア（独自算出の注目度）: 32.292481678592544
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linear-quadratic convergence rates of state-of-the-art sub-sampled Newton methods. However, in most practical cases, the effective dimension is not known beforehand, and this raises the question of how to pick a sketch size as small as the effective dimension while preserving a quadratic convergence rate. Our second and main contribution is thus to propose an adaptive sketch size algorithm with quadratic convergence rate and which does not require prior knowledge or estimation of the effective dimension: at each iteration, it starts with a small sketch size, and increases it until quadratic progress is achieved. Importantly, we show that the embedding dimension remains proportional to the effective dimension throughout the entire path and that our method achieves state-of-the-art computational complexity for solving convex optimization programs with a strongly convex component.
• Abstract（参考訳）: 自己調和型, 複合型, 強凸目的関数を用いた凸最適化問題に対して, 2次収束率のランダム化アルゴリズムを提案する。 提案手法は, ヘッセンのランダムなプロジェクションを用いて, 近似ニュートンステップを実行することに基づく。 私たちの最初の貢献は、各反復において、埋め込み次元(またはスケッチサイズ)がヘッセン行列の有効次元と同じくらい小さいことを示すことである。 この新たな基礎的結果を利用して,実効次元に比例するスケッチサイズを持つアルゴリズムを設計し,2次収束率を示す。 この結果は、最先端のサブサンプリングニュートン法の古典線形-四次収束率を劇的に改善する。 しかし、ほとんどの実践的な場合、有効次元は事前に分かっていないため、二次収束率を維持しながら、有効次元に匹敵するスケッチサイズを選ぶ方法が疑問視される。 そこで本研究では,2次収束率を持つ適応的スケッチサイズアルゴリズムを提案し,各反復において,より小さなスケッチサイズから開始し,二次進行が達成されるまで,事前の知識や有効次元の推定を必要としない。 重要なことは、埋め込み次元は経路全体の有効次元に比例し続け、我々の手法は凸最適化プログラムを強い凸成分で解くための最先端の計算複雑性を達成できることである。

関連論文リスト

• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  本研究では,スケッチ・アンド・プロジェクト手法の収束率の急激な保証を得るための理論的枠組みを開発する。 収束速度はスケッチサイズとともに少なくとも直線的に改善され、データ行列が特定のスペクトル崩壊を示すとさらに高速になることを示す。 我々の実験は、この理論を支持し、非常にスパースなスケッチでさえ、我々のフレームワークによって予測される収束特性を示すことを示した。
  論文  参考訳（メタデータ） (2022-08-20T03:11:13Z)
• Multiple Convex Objects Image Segmentation via Proximal Alternating Direction Method of Multipliers [2.294014185517203]
  前述した凸形状は、各対象に関連付けられた二項指示関数上の単純な二次不等式制約であることが判明した。 凸形状を予め確率ベースに組み込んだ画像分割モデルを提案する。 自然画像と医用画像の数値実験により,提案手法は既存の方法よりも優れていることが示された。
  論文  参考訳（メタデータ） (2022-03-22T00:05:19Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。 ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
  論文  参考訳（メタデータ） (2022-03-18T05:49:13Z)
• Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update [88.73437209862891]
  2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。 本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。 ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
  論文  参考訳（メタデータ） (2021-07-15T17:33:05Z)
• Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners [37.03247707259297]
  二次正則化を伴う最小二乗問題を検討し,適応的なスケッチサイズを持つ新しいスケッチベース反復手法を提案する。 スケッチのサイズは、線形収束を保証するためにデータ行列の有効次元と同じくらい小さくすることができる。 効果的な寸法の観点からスケッチサイズを選択する際の大きな困難は、後者が実際には通常不明であるという事実にあります。
  論文  参考訳（メタデータ） (2021-04-29T04:36:41Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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