-
作者：Yu, Qimeng; Kucukyavuz, Simge
作者单位：Universite de Montreal; Northwestern University
摘要：Diminishing returns (DR)-submodular functions encompass a broad class of functions that are generally nonconvex and nonconcave. We study the problem of minimizing any DR-submodular function with continuous and general integer variables under box constraints and, possibly, additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisin...
-
作者：Li, Yuan; Goldberg, David A.
作者单位：Amazon.com
摘要：We consider the FCFS GI/GI/n queue, and prove the first simple and explicit bounds that scale as( 1)/(1-rho) under only the assumption that inter-arrival times have finite second moment, and service times have finite 2+& varepsilon; moment for some & varepsilon;>0. Here rho denotes the corresponding traffic intensity. Conceptually, our results can be viewed as a multi-server analogue of Kingman's bound. Our main results are bounds for the tail of the steady-state queue length and the steady-st...
-
作者：Necoara, Ion; Chorobura, Flavia
作者单位：National University of Science & Technology POLITEHNICA Bucharest; Romanian Academy
摘要：This paper deals with composite optimization problems having the objective function formed as the sum of two terms; one has a Lipschitz continuous gradient along random subspaces and may be nonconvex, and the second term is simple and differentiable but possibly nonconvex and nonseparable. Under these settings, we design a stochastic coordinate proximal gradient method that takes into account the nonseparable composite form of the objective function. This algorithm achieves scalability by cons...
-
作者：Sharma, Salil; Tsakas, Elias; Voorneveld, Mark
作者单位：Stockholm School of Economics; Maastricht University
摘要：We study settings where information in the form of Bayesian signals is acquired by an expert on behalf of a principal. Information acquisition is costly for the expert and crucially not verifiable by the principal. The expert is compensated by the principal with a menu of state -contingent payments. We provide a full characterization of the set of all menus that implement (respectively, strictly implement) each signal. Moreover, we provide a closed -form characterization for the expected cost ...
-
作者：Bonesini, Ofelia; Campi, Luciano; Fischer, Markus
作者单位：Imperial College London; University of Padua; University of Milan
摘要：In a discrete space and time framework, we study the mean field game limit for a class of symmetric N-player games based on the notion of correlated equilibrium. We give a definition of correlated solution that allows us to construct approximate N-player correlated equilibria that are robust with respect to progressive deviations. We illustrate our definition by way of an example with explicit solutions.
-
作者：Zhao, Jingyang; Xiao, Mingyu
作者单位：University of Electronic Science & Technology of China
摘要：The traveling tournament problem (TTP) is a hard but interesting sports scheduling problem inspired by Major League Baseball, which is to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, minimizing the total distance traveled by all n teams (n is even). In this paper, we consider TTP-2 (i.e., TTP under the constraint that at most two consecutive home games or away games are allowed for each team). In this paper, we propose practical a...
-
作者：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...
-
作者：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...
