論文の概要: Average-case Acceleration for Bilinear Games and Normal Matrices
- arxiv url: http://arxiv.org/abs/2010.02076v1
- Date: Mon, 5 Oct 2020 15:13:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-10 22:33:30.973627
- Title: Average-case Acceleration for Bilinear Games and Normal Matrices
- Title（参考訳）: 双線型ゲームと正規行列に対する平均ケース加速度
- Authors: Carles Domingo-Enrich, Fabian Pedregosa, Damien Scieur
- Abstract要約: ゼロサム双線型ゲームでは、平均ケース最適法がハミルトニアンの最小化に最適な方法であることを示す。
ディスク内の固有値を持つ行列に特化し、最悪の最適アルゴリズムと比較して証明可能なスピードアップを示す。
- 参考スコア（独自算出の注目度）: 35.14328074551363
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Advances in generative modeling and adversarial learning have given rise to
renewed interest in smooth games. However, the absence of symmetry in the
matrix of second derivatives poses challenges that are not present in the
classical minimization framework. While a rich theory of average-case analysis
has been developed for minimization problems, little is known in the context of
smooth games. In this work we take a first step towards closing this gap by
developing average-case optimal first-order methods for a subset of smooth
games. We make the following three main contributions. First, we show that for
zero-sum bilinear games the average-case optimal method is the optimal method
for the minimization of the Hamiltonian. Second, we provide an explicit
expression for the optimal method corresponding to normal matrices, potentially
non-symmetric. Finally, we specialize it to matrices with eigenvalues located
in a disk and show a provable speed-up compared to worst-case optimal
algorithms. We illustrate our findings through benchmarks with a varying degree
of mismatch with our assumptions.
- Abstract（参考訳）: 生成的モデリングと敵対的学習の進歩は、滑らかなゲームに対する新たな関心をもたらした。
しかし、2階微分の行列における対称性の欠如は、古典的な最小化の枠組みには存在しない問題を引き起こす。
平均ケース分析の豊富な理論は最小化問題のために開発されてきたが、滑らかなゲームの文脈ではほとんど知られていない。
本研究では、スムーズなゲームの部分集合に対する平均ケース最適一階法を開発することにより、このギャップを埋める第一歩を踏み出す。
主な貢献は以下の3つである。
まず、ゼロサム双線型ゲームでは、平均ケース最適法はハミルトニアンの最小化の最適な方法であることを示す。
第二に、正規行列に対応する最適手法に対して、潜在的に非対称な明示的な表現を提供する。
最後に,ディスク内の固有値を持つ行列に特化して,最悪ケースの最適アルゴリズムと比較して,証明可能なスピードアップを示す。
本研究は,我々の仮定とミスマッチの程度が異なるベンチマークによる結果を示す。
関連論文リスト
- $\ell_1$-norm rank-one symmetric matrix factorization has no spurious second-order stationary points [20.82938951566065]
この問題の2階定常点(つまり局所最小点)は、実際には大域的に最適であることを示す。
我々の手法は、様々な高度な非滑らかな学習問題の最適化状況の分析に応用できる可能性がある。
論文 参考訳（メタデータ） (2024-10-07T13:25:37Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion [15.128477070895055]
本稿では,Majorization-Minimization Gauss-Newton (MMGN) と呼ばれる新しい1ビット行列補完法を提案する。
本手法は,元の最適化問題を標準的な低ランク行列補完問題に変換する偏極最小化原理に基づく。
論文 参考訳（メタデータ） (2023-04-27T03:16:52Z) - Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization
Problems [19.930021245647705]
低ランクおよび非滑らかな行列最適化問題は統計学や機械学習における多くの基本的なタスクを捉えている。
本稿では,このような問題に対する標準凸緩和について考察する。
本研究は, テクスト性相補性条件の下で, 比較的軽度な仮定の下では, 非滑らかな目的が2つの一般的なテクストミラー-プロキシ法の近似変種であるスムーズな関数の最大値として記述できることを証明した。
論文 参考訳（メタデータ） (2022-06-23T08:10:54Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - On the Efficient Implementation of the Matrix Exponentiated Gradient
Algorithm for Low-Rank Matrix Optimization [26.858608065417663]
スペクトル上の凸最適化は、機械学習、信号処理、統計学に重要な応用がある。
低ランク行列による最適化に適したMEGの効率的な実装を提案し、各イテレーションで単一の低ランクSVDのみを使用する。
また,本手法の正しい収束のための効率よく計算可能な証明書も提供する。
論文 参考訳（メタデータ） (2020-12-18T19:14: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) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。