Fugu-MT 論文翻訳(概要): Linear time dynamic programming for the exact path of optimal models selected from a finite set

論文の概要: Linear time dynamic programming for the exact path of optimal models selected from a finite set

arxiv url: http://arxiv.org/abs/2003.02808v1
Date: Thu, 5 Mar 2020 18:16:58 GMT
ステータス: 処理完了
システム内更新日: 2022-12-26 06:51:34.820470
Title: Linear time dynamic programming for the exact path of optimal models selected from a finite set
Title（参考訳）: 有限集合から選択した最適モデルの厳密な経路に対する線形時間動的計画法
Authors: Toby Hocking, Joseph Vargovich
Abstract要約: 本稿では,動的プログラミングアルゴリズムを用いて,ブレークポイントを線形時間で計算できることを示す。点検出問題に対する実証的な結果から,精度と速度の向上が示された。
参考スコア（独自算出の注目度）: 0.38073142980732994
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Many learning algorithms are formulated in terms of finding model parameters which minimize a data-fitting loss function plus a regularizer. When the regularizer involves the l0 pseudo-norm, the resulting regularization path consists of a finite set of models. The fastest existing algorithm for computing the breakpoints in the regularization path is quadratic in the number of models, so it scales poorly to high dimensional problems. We provide new formal proofs that a dynamic programming algorithm can be used to compute the breakpoints in linear time. Empirical results on changepoint detection problems demonstrate the improved accuracy and speed relative to grid search and the previous quadratic time algorithm.
Abstract（参考訳）: 多くの学習アルゴリズムは、データ適合損失関数と正規化器を最小化するモデルパラメータの発見の観点から定式化されている。正規化子が l0 擬ノルムを含むとき、結果として得られる正規化経路は有限のモデルの集合からなる。正規化経路のブレークポイントを計算するための最速の既存のアルゴリズムはモデル数で2倍であり、高次元問題へのスケールが不十分である。線形時間でブレークポイントを計算するために動的プログラミングアルゴリズムが利用できるという新しい公式な証明を提供する。変更点検出問題に対する実験結果から,グリッド探索と2次時間アルゴリズムによる精度と速度の向上が示された。

関連論文リスト

Efficient Numerical Algorithm for Large-Scale Damped Natural Gradient Descent [7.368877979221163]
本研究では,パラメータ数が利用可能なサンプル数を大幅に上回る大規模シナリオにおいて,減衰したフィッシャー行列を効率的に解くアルゴリズムを提案する。アルゴリズムはColesky分解に基づいており、一般に適用可能である。ベンチマークの結果、既存の手法よりもかなり高速であることが示されている。
論文参考訳（メタデータ） (2023-10-26T16:46:13Z)
Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation [0.135975510645475]
本研究は, 安全スクリーニングのルールを導出し, インテリジェンスサンプルを廃棄する。新しいテストは、特に高次元のパラメータ空間に関わる問題に対して、より高速に計算できる。本稿では,ラッソ法の正規化経路を計算するホモトピーアルゴリズムを,正方形 $ell_$-penalty に対して再パラメータ化する方法を示す。
論文参考訳（メタデータ） (2023-10-13T08:10:46Z)
Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique [0.6338047104436422]
ベストサブセットセクションは、このタイプの問題の聖杯として広く見なされている。軽度条件下での最適部分集合回復のためのアルゴリズムを提案し,提案した。我々の実装は、一般的な変数選択ツールキットと比較して約4倍のスピードアップを実現している。
論文参考訳（メタデータ） (2023-08-01T03:11:31Z)
Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-06-11T07:28:35Z)
Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
論文参考訳（メタデータ） (2023-05-12T13:53:03Z)
Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
論文参考訳（メタデータ） (2022-03-19T13:39:49Z)
Continuation Path with Linear Convergence Rate [18.405645120971496]
経路追従アルゴリズムは、一連のサブプロブレムを順次解決する合成最適化問題によく用いられる。本稿では,経路追従アルゴリズムの一次双対解析と,対象問題に対する線形収束率を保証するために,各サブプロブレムがどの程度正確に解けるかを決定する。スパーシリティ誘導ペナルティによる最適化を考慮し、正規化パラメータに対するアクティブセットの変化を分析する。
論文参考訳（メタデータ） (2021-12-09T18:42:13Z)
Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。 OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文参考訳（メタデータ） (2021-10-24T22:43:15Z)
Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
論文参考訳（メタデータ） (2021-09-13T18:10:52Z)
Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。本研究の結果は, 同時一次および二重側収束の形で表される。
論文参考訳（メタデータ） (2020-08-23T20:36:49Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。