-
作者：Ge, Rong; Ma, Tengyu
作者单位：Duke University; Stanford University
摘要：Non-convex optimization with local search heuristics has been widely used in machine learning, achieving many state-of-art results. It becomes increasingly important to understand why they can work for these NP-hard problems on typical data. The landscape of many objective functions in learning has been conjectured to have the geometric property that all local optima are (approximately) global optima, and thus they can be solved efficiently by local search algorithms. However, establishing suc...
-
作者：de Klerk, Etienne; Laurent, Monique
作者单位：Tilburg University; Centrum Wiskunde & Informatica (CWI)
摘要：We study the convergence rate of a hierarchy of upper bounds for polynomial minimization problems, proposed by Lasserre (SIAM J Optim 21(3):864-885, 2011), for the special case when the feasible set is the unit (hyper)sphere. The upper bound at level r is an element of N of the hierarchy is defined as the minimal expected value of the polynomial over all probability distributions on the sphere, when the probability density function is a sum-of-squares polynomial of degree at most 2r with respe...
-
作者：Cifuentes, Diego; Agarwal, Sameer; Parrilo, Pablo A.; Thomas, Rekha R.
作者单位：University System of Georgia; Georgia Institute of Technology; Alphabet Inc.; Google Incorporated; University of Washington; University of Washington Seattle; Massachusetts Institute of Technology (MIT)
摘要：We consider a parametric family of quadratically constrained quadratic programs and their associated semidefinite programming (SDP) relaxations. Given a nominal value of the parameter at which the SDP relaxation is exact, we study conditions (and quantitative bounds) under which the relaxation will continue to be exact as the parameter moves in a neighborhood around the nominal value. Our framework captures a wide array of statistical estimation problems including tensor principal component an...
-
作者：Faenza, Yuri; Munoz, Gonzalo; Pokutta, Sebastian
作者单位：Columbia University; Universidad de O'Higgins; Zuse Institute Berlin; Technical University of Berlin
摘要：Sparse structures are frequently sought when pursuing tractability in optimization problems. They are exploited from both theoretical and computational perspectives to handle complex problems that become manageable when sparsity is present. An example of this type of structure is given by treewidth: a graph theoretical parameter that measures how tree-like a graph is. This parameter has been used for decades for analyzing the complexity of various optimization problems and for obtaining tracta...
-
作者：Blekherman, Grigoriy; Madhusudhana, Bharath Hebbe
作者单位：University System of Georgia; Georgia Institute of Technology; University of Munich
摘要：Quantum states are represented by positive semidefinite Hermitian operators with unit trace, known as density matrices. An important subset of quantum states is that of separable states, the complement of which is the subset of entangled states. We show that the problem of deciding whether a quantum state is entangled can be seen as amoment problem in real analysis. Only a small number of such moments are accessible experimentally, and so in practice the question of quantum entanglement of a m...
-
作者：Frandsen, Abraham; Ge, Rong
作者单位：Duke University
摘要：Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconve...
