2021

最新文章

• The Running Intersection Relaxation of the Multilinear Polytope AI翻译
  作者：Del Pia, Alberto; Khajavirad, Aida
  作者单位：University of Wisconsin System; University of Wisconsin Madison; Lehigh University
  摘要：The multilinear polytope of a hypergraph is the convex hull of a set of binary points satisfying a collection of multilinear equations. We introduce the running intersection inequalities, a new class of facet-defining inequalities for the multilinear polytope. Accordingly, we define a new polyhedral relaxation of the multilinear polytope, referred to as the running intersection relaxation, and identify conditions under which this relaxation is tight. Namely, we show that for kite-free beta-acy...
• Fair Allocation of Indivisible Goods: Improvement AI翻译
  作者：Ghodsi, Mohammad; Hajiaghayi, Mohammad Taghi; Seddighin, Masoud; Seddighin, Saeed; Yami, Hadi
  作者单位：Sharif University of Technology; Institute for Research in Fundamental Sciences IPM; University System of Maryland; University of Maryland College Park
  摘要：We study the problem of fair allocation for indivisible goods. We use the maximin share paradigm introduced by Budish [Budish E (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. J. Political Econom. 119(6):1061-1103.] as a measure of fairness. Kurokawa et al. [Kurokawa D, Procaccia AD, Wang J (2018) Fair enough: Guaranteeing approximate maximin shares. J. ACM 65(2):8.] were the first to investigate this fundamental problem in the additive sett...
• Online Learning over a Finite Action Set with Limited Switching AI翻译
  作者：Altschuler, Jason M.; Talwar, Kunal
  作者单位：Massachusetts Institute of Technology (MIT); Alphabet Inc.; Google Incorporated
  摘要：This paper studies the value of switching actions in the Prediction From Experts problem (PFE) and Adversarial Multiarmed Bandits problem (MAB). First, we revisit the well-studied and practically motivated setting of PFE with switching costs. Many algorithms achieve the minimax optimal order for both regret and switches in expectation; however, high probability guarantees are an open problem. We present the first algorithms that achieve this optimal order for both quantities with high probabil...
• Trust Your Data or Not-StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization AI翻译
  作者：Bomze, Immanuel M.; Kahr, Michael; Leitner, Markus
  作者单位：University of Vienna; University of Vienna; University of Vienna; Vrije Universiteit Amsterdam
  摘要：We consider the robust standard quadratic optimization problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is optimized over the standard simplex. Following most approaches, we model the uncertainty sets by balls, polyhedra, or spectrahedra, more generally, by ellipsoids or order intervals intersected with subcones of the copositive matrix cone. We show that the copositive relaxation gap of the RStQP equals the minimax gap under some mild assumptions on the curvature of...
• Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis AI翻译
  作者：Kim, Jinhak; Tawarmalani, Mohit; Richard, Jean-Philippe P.
  作者单位：Northern Illinois University; Purdue University System; Purdue University; University of Minnesota System; University of Minnesota Twin Cities
  摘要：We develop techniques to convexify a set that is invariant under permutation and/or change of sign of variables and discuss applications of these results. First, we convexify the intersection of the unit ball of a permutation and sign-invariant norm with a cardinality constraint. This gives a nonlinear formulation for the feasible set of sparse principal component analysis (PCA) and an alternative proof of the K-support norm. Second, we characterize the convex hull of sets of matrices defined ...
• Sparse Solutions of a Class of Constrained Optimization Problems AI翻译
  作者：Yang, Lei; Chen, Xiaojun; Xiang, Shuhuang
  作者单位：National University of Singapore; Hong Kong Polytechnic University; Central South University
  摘要：In this paper, we consider a well-known sparse optimization problem that aims to find a sparse solution of a possibly noisy underdetermined system of linear equations. Mathematically, it can be modeled in a unified manner by minimizing parallel to x parallel to(p)(p) subject to parallel to Ax - b parallel to(q) <= sigma for given A is an element of R-mxn, b is an element of R-m, sigma >= 0, 0 <= p <= 1 and q >= 1. We then study various properties of the optimal solutions of this problem. Speci...
• Learning Optimal Forecast Aggregation in Partial Evidence Environments AI翻译
  作者：Babichenko, Yakov; Garber, Dan
  作者单位：Technion Israel Institute of Technology
  摘要：We consider the forecast aggregation problem in repeated settings where the forecasts are of a binary state of nature. In each period multiple experts provide forecasts about the state. The goal of the aggregator is to aggregate those forecasts into a subjective accurate forecast. We assume that the experts are Bayesian and the aggregator is non-Bayesian and ignorant of the information structure (i.e., the distribution over the signals) under which the experts make their forecasts. The aggrega...
• ε-Strong Simulation of Fractional Brownian Motion and Related Stochastic Differential Equations AI翻译
  作者：Chen, Yi; Dong, Jing; Ni, Hao
  作者单位：Northwestern University; Columbia University; University of London; University College London
  摘要：Consider a fractional Brownian motion (fBM) B-H = {B-H(t) : t is an element of [0, 1]} with Hurst index H is an element of (0, 1). We construct a probability space supporting both B-H and a fully simulatable process (B) over cap (H)(epsilon) such that sup(t is an element of[0,1])vertical bar B-H(t) - (B) over cap (H)(epsilon)(t)vertical bar <= epsilon with probability one for any user-specified error bound epsilon > 0. When H > 1/2, we further enhance our error guarantee to the alpha-Holder no...
• Popularity, Mixed Matchings, and Self-Duality AI翻译
  作者：Huang, Chien-Chung; Kavitha, Telikepalli
  作者单位：Universite PSL; Ecole Normale Superieure (ENS); Tata Institute of Fundamental Research (TIFR)
  摘要：Our input instance is a bipartite graph G where each vertex has a preference list ranking its neighbors in a strict order of preference. A matching M is popular if there is no matching N such that the number of vertices that prefer N to M outnumber those that prefer M to N. Each edge is associated with a utility and we consider the problem of matching vertices in a popular and utility-optimal manner. It is known that it is NP-hard to compute a max-utility popular matching. So we consider mixed...
• A General Analysis of Sequential Social Learning AI翻译
  作者：Arieli, Itai; Mueller-Frank, Manuel
  作者单位：Technion Israel Institute of Technology; University of Navarra; IESE Business School
  摘要：This paper analyzes a sequential social learning game with a general utility function, state, and action space. We show that asymptotic learning holds for every utility function if and only if signals are totally unbounded, that is, the support of the private posterior probability of every event contains both zero and one. For the case of finitely many actions, we provide a sufficient condition for asymptotic learning depending on the given utility function. Finally, we establish that for the ...