-
作者：Khamaru, Koulik; Mazumder, Rahul
作者单位：University of California System; University of California Berkeley; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Factor analysis is a classical multivariate dimensionality reduction technique popularly used in statistics, econometrics and data science. Estimation for factor analysis is often carried out via the maximum likelihood principle, which seeks to maximize the Gaussian likelihood under the assumption that the positive definite covariance matrix can be decomposed as the sum of a low-rank positive semidefinite matrix and a diagonal matrix with nonnegative entries. This leads to a challenging rank c...
-
作者：Sojoudi, Somayeh; Fattahi, Salar; Lavaei, Javad
作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：This paper is concerned with the minimum-cost flow problem over an arbitrary flow network. In this problem, each node is associated with some possibly unknown injection and each line has two unknown flows at its ends that are related to each other via a nonlinear function. Moreover, all injections and flows must satisfy certain box constraints. This problem, named generalized network flow (GNF), is highly non-convex due to its nonlinear equality constraints. Under the assumption of monotonicit...
-
作者：Beck, Amir; Hallak, Nadav
作者单位：Tel Aviv University; Technion Israel Institute of Technology
摘要：This paper studies a general form problem in which a lower bounded continuously differentiable function is minimized over a block separable set incorporating a group sparsity expression as a constraint or a penalty (or both) in the group sparsity setting. This class of problems is generally hard to solve, yet highly applicable in numerous practical settings. Particularly, we study the proximal mapping that includes group-sparsity terms, and derive an efficient method to compute it. Necessary o...
-
作者：Lee, Jason D.; Panageas, Ioannis; Piliouras, Georgios; Simchowitz, Max; Jordan, Michael I.; Recht, Benjamin
作者单位：University of Southern California; Singapore University of Technology & Design; University of California System; University of California Berkeley
摘要：We establish that first-order methods avoid strict saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including (manifold) gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical systems perspective in which appropriate instantiations of the Stable Manifold Theorem allow for a global stability analysis. Thus, neither access to second-orde...
-
作者：Liu, Tianxiang; Pong, Ting Kei; Takeda, Akiko
作者单位：Hong Kong Polytechnic University; University of Tokyo; RIKEN
摘要：We consider a class of nonconvex nonsmooth optimization problems whose objective is the sum of a smooth function and a finite number of nonnegative proper closed possibly nonsmooth functions (whose proximal mappings are easy to compute), some of which are further composed with linear maps. This kind of problems arises naturally in various applications when different regularizers are introduced for inducing simultaneous structures in the solutions. Solving these problems, however, can be challe...
-
作者：Li, Bowen; Jiang, Ruiwei; Mathieu, Johanna L.
作者单位：University of Michigan System; University of Michigan; University of Michigan System; University of Michigan
摘要：Optimization problems face random constraint violations when uncertainty arises in constraint parameters. Effective ways of controlling such violations include risk constraints, e.g., chance constraints and conditional Value-at-Risk constraints. This paper studies these two types of risk constraints when the probability distribution of the uncertain parameters is ambiguous. In particular, we assume that the distributional information consists of the first two moments of the uncertainty and a g...
-
作者：Renegar, James
作者单位：Cornell University
摘要：We develop a framework for applying accelerated methods to general hyperbolic programming, including linear, second-order cone, and semidefinite programming as special cases. The approach replaces a hyperbolic program with a convex optimization problem whose smooth objective function is explicit, and for which the only constraints are linear equations (one more linear equation than for the original problem). Virtually any first-order method can be applied. An iteration bound for a representati...
-
作者：Torrico, Alfredo; Ahmed, Shabbir; Toriello, Alejandro
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We study the i.i.d. online bipartite matching problem, a dynamic version of the classical model where one side of the bipartition is fixed and known in advance, while nodes from the other side appear one at a time as i.i.d. realizations of a uniform distribution, and must immediately be matched or discarded. We consider various relaxations of the polyhedral set of achievable matching probabilities, introduce valid inequalities, and discuss when they are facet-defining. We also show how several...
-
作者：Correa, Rafael; Hantoute, Abderrahim; Perez-Aros, Pedro
作者单位：Universidad de Chile; Universidad de Chile; Universidad de Chile; Universidad de O'Higgins; Universidad de Chile
摘要：In this work we give an extension of the Brondsted-Rockafellar Theorem, and some of its important consequences, to proper convex lower-semicontinuous epi-pointed functions defined in locally convex spaces. We use a new approach based on a simple variational principle, which also allows recovering the classical results in a natural way.
-
作者：Parpas, Panos; Ralph, Daniel; Wiesemann, Wolfram
作者单位：Imperial College London; Imperial College London; University of Cambridge
