2024

最新文章

• Oriented Calmness and Sweeping Process Dynamics AI翻译
  作者：Daniilidis, Aris; Tapia, Sebastian
  作者单位：Technische Universitat Wien
  摘要：Daniilidis and Drusviatskiy, in 2017, extended the celebrated Kurdyka- Lojasiewicz inequality from definable functions to definable multivalued maps by establishing that the coderivative mapping admits a desingularization around every critical value. As was the case in the gradient dynamics, this desingularization yields a uniform control of the lengths of all bounded orbits of the corresponding sweeping process. In this paper, working outside the framework of o-minimal geometry, we characteri...
• Stochastic First-Order Methods for Average-Reward Markov Decision Processes AI翻译
  作者：Li, Tianjiao; Wu, Feiyang; Lan, Guanghui
  作者单位：University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
  摘要：We study average-reward Markov decision processes (AMDPs) and develop novel first-order methods with strong theoretical guarantees for both policy optimization and policy evaluation. Compared with intensive research efforts in finite sample analysis of policy gradient methods for discounted MDPs, existing studies on policy gradient methods for AMDPs mostly focus on regret bounds under restrictive assumptions, and they often lack guarantees on the overall sample complexities. Toward this end, w...
• Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal AI翻译
  作者：Blanchard, Moise; Zhang, Junhui; Jaillet, Patrick
  作者单位：Massachusetts Institute of Technology (MIT)
  摘要：We give query complexity lower bounds for convex optimization and the related feasibility problem. We show that quadratic memory is necessary to achieve the optimal oracle complexity for first-order convex optimization. In particular, this shows that center-of-mass cutting-plane algorithms in dimension d , which use O ( d 2 ) memory and O ( d ) queries, are Pareto optimal for both convex optimization and the feasibility problem, up to logarithmic factors. Precisely, building upon techniques in...
• Primal-Dual Extrapolation Methods for Monotone Inclusions Under Local Lipschitz Continuity AI翻译
  作者：Lu, Zhaosong; Mei, Sanyou
  作者单位：University of Minnesota System; University of Minnesota Twin Cities
  摘要：In this paper, we consider a class of monotone inclusion (MI) problems of finding a zero of the sum of two monotone operators, in which one operator is maximal monotone, whereas the other is locally Lipschitz continuous. We propose primal-dual (PD) extrapolation methods to solve them using a point and operator extrapolation technique, whose parameters are chosen by a backtracking line search scheme. The proposed methods enjoy an operation complexity of O(log epsilon-1) and O(epsilon-1log epsil...
• Nontruthful Position Auctions Are More Robust to Misspecification AI翻译
  作者：Dutting, Paul; Fischer, Felix; Parkes, David C.
  作者单位：Alphabet Inc.; Google Incorporated; University of London; Queen Mary University London; Harvard University
  摘要：We consider the classical model of sponsored search due to Edelman et al. and Varian and examine how robust standard position auctions are to a misspecification of the position-dependent quality factors used by this model. We show that under both complete and incomplete information a nontruthful position auction admits an efficient equilibrium for a strictly broader range of parameter values than the Vickrey-Clarke-Groves (VCG) mechanism, which would be truthful if the parameters were specifie...
• Asymptotically Optimal Control of Make-to-Stock Systems AI翻译
  作者：Nie, Jiawang; Tang, Xindong
  作者单位：University of California System; University of California San Diego; Hong Kong Polytechnic University
  摘要：We consider multiclass make-to-stock production/inventory systems in which the manager makes three decisions, including pricing, outsourcing, and scheduling, to maximize the long-run average profit. For a sequence of systems in the heavy-traffic regime, with linear or strictly convex holding/waiting cost functions, we propose a sequence of policies and establish its asymptotic optimality. Our proof combines the lower bound approach and a thorough steady-state analysis of the systems. We also e...
• Rate-Optimal Bayesian Simple Regret in Best Arm Identification AI翻译
  作者：Komiyama, Junpei; Ariu, Kaito; Kato, Masahiro; Qin, Chao
  作者单位：New York University; Royal Institute of Technology; Columbia University
  摘要：We consider best arm identification in the multiarmed bandit problem. Assuming certain continuity conditions of the prior, we characterize the rate of the Bayesian simple regret. Differing from Bayesian regret minimization, the leading term in the Bayesian simple regret derives from the region in which the gap between optimal and suboptimal p ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi arms is smaller than (log T)/T. We propose a simple and easy-to-compute algorithm with its lead...
• Weak Approachability of Convex Sets in Absorbing Games AI翻译
  作者：Ragel, Thomas
  作者单位：Universite PSL; Universite Paris-Dauphine
  摘要：In this paper, we extend previous results on weak approachability in generalized quitting games with vector payoffs to the general case of absorbing games. Specifically, we show that a necessary condition and a different sufficient condition for weak approachability of a convex set, established by Flesch, Laraki, and Perchet, remain valid in the general case. To do so, we extend results on Blackwell approachability to a setup in which stage weights depend on past actions as well as the current...
• On the Diameter of the Stopped Spider Process AI翻译
  作者：Bednarz, Ewelina; Ernst, Philip A.; OseRkowskia, Adam
  作者单位：University of Warsaw; Imperial College London
  摘要：We consider the Brownian spider process, also known as Walsh Brownian motion, first introduced by J. B. Walsh [Walsh JB (1978) A diffusion with a discontinuous local time. Asterisque 52:37-45]. The paper provides the best constant Cn for the inequality root ffiffiffiffififfi ED tau <= Cn E tau ,where tau is the class of all adapted and integrable stopping times and D denotes the diameter of the spider process measured in terms of the British rail metric. This solves a variant of the long-stand...
• Extension of Additive Valuations to General Valuations on the Existence of EFX AI翻译
  作者：Mahara, Ryoga
  作者单位：University of Tokyo
  摘要：Envy freeness is one of the most widely studied notions in fair division. Because envy-free allocations do not always exist when items are indivisible, several relaxations have been considered. Among them, possibly the most compelling notion is envy freeness up to any item (EFX). Informally speaking, EFX requires that no agent i envies another agent j after the removal of any item in j's bundle. The existence of EFX allocations is a major open problem. We study the existence of EFX allocations...