論文の概要: Generalization Bounds for Data-Driven Numerical Linear Algebra
- arxiv url: http://arxiv.org/abs/2206.07886v1
- Date: Thu, 16 Jun 2022 02:23:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-18 14:24:49.512788
- Title: Generalization Bounds for Data-Driven Numerical Linear Algebra
- Title（参考訳）: データ駆動数値線形代数の一般化境界
- Authors: Peter Bartlett, Piotr Indyk, Tal Wagner
- Abstract要約: データ駆動アルゴリズムは、トレーニングされた入力サンプルから学習することで、未知のアプリケーション固有の分布からの入力に内部構造やパラメータを適用することができる。
いくつかの最近の研究は、数値線形代数における問題にこのアプローチを適用し、性能において顕著な経験的利得を得た。
本研究では、Gupta と Roughgarden が提案するデータ駆動アルゴリズム選択のためのPAC学習フレームワークにおいて、これらのアルゴリズムの一般化境界を証明する。
- 参考スコア（独自算出の注目度）: 24.961270871124217
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Data-driven algorithms can adapt their internal structure or parameters to
inputs from unknown application-specific distributions, by learning from a
training sample of inputs. Several recent works have applied this approach to
problems in numerical linear algebra, obtaining significant empirical gains in
performance. However, no theoretical explanation for their success was known.
In this work we prove generalization bounds for those algorithms, within the
PAC-learning framework for data-driven algorithm selection proposed by Gupta
and Roughgarden (SICOMP 2017). Our main results are closely matching upper and
lower bounds on the fat shattering dimension of the learning-based low rank
approximation algorithm of Indyk et al.~(NeurIPS 2019). Our techniques are
general, and provide generalization bounds for many other recently proposed
data-driven algorithms in numerical linear algebra, covering both
sketching-based and multigrid-based methods. This considerably broadens the
class of data-driven algorithms for which a PAC-learning analysis is available.
- Abstract（参考訳）: データ駆動アルゴリズムは、入力のトレーニングサンプルから学習することで、内部構造やパラメータを未知のアプリケーション固有分布からの入力に適応させることができる。
いくつかの最近の研究は、数値線形代数における問題にこのアプローチを適用し、性能において顕著な経験的利得を得た。
しかし、その成功に関する理論的説明は分かっていない。
本稿では,gupta と roughgarden (sicomp 2017) が提案するpac-learning framework for data-driven algorithm selectionにおいて,それらのアルゴリズムの一般化限界を証明する。
本研究の主な成果は,Indykらによる学習に基づく低ランク近似アルゴリズムの脂肪破砕次元の上下境界の密接な一致である。
〜(2019年)。
提案手法は一般化され,近年提案されている数値線形代数におけるデータ駆動アルゴリズムの多くに一般化境界を提供し,スケッチベースとマルチグリッドベースの両方の手法をカバーする。
これにより、PAC学習分析が利用可能なデータ駆動アルゴリズムのクラスが大幅に拡大される。
関連論文リスト
- A General Online Algorithm for Optimizing Complex Performance Metrics [5.726378955570775]
我々は,バイナリ,マルチクラス,マルチラベルの分類問題において,様々な複雑なパフォーマンス指標を用いて,直接的に使用可能な汎用オンラインアルゴリズムを導入,分析する。
アルゴリズムの更新と予測のルールは、過去のデータを保存することなく、非常にシンプルで計算的に効率的である。
論文 参考訳（メタデータ） (2024-06-20T21:24:47Z) - Performance Evaluation and Comparison of a New Regression Algorithm [4.125187280299247]
新たに提案した回帰アルゴリズムの性能を,従来の4つの機械学習アルゴリズムと比較した。
GitHubリポジトリにソースコードを提供したので、読者は結果の複製を自由にできます。
論文 参考訳（メタデータ） (2023-06-15T13:01:16Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Learning-Augmented Algorithms for Online Linear and Semidefinite
Programming [9.849604820019394]
Semidefinite Programming (SDP) は線形および二次的に制約されたプログラミングを一般化する統一フレームワークである。
SDPをカバーするための制約がオンラインに届くと、最適解を近似するためには、既知の不可能な結果が存在する。
予測器が正確であれば、これらの不可能な結果を効率よく回避し、最適解に対する定数係数近似を達成できることが示される。
論文 参考訳（メタデータ） (2022-09-21T19:16:29Z) - One-Pass Learning via Bridging Orthogonal Gradient Descent and Recursive
Least-Squares [8.443742714362521]
我々は,従来のデータポイントの予測にほとんど変化しない方向にパラメータを変更しながら,すべての新しいデータポイントに完全に適合するワンパス学習アルゴリズムを開発した。
我々のアルゴリズムは、インクリメンタル・プリンシパル・コンポーネント分析(IPCA)を用いてストリーミングデータの構造を利用して、メモリを効率的に利用する。
本実験では,提案手法の有効性をベースラインと比較した。
論文 参考訳（メタデータ） (2022-07-28T02:01:31Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Structure learning in polynomial time: Greedy algorithms, Bregman
information, and exponential families [12.936601424755944]
DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。
DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。
この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
論文 参考訳（メタデータ） (2021-10-10T06:37:51Z) - Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。
提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
論文 参考訳（メタデータ） (2021-05-23T19:21:55Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳（メタデータ） (2021-01-08T18:55:07Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。
最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
論文 参考訳（メタデータ） (2020-05-07T00:39:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。