-
作者：Sentenac, Flore; Noiry, Nathan; Lerasle, Matthieu; Menard, Laurent; Perchet, Vianney
作者单位：IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom Paris; Institut Polytechnique de Paris; Centre National de la Recherche Scientifique (CNRS); Institut Polytechnique de Paris; ENSAE Paris
摘要：We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any previously unmatched campaign that it is compatible with. Despite the limited theoretical guarantees, the greedy algorithm, which matches incoming users with any available campaign, exhibits outstanding performance in practice. Some theoretical support for this practical success has been established in specific classe...
-
作者：Ahn, Dohyun; Zheng, Lewen
作者单位：Chinese University of Hong Kong
摘要：We consider the problem of estimating the expectation over a convex polyhedron specified by a set of linear inequalities. This problem encompasses a multitude of financial applications, including systemic risk quantification, exotic option pricing, and portfolio management. We particularly focus on the case where the target event is rare, which corresponds to extreme systemic failures, deep out-of-the-money options, and high target returns in the aforementioned applications, respectively. This...
-
作者：Tran-Dinh, Quoc; Luo, Yang
作者单位：University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine
摘要：In this paper, we develop two new randomized block-coordinate optimistic gradient algorithms to approximate a solution of nonlinear equations in large-scale settings, which are known as root-finding problems. Our first algorithm is nonaccelerated with constant step sizes and achieves a O(1/k) best-iterate convergence rate on E[& Vert;Gxk & Vert;2] when the underlying operator G is Lipschitz continuous and possesses a weak Minty solution, in which E[] is the expectation and k is the iteration c...
-
作者：Xu, Yunbei; Zeevi, Assaf
作者单位：Columbia University
摘要：We study problem-dependent rates, that is, generalization errors that scale near-optimally with the variance, effective loss, or gradient norms evaluated at the best hypothesis. We introduce a principled framework dubbed uniform localized convergence and characterize sharp problem-dependent rates for central statistical learning problems. From a methodological viewpoint, our framework resolves several fundamental limitations of existing uniform convergence and localization analysis approaches....
-
作者：Cembrano, Javier; Correa, Jose; Schmidt-Kraepelin, Ulrike; Tsigonias-Dimitriadis, Alexandros; Verdugo, Victor
作者单位：Max Planck Society; Universidad de Chile; Eindhoven University of Technology; European Central Bank; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：The apportionment problem constitutes a fundamental problem in democratic societies: How to distribute a fixed number of seats among a set of states in proportion to the states' populations? This-seemingly simple-task has led to a rich literature and has become well known in the context of the U.S. House of Representatives. In this paper, we connect the design of monotone apportionment methods to classic problems from discrete geometry and combinatorial optimization and explore the extent to w...
-
作者：Chen, Lin; Tao, Liangde; Verschae, Jose
作者单位：Zhejiang University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
摘要：We consider a classical scheduling problem on m identical machines. For an arbitrary constant q > 1, the aim is to assign jobs to machines such that Sigma(m)(i=1) C-i(q) is minimized, where C-i is the total processing time of jobs assigned to machine i. It is well known that this problem is strongly NP-hard. Under mild assumptions, the running time of a (1 + epsilon)-approximation algorithm for a strongly NP-hard problem cannot be polynomial on 1/epsilon, unless P=NP. For most problems in the ...
-
作者：Lassiter, Julie Bowers; Hadavas, Paul T.; Adams, Warren P.
作者单位：Clemson University; University System of Georgia; Georgia Southern University
摘要：We define a multilinear program to be persistent if every variable realizing a value at either its lower or upper bound in an optimum to a specified linear relaxation persists in retaining that same value in an optimum to the original problem. Few persistency results are known, and all deal with binary or mixed 0-1 problems, reformulating nonlinear instances as equivalent mixed 0-1 linear programs and showing the preference of a binary variable over its complement. We extend the knowledge of p...
-
作者：Kruk, Lukasz
作者单位：Maria Curie-Sklodowska University
摘要：A single-server queue with renewal arrivals and generally distributed independent and identically distributed service times is considered. Customers are served using the longest job first (LJF) scheduling algorithm with first in, first out being used as a tiebreaking rule. We introduce a fluid model for the evolution of a measure-valued state descriptor of this queue, and we investigate its properties. We also prove a fluid limit theorem justifying our fluid model as the first order approximat...
-
作者：Aydin, Ugur; Saldi, Naci
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Ihsan Dogramaci Bilkent University
摘要：In this paper, we investigate the robustness of stationary mean-field equilibria in the presence of model uncertainties, specifically focusing on infinite-horizon discounted cost functions. To achieve this, we initially establish convergence conditions for value iterationbased algorithms in mean-field games. Subsequently, utilizing these results, we demonstrate that the mean-field equilibrium obtained through this value iteration algorithm remains robust even in the face of system dynamics mis...
-
作者：Tang, Wenpin; Yao, David D.
作者单位：Columbia University
摘要：We propose and study a new class of polynomial voting rules for a general decentralized decision/consensus system, and more specifically for the proof -of -stake protocol. The main idea, inspired by the Penrose square -root law and the more recent quadratic voting rule, is to differentiate a voter's voting power and the voter's share (fraction of the total in the system). We show that, whereas voter shares form a martingale process that converges to a Dirichlet distribution, their voting power...
