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

• URL: http://arxiv.org/abs/2404.17158v1
• Date: Fri, 26 Apr 2024 05:03:48 GMT
• Title: Online $\mathrm{L}^{\natural}$-Convex Minimization
• Abstract summary: An online decision-making problem is a learning problem in which a player repeatedly makes decisions order to the longterm loss. An existing general framework for minimization is the online submodular minimization. This paper introduces the online $mathrmLnatural$$- subsets a submodular function so that the domain subset is a subset of the unit hypercube.
• Score: 31.045112870480537
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 $\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.

Related papers

• Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach [1.220074067604011]
  We consider problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser.<n>We investigate the performance of a zeroth-order method applied to this problem.
  arXiv  Detail & Related papers  (2026-01-29T04:04:27Z)
• Effective Policy Learning for Multi-Agent Online Coordination Beyond Submodular Objectives [64.16056378603875]
  We present two policy learning algorithms for multi-agent online coordination problem.<n>The first one, textttMA-SPL, can achieve the optimal $(fracce)$-approximation for the MA-OC problem.<n>The second online algorithm named textttMA-MPL can simultaneously maintain the same approximation ratio.
  arXiv  Detail & Related papers  (2025-09-26T17:16:34Z)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  We provide a unified analysis of two-timescale gradient ascent (TTGDA) for solving structured non minimax optimization problems. Our contribution is to design TTGDA algorithms are effective beyond the setting.
  arXiv  Detail & Related papers  (2024-08-21T20:14:54Z)
• A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
  We construct an algorithm that returns a point $hat xin barmathcal X$ such that $f(hat x)$ is as small as possible. We prove that this method is such that the $f(hat x) - min_xin barmathcal X f(x)$ is of smaller order than $d2/sqrtn$ up to poly-logarithmic terms.
  arXiv  Detail & Related papers  (2024-06-26T18:19:10Z)
• No-Regret M${}^{\ atural}$-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Setting [27.973926244529267]
  We study online M$natural$-concave function problems, which are interactive versions of the problem studied by Murota and Shioura (1999).<n>For the bandit setting, we present $O(T-1/2)$-simple regret and $O(T2/3)$-regret algorithms under $T$ times access to noisy value oracles of M$natural$-concave functions.<n>We prove that even with full-information feedback, no algorithms that run in time per round can achieve $O(T1-c)$ regret for any constant $c
  arXiv  Detail & Related papers  (2024-05-21T01:31:44Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
  The minimax algorithms for neural networks have been developed to solve many problems. In this paper, we propose two types of minimax algorithms. For the setting, we propose DRSGDA and prove that our method achieves a gradient.
  arXiv  Detail & Related papers  (2023-02-08T01:42:45Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets [13.23676270963484]
  DR-submodular continuous functions have many real-worlds applications in the domains of machine learning, communication systems, research and economics. We present a time online algorithm matching the $tfrac14 (1 - m)$-the-art offline algorithm. We also show that our algorithm and Du's (2022) offline are both optimal in a strong sense.
  arXiv  Detail & Related papers  (2022-10-12T07:04:24Z)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  Minimax problems extend beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization.
  arXiv  Detail & Related papers  (2021-11-01T21:06:35Z)
• Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity [14.93584434176082]
  Class of quasi-concave set functions induced as a dual class to monotone linkage functions. We show a potential for widespread applications via an example of diverse feature subset selection with exact global maxi-min guarantees.
  arXiv  Detail & Related papers  (2021-08-19T15:50:41Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
  Several learning problems involve solving min-max problems, e.g., empirical distributional robust learning or minimization with non-standard aggregated losses. More specifically, these problems are convex-linear problems where the learning is carried out over the model parameters $winmathcalW$ and over the empirical distribution $pinmathcalK$ of the training set. To design efficient methods, we let an online learning algorithm play against a (combinatorial) bandit algorithm.
  arXiv  Detail & Related papers  (2021-05-28T16:01:42Z)
• Decomposable Submodular Function Minimization via Maximum Flow [6.993741009069205]
  This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization. We provide improved running times for this problem by reducing it to a number of calls to maximum flow oracle.
  arXiv  Detail & Related papers  (2021-03-05T18:46:38Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  We study the problem of maximizing monotone submodular functions subject to matroid constraints in the framework of differential privacy. We give the first $frac12$-approximation algorithm that preserves $k$submodular functions subject to matroid constraints.
  arXiv  Detail & Related papers  (2020-06-28T23:18:58Z)
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
  We consider non-con minimax problems, $min_mathbfx max_mathhidoty f(mathbfdoty)$ efficiently.
  arXiv  Detail & Related papers  (2019-06-02T03:03:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.