Online $\mathrm{L}^{\natural}$-Convex Minimization
This work addresses limitations in existing online submodular minimization frameworks for practical applications with combinatorial structures, offering a more general approach for researchers and practitioners in optimization and machine learning.
The paper tackles the problem of online decision-making with nonlinear combinatorial objective functions by introducing online L♮-convex minimization, which generalizes submodular functions to integer lattice domains, and proposes efficient algorithms with tight regret bounds in full information and bandit settings.
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 $\mathrm{L}^{\natural}$-convex minimization, where an $\mathrm{L}^{\natural}$-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 $\mathrm{L}^{\natural}$-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 $\mathrm{L}^{\natural}$-convex minimization.