-
作者：Soma, Tasuku; Uschmajew, Andre
作者单位：Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; University of Augsburg; University of Augsburg
摘要：We propose accelerated versions of the operator Sinkhorn iteration for operator scaling using successive overrelaxation. We analyze the local convergence rates of these accelerated methods via linearization, which allows to determine the asymptotically optimal relaxation parameter based on Young's SOR theorem. Using the Hilbert metric on positive definite cones, we also obtain a global convergence result for a geodesic version of overrelaxation in a specific range of relaxation parameters. The...
-
作者：Bravo, Mario; Contreras, Juan Pablo
作者单位：Universidad de Santiago de Chile; University Diego Portales
摘要：We analyze the oracle complexity of the stochastic Halpern iteration with minibatch, where we aim to approximate fixed-points of nonexpansive and contractive operators in a normed finite-dimensional space. We show that if the underlying stochastic oracle has uniformly bounded variance, our method exhibits an overall oracle complexity of O(epsilon(-5)), to obtain expected fixed-point residual for nonexpansive operators, improving recent rates established for the stochastic Krasnoselskii-Mann it...
-
作者：Leyffer, Sven; Manns, Paul
作者单位：United States Department of Energy (DOE); Argonne National Laboratory
-
作者：Mizutani, Ryuhei; Yoshida, Yuki
作者单位：Keio University
摘要：A fundamental result in combinatorial optimization is that submodular functions can be minimized in polynomial-time. In this paper, we consider the minimization problem for a more general class of set functions that contains all submodular functions. A set function is called 2/3-submodular if the submodular inequality holds for at least two pairs formed from every distinct three subsets. In this paper, we provide two weakly polynomial-time algorithms to minimize 2/3-submodular functions. We al...
-
作者：Huang, Chien-Chung; Acosta, Nidia Obscura; Yingchareonthawornchai, Sorrachai
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Universite PSL; Telecom SudParis; Ecole Normale Superieure (ENS); Aalto University; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：In the connectivity interdiction problem, we are asked to find a global graph cut and remove a subset of edges under a budget constraint, so that the total weight of the remaining edges in this cut is minimized. This problem easily includes the knapsack problem as a special case, hence it is NP-hard. For this problem, Zenklusen [Zenklusen'14] designed a polynomial-time approximation scheme (PTAS) and exact algorithms for the special case of unit edge costs. He posed the question of whether a f...
-
作者：Foussoul, Ayoub; Goyal, Vineet; Kumar, Amit
作者单位：Columbia University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi
摘要：We study the classical load balancing problem in a fully dynamic setting where jobs both arrive and depart. Each job can only be assigned to a subset of machines and can be reassigned at any time step. The goal is to maintain a near-optimal maximum load at all time steps with a small total number of reassignments. We consider the setting where the degree of the jobs (number of machines they can be assigned to) is bounded. This is motivated by natural settings where jobs can only be locally ass...
-
作者：Li, Yan; Shapiro, Alexander
作者单位：Texas A&M University System; Texas A&M University College Station; University System of Georgia; Georgia Institute of Technology
摘要：The main goal of this paper is to discuss several approaches to the formulation of distributionally robust counterparts of Markov Decision Processes, where the transition kernels are not specified exactly but rather are assumed to be elements of the corresponding ambiguity sets. The intent is to clarify some connections between the game and static formulations of distributionally robust MDPs, and delineate the role of rectangularity associated with ambiguity sets in determining these connectio...
-
作者：Wang, Ruodu; Zhang, Zhenyuan
作者单位：University of Waterloo; Stanford University
摘要：We introduce the framework of quadratic-form optimal transport (QOT), whose transport cost has the form integral integral cd pi circle times d pi for some coupling pi between two marginals. Interesting examples of quadratic-form transport cost and their optimization include inequality measurement, the variance of a bivariate function, covariance, Kendall's tau, the Gromov-Wasserstein distance, quadratic assignment problems, and quadratic regularization of classic optimal transport. QOT leads t...
-
作者：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-...
-
作者：Lozano, Leonardo; Borrero, Juan S.
作者单位：University System of Ohio; University of Cincinnati; State University System of Florida; University of South Florida
摘要：We study a class of decision-making problems under uncertainty, where the planner hedges against the worst-case realization in an integer uncertainty set that has a functional dependence on the decisions of the planner. We propose three methods to reformulate and solve these problems: the first is based on a single-level 'semi-infinite' reformulation, where the dependence of the uncertainty on the decisions is modeled with auxiliary binary variables; the second is based on a single-follower bi...
