論文の概要: Learning from Censored and Dependent Data: The case of Linear Dynamics
- arxiv url: http://arxiv.org/abs/2104.05087v1
- Date: Sun, 11 Apr 2021 19:55:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-14 06:40:27.747534
- Title: Learning from Censored and Dependent Data: The case of Linear Dynamics
- Title（参考訳）: 検閲データと依存データからの学習:線形ダイナミクスの場合
- Authors: Orestis Plevrakis
- Abstract要約: センサーの飽和化、検出効果の制限、画像フレーム効果により、センサは実用的です。
線形力学系を学習する最近の進歩を踏まえ,LDSを検閲された観察から学習する数十年前の問題を再考する。
我々は,oracle がセット $s_t$ へのアクセスのみを仮定して,システム学習のための計算量および統計効率のよい最初のアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 6.09170287691728
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Observations from dynamical systems often exhibit irregularities, such as
censoring, where values are recorded only if they fall within a certain range.
Censoring is ubiquitous in practice, due to saturating sensors,
limit-of-detection effects, and image-frame effects. In light of recent
developments on learning linear dynamical systems (LDSs), and on censored
statistics with independent data, we revisit the decades-old problem of
learning an LDS, from censored observations (Lee and Maddala (1985); Zeger and
Brookmeyer (1986)). Here, the learner observes the state $x_t \in \mathbb{R}^d$
if and only if $x_t$ belongs to some set $S_t \subseteq \mathbb{R}^d$. We
develop the first computationally and statistically efficient algorithm for
learning the system, assuming only oracle access to the sets $S_t$. Our
algorithm, Stochastic Online Newton with Switching Gradients, is a novel
second-order method that builds on the Online Newton Step (ONS) of Hazan et al.
(2007). Our Switching-Gradient scheme does not always use (stochastic)
gradients of the function we want to optimize, which we call "censor-aware"
function. Instead, in each iteration, it performs a simple test to decide
whether to use the censor-aware, or another "censor-oblivious" function, for
getting a stochastic gradient.
In our analysis, we consider a "generic" Online Newton method, which uses
arbitrary vectors instead of gradients, and we prove an error-bound for it.
This can be used to appropriately design these vectors, leading to our
Switching-Gradient scheme. This framework significantly deviates from the
recent long line of works on censored statistics (e.g., Daskalakis et al.
(2018); Kontonis et al. (2019); Daskalakis et al. (2019)), which apply
Stochastic Gradient Descent (SGD), and their analysis reduces to establishing
conditions for off-the-shelf SGD-bounds.
- Abstract（参考訳）: 力学系からの観測は、しばしば検閲のような不規則性を示すが、そこでは値が一定の範囲内にある場合にのみ記録される。
センサーの飽和、検出の限界効果、画像フレーム効果などにより、実際にセンサはユビキタスである。
近年の線形力学系(LDSs)の学習や、独立データを用いた検閲統計学の発展を踏まえて、検閲された観測結果(Lee and Maddala (1985), Zeger and Brookmeyer (1986) から LDS を学習する数十年前の問題を再考する。
ここで、学習者は、$x_t \in \mathbb{r}^d$ if と $x_t$ がいくつかの集合 $s_t \subseteq \mathbb{r}^d$ に属する場合に限り、状態を監視する。
我々は,oracle がセット $s_t$ へのアクセスのみを仮定して,システム学習のための計算量および統計効率のよい最初のアルゴリズムを開発した。
我々のアルゴリズムであるStochastic Online Newton with Switching Gradientsは、HazanらのOnline Newton Step(ONS)上に構築された新しい2階法である。
(2007).
私たちのスイッチンググレードのスキームでは、最適化したい機能の(統計的)勾配が常に使われてはいません。
代わりに、各イテレーションで、確率勾配を得るために検閲対応か、あるいは別の「検閲対応」関数を使うかを決定するための簡単なテストを実行する。
本解析では,勾配の代わりに任意のベクトルを用いる「ジェネリック」オンラインニュートン法を考察し,誤りバウンドを証明した。
これはこれらのベクトルを適切に設計するために使用することができ、Switching-Gradientスキームに繋がる。
この枠組みは、検閲された統計に関する最近の長い研究(例えば、ダスカラキスなど)から著しく逸脱している。
(2018年)、Kontonis et al。
(2019) daskalakisら。
(2019) をSGD (Stochastic Gradient Descent) に適用し, その解析は既成のSGD境界条件の確立に還元する。
関連論文リスト
- Agnostic Smoothed Online Learning [5.167069404528051]
本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。
R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
論文 参考訳（メタデータ） (2024-10-07T15:25:21Z) - Rethinking PGD Attack: Is Sign Function Necessary? [131.6894310945647]
本稿では,このような手話に基づく更新アルゴリズムが段階的攻撃性能にどのように影響するかを理論的に分析する。
本稿では,手話の使用を排除したRGDアルゴリズムを提案する。
提案したRGDアルゴリズムの有効性は実験で広く実証されている。
論文 参考訳（メタデータ） (2023-12-03T02:26:58Z) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳（メタデータ） (2023-09-12T14:36:13Z) - Deletion and Insertion Tests in Regression Models [1.2891210250935148]
説明可能なAI(XAI)の基本課題は、ブラックボックス関数$f$による予測の背後にある最も重要な特徴を特定することである。
Petsiuk et al. Kernel の挿入と削除テストは、分類においてピクセルを最も重要視するアルゴリズムの品質を判断するために用いられる。
論文 参考訳（メタデータ） (2022-05-25T00:55:47Z) - Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。
そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。
後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
論文 参考訳（メタデータ） (2022-03-19T13:39:49Z) - Fast Gradient Non-sign Methods [67.56549792690706]
Fast Gradient Non-sign Method (FGNM) は一般的なルーチンであり、グラデーションベースの攻撃において従来の$sign$操作をシームレスに置き換えることができる。
我々の手法は、textbf27.5% と textbf9.5% でそれらを上回ります。
論文 参考訳（メタデータ） (2021-10-25T08:46:00Z) - What Happens after SGD Reaches Zero Loss? --A Mathematical Framework [35.31946061894308]
SGD(Gradient Descent)の暗黙のバイアスを理解することは、ディープラーニングにおける重要な課題の1つである。
本稿では、Katzenberger (1991) のアイデアを適応させることにより、そのような分析の一般的な枠組みを提供する。
1) a global analysis of the implicit bias for $eta-2$ steps, not to the local analysis of Blanc et al. (2020) that is only for $eta-1.6$ steps and (2) allowing any noise covariance。
論文 参考訳（メタデータ） (2021-10-13T17:50:46Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - Statistical-Query Lower Bounds via Functional Gradients [19.5924910463796]
我々は、寛容$n- (1/epsilon)b$の統計クエリアルゴリズムは、一定の$bに対して少なくとも$2nc epsilon$クエリを使用する必要があることを示す。
実数値学習では珍しいSQ学習アルゴリズムが一般的である(相関学習とは対照的に)。
論文 参考訳（メタデータ） (2020-06-29T05:15:32Z) - Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z) - NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient
Descent [1.0953917735844645]
マルチウェイオンラインデータに基づく$(N)Nにおける非効率的な問題に対して,NeCPDという新しい効率的な分解アルゴリズムを提案する。
さらに,本手法を構造的データセットを用いた実生活モニタリングの分野に適用する。
論文 参考訳（メタデータ） (2020-03-18T04:44:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。