1-2期

最新文章

• Constrained optimization of rank-one functions with indicator variables AI翻译
  作者：Shafiee, Soroosh; Kilinc-Karzan, Fatma
  作者单位：Cornell University; Carnegie Mellon University
  摘要：Optimization problems involving minimization of a rank-one convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine learning applications. These problems are often modeled with indicator variables for identifying the support of the continuous variables. In this paper we investigate compact extended formulations for such problems through perspective reformulation techniques. In contrast to the majority of previous work that relies...
• Quasi-polynomial time approximation schemes for assortment optimization under Mallows-based rankings AI翻译
  作者：Rieger, Alon; Segev, Danny
  作者单位：Tel Aviv University
  摘要：In spite of its widespread applicability in learning theory, probability, combinatorics, and in various other fields, the Mallows model has only recently been examined from revenue management perspectives. To our knowledge, the only provably-good approaches for assortment optimization under the Mallows model have recently been proposed by Desir et al. (Oper Res 69(4):1206-1227, 2021), who devised three approximation schemes that operate in very specific circumstances. Unfortunately, these algo...
• A unified stochastic approximation framework for learning in games AI翻译
  作者：Mertikopoulos, Panayotis; Hsieh, Ya-Ping; Cevher, Volkan
  作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria
  摘要：We develop a flexible stochastic approximation framework for analyzing the long-run behavior of learning in games (both continuous and finite). The proposed analysis template incorporates a wide array of popular learning algorithms, including gradient-based methods, the exponential/multiplicative weights algorithm for learning in finite games, optimistic and bandit variants of the above, etc. In addition to providing an integrated view of these algorithms, our framework further allows us to ob...
• FPT algorithms for a special block-structured integer program with applications in scheduling AI翻译
  作者：Chen, Hua; Chen, Lin; Zhang, Guochuan
  作者单位：Zhejiang University; Texas Tech University System; Texas Tech University
  摘要：In this paper, a special case of the generalized 4-block n-fold IPs is investigated, where B-i = B and B has a rank at most 1. Such IPs, called almost combinatorial 4-block n-fold IPs, include the generalized n-fold IPs as a subcase. We are interested in fixed parameter tractable (FPT) algorithms by taking as parameters the dimensions of the blocks and the largest coefficient. For almost combinatorial 4-block n-fold IPs, we first show that there exists some lambda <= g(gamma ) such that for an...
• Stochastic algorithms with geometric step decay converge linearly on sharp functions AI翻译
  作者：Davis, Damek; Drusvyatskiy, Dmitriy; Charisopoulos, Vasileios
  作者单位：Cornell University; University of Washington; University of Washington Seattle
  摘要：Stochastic (sub)gradient methods require step size schedule tuning to perform well in practice. Classical tuning strategies decay the step size polynomially and lead to optimal sublinear rates on (strongly) convex problems. An alternative schedule, popular in nonconvex optimization, is called geometric step decay and proceeds by halving the step size after every few epochs. In recent work, geometric step decay was shown to improve exponentially upon classical sublinear rates for the class of s...
• Matroid-based TSP rounding for half-integral solutions AI翻译
  作者：Gupta, Anupam; Lee, Euiwoong; Li, Jason; Mucha, Marcin; Newman, Heather; Sarkar, Sherry
  作者单位：Carnegie Mellon University; University of Michigan System; University of Michigan; University of California System; University of California Berkeley; University of Warsaw
  摘要：We show how to round any half-integral solution to the subtour-elimination relaxation for the TSP, while losing a less-than-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$-$$\end{document} 1.5 factor. Such a rounding algorithm was recently given by Karlin, Klein, and Oveis Gharan based on sampling from max-entropy...
• A general framework for multi-marginal optimal transport AI翻译
  作者：Pass, Brendan; Vargas-Jimenez, Adolfo
  作者单位：University of Alberta; University of Ottawa
  摘要：We establish a general condition on the cost function to obtain uniqueness and Monge solutions in the multi-marginal optimal transport problem, under the assumption that a given collection of the marginals are absolutely continuous with respect to local coordinates. When only the first marginal is assumed to be absolutely continuous, our condition is equivalent to the twist on splitting sets condition found in Kim and Pass (SIAM J Math Anal 46:1538-1550, 2014; SIAM J Math Anal 46:1538-1550, 20...
• A 2-approximation for the bounded treewidth sparsest cutproblem in FPT Time AI翻译
  作者：Cohen-Addad, Vincent; Moemke, Tobias; Verdugo, Victor
  作者单位：Alphabet Inc.; Google Incorporated; University of Augsburg; Universidad de O'Higgins
  摘要：In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time fo...
• Tropical medians by transportation AI翻译
  作者：Comaneci, Andrei; Joswig, Michael
  作者单位：Technical University of Berlin; Max Planck Society
  摘要：Fermat-Weber points with respect to an asymmetric tropical distance function are studied. It turns out that they correspond to the optimal solutions of a transportation problem. The results are applied to obtain a new method for computing consensus trees in phylogenetics. This method has several desirable properties; e.g., it is Pareto and co-Pareto on rooted triplets.
• Worst-case complexity of an SQP method for nonlinear equality constrained stochastic optimization AI翻译
  作者：Curtis, Frank E.; O'Neill, Michael J.; Robinson, Daniel P.
  作者单位：Lehigh University; University of North Carolina; University of North Carolina Chapel Hill
  摘要：A worst-case complexity bound is proved for a sequential quadratic optimization (commonly known as SQP) algorithm that has been designed for solving optimization problems involving a stochastic objective function and deterministic nonlinear equality constraints. Barring additional terms that arise due to the adaptivity of the monotonically nonincreasing merit parameter sequence, the proved complexity bound is comparable to that known for the stochastic gradient algorithm for unconstrained nonc...