2期

最新文章

• Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management AI翻译
  作者：Chen, Xin; He, Niao; Hu, Yifan; Ye, Zikun
  作者单位：University System of Georgia; Georgia Institute of Technology; Swiss Federal Institutes of Technology Domain; ETH Zurich; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of Washington; University of Washington Seattle
  摘要：We study a class of stochastic nonconvex optimization in the form of min(x is an element of X) F(x) := E-xi[f (phi(x, xi))], that is, F is a composition of a convex function f and a random function phi. Leveraging an (implicit) convex reformulation via a variable transformation u = E[phi(x, xi)], we develop stochastic gradient-based algorithms and establish their sample and gradient complexities for achieving an epsilon-global optimal solution. Interestingly, our proposed Mirror Stochastic Gra...
• On (Random-Order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs AI翻译
  作者：MacRury, Calum; Ma, Will; Grammel, Nathaniel
  作者单位：Columbia University; Columbia University; University System of Maryland; University of Maryland College Park
  摘要：Online Contention Resolution Schemes (OCRSs) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRSs have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions-accept/reject, probing, pricing-in a unified manner. This paper analyzes OCRSs for resource constraints defined by matchings...
• Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games AI翻译
  作者：Cominetti, Roberto; Scarsini, Marco; Schroder, Marc; Stier-Mosesd, Nicolas E.
  作者单位：Universidad Adolfo Ibanez; Luiss Guido Carli University; Maastricht University
  摘要：We consider an atomic congestion game in which each player i participates in the game with an exogenous and known probability p(i) is an element of (0, 1], independently of everybody else, or stays out and incurs no cost. We compute the parameterized price of anarchy to characterize the impact of demand uncertainty on the efficiency of selfish behavior, considering two different notions of a social planner. A prophet planner knows the realization of the random participation in the game; the or...
• Asymptotically Tight Bounds on the Optimal Pricing Strategy with Patient Customers AI翻译
  作者：Qian, Shuaijie; Su, Xizhi; Zhou, Chao
  作者单位：Hong Kong University of Science & Technology; National University of Singapore; National University of Singapore
  摘要：This work considers a monopolist seller facing both patient and impatient customers. Given the current price, the impatient customers will either purchase or leave immediately, depending on the relative magnitude between this price and their valuation of the product. In comparison, the patient customers will wait for some periods to see if the price will drop to their valuation, and if that occurs, they will purchase immediately. The monopolist designs the pricing strategy to maximize the long...
• Technical Note-On the Convergence Rate of Stochastic Approximation for Gradient-Based Stochastic Optimization AI翻译
  作者：Hu, Jiaqiao; Fu, Michael C.
  作者单位：State University of New York (SUNY) System; Stony Brook University; University System of Maryland; University of Maryland College Park; University System of Maryland; University of Maryland College Park
  摘要：We consider stochastic optimization via gradient -based search. Under a stochastic approximation framework, we apply a recently developed convergence rate analysis to provide a new finite -time error bound for a class of problems with convex differentiable structures. For noisy black -box functions, our main result allows us to derive finite -time bounds in the setting where the gradients are estimated via finite -difference estimators, including those based on randomized directions such as th...
• Recovering Dantzig-Wolfe Bounds by Cutting Planes AI翻译
  作者：Chen, Rui; Gunluk, Oktay; Lodi, Andrea
  作者单位：Cornell University
  摘要：Dantzig-Wolfe (DW) decomposition is a well-known technique in mixedinteger programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate cutting planes that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. More precisely, we generate one cut for each DW block, and when combined with the constraints in the original formulation, these cuts imply the objectiv...
• Computing Bayes-Nash Equilibrium Strategies in Auction Games via Simultaneous Online Dual Averaging AI翻译
  作者：Bichler, Martin; Fichtl, Max; Oberlechner, Matthias
  作者单位：Technical University of Munich
  摘要：Auctions are modeled as Bayesian games with continuous type and action spaces. Determining equilibria in auction games is computationally hard in general, and no exact solution theory is known. We introduce an algorithmic framework in which we discretize type and action space and then learn distributional strategies via online optimization algorithms. One advantage of distributional strategies is that we do not have to make any assumptions on the shape of the bid function. Besides, the expecte...
• Linear Classifiers Under Infinite Imbalance AI翻译
  作者：Glasserman, Paul; Li, Mike
  作者单位：Columbia University
  摘要：We study the behavior of linear discriminant functions for binary classification in the infinite-imbalance limit, where the sample size of one class grows without bound while the sample size of the other remains fixed. The coefficients of the classifier minimize an empirical loss specified through a weight function. We show that for a broad class of weight functions, the intercept diverges but the rest of the coefficient vector has a finite almost sure limit under infinite imbalance, extending...
• Inverse Optimization: Theory and Applications AI翻译
  作者：Chan, Timothy C. Y.; Mahmood, Rafid; Zhu, Ian Yihang
  作者单位：University of Toronto; University of Ottawa; National University of Singapore
  摘要：Inverse optimization describes a process that is the reverse of traditional mathematical optimization. Unlike traditional optimization, which seeks to compute optimal decisions given an objective and constraints, inverse optimization takes decisions as input and determines objective and/or constraint parameters that render these decisions approximately or exactly optimal. In recent years, there has been an explosion of interest in the mathematics and applications of inverse optimization. This ...
• Generalization Guarantees for Multi-Item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms AI翻译
  作者：Balcan, Maria-Florina; Sandholm, Tuomas; Vitercik, Ellen
  作者单位：Carnegie Mellon University; Stanford University; Stanford University
  摘要：We study multi-item profit maximization when there is an underlying distribution over buyers' values. In practice, a full description of the distribution is typically unavailable, so we study the setting where the mechanism designer only has samples from the distribution. If the designer uses the samples to optimize over a complex mechanism class- such as the set of all multi-item, multibuyer mechanisms-a mechanism may have high average profit over the samples, but low expected profit. This ra...