Online Linear Optimization with Sparsity Constraints

Jun-Kun Wang, Chi-Jen Lu, Shou-De Lin
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:883-897, 2019.

Abstract

We study the problem of online linear optimization with sparsity constraints in the semi-bandit setting. It can be seen as a marriage between two well-known problems: the online linear optimization problem and the combinatorial bandit problem. For this problem, we provide an algorithm which is efficient and achieves a sublinear regret bound. Moreover, we extend our results to two generalized settings, one with delayed feedbacks and one with costs for receiving feedbacks. Finally, we conduct experiments which show the effectiveness of our methods in practice.

Cite this Paper

BibTeX
@InProceedings{pmlr-v98-wang19b, title = {Online Linear Optimization with Sparsity Constraints}, author = {Wang, Jun-Kun and Lu, Chi-Jen and Lin, Shou-De}, booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory}, pages = {883--897}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/wang19b/wang19b.pdf}, url = {https://proceedings.mlr.press/v98/wang19b.html}, abstract = { We study the problem of online linear optimization with sparsity constraints in the semi-bandit setting. It can be seen as a marriage between two well-known problems: the online linear optimization problem and the combinatorial bandit problem. For this problem, we provide an algorithm which is efficient and achieves a sublinear regret bound. Moreover, we extend our results to two generalized settings, one with delayed feedbacks and one with costs for receiving feedbacks. Finally, we conduct experiments which show the effectiveness of our methods in practice.} }
Endnote
%0 Conference Paper %T Online Linear Optimization with Sparsity Constraints %A Jun-Kun Wang %A Chi-Jen Lu %A Shou-De Lin %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-wang19b %I PMLR %P 883--897 %U https://proceedings.mlr.press/v98/wang19b.html %V 98 %X We study the problem of online linear optimization with sparsity constraints in the semi-bandit setting. It can be seen as a marriage between two well-known problems: the online linear optimization problem and the combinatorial bandit problem. For this problem, we provide an algorithm which is efficient and achieves a sublinear regret bound. Moreover, we extend our results to two generalized settings, one with delayed feedbacks and one with costs for receiving feedbacks. Finally, we conduct experiments which show the effectiveness of our methods in practice.
APA
Wang, J., Lu, C. & Lin, S.. (2019). Online Linear Optimization with Sparsity Constraints. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:883-897 Available from https://proceedings.mlr.press/v98/wang19b.html.

Related Material