-
作者：Hofer, Felix; Soner, H. Mete
作者单位：Princeton University
摘要：We propose a new mean-field game model with two states to study synchronization phenomena, and we provide a comprehensive characterization of stationary and dynamic equilibria along with their stability properties. The game undergoes a phase transition with increasing interaction strength. In the subcritical regime, the uniform distribution, representing incoherence, is the unique and stable stationary equilibrium. Above the critical interaction threshold, the uniform equilibrium becomes unsta...
-
作者：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...
-
作者：Liu, Wei; Lin, Qihang; Xu, Yangyang
作者单位：Rensselaer Polytechnic Institute; University of Iowa
摘要：Many recent studies on first-order methods (FOMs) focus on composite nonconvex nonsmooth optimization with linear and/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their optimality, as no lower bound is known except for a few special smooth nonconvex cases. In this paper, we make the first attempt to establish lower complexity bounds of FOMs for solving a class of composite nonconvex nons...
-
作者：Han, Xia; Wang, Qiuqi; Wang, Ruodu; Xia, Jianming
作者单位：Nankai University; Nankai University; University System of Georgia; Georgia State University; University of Waterloo; Chinese Academy of Sciences
摘要：In the literature on risk measures, cash subadditivity was proposed to replace cash additivity, motivated by the presence of stochastic or ambiguous interest rates and defaultable contingent claims. Cash subadditivity has been traditionally studied together with quasi-convexity, in a way similar to cash additivity with convexity. In this paper, we study cash-subadditive risk measures without quasi-convexity. One of our major results is that a general cash-subadditive risk measure can be repres...
-
作者：Portales, Leo; Cazelles, Elsa; Pauwelsc, Edouard
作者单位：Communaute d'universites et etablissements de Toulouse (Comue); Universite de Toulouse (EPE); Universite Toulouse 1 Capitole; Institut National Polytechnique de Toulouse; Toulouse School of Economics; Centre National de la Recherche Scientifique (CNRS); Communaute d'universites et etablissements de Toulouse (Comue); Communaute d'universites et etablissements de Toulouse (Comue); Universite Toulouse 1 Capitole; Toulouse School of Economics
摘要：Lloyd's algorithm is an iterative method that solves the quantization problem, that is, the approximation of a target probability measure by a discrete one, and is particularly used in digital applications. This algorithm can be interpreted as a gradient method on a certain quantization functional which is given by optimal transport. We study the sequential convergence (to a single accumulation point) for two variants of Lloyd's method: (i) optimal quantization with an arbitrary discrete measu...
-
作者：Govindan, Srihari; Laraki, Rida; Pahl, Lucas
作者单位：University of Rochester; Mohammed VI Polytechnic University; University of Sheffield
摘要：We present the following analog of O'Neill's theorem (O'Neill B (1953) Essential sets and fixed points. Amer. J. Math. 75(3):497-509 (theorem 5.2)) for finite games. Let C-1,. . . , C-k be the components of Nash equilibria of a finite normal-form game G. For each i, let ci be the index of C-i. For each epsilon > 0, there exist pairwise disjoint neighborhoods V-1,. . ., V-k of the components such that for any choice of finitely many distinct completely mixed strategy profiles {sigma(ij)}(ij), s...
-
作者：Gomes, Alexandra A.; Gomes, Diogo A.
作者单位：King Abdullah University of Science & Technology
摘要：We introduce a derivative-free optimization algorithm that efficiently computes minima for various classes of one-dimensional functions, including nonconvex and nonsmooth functions. This algorithm numerically approximates the gradient flow of a relaxed functional, integrating strategies such as Monte Carlo methods, rejection sampling, and adaptive techniques. These strategies enhance performance in solving a diverse range of optimization problems while significantly reducing the number of requ...
-
作者：Ghosal, Promit; Nutz, Marcel
作者单位：University of Chicago; Columbia University
摘要：We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate pi t is shown to satisfy H(pi t|pi*) + H(pi*|pi t) = O(t(-1)), where H denotes relative entropy and pi* denotes the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with sub-Gaussian marginals. We also obtain the rate O(t(-1)) for the dual suboptimality and O(t(-2)) for the marginal entropies. More precisely, we derive nonasymptot...
-
作者：He, Shengyi; Lam, Henry
作者单位：Columbia University
摘要：Distributionally robust optimization (DRO) is a worst-case framework for stochastic optimization under uncertainty that has drawn fast-growing studies in recent years. When the underlying probability distribution is unknown and observed from data, DRO suggests computing the worst-case distribution within a so-called uncertainty set that captures the involved statistical uncertainty. In particular, DRO with uncertainty set constructed as a statistical divergence neighborhood ball has been shown...
-
作者：Banerjee, Sayan; Budhiraja, Amarjit; Estevez, Benjamin
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：Consider a queuing system with K parallel queues in which the server for each queue processes jobs at rate n and the total arrival rate to the system is nK - v root n, where v is an element of (0,infinity) and n is large. Interarrival and service times are taken to be independent and exponentially distributed. It is well known that the join-the-shortest-queue (JSQ) policy has many desirable load-balancing properties. In particular, in comparison with uniformly at random routing, the time asymp...
