Online $\mathrm{L}^{\natural}$-Convex Minimization

In this paper, we propose algorithms for online $\mathrm{L}^{\natural}$-convex function minimization in two settings commonly addressed in previous studies. The first one is the full information setting, where, after making a decision, the player has access to all information relevant to that decision. The second one is the bandit setting, in which the player receives feedback only on the results of selected actions and cannot know the results of unselected actions.

We evaluate our algorithms in terms of regret, which is common in online decision making. Regret $R_{T}$ is the difference between the sum of losses up to period $T$ in each iteration and the sum of losses for the fixed choice that is optimal in hindsight. See Equation 3 in Section 2 for a formal definition of the regret.

Notation needed for explaining the contributions in this paper is listed in Table 1. The contributions of our study can be summarized as follows.

• •

  In the full information setting of online L^♮-convex function minimization, we propose a computationally efficient randomized algorithm that achieves the following regret bound:

  $$\mathbf{E}[R_{T}]=O(\hat{L}N\sqrt{dT}).$$

• •

  In the bandit setting of online L^♮-convex function minimization, we propose a computationally efficient randomized algorithm that achieves the following regret bound:

  $$\mathbf{E}[R_{T}]=O(MdNT^{2/3}).$$

• •

  In the Online L^♮-convex function minimization, for any algorithm, there is a sequence of L^♮-convex cost functions such that the algorithm has regret at least $\Omega(\hat{L}N\sqrt{dT})$. Therefore, our proposed algorithm for the full information setting achieves the best regret bound up to a constant factor.

• •

  We also present an example of problems that can be naturally formulated as online $\mathrm{L}^{\natural}$-convex minimization in Section 5.

Table 2 summerizes regret bounds on the models of online submodular minimization and online $\mathrm{L}^{\natural}$-convex minimization.

$\mathrm{L}^{\natural}$-convex functions are central functions in discrete convex analysis, which aims to establish a general framework for minimization of discrete functions (i.e., functions defined on the integer lattice) by means of a combination of the ideas in continuous and discrete optimization. As mentioned above, $\mathrm{L}^{\natural}$-convex functions generalize submodular functions and can formulate various problems in diverse fields such as operations research [7, 8], economics [18], and computer vision [22]. A combination of $\mathrm{L}^{\natural}$-convex functions and machine learning have been seen in, e.g, [24, 20]. An efficient algorithm has been proposed to minimize $\mathrm{L}^{\natural}$-convex functions [16], however devising an algorithm for online $\mathrm{L}^{\natural}$-convex minimization requires a careful combination of online optimization and discrete convex analysis and thus it is a nontrivial task.

Compared with the number of online decision-making problems on continuous domains, the number of those on discrete domains are relatively small. A submodular function is a discrete function which appears in a variety of applications in the field matching online optimization such as price optimization and thus online submodular optimization is a well-studied topic. Note that submodular functions are special cases of $\mathrm{L}^{\natural}$-convex functions with the domain restricted to $\{0,1\}^{d}$. For online submodular minimization, Hazan and Kale [12] obtained a tight regret bound for the full information setting, while Bubeck et al. [4] obtained that for the bandit setting for general online convex function minimizatin and thus for online submodular minimization (through a convex extension). Chen et al. [6] gave an algorithm for online continuous submodular maximization and demonstrate its performance in experiments.

We should note that our techniques for online $\mathrm{L}^{\natural}$-convex minimization resemble those for stochastic $\mathrm{L}^{\natural}$-convex minimization [24], however problem settings are different in that they aim to obtain PAC grarantees in stochastic models.

In the online $\mathrm{L}^{\natural}$-convex minimization, across iterations $t=1,2,\dots,T$, an online decision maker is tasked with consistently determining the point $z_{t}\in\mathcal{K}$. Following the selection of $z_{t}$ in each iteration, feedback is provided in the form of the cost $f_{t}(z_{t})$, where $f_{t}:\mathcal{K}\rightarrow\mathbb{R}$ is an $\mathrm{L}^{\natural}$-convex function.

In this paper, we consider two distinct problem settings characterized by different levels of information feedback:

• •

  In the full information setting, at each round $t$, the player has comprehensive access to the sequence of past functions $f_{1},f_{2},\dots,f_{t-1}$ applicable to any input.

• •

  In the bandit setting, at each round $t$, the player is restricted to observing the values of the functions $f_{1}(z_{1}),f_{2}(z_{2}),\dots,f_{t-1}(z_{t-1})$ corresponding to one’s previous selections $z_{j}~{}(j=1,2,\dots,t-1)$.

We introduce the Lovász extension on submodular functions, a key algorithmic tool. We leverage the fact that the restriction of an $\mathrm{L}^{\natural}$-convex function on an arbitary unit hypercube $z+\{0,1\}^{d}~{}(z\in\mathbb{Z}^{d})$, results in a submodular function [16]. Further, for any $\mathrm{L}^{\natural}$-convex set $\mathcal{K}$ and $z\in\mathcal{K}$, $\mathcal{K}\cap(z+\{0,1\}^{d})$ is a distributive lattice, where a submodular function can be defined. To define a convex extension of $\mathrm{L}^{\natural}$-convex set and function, we define the Lovász extension of a submodular function on distributive lattice. Without loss of generality we assume that distribute lattices appear in this paper are simple.

This definition follows from Theorem 3.9 in [10]. Let $\overline{D}$ denote the convex hull of $D$. Before we proceed with the formal definition of the Lovász extension, we introduce the concept of a chain.

For any $x\in\overline{D}$, there exists a unique chain that can represent $x$ as a convex combination:

where $\mu_{i}>0,~{}\sum_{i=0}^{p}\mu_{i}=1,~{}\chi_{A_{i}}\in D$ is the characteristic vector of $A_{i}\subseteq[d]~{}(i=0,\dots,d)$ [10].

It is known that any maximal chain such that all the characteristic vectors of the elements in the chain are in $D$ has length $d+1$ when $D$ is a simple distributive lattice. Moreover, such maximal chains have one-to-one correspondence to the set of total orders obtainable by topologically sorting the elements of poset $\mathcal{P}=([d],\preceq)$ representing $D$ as in Definition 3.

We define the Lovász extension on a simple distributive lattice.

We say a maximal chain is associated with $x$ if (i) all of its elements are contained in $D$ and (ii) it contains the unique maximal chain in Definition 5 as a subchain. We highlight the properties of the Lovász extension and submodular functions that are particularly critical, as outlined below.

We introduce a convex extension of an $\mathrm{L}^{\natural}$-convex function by piecing together the Lovász extension of submodular functions introduced in the previous subsection. As a preparation, we introduce a maximal chain associated with $x\in\overline{\mathcal{K}}$.

We define a convex extension of $\mathrm{L}^{\natural}$-convex functions.

This convex extension $\hat{f}$ is piecewise linear by definition, and the subgradient of $\hat{f}$ at $x\in\overline{\mathcal{K}}$ can be easily computed by the chain.

Next, we introduce an important property of $\hat{f}$ defined by Equation 8.

In addition, as with the case of submodular function, the following is known.

We have defined the convex extension $\hat{f}:\overline{\mathcal{K}}\rightarrow\mathbb{R}$ of an $\mathrm{L}^{\natural}$-convex function $f:\mathcal{K}\rightarrow\mathbb{R}$ in the previous subsection. Our algorithms in Section 3 rely on the fact that the subgradient $g$ of $\hat{f}$ at a given point $x\in\overline{\mathcal{K}}$ can be computed efficiently. Here, we explain how this can be done.

Recall that the convex extension $\hat{f}$ of an $\mathrm{L}^{\natural}$-convex function $f$ is constructed by piecing together the Lovász extension of the submodular function restricted to each unit hypercube $z+\{0,1\}^{d}$ ($z\in\mathbb{Z}^{d}$). Since we can compute the subgradient for submodular functions, it suffices to show that, given a point $x\in\overline{\mathcal{K}}$, we can compute a maximal chain associated with $x$ (see Definition 6). This can be easily done when each $x_{i}\notin\mathbb{Z}$, since we can set $z=\lfloor x\rfloor$ and express $x$ as a convex combination of the characteristic vectors corresponding to a maximal chain of $z+\{0,1\}^{d}$. Hence, the challenge here is to compute such a maximal chain when $x_{i}\in\mathbb{Z}$ for some $i\in[d]$ (consider the case when $\mathcal{K}=\{y\in\mathbb{Z}^{2}\mid y_{1},y_{2}\leq 2\}$ and $x=(2,2)$, where we cannot set $z=\lfloor x\rfloor$), and we show how to do this in the following.

We use the fact that the domain $\mathcal{K}$ is an $\mathrm{L}^{\natural}$-convex set that can be expressed by a system of linear inequalities using $\check{\gamma},\hat{\gamma}:[d]\to\mathbb{Z}$ and $\gamma:[d]^{2}\to\mathbb{Z}$ as follows (see, e.g., [17]):

where

It is also known that $\overline{\mathcal{K}}=P(\gamma,\check{\gamma},\hat{\gamma})$. We assume that the expression (9) is explicitly given.

As in the case of submodular functions, we assume without loss of generality that $\overline{\mathcal{K}}$ is full-dimensional (this corresponds to that the domain of a submodular function is a simple distributive lattice).

As noted above, we would like to compute a maximal chain associated with $x$ for given $x\in\overline{\mathcal{K}}$. As shown in Subsection 2.3, a maximal chain can be found when $(z+[0,1]^{d})\cap\overline{\mathcal{K}}$ is full-dimensional. Hence, above computation can be reduced to the following problem: given $x\in\overline{\mathcal{K}}$, find $\underline{z}\in\mathbb{Z}^{d}$ such that $(\underline{z}+[0,1]^{d})\cap\overline{\mathcal{K}}$ is full-dimensional, i.e., a simple distributive lattice. This problem can be solved by the following procedure.

Now, we show the correctness of the above procedure, We first claim that each $D_{i}$ ($i=0,1,2,\dots,d$) is full-dimensional. Since $D_{d}=(\underline{z}+[0,1]^{d})\cap\overline{\mathcal{K}}$, $(\underline{z}+[0,1]^{d})\cap\overline{\mathcal{K}}$ is full-dimensional as desired. To show this claim, we need the following auxiliary lemma. For $c\in\mathbb{R}^{d}$ and $r>0$, let $B(c,r)\subseteq\mathbb{R}^{d}$ be the open ball with center $c$ and radius $r$, i.e., $B(c,r)=\{y\in\mathbb{R}^{d}\mid||y-c||_{2}<r\}$. Note that a subset of $\mathbb{R}^{d}$ is full-dimensional if and only if it includes an open ball (which in turn is equivalent to that it has a positive volume).

We are ready to prove that $D_{i}$ is full-dimensional for each $i=0,1,2,\dots,d$.

Since $(\underline{z}+[0,1]^{d})\cap\overline{\mathcal{K}}$ is full-dimensional as shown above, the function $f_{\underline{z}}:=f|_{\mathcal{K}\cap(\underline{z}+[0,1]^{d})}$ is a submodular function over a simple distributive lattice. Also, we can compute the poset representation of ${\rm dom}\,(f_{\underline{z}})(=K\cap(z+[0,1]^{d}))$ as follows. $i\preceq j$ if $\underline{z}_{i}-\underline{z}_{j}=\delta_{i,j}:=\max_{y\in\overline{\mathcal{K}}}y_{i}-y_{j}$. By topologically sorting this poset, we can compute a maximal chain in $(\underline{z}+\{0,1\}^{d})\cap\mathcal{K}$ and thus compute the subgradient of $\hat{f}$ at $x$ by (7) in Lemma 1. We summarize this as a proposition as follows.

In this section, we extend the online submodular minimization algorithm (Algorithm 2 from Hazan and Kale [12]) to $\mathrm{L}^{\natural}$-convex functions in the full information setting. Subsequently, we derive an upper bound for the regret of the algorithm.

Let $\mathcal{K}$ be an arbitrary $\mathrm{L}^{\natural}$-convex set, and let $\overline{\mathcal{K}}$ be the convex hull of $\mathcal{K}$. As a preparation, define the convex projection $\Pi_{\overline{\mathcal{K}}}:\mathbb{R}^{d}\rightarrow\overline{\mathcal{K}}$ onto the convex set $\overline{\mathcal{K}}$ as follows:

When $\mathcal{K}=[N]^{d}$, $\Pi_{\overline{\mathcal{K}}}(y)$ can be easily calculated as follows:

We assume that this projection operation can be done efficiently, since it is a minimization of a convex function.

Next, define the rounding function $\mathcal{P}_{\tau}:\mathbb{R}^{d}\rightarrow\mathbb{Z}^{d}$ using the threshold $\tau\in[0,1]$ as follows:

With these preparatory definitions in place, we now detail the operational flow of the Algorithm 2 (L^♮-convex Subgradient Descent).

At each iteration $t$, a threshold $\tau$ is chosen uniformly at random from the interval $[0,1]$. This threshold is then used to discretize the continuous decision variable $x_{t}\in\overline{\mathcal{K}}$ into a discrete variable $z_{t}\in\mathcal{K}$. Subsequently, the cost associated with $z_{t}$ is determined. Based on this cost, $x_{t}$ is updated using the calculated subgradient. The algorithm repeats this process $T$ times. The process flow can be summarized as shown in Algorithm 2 below.

Here, at each round $t$, the most computationally expensive part is the element-by-element sorting required to find the Lovász extension, with a computational complexity of $O(d\log d)$. Therefore, the overall computational complexity is $O(Td\log d)$, which can be computed in polynomial time.

Next, in preparation for showing the regret upper bound of Algorithm 2, we introduce the Lemma 6. Lemma 6 states that the norm of the subgradient is bounded above by the Lipschitz constant.

For regret analysis, we extend Lemma 11 in Hazan and Kale [12] over $\mathcal{K}$.

The proof is similar to Lemma 11 in Hazan and Kale [12].

Building on the aforementioned results, we give the regret bounds in Theorem 3.1.

It can be proved by using Lemmas 1, 6, and 7.

In this section, we extend the online submodular minimization algorithm (Algorithm 3 in Hazan and Kale [12]) to L^♮-convex functions to obtain upper bound on regret. Let $f_{t}:\mathcal{K}\rightarrow[-M,M]~{}(\forall t\in[T])$, where the function value is bounded.

We describe the subgradient descent algorithm under the bandit setting for $\mathrm{L}^{\natural}$-convex functions. For each iteration $t$, the algorithm identifies the maximal chain associated with $x_{t}$ and its associated permutation $\pi$. This allows for the representation of $x_{t}$ as a convex combination. A point $z_{t}$ is chosen based on probabilities $\rho_{i}$, which are derived from coefficients $\mu_{i}$ in the representation of $x_{t}$ and parameter $\delta$. The cost $f_{t}(z_{t})$ at the chosen point $z_{t}$ is obtained. An unbiased estimator of the subgradient $\hat{g}_{t}$ of $\hat{f}_{t}$ at $x_{t}$ is computed, varying according to the value of $z_{t}$, probabilities $\rho_{i}$, and a randomly selected $\varepsilon_{t}$. The algorithm updates $x_{t+1}$ using the current point $x_{t}$, step size $\eta$, and the estimated subgradient $\hat{g}_{t}$. The process flow can be summarized as shown in Algorithm 3 below.