[1S3-GS-2] Machine learning:

[1S3-GS-2-02] Online Submodular Minimization for the Stochastically Extended Adversarial Model

〇Tsubasa Harada¹, Kei Takemura², Tatsuya Matsuoka² (1. Institute of Science Tokyo, 2. NEC Corporation)

Keywords:Online Learning, Regret Analysis, Submodular Minimization

In online submodular minimization, a player selects a subset of a known finite set in each round and then receives a submodular loss function. The objective is to minimize the cumulative loss. Under the stochastically extended adversarial (SEA) model for online optimization, a probability distribution of the loss function is determined adversarially at the beginning of each round, and a loss function is sampled according to that distribution. This model encompasses both stochastic and adversarial environments and can represent intermediate environments between these two extremes.

In this paper, we address online submodular minimization under the SEA model, originally developed in the context of online convex optimization, and propose a new algorithm for this setting. The proposed algorithm guarantees a regret bound that aligns with the existing regret bounds for online convex optimization in SEA environments while also ensuring another regret bound tailored to online submodular minimization in stochastic environments.