-
作者：Doikov, Nikita; Nesterov, Yurii
摘要：In this paper, we propose a first second-order scheme based on arbitrary non-Euclidean norms, incorporated by Bregman distances. They are introduced directly in the Newton iterate with regularization parameter proportional to the square root of the norm of the current gradient. For the basic scheme, as applied to the composite convex optimization problem, we establish the global convergence rate of the order O(k(-2)) both in terms of the functional residual and in the norm of subgradients. Our...
-
作者：Moseley, Benjamin; Pruhs, Kirk; Stein, Clifford; Zhou, Rudy
作者单位：Carnegie Mellon University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; Columbia University
摘要：This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on m identical machines. The main result is an O(1) competitive deterministic algorithm for any number of machines m>1.
-
作者：Li, Yan; Lan, Guanghui; Zhao, Tuo
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We study a new variant of policy gradient method, named homotopic policy mirror descent (HPMD), for solving discounted, infinite horizon MDPs with finite state and action spaces. HPMD performs a mirror descent type policy update with an additional diminishing regularization term, and possesses several computational properties that seem to be new in the literature. When instantiated with Kullback-Leibler divergence, we establish the global linear convergence of HPMD applied to any MDP instance,...
-
作者：Song, Zhuoqing; Shi, Lei; Pu, Shi; Yan, Ming
作者单位：Fudan University; Fudan University; The Chinese University of Hong Kong, Shenzhen
摘要：In this paper, we focus on solving the decentralized optimization problem of minimizing the sum of n objective functions over a multi-agent network. The agents are embedded in an undirected graph where they can only send/receive information directly to/from their immediate neighbors. Assuming smooth and strongly convex objective functions, we propose an Optimal Gradient Tracking (OGT) method that achieves the optimal gradient computation complexity O (root kappa log 1/epsilon) and the optimal ...
-
作者：Boob, Digvijay; Guzman, Cristobal
作者单位：Southern Methodist University; Pontificia Universidad Catolica de Chile
摘要：In this work, we conduct the first systematic study of stochastic variational inequality (SVI) and stochastic saddle point (SSP) problems under the constraint of differential privacy (DP). We propose two algorithms: Noisy Stochastic Extragradient (NSEG) and Noisy Inexact Stochastic Proximal Point (NISPP). We show that a stochastic approximation variant of these algorithms attains risk bounds vanishing as a function of the dataset size, with respect to the strong gap function; and a sampling wi...
-
作者：Koessler, Frederic; Laclau, Marie; Renault, Jerome; Tomala, Tristan
作者单位：Paris School of Economics; Centre National de la Recherche Scientifique (CNRS); Hautes Etudes Commerciales (HEC) Paris; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：This paper studies zero-sum splitting games with finite sets of states. Players dynamically choose a pair of martingales {p(t) , q(t)}(t), in order to control a terminal payoff u(p(infinity),q(infinity)). A first part introduces the notion of Mertens-Zamir transform of a real-valued matrix and use it to approximate the solution of the Mertens-Zamir system for continuous functions on the square [0, 1](2). A second part considers the general case of finite splitting games with arbitrary correspo...
-
作者：Lagarde, Antoine; Tomala, Tristan
作者单位：Hautes Etudes Commerciales (HEC) Paris
摘要：We consider the problem of optimal partisan gerrymandering: a legislator in charge of redrawing the boundaries of equal-sized congressional districts wants to ensure the best electoral outcome for his own party. The so-called gerrymanderer faces two issues: the number of districts is finite and there is uncertainty at the level of each district. Solutions to this problem consists in cracking favorable voters in as many districts as possible to get tight majorities, and in packing unfavorable v...
-
作者：Joswig, Michael; Klimm, Max; Spitz, Sylvain
作者单位：Technical University of Berlin; Max Planck Society; Technical University of Berlin
摘要：The difference set of an outcome in an auction is the set of types that the auction mechanism maps to the outcome. We give a complete characterization of the geometry of the difference sets that can appear for a dominant strategy incentive compatible multi-unit auction showing that they correspond to regular subdivisions of the unit cube. Similarly, we describe the geometry for affine maximizers for n players and m items, showing that they correspond to regular subdivisions of the m-fold produ...
-
作者：Ambrus, Gergely; Csiszarik, Adrian; Matolcsi, Mate; Varga, Daniel; Zsamboki, Pal
作者单位：Szeged University; HUN-REN; HUN-REN Alfred Renyi Institute of Mathematics; Eotvos Lorand University; Budapest University of Technology & Economics
摘要：By improving upon previous estimates on a problem posed by L. Moser, we prove a conjecture of Erdos that the density of any measurable planar set avoiding unit distances is less than 1/4. Our argument implies the upper bound of 0.2470.
-
作者：Chen, Rui; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset I of the binary variables. We show that by restricting the support of the cut to the same set of variables I, a cut can be obtained by solving a linear program with 2(vertical bar I vertical bar) constraints. While this limits the size of the set I used to define the multi-term ...
