We consider semidefinite programs (SDPs) with equality constraints. The variable to be optimized is a positive semidefinite matrix X of size n. Following the Burer‐Monteiro approach, we optimize a factor Y of size n × p instead, such that X = YYT. This ensures positive semidefiniteness at no cost and can reduce the dimension of the problem if p is small, but results in a nonconvex optimization problem with a quadratic cost function and quadratic equality constraints in Y. In this paper, we show that if the set of constraints on Y regularly defines a smooth manifold, then, despite nonconvexity, first‐ and second‐order necessary optimality conditions are also sufficient, provided p is large enough. For smaller values of p, we show a similar result holds for almost all (linear) cost functions. Under those conditions, a global optimum Y maps to a global optimum X = YYT of the SDP. We deduce old and new consequences for SDP relaxations of the generalized eigenvector problem, the trust‐region subproblem, and quadratic optimization over several spheres, as well as for the Max‐Cut and Orthogonal‐Cut SDPs, which are common relaxations in stochastic block modeling and synchronization of rotations. © 2018 Wiley Periodicals, Inc.
Smoothed analysis of the lowrank approach for smooth semidefinite programs
We consider semidefinite programs (SDPs) of size n with equality constraints. In
order to overcome scalability issues, Burer and Monteiro proposed a factorized
approach based on optimizing over a matrix Y of size nk such that X = Y Y is
the SDP variable. The advantages of such formulation are twofold: the dimension
of the optimization variable is reduced, and positive semidefiniteness is naturally
enforced. However, optimization in Y is nonconvex. In prior work, it has been
shown that, when the constraints on the factorized variable regularly define a
smooth manifold, provided k is large enough, for almost all cost matrices, all
secondorder stationary points (SOSPs) are optimal. Importantly, in practice,
one can only compute points which approximately satisfy necessary optimality
conditions, leading to the question: are such points also approximately optimal?
To answer it, under similar assumptions, we use smoothed analysis to show that
approximate SOSPs for a randomly perturbed objective function are approximate
global optima, with k scaling like the square root of the number of constraints (up
to log factors). Moreover, we bound the optimality gap at the approximate solution
of the perturbed problem with respect to the original problem. We particularize our
results to an SDP relaxation of phase retrieval.
 Award ID(s):
 1719558
 Publication Date:
 NSFPAR ID:
 10098799
 Journal Name:
 Neural Information Processing Systems (NIPS)
 Sponsoring Org:
 National Science Foundation
More Like this


Abstract
Site description. This data package consists of data obtained from sampling surface soil (the 07.6 cm depth profile) in black mangrove (Avicennia germinans) dominated forest and black needlerush (Juncus roemerianus) saltmarsh along the Gulf of Mexico coastline in peninsular westcentral Florida, USA. This location has a subtropical climate with mean daily temperatures ranging from 15.4 °C in January to 27.8 °C in August, and annual precipitation of 1336 mm. Precipitation falls as rain primarily between June and September. Tides are semidiurnal, with 0.57 m median amplitudes during the year preceding sampling (U.S. NOAA National Ocean Service, Clearwater Beach, Florida, station 8726724). Sealevel rise is 4.0 ± 0.6 mm per year (19732020 trend, mean ± 95 % confidence interval, NOAA NOS Clearwater Beach station). The A. germinans mangrove zone is either adjacent to water or fringed on the seaward side by a narrow band of red mangrove (Rhizophora mangle). A nearmonoculture of J. roemerianus is often adjacent to and immediately landward of the A. germinans zone. The transition from the mangrove to the J. roemerianus zone is variable in our study area. An abrupt edge between closedcanopy mangrove and J. roemerianus monoculture may extend for up to several hundred meters 
Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of lowrank solutions and low complexity algorithms, we consider the Burer–Monteiro factorization approach for solving SDPs. For a large class of SDPs, upon random perturbation of the cost matrix, with high probability, we show that all approximate secondorder stationary points are approximate global optima for the penalty formulation of appropriately rankconstrained SDPs, as long as the number of constraints scales subquadratically with the desired rank. Our result is based on a simple penalty function formulation of the rankconstrained SDP along with a smoothed analysis to avoid worstcase cost matrices. We particularize our results to two applications, namely, MaxCut and matrix completion.

In the unitcost comparison model, a black box takes an input two items and outputs the result of the comparison. Problems like sorting and searching have been studied in this model, and it has been general ized to include the concept of priced information, where different pairs of items (say database records) have different comparison costs. These comparison costs can be arbitrary (in which case no algorithm can be close to optimal (Charikar et al. STOC 2000)), structured (for exam ple, the comparison cost may depend on the length of the databases (Gupta et al. FOCS 2001)), or stochastic (Angelov et al. LATIN 2008). Motivated by the database setting where the cost depends on the sizes of the items, we consider the problems of sorting and batched predecessor where two nonuniform sets of items A and B are given as input. (1) In the RAM setting, we consider the scenario where both sets have n keys each. The cost to compare two items in A is a, to compare an item of A to an item of B is b, and to compare two items in B is c. We give upper and lower bounds for the case a ≤more »

We study the classic set cover problem from the perspective of sublinear algorithms. Given access to a collection of m sets over n elements in the query model, we show that sublinear algorithms derived from existing techniques have almost tight query complexities. On one hand, first we show an adaptation of the streaming algorithm presented in [17] to the sublinear query model, that returns an αapproximate cover using Õ(m(n/k)^1/(α–1) + nk) queries to the input, where k denotes the value of a minimum set cover. We then complement this upper bound by proving that for lower values of k, the required number of queries is , even for estimating the optimal cover size. Moreover, we prove that even checking whether a given collection of sets covers all the elements would require Ω(nk) queries. These two lower bounds provide strong evidence that the upper bound is almost tight for certain values of the parameter k. On the other hand, we show that this bound is not optimal for larger values of the parameter k, as there exists a (1 + ε)approximation algorithm with Õ(mn/kε^2) queries. We show that this bound is essentially tight for sufficiently small constant ε, by establishing amore »