論文の概要: Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
- arxiv url: http://arxiv.org/abs/2105.08285v1
- Date: Tue, 18 May 2021 05:23:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-19 14:08:46.872854
- Title: Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing
- Title（参考訳）: 局所感性ハッシュによる線形最小二乗値反復
- Authors: Anshumali Shrivastava, Zhao Song, Zhaozhuo Xu
- Abstract要約: 本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。
我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
- 参考スコア（独自算出の注目度）: 49.73889315176884
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We present the first provable Least-Squares Value Iteration (LSVI) algorithms
that have runtime complexity sublinear in the number of actions. We formulate
the value function estimation procedure in value iteration as an approximate
maximum inner product search problem and propose a locality sensitive hashing
(LSH) [Indyk and Motwani STOC'98, Andoni and Razenshteyn STOC'15, Andoni,
Laarhoven, Razenshteyn and Waingarten SODA'17] type data structure to solve
this problem with sublinear time complexity. Moreover, we build the connections
between the theory of approximate maximum inner product search and the regret
analysis of reinforcement learning. We prove that, with our choice of
approximation factor, our Sublinear LSVI algorithms maintain the same regret as
the original LSVI algorithms while reducing the runtime complexity to sublinear
in the number of actions. To the best of our knowledge, this is the first work
that combines LSH with reinforcement learning resulting in provable
improvements. We hope that our novel way of combining data-structures and
iterative algorithm will open the door for further study into cost reduction in
optimization.
- Abstract（参考訳）: 本稿では,動作数において実行時の複雑性を部分線形に有する,最初の証明可能な最小二乗値反復 (lsvi) アルゴリズムを提案する。
本稿では,最大内部積探索問題として値反復値関数推定法を定式化し,局所性に敏感なハッシュ (LSH) [Indyk and Motwani STOC'98, Andoni and Razenshteyn STOC'15, Andoni, Laarhoven, Razenshteyn and Waingarten SODA'17] 型データ構造を提案する。
さらに, 近似最大内積探索理論と強化学習の後悔分析との関係を明らかにした。
我々は、近似係数を選択することで、我々のSublinear LSVIアルゴリズムが元のLSVIアルゴリズムと同じ後悔を保ちつつ、実行時の複雑さをアクションの数でサブリニアに減らすことを証明した。
私たちの知る限りでは、これはlshと強化学習を組み合わせることで、証明可能な改善をもたらす最初の仕事です。
データ構造と反復アルゴリズムを組み合わせた新しい手法が、コスト削減と最適化のさらなる研究の扉を開くことを願っている。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Making RL with Preference-based Feedback Efficient via Randomization [11.019088464664696]
人間のフィードバックから学習する強化学習アルゴリズムは、統計複雑性、計算複雑性、クエリ複雑性の点で効率的である必要がある。
提案するアルゴリズムは, サンプル効率のよいアルゴリズム(すなわち, ほぼ最適ケースの後悔境界)と実行時間(すなわち, 関連するパラメータに関して計算複雑性が最悪の場合)を提案する。
結果をより一般的な非線形関数近似に拡張するために、トンプソンサンプリングのアイデアに触発されたモデルベースランダム化アルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-10-23T04:19:35Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Ordering for Non-Replacement SGD [7.11967773739707]
我々は,アルゴリズムの非置換形式に対する収束率を改善する順序付けを求める。
我々は,強い凸関数と凸関数のステップサイズを一定かつ小さくするための最適順序付けを開発する。
さらに、注文とミニバッチを組み合わせることで、より複雑なニューラルネットワークにも適用できます。
論文 参考訳（メタデータ） (2023-06-28T00:46:58Z) - Recovering Simultaneously Structured Data via Non-Convex Iteratively
Reweighted Least Squares [0.8702432681310401]
線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。
IRLS法は,低/複合状態の計測に好適であることを示す。
論文 参考訳（メタデータ） (2023-06-08T06:35:47Z) - A Recursively Recurrent Neural Network (R2N2) Architecture for Learning
Iterative Algorithms [64.3064050603721]
本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。
本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
論文 参考訳（メタデータ） (2022-11-22T16:30:33Z) - Linear regression with partially mismatched data: local search with
theoretical guarantees [9.398989897176953]
本稿では,予測と応答のペアが部分的に一致しない線形回帰の重要な変種について検討する。
最適化定式化を用いて、基礎となる回帰係数とミスマッチに対応する置換を同時に学習する。
我々は,局所探索アルゴリズムが線形速度でほぼ最適解に収束することを証明した。
論文 参考訳（メタデータ） (2021-06-03T23:32:12Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - A Robust Matching Pursuit Algorithm Using Information Theoretic Learning [37.968665739578185]
情報理論学習(ITL)に基づく新しいOMPアルゴリズムの開発
シミュレーションおよび実世界の両方のデータに対する実験結果は、データ復元、画像再構成、分類において提案したOMPアルゴリズムの優位性を一貫して示している。
論文 参考訳（メタデータ） (2020-05-10T01:36:00Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。