Mathematical Programming

最新文章

• On the maximal number of columns of a ?-modular integer matrix: bounds and computations AI翻译
  作者：Averkov, Gennadiy; Schymura, Matthias
  作者单位：Brandenburg University of Technology Cottbus
  摘要：We study the maximal number of pairwise distinct columns in a ?-modular integer matrix with m rows. Recent results by Lee et al. provide an asymptotically tight upper bound of O (m(2)) for fixed ?. We complement this and obtain an upper bound of the form O(?) for fixed m, and with the implied constant depending polynomially on m.
• 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...
• Homogenization of SGD in high-dimensions: exact dynamics and generalization properties AI翻译
  作者：Paquette, Courtney; Paquette, Elliot; Adlam, Ben; Pennington, Jeffrey
  作者单位：McGill University; Alphabet Inc.; DeepMind
  摘要：We develop a stochastic differential equation, called homogenized SGD, for analyzing the dynamics of stochastic gradient descent (SGD) on a high-dimensional random least squares problem with l(2)-regularization. We show that homogenized SGD is the high-dimensional equivalence of SGD-for any quadratic statistic (e.g., population risk with quadratic loss), the statistic under the iterates of SGD converges to the statistic under homogenized SGD when the number of samples n and number of features ...
• Decomposition of probability marginals for security games in max-flow/min-cut systems AI翻译
  作者：Matuschke, Jannik
  作者单位：KU Leuven
  摘要：Given a set system (E,P)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(E, \mathcal {P})$$\end{document} with rho is an element of[0,1]E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \...
• 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...