-
作者：Altschuler, Jason M.; Parrilo, Pablo A.
作者单位：Massachusetts Institute of Technology (MIT)
摘要：We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osborne's algorithm has been the practitioners' algorithm of choice, and is now implemented in most numerical software packages. However, the theoretical properties of Osborne's algorithm are not well understood. Here, we show that a simple random variant of Osborne's algorithm converges in near-linear time in the input sparsity. Specifically, it balances K is a...
-
作者：Saunderson, James; Chandrasekaran, Venkat
作者单位：Monash University; California Institute of Technology; California Institute of Technology
摘要：We present a generalization of the notion of neighborliness to non-polyhedral convex cones. Although a definition of neighborliness is available in the non-polyhedral case in the literature, it is fairly restrictive as it requires all the low-dimensional faces to be polyhedral. Our approach is more flexible and includes, for example, the cone of positive-semidefinite matrices as a special case (this cone is not neighborly in general). We term our generalization Terracini convexity due to its c...
-
作者：Sun, Hailin; Shapiro, Alexander; Chen, Xiaojun
作者单位：Nanjing Normal University; University System of Georgia; Georgia Institute of Technology; Hong Kong Polytechnic University
摘要：We propose a formulation of the distributionally robust variational inequality (DRVI) to deal with uncertainties of distributions of the involved random variables in variational inequalities. Examples of the DRVI are provided, including the optimality conditions for distributionally robust optimization and distributionally robust games (DRG). The existence of solutions and monotonicity of the DRVI are discussed. Moreover, we propose a sample average approximation (SAA) approach to the DRVI and...
-
作者：Basu, Amitabh; Jiang, Hongyi
作者单位：Johns Hopkins University
摘要：We define a new cutting plane closure for pure integer programs called the two-halfspace closure. It is a natural generalization of the well-known Chvatal-Gomory closure. We prove that the two-halfspace closure is polyhedral. We also study the corresponding two-halfspace rank of any valid inequality and show that it is at most the split rank of the inequality. Moreover, while the split rank can be strictly larger than the two-halfspace rank, the split rank is at most twice the two-halfspace ra...
-
作者：Zamani, Moslem; Hladik, Milan
作者单位：Tilburg University; Charles University Prague
摘要：Due to their relation to the linear complementarity problem, absolute value equations have been intensively studied recently. In this paper, we present error bound conditions for absolute value equations. Along with the error bounds, we introduce a condition number. We consider general scaled matrix p-norms, as well as particular p-norms. We discuss basic properties of the condition number, including its computational complexity. We present various bounds on the condition number, and we give e...
-
作者：Garrigos, Guillaume; Rosasco, Lorenzo; Villa, Silvia
作者单位：Centre National de la Recherche Scientifique (CNRS); Universite Paris Cite; University of Genoa; Istituto Italiano di Tecnologia - IIT; University of Genoa
摘要：We provide a comprehensive study of the convergence of the forward-backward algorithm under suitable geometric conditions, such as conditioning or Lojasiewicz properties. These geometrical notions are usually local by nature, and may fail to describe the fine geometry of objective functions relevant in inverse problems and signal processing, that have a nice behaviour on manifolds, or sets open with respect to a weak topology. Motivated by this observation, we revisit those geometric notions o...
-
作者：Jiang, Bo; Meng, Xiang; Wen, Zaiwen; Chen, Xiaojun
作者单位：Nanjing Normal University; Massachusetts Institute of Technology (MIT); Peking University; Peking University; Hong Kong Polytechnic University
摘要：Optimization with nonnegative orthogonality constraints has wide applications in machine learning and data sciences. It is NP-hard due to some combinatorial properties of the constraints. We first propose an equivalent optimization formulation with nonnegative and multiple spherical constraints and an additional single nonlinear constraint. Various constraint qualifications, the first- and second-order optimality conditions of the equivalent formulation are discussed. By establishing a local e...
-
作者：Bollapragada, Raghu; Scieur, Damien; D'Aspremont, Alexandre
作者单位：University of Texas System; University of Texas Austin; Inria; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I); Universite PSL; Ecole Normale Superieure (ENS); Universite PSL; Ecole Normale Superieure (ENS); Centre National de la Recherche Scientifique (CNRS)
摘要：We describe convergence acceleration schemes for multistep optimization algorithms where the underlying fixed-point operator is not symmetric. In particular, our analysis handles algorithms with momentum terms such as Nesterov's accelerated method or primal-dual methods. The acceleration technique combines previous iterates through a weighted sum, whose coefficients are computed via a simple linear system. We analyze performance in both online and offline modes, and we study in particular a va...
-
作者：Davis, Damek
作者单位：Cornell University
摘要：Minimizing finite sums of smooth and strongly convex functions is an important task in machine learning. Recent work has developed stochastic gradient methods that optimize these sums with less computation than methods that do not exploit the finite sum structure. This speedup results from using efficiently constructed stochastic gradient estimators, which have variance that diminishes as the algorithm progresses. In this work, we ask whether the benefits of variance reduction extend to fixed ...
-
作者：Shen, Haoming; Jiang, Ruiwei
作者单位：University of Michigan System; University of Michigan
摘要：We study a generalized distributionally robust chance-constrained set covering problem (DRC) with a Wasserstein ambiguity set, where both decisions and uncertainty are binary-valued. We establish the NP-hardness of DRC and recast it as a two-stage stochastic program, which facilitates decomposition algorithms. Furthermore, we derive two families of valid inequalities. The first family targets the hypograph of a shifted submodular function, which is associated with each scenario of the two-stag...
