-
作者：Ickstadt, Constantin; Theobald, Thorsten; von Stengel, Bernhard
作者单位：Goethe University Frankfurt; London School Economics & Political Science; University of London; London School Economics & Political Science
摘要：Quint and Shubik conjectured that a nondegenerate nxn game has at most 2n-1 Nash equilibria in mixed strategies. The conjecture is true for n <= 4 but false for n >= 6. We answer it positively for the remaining case n=5, which had been open since 1999. The problem can be translated to a combinatorial question about the vertices of a pair of simple n-polytopes with 2n facets. We introduce a novel obstruction based on the index of an equilibrium, which states that equilibrium vertices belong to ...
-
作者：Wang, Jiaqi; Xie, Weijun; Ryzhov, Ilya O.
作者单位：University System of Georgia; Georgia Institute of Technology; University System of Maryland; University of Maryland College Park
摘要：D-optimal experimental design is a classical statistical problem in which one chooses a collection of data vectors, from some available large pool, in order to maximize a measure of predictive quality. In the classical formulation, the only constraint is on the cardinality of the collection, that is, the number of vectors chosen. We study a more general budget-constrained variant in which vectors have heterogeneous costs, and develop four new algorithms (two deterministic and two randomized) w...
-
作者：Zha, Xiao; Allen-Zhao, Zhihua; Chen, Xiaojun
作者单位：Hong Kong Polytechnic University; Xidian University
摘要：We propose a stochastic minimization model to find a robust solution of a system of stochastic vertical linear complementarity problems. This model aims to minimize a risk function under stochastic vertical linear complementarity constraints. We reformulate the model with a finite support set as a linearly constrained piecewise smooth minimization problem by a penalty method. We prove the existence of exact penalty parameters regarding global and local minimizers. We define a smoothing functio...
-
作者：Mangoubi, Oren; Vishnoi, Nisheeth K.
作者单位：Worcester Polytechnic Institute; Yale University
摘要：Min-max optimization of a function f from Rd x Rd to R is an important framework for modeling robustness in adversarial settings with applications to optimization, economics, and deep learning. Oftentimes, f is nonconvex-nonconcave, and finding a global min-max point is computationally intractable. There is a long line of work that seeks computationally tractable algorithms for alternatives to the min-max optimization formulation. However, many of these alternative solution concepts guarantee ...
-
作者：Dong, Youran; Ma, Shiqian; Yang, Tunfeng; Yin, Chao
作者单位：Nanjing University; Rice University; Hohai University
摘要：Bilevel optimization has gained significant attention in recent years because of its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is built on the basis of the SOBA framework, and it is a fully single-loop method that approximates the hypergradient by using merely two matrix-vector multi...
-
作者：Srikant, R.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
摘要：We prove a nonasymptotic central limit theorem (CLT) for vector-valued martingale differences using Stein's method, and we use Poisson's equation to extend the result to functions of Markov chains. We then show that these results can be applied to establish a nonasymptotic CLT for temporal difference learning with averaging.
-
作者：Deng, Kangkang; Hu, Jiang; Wu, Jiayuan; Wen, Zaiwen
作者单位：National University of Defense Technology - China; Tsinghua University; Peking University; Peking University
摘要：In this paper, we present two novel manifold inexact augmented Lagrangian methods, ManIAL for deterministic settings and StoManIAL for stochastic settings, solving non-smooth composite optimization problems on a compact submanifold embedded in the Euclidean space. By using the Riemannian gradient method as a subroutine, we establish an O(epsilon-3) oracle complexity result of ManIAL, matching the best-known complexity result. Our algorithm relies on the careful selection of penalty parameters ...
-
作者：Chen, Rui; Zhu, Haoran
作者单位：The Chinese University of Hong Kong, Shenzhen; Microsoft
摘要：The complexity class Dp is the class of all languages that are the intersection of a language in NP and a language in co-NP. It was conjectured that recognizing a facet for the knapsack polytope is Dp-complete. We provide a positive answer to this conjecture. Moreover, despite the Dp-hardness of the recognition problem, we give a polynomial-time algorithm for deciding if an inequality with a fixed number of distinct coefficients defines a facet of a knapsack polytope.
-
作者：Csaji, Gergely; Kiraly, Tamas; Yokoi, Yu
作者单位：Eotvos Lorand University; Eotvos Lorand University; Institute of Science Tokyo
摘要：This paper considers the problem of finding maximum-size stable matchings in the presence of ties, a well-known NP-hard problem, by extending the existing 32-approximation algorithm to a common generalization of many previously studied and newly introduced models. These include the existence of critical agents, where matching as many of these agents as possible is prioritized; free edges that cannot be blocking edges; and triangle-stabilities, which mean that for an edge to block, the improvem...
-
作者：Luke, D. Russell; Tam, Matthew K.
作者单位：University of Gottingen; University of Melbourne
摘要：We study the proximal point algorithm when the operator of interest is metrically subregular and satisfies a submonotonicity property. The latter property can be viewed as a quantified weakening of the standard definition of a monotone operator. Our main result gives a condition under which locally, the proximal point algorithm generates sequences that are linearly convergent to a zero of the underlying operator. General properties of our notion of submonotonicity are also explored as well as ...
