-
作者：Buke, Burak; Qin, Wenyi
作者单位：University of Edinburgh; Beihang University
摘要：We consider many-server queueing systems with heterogeneous exponential servers, for which the service rate of each server is a random variable drawn from a given distribution. We develop a framework for analyzing the heavy-traffic diffusion limits of these queues using measure-valued stochastic processes. We introduce the measure-valued fairness process, which denotes the proportion of cumulative idleness experienced by servers whose rates fall in a Borel subset of the support of the service ...
-
作者：Ashlagi, Itai; Burq, Maximilien; Dutta, Chinmoy; Jaillet, Patrick; Saberi, Amin; Sholley, Chris
作者单位：Stanford University; Massachusetts Institute of Technology (MIT)
摘要：Consider amatching problem, in which agents arrive to amarketplace over time and leave after some time periods. Agents can only bematchedwhile present in themarketplace. Each pair of agents can yield a different match value, and a social planner seeks to maximize the total value from matches over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. For the case when agents depart in the order of arrival, we provide a randomized 1/4-competitive algori...
-
作者：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...
-
作者：Ok, Efe A.; Weaver, Nik
作者单位：New York University; New York University; Washington University (WUSTL)
摘要：We obtain several variants of the classic von Neumann-Morgenstern expected utility theorem with and without the completeness axiom in which the derived Bernoulli utility functions are Lipschitz. The prize space in these results is an arbitrary separable metric space, and the utility functions are allowed to be unbounded. The main ingredient of our results is a novel (behavioral) axiom on the underlying preference relations, which is satisfied by virtually all stochastic orders. The proof of th...
-
作者：Molinaro, Marco
作者单位：Pontificia Universidade Catolica do Rio de Janeiro
摘要：It is known that the curvature of the feasible set in convex optimization allows for algorithms with better convergence rates, and there is renewed interest in this topic for both off-line and online problems. In this paper, leveraging results on geometry and convex analysis, we further our understanding of the role of curvature in optimization: center dot We first show the equivalence of two notions of curvature, namely, strong convexity and gauge bodies, proving a conjecture of Abernethy et ...
-
作者：Kong, Weiwei; Melo, Jefferson G.; Monteiro, Renato D. C.
作者单位：United States Department of Energy (DOE); Oak Ridge National Laboratory; Universidade Federal de Goias; University System of Georgia; Georgia Institute of Technology
摘要：This paper proposes and analyzes a proximal augmented Lagrangian (NL-IAPIAL) method for solving constrained nonconvex composite optimization problems, where the constraints are smooth and convex with respect to the order given by a closed convex cone. Each NL-IAPIAL iteration consists of inexactly solving a proximal augmented Lagrangian subproblem by an accelerated composite gradient method followed by a Lagrange multiplier update. Under some mild assumptions, a complexity bound for NL-IAPIAL ...
-
作者：Laurent, Monique; Vargas, Luis Felipe
作者单位：Tilburg University
摘要：De Klerk and Pasechnik introduced in 2002 semidefinite bounds theta((r))(G)(r >= 0) for the stability number alpha(G) of a graph G and conjectured their exactness at order r = alpha(G) - 1. These bounds rely on the conic approximations K-n((r)) introduced by Parrilo in 2000 for the copositive cone COPn. A difficulty in the convergence analysis of the bounds is the bad behavior of Parrilo's cones under adding a zero row/column: when applied to a matrix not in K-n((r)) this gives a matrix that d...
-
作者：Lehrer, Ehud; Shaiderman, Dimitry
作者单位：Tel Aviv University
摘要：Consider a stationary process taking values in a finite state space. Each state is associated with a finite one-shot zero-sum game. We investigate the infinitely repeated zero-sum game with incomplete information on one side in which the state of the game evolves according to the stationary process. Two players, named the observer and the adversary, play the following game. At the beginning of any stage, only the observer is informed of the state xi(n) and is therefore the only one who knows t...
-
作者：Del Pia, Alberto; Khajavirad, Aida; Kunisky, Dmitriy
作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University; Yale University
摘要：The problem of community detection with two equal-sized communities is closely related to the minimum graph bisection problem over certain random graph models. In the stochastic block model distribution over networks with community structure, a well-known semidefinite programming (SDP) relaxation of the minimum bisection problem recovers the underlying communities whenever possible. Motivated by their superior scalability, we study the theoretical performance of linear programming (LP) relaxat...
-
作者：Mai, Ngoc Hoang Anh; Magron, Victor; Lasserre, Jean
作者单位：Centre National de la Recherche Scientifique (CNRS)
摘要：If f is a positive definite form, Reznick's Positivstellensatz states that there exists k is an element of N such that parallel to x parallel to(2k)(2)f is a sum of squares of polynomials. Assuming that f can be written as a sumof forms Sigma(p)(l=1) f(l), where each fl depends on a subset of the initial variables, and assuming that these subsets satisfy the so-called running intersection property, we provide a sparse version of Reznick's Positivstellensatz. Namely, there exists k is an elemen...
