Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm

• URL: http://arxiv.org/abs/2310.12629v2
• Date: Sun, 19 Nov 2023 07:16:41 GMT
• Title: Online Combinatorial Linear Optimization via a Frank-Wolfe-based Metarounding Algorithm
• Authors: Ryotaro Mitsuboshi, Kohei Hatano, and Eiji Takimoto
• Abstract summary: We propose a new metarounding algorithm under a natural assumption that a relax-based approximation algorithm exists for the class. Our algorithm is much more efficient in both theoretical and practical aspects.
• Score: 0.589889361990138
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Metarounding is an approach to convert an approximation algorithm for linear optimization over some combinatorial classes to an online linear optimization algorithm for the same class. We propose a new metarounding algorithm under a natural assumption that a relax-based approximation algorithm exists for the combinatorial class. Our algorithm is much more efficient in both theoretical and practical aspects.

Related papers

• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Composite Optimization Algorithms for Sigmoid Networks [3.160070867400839]
  We propose the composite optimization algorithms based on the linearized proximal algorithms and the alternating direction of multipliers. Numerical experiments on Frank's function fitting show that the proposed algorithms perform satisfactorily robustly.
  arXiv  Detail & Related papers  (2023-03-01T15:30:29Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Optimistic Optimisation of Composite Objective with Exponentiated Update [2.1700203922407493]
  The algorithms can be interpreted as the combination of the exponentiated gradient and $p$-norm algorithm. They achieve a sequence-dependent regret upper bound, matching the best-known bounds for sparse target decision variables.
  arXiv  Detail & Related papers  (2022-08-08T11:29:55Z)
• Iterative Linear Quadratic Optimization for Nonlinear Control: Differentiable Programming Algorithmic Templates [9.711326718689495]
  We present the implementation of nonlinear control algorithms based on linear and quadratic approximations of the objective from a functional viewpoint. We derive the computational complexities of all algorithms in a differentiable programming framework and present sufficient optimality conditions. The algorithms are coded in a differentiable programming language in a publicly available package.
  arXiv  Detail & Related papers  (2022-07-13T17:10:47Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

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.