Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929232888725504 |
|---|---|
| author | Nguyen, Tuan-Anh Thang, Nguyen Kim Trystram, Denis |
| author_facet | Nguyen, Tuan-Anh Thang, Nguyen Kim Trystram, Denis |
| contents | Learning at the edges has become increasingly important as large quantities of data are continually generated locally. Among others, this paradigm requires algorithms that are simple (so that they can be executed by local devices), robust (again uncertainty as data are continually generated), and reliable in a distributed manner under network issues, especially delays. In this study, we investigate the problem of online convex optimization under adversarial delayed feedback. We propose two projection-free algorithms for centralised and distributed settings in which they are carefully designed to achieve a regret bound of O(\sqrt{B}) where B is the sum of delay, which is optimal for the OCO problem in the delay setting while still being projection-free. We provide an extensive theoretical study and experimentally validate the performance of our algorithms by comparing them with existing ones on real-world problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02114 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach Nguyen, Tuan-Anh Thang, Nguyen Kim Trystram, Denis Machine Learning Data Structures and Algorithms Learning at the edges has become increasingly important as large quantities of data are continually generated locally. Among others, this paradigm requires algorithms that are simple (so that they can be executed by local devices), robust (again uncertainty as data are continually generated), and reliable in a distributed manner under network issues, especially delays. In this study, we investigate the problem of online convex optimization under adversarial delayed feedback. We propose two projection-free algorithms for centralised and distributed settings in which they are carefully designed to achieve a regret bound of O(\sqrt{B}) where B is the sum of delay, which is optimal for the OCO problem in the delay setting while still being projection-free. We provide an extensive theoretical study and experimentally validate the performance of our algorithms by comparing them with existing ones on real-world problems. |
| title | Handling Delayed Feedback in Distributed Online Optimization : A Projection-Free Approach |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.02114 |