-
作者：Yang, Zhuoran; Yang, Lin F.; Fang, Ethan X.; Zhao, Tuo; Wang, Zhaoran; Neykov, Matey
作者单位：Princeton University; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; Pennsylvania Commonwealth System of Higher Education (PCSHE); Pennsylvania State University; Pennsylvania State University - University Park; University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology; Northwestern University; Carnegie Mellon University
摘要：Existing nonconvex statistical optimization theory and methods crucially rely on the correct specification of the underlying true statistical models. To address this issue, we take a first step towards taming model misspecification by studying the high-dimensional sparse phase retrieval problem with misspecified link functions. In particular, we propose a simple variant of the thresholded Wirtinger flow algorithm that, given a proper initialization, linearly converges to an estimator with opti...
-
作者：Adams, Warren; Gupte, Akshay; Xu, Yibo
作者单位：Clemson University
摘要：Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of . This implies additive error bounds for relaxing a polynomial optimization problem by convexifying each monomial separately. Our main error bounds dep...
-
作者：Roosta-Khorasani, Farbod; Mahoney, Michael W.
作者单位：University of Queensland; University of California System; University of California Berkeley; University of California System; University of California Berkeley
摘要：For large-scale finite-sum minimization problems, we study non-asymptotic and high-probability global as well as local convergence properties of variants of Newton's method where the Hessian and/or gradients are randomly sub-sampled. For Hessian sub-sampling, using random matrix concentration inequalities, one can sub-sample in a way that second-order information, i.e., curvature, is suitably preserved. For gradient sub-sampling, approximate matrix multiplication results from randomized numeri...
-
作者：Necoara, I.; Nesterov, Yu.; Glineur, F.
作者单位：National University of Science & Technology POLITEHNICA Bucharest; Universite Catholique Louvain
摘要：The standard assumption for proving linear convergence of first order methods for smooth convex optimization is the strong convexity of the objective function, an assumption which does not hold for many practical applications. In this paper, we derive linear convergence rates of several first order methods for solving smooth non-strongly convex constrained optimization problems, i.e. involving an objective function with a Lipschitz continuous gradient that satisfies some relaxed strong convexi...
-
作者：Kouri, Drew P.
作者单位：United States Department of Energy (DOE); Sandia National Laboratories
摘要：We develop a general risk quadrangle that gives rise to a large class of spectral risk measures. The statistic of this new risk quadrangle is the average value-at-risk at a specific confidence level. As such, this risk quadrangle generates a continuum of error measures that can be used for superquantile regression. For risk-averse optimization, we introduce an optimal approximation of spectral risk measures using quadrature. We prove the consistency of this approximation and demonstrate our re...
-
作者：Lamm, Michael; Lu, Shu
作者单位：SAS Institute Inc; University of North Carolina; University of North Carolina Chapel Hill
摘要：Stochastic variational inequalities (SVI) provide a unified framework for the study of a general class of nonlinear optimization and Nash-type equilibrium problems with uncertain model data. Often the true solution to an SVI cannot be found directly and must be approximated. This paper considers the use of a sample average approximation (SAA), and proposes a new method to compute confidence intervals for individual components of the true SVI solution based on the asymptotic distribution of SAA...
-
作者：Nouiehed, Maher; Pang, Jong-Shi; Razaviyayn, Meisam
作者单位：University of Southern California
-
作者：Aouad, Ali; Segev, Danny
作者单位：University of London; London Business School; University of Haifa
摘要：In the last two decades, a steady stream of research has been devoted to studying various computational aspects of the ordered k-median problem, which subsumes traditional facility location problems (such as median, center, p-centrum, etc.) through a unified modeling approach. Given a finite metric space, the objective is to locate k facilities in order to minimize the ordered median cost function. In its general form, this function penalizes the coverage distance of each vertex by a multiplic...
-
作者：Curtis, Frank E.; Robinson, Daniel P.
作者单位：Lehigh University; Johns Hopkins University
摘要：This paper addresses the question of whether it can be beneficial for an optimization algorithm to follow directions of negative curvature. Although prior work has established convergence results for algorithms that integrate both descent and negative curvature steps, there has not yet been extensive numerical evidence showing that such methods offer consistent performance improvements. In this paper, we present new frameworks for combining descent and negative curvature directions: alternatin...
-
作者：Eisenach, Carson; Liu, Han
作者单位：Princeton University; Northwestern University
摘要：Motivated by the task of clustering either d variables or d points into K groups, we investigate efficient algorithms to solve the Peng-Wei (P-W) K-means semi-definite programming (SDP) relaxation. The P-W SDP has been shown in the literature to have good statistical properties in a variety of settings, but remains intractable to solve in practice. To this end we propose FORCE, a new algorithm to solve this SDP relaxation. Compared to off-the-shelf interior point solvers, our method reduces th...
