Mathematics of Operations Research

最新文章

• Rank-One Boolean Tensor Factorization and the Multilinear Polytope AI翻译
  作者：Del Pia, Alberto; Khajavirad, Aida
  作者单位：University of Wisconsin System; University of Wisconsin Madison; University of Wisconsin System; University of Wisconsin Madison; Lehigh University
  摘要：We consider the NP-hard problem of finding the closest rank-one binary tensor to a given binary tensor, which we refer to as the rank-one Boolean tensor factorization (BTF) problem. This optimization problem can be used to recover a planted rankone tensor from noisy observations. We formulate rank-one BTF as the problem of minimizing a linear function over a highly structured multilinear set. Leveraging on our prior results regarding the facial structure of multilinear polytopes, we propose no...
• Robust Faber-Schauder Approximation Based on Discrete Observations of an Antiderivative AI翻译
  作者：Han, Xiyue; Schied, Alexander
  作者单位：University of Waterloo
  摘要：We study the problem of reconstructing the Faber-Schauder coefficients of a continuous functionf from discrete observations of its antiderivative F. For instance, this question arises in financial mathematics when estimating the roughness of volatility from the integrated volatility of an asset price trajectory. Our approach starts with mathematically formulating the reconstruction problem through piecewise quadratic spline interpolation. We then provide a closed-form solution and an in-depth ...
• SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization AI翻译
  作者：Kurpisz, Adam; Potechin, Aaron; Wirth, Elias
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Chicago; Technical University of Berlin
  摘要：We introduce several methods to study the rank of the sum of squares (SoS) hierarchy for problems over the Boolean hypercube. We apply our techniques to improve upon existing results, thus answering several open questions. We answer the question by Laurent regarding the SoS rank of the empty integral hull (EIH) problem. We prove that the SoS rank is between inverted right perpendicularn/2inverted left perpendicular and inverted right perpendicularn/2+ root n log 2ninverted left perpendicular. ...
• Variance-Reduced Accelerated First-Order Methods: Central Limit Theorems and Confidence Statements AI翻译
  作者：Lei, Jinlong; Shanbhag, Uday V.
  作者单位：Tongji University; Tongji University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park
  摘要：In this paper, we consider a strongly convex stochastic optimization problem and propose three classes of variable sample -size stochastic first -order methods: (i) the standard stochastic gradient descent method, (ii) its accelerated variant, and (iii) the stochastic heavy -ball method. In each scheme, the exact gradients are approximated by averaging across an increasing batch size of sampled gradients. We prove that when the sample size increases at a geometric rate, the generated estimates...
• Fast Rates for the Regret of Offline Reinforcement Learning AI翻译
  作者：Hu, Yichun; Kallus, Nathan; Uehara, Masatoshi
  作者单位：Cornell University
  摘要：We study the regret of offline reinforcement learning in an infinite -horizon discounted Markov decision process (MDP). While existing analyses of common approaches, such as fitted Q -iteration (FQI), suggest root -n convergence for regret, empirical behavior exhibits much faster convergence. In this paper, we present a finer regret analysis that exactly characterizes this phenomenon by providing fast rates for the regret convergence. First, we show that given any estimate for the optimal qual...
• Submodular Functions and Perfect Graphs AI翻译
  作者：Abrishami, Tara; Chudnovsky, Maria; Dibek, Cemil; Vuskovic, Kristina
  作者单位：University of Hamburg; Princeton University; Princeton University; University of Leeds
  摘要：We give a combinatorial polynomial-time algorithm to find a maximum weight independent set in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph. An even pair in a graph is a pair of vertices all induced paths between which are even. An even set is a set of vertices every two of which are an even pair. We show that every perfect graph that does not contain a prism or a hole of length four as an induced subgraph has a balanced separator ...
• Scheduling in the High-Uncertainty Heavy Traffic Regime AI翻译
  作者：Atar, Rami; Castiel, Eyal; Shadmi, Yonatan
  摘要：We propose a model uncertainty approach to heavy traffic asymptotics that allows for a high level of uncertainty. That is, the uncertainty classes of underlying distributions accommodate disturbances that are of order 1 at the usual diffusion scale as opposed to asymptotically vanishing disturbances studied previously in relation to heavy traffic. A main advantage of the approach is that the invariance principle underlying diffusion limits makes it possible to define uncertainty classes in ter...
• Synchronization Games AI翻译
  作者：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...
• A Momentum-Based Linearized Augmented Lagrangian Method for Nonconvex Constrained Stochastic Optimization AI翻译
  作者：Shi, Qiankun; Wang, Xiao; Wang, Hao
  作者单位：Sun Yat Sen University; ShanghaiTech University
  摘要：Nonconvex constrained stochastic optimization has emerged in many important application areas. Subject to general functional constraints, it minimizes the sum of an expectation function and a nonsmooth regularizer. Main challenges arise because of the stochasticity in the random integrand and the possibly nonconvex functional constraints. To address these issues, we propose a momentum-based linearized augmented Lagrangian method (MLALM). MLALM adopts a single-loop framework and incorporates a ...
• The Minimax Property in Infinite Two-Person Win-Lose Games AI翻译
  作者：Holzman, Ron
  作者单位：Technion Israel Institute of Technology
  摘要：We explore a version of the minimax theorem for two-person win-lose games with infinitely many pure strategies. In the countable case, we give a combinatorial condition on the game which implies the minimax property. In the general case, we prove that a game satisfies the minimax property along with all its subgames if and only if none of its subgames is isomorphic to the larger number game. This generalizes a recent theorem of Hanneke, Livni, and Moran. We also propose several applications of...