-
作者：Baldi, Lorenzo; Mourrain, Bernard
作者单位：Universite Cote d'Azur
摘要：We analyse the representation of positive polynomials in terms of Sums of Squares. We provide a quantitative version of Putinar's Positivstellensatz over a compact basic semialgebraic set S, with a new polynomial bound on the degree of the positivity certificates. This bound involves a Lojasiewicz exponent associated to the description of S. We show that if the gradients of the active constraints are linearly independent on S (Constraint Qualification condition), this Lojasiewicz exponent is e...
-
作者：Dvurechensky, Pavel; Safin, Kamil; Shtern, Shimrit; Staudigl, Mathias
作者单位：Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Moscow Institute of Physics & Technology; Technion Israel Institute of Technology; Maastricht University
摘要：Projection-free optimization via different variants of the Frank-Wolfe method has become one of the cornerstones of large scale optimization for machine learning and computational statistics. Numerous applications within these fields involve the minimization of functions with self-concordance like properties. Such generalized self-concordant functions do not necessarily feature a Lipschitz continuous gradient, nor are they strongly convex, making them a challenging class of functions for first...
-
作者：Bareilles, Gilles; Iutzeler, Franck; Malick, Jerome
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：Proximal methods are known to identify the underlying substructure of nonsmooth optimization problems. Even more, in many interesting situations, the output of a proximity operator comes with its structure at no additional cost, and convergence is improved once it matches the structure of a minimizer. However, it is impossible in general to know whether the current structure is final or not; such highly valuable information has to be exploited adaptively. To do so, we place ourselves in the ca...
-
作者：Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology
摘要：We present new policy mirror descent (PMD) methods for solving reinforcement learning (RL) problems with either strongly convex or general convex regularizers. By exploring the structural properties of these overall highly nonconvex problems we show that the PMD methods exhibit fast linear rate of convergence to the global optimality. We develop stochastic counterparts of these methods, and establish an O(1/epsilon) (resp., O(1/epsilon(2))) sampling complexity for solving these RL problems wit...
-
作者：Murray, Riley; Naumann, Helen; Theobald, Thorsten
作者单位：University of California System; University of California Berkeley; California Institute of Technology; Goethe University Frankfurt
摘要：Conditional Sums-of-AM/GM-Exponentials (conditional SAGE) is a decomposition method to prove nonnegativity of a signomial or polynomial over some subset X of real space. In this article, we undertake the first structural analysis of conditional SAGE signomials for convex sets X. We introduce the X-circuits of a finite subset A subset of R-n, which generalize the simplicial circuits of the affine-linear matroid induced by A to a constrained setting. The X-circuits serve as the main tool in our ...
-
作者：Boob, Digvijay; Deng, Qi; Lan, Guanghui
作者单位：University System of Georgia; Georgia Institute of Technology; Shanghai University of Finance & Economics
摘要：Functional constrained optimization is becoming more and more important in machine learning and operations research. Such problems have potential applications in risk-averse machine learning, semisupervised learning and robust optimization among others. In this paper, we first present a novel Constraint Extrapolation (ConEx) method for solving convex functional constrained problems, which utilizes linear approximations of the constraint functions to define the extrapolation (or acceleration) s...
