Skip to main navigation Skip to search Skip to main content

Online L♮-Convex Minimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2024, Proceedings
EditorsAlbert Bifet, Jesse Davis, Tomas Krilavicius, Meelis Kull, Eirini Ntoutsi, Indre Žliobaite
PublisherSpringer Science and Business Media Deutschland GmbH
Pages319-336
Number of pages18
ISBN (Print)9783031703614
DOIs
Publication statusPublished - 2024
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2024 - Vilnius, Lithuania
Duration: Sept 9 2024 → Sept 13 2024

Publication series

NameLecture Notes in Computer Science
Volume14945 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2024
Country/TerritoryLithuania
CityVilnius
Period9/9/24 → 9/13/24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Online L♮-Convex Minimization'. Together they form a unique fingerprint.

Cite this