TY - GEN
T1 - Online L♮-Convex Minimization
AU - Yokoyama, Ken
AU - Ito, Shinji
AU - Matsuoka, Tatsuya
AU - Kimura, Kei
AU - Yokoo, Makoto
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
PY - 2024
Y1 - 2024
N2 - An online decision-making problem is a learning problem in which a player repeatedly makes decisions in order to minimize the long-term loss. These problems that emerge in applications often have nonlinear combinatorial objective functions, and developing algorithms for such problems has attracted considerable attention. An existing general framework for dealing with such objective functions is the online submodular minimization. However, practical problems are often out of the scope of this framework, since the domain of a submodular function is limited to a subset of the unit hypercube. To manage this limitation of the existing framework, we in this paper introduce the online L♮-convex minimization, where an L♮-convex function generalizes a submodular function so that the domain is a subset of the integer lattice. We propose computationally efficient algorithms for the online L♮-convex function minimization in two major settings: the full information and the bandit settings. We analyze the regrets of these algorithms and show in particular that our algorithm for the full information setting obtains a tight regret bound up to a constant factor. We also demonstrate several motivating examples that illustrate the usefulness of the online L♮-convex minimization. The proofs in this paper have been omitted due to page limitations. The link to the full version is as follows: https://arxiv.org/abs/2404.17158.
AB - An online decision-making problem is a learning problem in which a player repeatedly makes decisions in order to minimize the long-term loss. These problems that emerge in applications often have nonlinear combinatorial objective functions, and developing algorithms for such problems has attracted considerable attention. An existing general framework for dealing with such objective functions is the online submodular minimization. However, practical problems are often out of the scope of this framework, since the domain of a submodular function is limited to a subset of the unit hypercube. To manage this limitation of the existing framework, we in this paper introduce the online L♮-convex minimization, where an L♮-convex function generalizes a submodular function so that the domain is a subset of the integer lattice. We propose computationally efficient algorithms for the online L♮-convex function minimization in two major settings: the full information and the bandit settings. We analyze the regrets of these algorithms and show in particular that our algorithm for the full information setting obtains a tight regret bound up to a constant factor. We also demonstrate several motivating examples that illustrate the usefulness of the online L♮-convex minimization. The proofs in this paper have been omitted due to page limitations. The link to the full version is as follows: https://arxiv.org/abs/2404.17158.
KW - Discrete convex analysis
KW - L-convex functions
KW - Online optimization
UR - https://www.scopus.com/pages/publications/105023380049
UR - https://www.scopus.com/pages/publications/105023380049#tab=citedBy
U2 - 10.1007/978-3-031-70362-1_19
DO - 10.1007/978-3-031-70362-1_19
M3 - Conference contribution
AN - SCOPUS:105023380049
SN - 9783031703614
T3 - Lecture Notes in Computer Science
SP - 319
EP - 336
BT - Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2024, Proceedings
A2 - Bifet, Albert
A2 - Davis, Jesse
A2 - Krilavicius, Tomas
A2 - Kull, Meelis
A2 - Ntoutsi, Eirini
A2 - Žliobaite, Indre
PB - Springer Science and Business Media Deutschland GmbH
T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2024
Y2 - 9 September 2024 through 13 September 2024
ER -