論文の概要: Optimal Diagonal Preconditioning: Theory and Practice
- arxiv url: http://arxiv.org/abs/2209.00809v1
- Date: Fri, 2 Sep 2022 04:21:28 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-05 12:14:20.293739
- Title: Optimal Diagonal Preconditioning: Theory and Practice
- Title（参考訳）: 最適対角プレコンディショニング:理論と実践
- Authors: Zhaonan Qu, Wenzhi Gao, Oliver Hinder, Yinyu Ye, Zhengyuan Zhou
- Abstract要約: 本稿では,列数や列数の最大化を同時に達成するために,最適対角前処理の問題を提案する。
実装が容易なベースライン分岐アルゴリズムを提案する。
次に, 片側最適対角前条件問題に特化し, 標準双対SDP問題として定式化できることを実証する。
- 参考スコア（独自算出の注目度）: 23.79536881427839
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Preconditioning has been a staple technique in optimization and machine
learning. It often reduces the condition number of the matrix it is applied to,
thereby speeding up convergence of optimization algorithms. Although there are
many popular preconditioning techniques in practice, most lack theoretical
guarantees for reductions in condition number. In this paper, we study the
problem of optimal diagonal preconditioning to achieve maximal reduction in the
condition number of any full-rank matrix by scaling its rows or columns
separately or simultaneously. We first reformulate the problem as a
quasi-convex problem and provide a baseline bisection algorithm that is easy to
implement in practice, where each iteration consists of an SDP feasibility
problem. Then we propose a polynomial time potential reduction algorithm with
$O(\log(\frac{1}{\epsilon}))$ iteration complexity, where each iteration
consists of a Newton update based on the Nesterov-Todd direction. Our algorithm
is based on a formulation of the problem which is a generalized version of the
Von Neumann optimal growth problem. Next, we specialize to one-sided optimal
diagonal preconditioning problems, and demonstrate that they can be formulated
as standard dual SDP problems, to which we apply efficient customized solvers
and study the empirical performance of our optimal diagonal preconditioners.
Our extensive experiments on large matrices demonstrate the practical appeal of
optimal diagonal preconditioners at reducing condition numbers compared to
heuristics-based preconditioners.
- Abstract（参考訳）: プレコンディショニングは最適化と機械学習において重要なテクニックである。
これはしばしば適用される行列の条件数を減らし、最適化アルゴリズムの収束を高速化する。
実際には多くのプリコンディショニング技術があるが、ほとんどが条件数の減少に関する理論的保証を欠いている。
本稿では,任意のフルランク行列の条件数に対して,行や列を個別に,あるいは同時にスケーリングすることで最大化を実現するために,最適対角前処理の問題を検討する。
まず,この問題を準凸問題として再検討し,各イテレーションがsdp実現可能性問題からなるような,実装が容易なベースライン二分割アルゴリズムを提供する。
次に、各イテレーションがネステロフ-トッド方向に基づくニュートン更新からなる、$o(\log(\frac{1}{\epsilon}))$イテレーション複雑性を持つ多項式時間ポテンシャル低減アルゴリズムを提案する。
我々のアルゴリズムは、フォン・ノイマン最適成長問題の一般化版である問題の定式化に基づいている。
次に, 片側最適対角前条件問題に特化し, 標準双対SDP問題として定式化できることを示し, 効率的なカスタマイズ解法を適用し, 最適対角前条件器の実証性能について検討する。
大規模行列に関する広範な実験は, ヒューリスティックス型プリコンディショナーと比較して, 最適対角型プリコンディショナーの条件数低減の実用性を示す。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳（メタデータ） (2023-10-18T10:29:58Z) - Fast Screening Rules for Optimal Design via Quadratic Lasso
Reformulation [0.135975510645475]
本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。
新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。
本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
論文 参考訳（メタデータ） (2023-10-13T08:10:46Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Infeasible Deterministic, Stochastic, and Variance-Reduction Algorithms for Optimization under Orthogonality Constraints [9.301728976515255]
本稿では,着陸アルゴリズムの実用化と理論的展開について述べる。
まず、この方法はスティーフェル多様体に拡張される。
また、コスト関数が多くの関数の平均である場合の分散還元アルゴリズムについても検討する。
論文 参考訳（メタデータ） (2023-03-29T07:36:54Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank
Constraints [3.179831861897336]
低ランク最適化問題を証明可能な最適性に解決するためのフレームワークを提供する。
我々のフレームワークは、ラウンドリングや局所探索技術を通じて、ほぼ最適のソリューションを提供する。
論文 参考訳（メタデータ） (2020-09-22T08:59:06Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。