論文の概要: Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances
- arxiv url: http://arxiv.org/abs/2310.02246v2
- Date: Thu, 2 May 2024 04:59:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-03 22:20:15.544623
- Title: Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances
- Title（参考訳）: Relaxの学習: 線形システムインスタンスのシーケンス全体にわたるソルバーパラメータの設定
- Authors: Mikhail Khodak, Edmond Chow, Maria-Florina Balcan, Ameet Talwalkar,
- Abstract要約: オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
- 参考スコア（独自算出の注目度）: 42.16343861129583
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Solving a linear system $Ax=b$ is a fundamental scientific computing primitive for which numerous solvers and preconditioners have been developed. These come with parameters whose optimal values depend on the system being solved and are often impossible or too expensive to identify; thus in practice sub-optimal heuristics are used. We consider the common setting in which many related linear systems need to be solved, e.g. during a single numerical simulation. In this scenario, can we sequentially choose parameters that attain a near-optimal overall number of iterations, without extra matrix computations? We answer in the affirmative for Successive Over-Relaxation (SOR), a standard solver whose parameter $\omega$ has a strong impact on its runtime. For this method, we prove that a bandit online learning algorithm--using only the number of iterations as feedback--can select parameters for a sequence of instances such that the overall cost approaches that of the best fixed $\omega$ as the sequence length increases. Furthermore, when given additional structural information, we show that a contextual bandit method asymptotically achieves the performance of the instance-optimal policy, which selects the best $\omega$ for each instance. Our work provides the first learning-theoretic treatment of high-precision linear system solvers and the first end-to-end guarantees for data-driven scientific computing, demonstrating theoretically the potential to speed up numerical methods using well-understood learning algorithms.
- Abstract（参考訳）: 線形システムの解法である$Ax=b$は、多くの解法とプリコンディショナーが開発された基本的な科学計算プリミティブである。
これらのパラメータは、解決されるシステムに依存する最適な値を持ち、しばしば識別が不可能または高価であるため、実際には準最適ヒューリスティックが使用される。
一つの数値シミュレーションにおいて,多くの関係線形系を解かなければならないような共通設定について考察する。
このシナリオでは、余分な行列計算なしで、ほぼ最適に近い反復数が得られるパラメータを逐次選択できるだろうか?
パラメータが$\omega$の標準解法であるSOR(Successive Over-Relaxation)はランタイムに強い影響を与える。
そこで本手法では,反復回数のみをフィードバックとして使用するバンディットオンライン学習アルゴリズムが,シーケンス長が増加するにつれて最大固定$\omega$に近づくような,一連のインスタンスのパラメータを選択できることを示す。
さらに、追加構造情報を与えると、文脈的バンディット法がインスタンス最適化ポリシーの性能を漸近的に達成し、各インスタンスに対して最高の$\omega$を選択することを示す。
我々の研究は、高精度線形システム解法の最初の学習理論的処理と、データ駆動型科学計算のエンドツーエンド保証を提供し、よく理解された学習アルゴリズムを用いて数値的手法を高速化する可能性を理論的に実証した。
関連論文リスト
- Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - OKRidge: Scalable Optimal k-Sparse Ridge Regression [21.17964202317435]
スパースリッジ回帰のための高速アルゴリズムOKRidgeを提案する。
また,ビームサーチを利用した解法を温める方法を提案する。
論文 参考訳（メタデータ） (2023-04-13T17:34:44Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳（メタデータ） (2022-10-23T21:24:37Z) - Data-Driven Reachability Analysis from Noisy Data [5.949143454441281]
与えられたシステムモデルなしでノイズの多いデータから到達可能な集合を直接計算する問題を検討する。
いくつかのリーチビリティアルゴリズムが提示され、その精度は、データを生成する基盤システムに依存することが示されている。
論文 参考訳（メタデータ） (2021-05-15T14:11:57Z) - Algorithmic Solution for Systems of Linear Equations, in
$\mathcal{O}(mn)$ time [0.0]
方程式の線形系の探索解を超高速に求める新しいアルゴリズムを提案する。
実行時間は最先端のメソッドと比較して非常に短い。
この論文はアルゴリズム収束の理論的証明も含んでいる。
論文 参考訳（メタデータ） (2021-04-26T13:40:31Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳（メタデータ） (2020-07-13T16:30:47Z) - Symbolic Regression using Mixed-Integer Nonlinear Optimization [9.638685454900047]
シンボリック回帰(SR)問題は、機械学習において難しい問題である。
混合整数非線形最適化と明示列挙法を組み合わせたハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、いくつかの合成データセットに対して、最先端のSRソフトウェアと最近の物理学に触発されたAI Feynmanという手法で競合していることを示す。
論文 参考訳（メタデータ） (2020-06-11T20:53:17Z) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。