2025

最新文章

• Fast Convergence of Frank-Wolfe Algorithms on Polytopes AI翻译
  作者：Wirth, Elias; Pena, Javier; Pokutta, Sebastian
  作者单位：Technical University of Berlin; Carnegie Mellon University; Zuse Institute Berlin
  摘要：We provide a template to derive affine-invariant convergence rates for the following popular versions of the Frank-Wolfe algorithm on polytopes: vanilla Frank-Wolfe, Frank-Wolfe with away steps, Frank-Wolfe with blended pairwise steps, and Frank-Wolfe with in-face directions. Our template shows how the convergence rates follow from two affine-invariant properties of the problem, namely, error bound and extended curvature. These properties depend solely on the polytope and objective function bu...
• Opinion Dynamics on Directed Complex Networks AI翻译
  作者：Fraiman, Nicolas; Lin, Tzu-Chi; Olvera-Cravioto, Mariana
  作者单位：University of North Carolina; University of North Carolina Chapel Hill
  摘要：We propose and analyze a mathematical model for the evolution of opinions on directed complex networks. Our model generalizes the popular DeGroot and FriedkinJohnsen models by allowing vertices to have attributes that may influence the opinion dynamics. We start by establishing sufficient conditions for the existence of a stationary opinion distribution on any fixed graph, and then provide an increasingly detailed characterization of its behavior by considering a sequence of directed random gr...
• Mean-Field Multiagent Reinforcement Learning: A Decentralized Network Approach AI翻译
  作者：Gu, Haotian; Guo, Xin; Wei, Xiaoli; Xu, Renyuan
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; Tsinghua Shenzhen International Graduate School; University of Southern California
  摘要：One of the challenges for multiagent reinforcement learning (MARL) is designing efficient learning algorithms for a large system in which each agent has only limited or partial information of the entire system. Whereas exciting progress has been made to analyze decentralized MARL with the network of agents for social networks and team video games, little is known theoretically for decentralized MARL with the network of states for modeling self -driving vehicles, ride -sharing, and data and tra...
• Newton-CG Methods for Nonconvex Unconstrained Optimization with Holder Continuous Hessian AI翻译
  作者：He, Chuan; Huang, Heng; Lu, Zhaosong
  作者单位：Linkoping University; University System of Maryland; University of Maryland College Park; University of Minnesota System; University of Minnesota Twin Cities
  摘要：In this paper, we consider a nonconvex unconstrained optimization problem minimizing a twice differentiable objective function with Holder continuous Hessian. Specifically, we first propose a Newton-conjugate gradient (Newton-CG) method for finding an approximate firstand second-order stationary point of this problem, assuming the associated Holder parameters are explicitly known. Then, we develop a parameter-free Newton-CG method without requiring any prior knowledge of these parameters. To t...
• Uniform Moment Bounds for Generalized Jackson Networks in Multiscale Heavy Traffic AI翻译
  作者：Guang, Jin; Chen, Xinyun; Dai, J. G.
  作者单位：The Chinese University of Hong Kong, Shenzhen; Cornell University
  摘要：We establish uniform moment bounds for steady-state queue lengths of generalized Jackson networks (GJNs) in multiscale heavy traffic as recently proposed by Dai et al. in 2023. Uniform moment bounds lay the foundation for further analysis of the limit stationary distribution. Our result can be used to verify the crucial moment state space collapse (SSC) assumption in Dai et al. in 2023 to establish a product-form limit of GJN in the multiscale heavy traffic regime. Our proof critically utilize...
• Mode Connectivity in Auction Design AI翻译
  作者：Hertrich, Christoph; Tao, Yixin; Vegh, Laszlo A.
  作者单位：Shanghai University of Finance & Economics; University of Bonn
  摘要：Optimal auction design is a fundamental problem in algorithmic game theory. This problem is notoriously difficult already in very simple settings. Recent work in differentiable economics showed that neural networks can efficiently learn known optimal auction mechanisms and discover interesting new ones. In an attempt to theoretically justify their empirical success, we focus on one of the first such networks, RochetNet, and a generalized version for affine maximizer auctions. We prove that the...
• The IID Prophet Inequality with Limited Flexibility AI翻译
  作者：Perez-Salazar, Sebastian; Singh, Mohit; Toriello, Alejandro
  作者单位：Rice University; University System of Georgia; Georgia Institute of Technology
  摘要：In online sales, sellers usually offer each potential buyer a posted price in a takeit-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted-price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed-price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work exami...
• Information Design and Sharing in Supply Chains AI翻译
  作者：Caldentey, Rene; Giloni, Avi; Hurvich, Clifford; Zhang, Yichen
  作者单位：University of Chicago; Yeshiva University; New York University; Purdue University System; Purdue University
  摘要：We study the interplay between inventory replenishment policies and information sharing in the context of a two-tier supply chain with a single supplier and a single retailer serving an independent and identically distributed Gaussian market demand. We investigate how the retailer's inventory policy impacts the supply chain's cumulative expected long-term average inventory costs C in two extreme information-sharing cases: (a) full information sharing and (b) no information sharing. To find the...
• Finite-Time High-Probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation AI翻译
  作者：Durmus, Alain; Moulines, Eric; Naumov, Alexey; Samsonov, Sergey
  作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; HSE University (National Research University Higher School of Economics); Russian Academy of Sciences; Steklov Mathematical Institute of the Russian Academy of Sciences; Kharkevich Institute for Information Transmission Problems of the RAS
  摘要：This paper provides a finite-time analysis of linear stochastic approximation (LSA) algorithms with fixed step size, a core method in statistics and machine learning. LSA is used to compute approximate solutions of a d-dimensional linear system (A) over bar theta = (b) over bar for which ((A) over bar, (b) over bar) can only be estimated by (asymptotically) unbiased observations {(A(Z(n)),b(Z(n)))}(n is an element of N). We consider here the case where {Z(n)}(n is an element of N) is an a sequ...
• On the (Im-)Possibility of Representing Probability Distributions as a Difference of IID Noise Terms AI翻译
  作者：Ewerhart, Christian; Serena, Marco
  作者单位：University of Zurich; CUNEF Universidad
  摘要：A random variable is difference -form decomposable (DFD) if it may be written as the difference of two i.i.d. random terms. We show that densities of such variables exhibit a remarkable degree of structure. Specifically, a DFD density can be neither approximately uniform, nor quasiconvex, nor strictly concave. On the other hand, a DFD density need, in general, be neither unimodal nor logconcave. Regarding smoothness, we show that a compactly supported DFD density cannot be analytic and will of...