Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2206.00861 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929447280574464 |
|---|---|
| author | Ohnishi, Motoya Ishikawa, Isao Kuroki, Yuko Ikeda, Masahiro |
| author_facet | Ohnishi, Motoya Ishikawa, Isao Kuroki, Yuko Ikeda, Masahiro |
| contents | This work tackles the dynamic structure estimation problems for periodically behaved discrete dynamical system in the Euclidean space. We assume the observations become sequentially available in a form of bandit feedback contaminated by a sub-Gaussian noise. Under such fairly general assumptions on the noise distribution, we carefully identify a set of recoverable information of periodic structures. Our main results are the (computation and sample) efficient algorithms that exploit asymptotic behaviors of exponential sums to effectively average out the noise effect while preventing the information to be estimated from vanishing. In particular, the novel use of the Weyl sum, a variant of exponential sums, allows us to extract spectrum information for linear systems. We provide sample complexity bounds for our algorithms, and we experimentally validate our theoretical claims on simulations of toy examples, including Cellular Automata. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2206_00861 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums Ohnishi, Motoya Ishikawa, Isao Kuroki, Yuko Ikeda, Masahiro Discrete Mathematics Machine Learning This work tackles the dynamic structure estimation problems for periodically behaved discrete dynamical system in the Euclidean space. We assume the observations become sequentially available in a form of bandit feedback contaminated by a sub-Gaussian noise. Under such fairly general assumptions on the noise distribution, we carefully identify a set of recoverable information of periodic structures. Our main results are the (computation and sample) efficient algorithms that exploit asymptotic behaviors of exponential sums to effectively average out the noise effect while preventing the information to be estimated from vanishing. In particular, the novel use of the Weyl sum, a variant of exponential sums, allows us to extract spectrum information for linear systems. We provide sample complexity bounds for our algorithms, and we experimentally validate our theoretical claims on simulations of toy examples, including Cellular Automata. |
| title | Dynamic Structure Estimation from Bandit Feedback using Nonvanishing Exponential Sums |
| topic | Discrete Mathematics Machine Learning |
| url | https://arxiv.org/abs/2206.00861 |