-
作者：Baldwin, Elizabeth; Bichler, Martin; Fichtl, Maximilian; Klemperer, Paul
作者单位：University of Oxford; University of Oxford; Technical University of Munich; University of Oxford; University of Oxford
摘要：We show the strong substitutes product-mix auction bidding language provides an intuitive and geometric interpretation of strong substitutes as Minkowski differences between sets that are easy to identify. We prove that competitive equilibrium prices for agents with strong substitutes preferences can be computed by minimizing the difference between two linear programs for the positive and the negative bids with suitably relaxed resource constraints. This also leads to a new algorithm for compu...
-
作者：Harks, Tobias; Schedel, Anja
作者单位：University of Augsburg
摘要：We study a Stackelberg game with multiple leaders and a continuum of followers that are coupled via congestion effects. The followers' problem constitutes a nonatomic congestion game, where a population of infinitesimal players is given and each player chooses a resource. Each resource has a linear cost function which depends on the congestion of this resource. The leaders of the Stackelberg game each control a resource and determine a price per unit as well as a service capacity for the resou...
-
作者：Diakonikolas, Jelena; Guzman, Cristobal
作者单位：University of Wisconsin System; University of Wisconsin Madison; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：Composite minimization is a powerful framework in large-scale convex optimization, based on decoupling of the objective function into terms with structurally different properties and allowing for more flexible algorithmic design. We introduce a new algorithmic framework for complementary composite minimization, where the objective function decouples into a (weakly) smooth and a uniformly convex term. This particular form of decoupling is pervasive in statistics and machine learning, due to its...
-
作者：Zadik, Ilias; Lubin, Miles; Vielma, Juan Pablo
作者单位：Massachusetts Institute of Technology (MIT)
摘要：Mixed-integer convex representable (MICP-R) sets are those sets that can be represented exactly through a mixed-integer convex programming formulation. Following up on recent work by Lubin et al. (in: Eisenbrand (ed) Integer Programming and Combinatorial Optimization - 19th International Conference, Springer, Waterloo), (Math. Oper. Res. 47:720-749, 2022) we investigate structural geometric properties of MICP-R sets, which strongly differentiate them from the class of mixed-integer linear repr...
-
作者：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...
