論文の概要: 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問題として定式化できることを示し, 効率的なカスタマイズ解法を適用し, 最適対角前条件器の実証性能について検討する。
大規模行列に関する広範な実験は, ヒューリスティックス型プリコンディショナーと比較して, 最適対角型プリコンディショナーの条件数低減の実用性を示す。
関連論文リスト
- Matrix Reordering for Noisy Disordered Matrices: Optimality and
Computationally Efficient Algorithms [5.011150818987905]
まず、行列の順序付け問題に対する基本的な統計的限界を決定理論の枠組みで確立する。
そこで我々は,性能の向上を保証した新しい時間適応ソートアルゴリズムを提案する。
既存の手法よりも適応的ソートアルゴリズムの方が優れていることがシミュレーション研究および2つの実シングルセルRNAシークエンシングデータセットの解析で示されている。
論文 参考訳（メタデータ） (2022-01-17T14:53:52Z) - An Accelerated Variance-Reduced Conditional Gradient Sliding Algorithm
for First-order and Zeroth-order Optimization [111.24899593052851]
条件勾配アルゴリズム(Frank-Wolfeアルゴリズムとも呼ばれる)は、最近、機械学習コミュニティで人気を取り戻している。
ARCSは、ゼロ階最適化において凸問題を解く最初のゼロ階条件勾配スライディング型アルゴリズムである。
1次最適化では、ARCSの収束結果は、勾配クエリのオラクルの数で、従来のアルゴリズムよりも大幅に優れていた。
論文 参考訳（メタデータ） (2021-09-18T07:08:11Z) - Reducing the Variance of Gaussian Process Hyperparameter Optimization
with Preconditioning [54.01682318834995]
プレコンディショニングは、行列ベクトル乗算を含む反復的な方法にとって非常に効果的なステップである。
プレコンディショニングには、これまで検討されていなかった付加的なメリットがあることを実証する。
基本的に無視可能なコストで、同時に分散を低減することができる。
論文 参考訳（メタデータ） (2021-07-01T06:43:11Z) - 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) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。