-
作者：Chizat, Lenaic; Delalande, Alex; Vaskevicius, Tomas
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
摘要：We study the convergence rate of Sinkhorn's algorithm for solving entropy-regularized optimal transport problems when at least one of the probability measures, mu, admits a density over R-d. For a semi-concave cost function bounded by cand a regularization parameter lambda > 0, we obtain exponential convergence guarantees on the dual sub-optimality gap with contraction rates that are polynomial in lambda/c(infinity). This represents an exponential improvement over the known contraction rate 1-...
-
作者：Marinkovic, Javier; Soto, Jose A.; Verdugo, Victor
作者单位：Universidad de Chile; Universidad de Chile; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile; University System of Maryland; University of Maryland College Park
摘要：We consider an online multi-weighted generalization of several classic online optimization problems called the online combinatorial assignment problem. We are given an independence system over a ground set of elements and agents that arrive online one by one. Upon arrival, each agent reveals a weight function over the elements of the ground set. If the independence system is given by the matchings of a hypergraph, we recover the combinatorial auction problem, where every node represents an ite...
-
作者：Heimendahl, Arne; Lucke, Moritz; Vallentin, Frank; Zimmermann, Marc Christian
作者单位：University of Cologne
摘要：We derive and analyze an infinite-dimensional semidefinite program which computes least distortion embeddings of flat tori Rn/L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {R}<^>n/L$$\end{document}, where L is an n-dimensional lattice, into Hilbert spaces. This enables us to provide a constant factor imp...
-
作者：Brosch, Daniel; Puges, Diane
作者单位：University of Klagenfurt
摘要：The inducibility of a graph represents its maximum density as an induced subgraph over all possible sequences of graphs of size growing to infinity. This invariant of graphs has been extensively studied since its introduction in 1975 by Pippenger and Golumbic. In 2017, Czabarka, Sz & eacute;kely and Wagner extended this notion to leaf-labeled rooted binary trees, which are objects widely studied in the field of phylogenetics. They obtain the first results and bounds for the densities and induc...
-
作者：Jin, Qiujiang; Jiang, Ruichen; Mokhtari, Aryan
作者单位：University of Texas System; University of Texas Austin
摘要：In this paper, we explore the non-asymptotic global convergence rates of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) method implemented with exact line search. Notably, due to Dixon's equivalence result, our findings are also applicable to other quasi-Newton methods in the convex Broyden class employing exact line search, such as the Davidon-Fletcher-Powell (DFP) method. Specifically, we focus on problems where the objective function is strongly convex with Lipschitz continuous gradient and He...
-
作者：Catanzaro, Daniele; Pesenti, Raffaele; Sapucaia, Allan; Wolsey, Laurence
作者单位：Universite Catholique Louvain; Universita Ca Foscari Venezia
摘要：Path-Length Matrices (PLMs) form a tree encoding scheme that is often used in the context of optimization problems defined over Unrooted Binary Trees (UBTs). Determining the conditions that a symmetric integer matrix of order n >= 3 must satisfy to encode the PLM of a UBT with n leaves is central to these applications. Here, we show that a certain subset of known necessary conditions is also sufficient to characterize the set Theta(n) of PLMs induced by the set of UBTs with n leaves. We also i...
-
作者：Kukharenko, Kirill; Sanita, Laura
作者单位：Otto von Guericke University; Bocconi University
摘要：The simplex algorithm is one of the most popular algorithms to solve linear programs (LPs). Starting at an extreme point solution of an LP, it performs a sequence of basis exchanges (called pivots) that allows one to move to a better extreme point along an improving edge-direction of the underlying polyhedron. A key issue in the simplex algorithm's performance is degeneracy, which may lead to a (potentially long) sequence of basis exchanges which do not change the current extreme point solutio...
-
作者：Gallego, Guillermo; Segev, Danny
作者单位：The Chinese University of Hong Kong, Shenzhen; Tel Aviv University; Tel Aviv University
摘要：In the adaptive ProbeTopK problem, given a collection of mutually independent random variables X1,..., Xn, our goal is to design an adaptive probing policy to sample these variables in a sequence of T stages, with the objective ofmaximizing the expected sum of the K highest rewards sampled. In spite of its stylized formulation, this setting captures numerous technical hurdles inherent to stochastic optimization, related to both information structure and efficient computation. For these reasons...
-
作者：Byrka, Jaroslaw; Vygen, Jens
作者单位：University of Wroclaw; University of Bonn; University of Bonn
-
作者：Soma, Tasuku; Tung, Kam Chuen; Yoshida, Yuichi
作者单位：Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Waterloo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：We provide the first online algorithm for spectral hypergraph sparsification. In the online setting, hyperedges with positive weights are arriving in a stream, and upon the arrival of each hyperedge, we must irrevocably decide whether or not to include it in the sparsifier. Our algorithm produces an (epsilon,delta)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \set...
