English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem of estimating a linear time-invariant (LTI) dynamicalsystem from a single trajectory via streaming algorithms, which is encounteredin several applications including reinforcement learning (RL) and time-seriesanalysis. While the LTI system estimation problem is well-studied in the {\emoffline} setting, the practically important streaming/online setting hasreceived little attention. Standard streaming methods like stochastic gradientdescent (SGD) are unlikely to work since streaming points can be highlycorrelated. In this work, we propose a novel streaming algorithm, SGD withReverse Experience Replay ($\mathsf{SGD}-\mathsf{RER}$), that is inspired bythe experience replay (ER) technique popular in the RL literature.$\mathsf{SGD}-\mathsf{RER}$ divides data into small buffers and runs SGDbackwards on the data stored in the individual buffers. We show that thisalgorithm exactly deconstructs the dependency structure and obtains informationtheoretically optimal guarantees for both parameter error and prediction error.Thus, we provide the first -- to the best of our knowledge -- optimal SGD-stylealgorithm for the classical problem of linear system identification with afirst order oracle. Furthermore, $\mathsf{SGD}-\mathsf{RER}$ can be applied tomore general settings like sparse LTI identification with known sparsitypattern, and non-linear dynamical systems. Our work demonstrates that theknowledge of data dependency structure can aid us in designing statisticallyand computationally efficient algorithms which can "decorrelate" streamingsamples.

Streaming Linear System Identification with Reverse Experience Replay