-
作者：Kleer, Pieter
作者单位：Tilburg University
摘要：Logit dynamics is a form of randomized game dynamics in which players have a bias toward strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converge to the so-called Gibbs distribution over the set of all strategy profiles when interpreted as a Markov chain. In general, logit dynamics can converge slowly to the Gibbs distribution, but beyond that, not much is known about its algorithmic aspects, nor ...
-
作者：Christodoulou, George; Gairing, Martin; Giannakopoulos, Yiannis; Pocas, Diogo; Waldmann, Clara
作者单位：Aristotle University of Thessaloniki; University of Liverpool; University of Erlangen Nuremberg; Technical University of Munich
摘要：We study the existence of approximate pure Nash equilibria (alpha-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously, it was known that d-PNE always exist, whereas nonexistence was established only for small constants, namely, for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have (Theta) over tilde(root d)-PNE, which provides the first superconstant lower bound. Furthermore, we provide a black-...
-
作者：Argue, C. J.; Kilinc-Karzan, Fatma; Wang, Alex L.
作者单位：Carnegie Mellon University; Carnegie Mellon University; Carnegie Mellon University
摘要：A closed convex conic subset S of the positive semidefinite (PSD) cone is rank-one generated (ROG) if all of its extreme rays are generated by rank-one matrices. The ROG property of S is closely related to the exactness of semidefinite program (SDP) relaxations of nonconvex quadratically constrained quadratic programs (QCQPs) related to S. We consider the case where S is obtained as the intersection of the PSD cone with finitely many homogeneous linear matrix inequalities and conic constraints...
-
作者：Viet Anh Nguyen; Shafieezadeh-Abadeh, Soroosh; Kuhn, Daniel; Esfahani, Peyman Mohajerin
作者单位：Stanford University; Carnegie Mellon University; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Delft University of Technology
摘要：We introduce a distributionally robust minimium mean square error estimation model with a Wasserstein ambiguity set to recover an unknown signal from a noisy observation. The proposed model can be viewed as a zero-sum game between a statistician choosing an estimator-that is, a measurable function of the observation-and a fictitious adversary choosing a prior-that is, a pair of signal and noise distributions ranging over independent Wasserstein balls-with the goal to minimize and maximize the ...
-
作者：Gunluk, Oktay; Hauser, Raphael Andreas; Kovacs, Reka Agnes
作者单位：Cornell University; University of Oxford; Alan Turing Institute
摘要：Binary matrix factorization is an essential tool for identifying discrete patterns in binary data. In this paper, we consider the rank -k binary matrix factorization problem (k- BMF) under Boolean arithmetic: we are given an n x m binary matrix X with possibly missing entries and need to find two binary matrices A and B of dimension n x k and k x m, respectively, which minimize the distance between X and the Boolean product of A and B in the squared Frobenius distance. We present a compact and...
-
作者：Fujii, Kaito; Yoshida, Yuichi
作者单位：Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
摘要：The value maximization version of the secretary problem is the problem of hiring a candidate with the largest value from a randomly ordered sequence of candidates. In this work, we consider a setting where predictions of candidate values are provided in advance. We propose an algorithm that achieves a nearly optimal value if the predictions are accurate and results in a constant-factor competitive ratio otherwise. We also show that the worst-case competitive ratio of an algorithm cannot be hig...
-
作者：Dadush, Daniel; Koh, Zhuan Khye; Natura, Bento; Vegh, Laszlo A.
作者单位：University of London; London School Economics & Political Science
摘要：We present an accelerated or look-ahead version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceleration halves the Bregman divergence between the current iterate and the optimal solution within every two iterations. Using the Bregman divergence as a potential in conjunction with combinatorial arguments, we obtain strongly polynomial algorithms in three applications domains. (i) For linear fractional combinatorial op...
-
作者：Sering, Leon; Koch, Laura Vargas; Ziemke, Theresa
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin; Technical University of Berlin
摘要：Mathematical approaches for modeling dynamic traffic can be roughly divided into two categories: discrete packet routing models and continuous flow over time models. Despite very vital research activities on models in both categories, their connection was poorly understood so far. We build this connection by specifying a (competitive) packet routing model, which is discrete in terms of flow and time, and proving its convergence to the intensively studied model of flows over time with determini...
-
作者：Li, Jiaxiang; Balasubramanian, Krishnakumar; Ma, Shiqian
作者单位：University of California System; University of California Davis; University of California System; University of California Davis; Rice University
摘要：We consider stochastic zeroth-order optimization over Riemannian submanifolds embedded in Euclidean space, where the task is to solve Riemannian optimization problems with only noisy objective function evaluations. Toward this, our main contribution is to propose estimators of the Riemannian gradient and Hessian from noisy objective function evaluations, based on a Riemannian version of the Gaussian smoothing technique. The proposed estimators overcome the difficulty of nonlinearity of the man...
-
作者：Liang, Jiaming; Monteiro, Renato D. C.
作者单位：Yale University; University System of Georgia; Georgia Institute of Technology
摘要：This paper presents a proximal bundle (PB) framework based on a generic bundle update scheme for solving the hybrid convex composite optimization (HCCO) problem and establishes a common iteration-complexity bound for any variant belonging to it. As a consequence, iteration-complexity bounds for three PB variants based on different bundle update schemes are obtained in the HCCO context for the first time and in a unified manner. Although two of the PB variants are universal (i.e., their impleme...
