-
作者：Hu, Bin; Seiler, Peter; Lessard, Laurent
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University of Michigan System; University of Michigan; University of Wisconsin System; University of Wisconsin Madison
摘要：We present a convergence rate analysis for biased stochastic gradient descent (SGD), where individual gradient updates are corrupted by computation errors. We develop stochastic quadratic constraints to formulate a small linear matrix inequality (LMI) whose feasible points lead to convergence bounds of biased SGD. Based on this LMI condition, we develop a sequential minimization approach to analyze the intricate trade-offs that couple stepsize selection, convergence rate, optimization accuracy...
-
作者：Haeser, Gabriel; Hinder, Oliver; Ye, Yinyu
作者单位：Universidade de Sao Paulo; Stanford University
摘要：We analyze sequences generated by interior point methods (IPMs) in convex and nonconvex settings. We prove that moving the primal feasibility at the same rate as the barrier parameter mu ensures the Lagrange multiplier sequence remains bounded, provided the limit point of the primal sequence has a Lagrange multiplier. This result does not require constraint qualifications. We also guarantee the IPM finds a solution satisfying strict complementarity if one exists. On the other hand, if the prim...
-
作者：Padmanabhan, Divya; Natarajan, Karthik; Murthy, Karthyek
作者单位：Singapore University of Technology & Design
摘要：In this paper, we identify partial correlation information structures that allow for simpler reformulations in evaluating the maximum expected value of mixed integer linear programs with random objective coefficients. To this end, assuming only the knowledge of the mean and the covariance matrix entries restricted to block-diagonal patterns, we develop a reduced semidefinite programming formulation, the complexity of solving which is related to characterizing a suitable projection of the conve...
-
作者：Shitov, Yaroslav
作者单位：Moscow Institute of Physics & Technology
摘要：We present an example of a subfield F. R and a matrix A whose conventional and nonnegative ranks equal five, but the nonnegative rank with respect to F equals six. In other words, A can be represented as a sum of five rank-one matrices with nonnegative real entries but not as a sum of five rank-one matrices with nonnegative entries in F.
-
作者：Wolsey, Laurence A.; Yaman, Hande
作者单位：Universite Catholique Louvain; KU Leuven
摘要：For single node flow sets with fixed costs and constant capacities on the inflow and outflow arcs, a family of constant capacity flow covers are known to provide the convex hull in different special cases and are conjectured to provide it in the general case. Here we study more general mixed integer sets for which such single node flow cover inequalities suffice to give the convex hull. In particular we consider the case of a path in which each node has one (or several) incoming and outgoing a...
-
作者：Allen-Zhu, Zeyuan; Li, Yuanzhi; Singh, Aarti; Wang, Yining
作者单位：Microsoft; Carnegie Mellon University; State University System of Florida; University of Florida
摘要：The experimental design problem concerns the selection of k points from a potentially large design pool of p-dimensional vectors, so as to maximize the statistical efficiency regressed on the selected k design points. Statistical efficiency is measured by optimality criteria, including A(verage), D(eterminant), T(race), E(igen), V(ariance) and G-optimality. Except for the T-optimality, exact optimization is challenging, and for certain instances of D/E-optimality exact or even approximate opti...
-
作者：Sun, Ruoyu; Ye, Yinyu
作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Stanford University
摘要：This paper concerns the worst-case complexity of cyclic coordinate descent (C-CD) for minimizing a convex quadratic function, which is equivalent to Gauss-Seidel method, Kaczmarz method and projection onto convex sets (POCS) in this simple setting. We observe that the known provable complexity of C-CD can be O(n(2)) times slower than randomized coordinate descent (R-CD), but no example was proven to exhibit such a large gap. In this paper we show that the gap indeed exists. We prove that there...
-
作者：Mohammad-Nezhad, Ali; Terlaky, Tamas
作者单位：Purdue University System; Purdue University; Lehigh University
摘要：In this paper, using an optimal partition approach, we study the parametric analysis of a second-order conic optimization problem, where the objective function is perturbed along a fixed direction. We characterize the notions of so-called invariancy set and nonlinearity interval, which serve as stability regions of the optimal partition. We then propose, under the strict complementarity condition, an iterative procedure to compute a nonlinearity interval of the optimal partition. Furthermore, ...
-
作者：Potschka, Andreas; Bock, Hans Georg
-
作者：Basu, Amitabh; Ryan, Christopher Thomas; Sankaranarayanan, Sriram
作者单位：Johns Hopkins University; University of Chicago; Universite de Montreal; Polytechnique Montreal
摘要：We study the representability of sets by extended formulations using mixed-integer bilevel programs. We show that feasible regions modeled by continuous bilevel constraints (with no integer variables), complementarity constraints, and polyhedral reverse convex constraints are all finite unions of polyhedra. Conversely, any finite union of polyhedra can be represented using any one of these three paradigms. We then prove that the feasible region of bilevel problems with integer variables exclus...
