Nonconvex reformulations via low-rank factorization for stochastic convex semidefinite optimization problem have attracted arising attention due to their empirical efficiency and scalability. Compared with the original convex formulations, the nonconvex ones typically involve much fewer variables, allowing them to scale to scenarios with millions of variables. However, it opens a new challenge that under what conditions the nonconvex stochastic algorithms may find the population minimizer within the optimal statistical precision despite their empirical success in applications. In this paper, we provide an answer that the stochastic gradient descent (SGD) method can be adapted to solve the nonconvex reformulation of the original convex problem, with a global linear convergence when using a fixed step size, i.e., converging exponentially fast to the population minimizer within an optimal statistical precision in the restricted strongly convex case. If a diminishing step size is adopted, the bad effect caused by the variance of gradients on the optimization error can be eliminated but the rate is dropped to be sublinear. The core of our treatment relies on a novel second-order descent lemma, which is more general than the existing best result in the literature and improves the analysis on both online and batch algorithms. The developed theoretical results and effectiveness of the suggested SGD are also verified by a series of experiments.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

We introduce a new equivalence relation for complete alge- braic varieties with canonical singularities, generated by birational equivalence, by flat algebraic deformations (of varieties with canon- ical singularities), and by quasi-´etale morphisms, i.e., morphisms which are unramified in codimension 1. We denote the above equivalence by A.Q.E.D. : = Algebraic-Quasi-´ Etale- Deformation. A completely similar equivalence relation, denoted by C-Q.E.D., can be considered for compact complex spaces with canonical sin- gularities. By a recent theorem of Siu, dimension and Kodaira dimension are invariants for A.Q.E.D. of complex varieties. We address the interesting question whether conversely two al- gebraic varieties of the same dimension and with the same Ko- daira dimension are Q.E.D. - equivalent (A.Q.E.D., or at least C-Q.E.D.), the answer being positive for curves by well known results. Using Enriques’ (resp. Kodaira’s) classification we show first that the answer to the C-Q.E.D. question is positive for special algebraic surfaces (those with Kodaira dimension at most 1), resp. for compact complex surfaces with Kodaira dimension 0, 1 and even first Betti number. The appendix by S¨onke Rollenske shows that the hypothesis of even first Betti number is necessary: he proves that any sur- face which is C-Q.E.D.-equivalent to a Kodaira surface is itself a Kodaira surface. We show also that the answer to the A.Q.E.D. question is pos- itive for complex algebraic surfaces of Kodaira dimension ≤ 1. The answer to the Q.E.D. question is instead negative for sur- faces of general type: the other appendix, due to Fritz Grunewald, is devoted to showing that the (rigid) Kuga-Shavel type surfaces of general type obtained as quotients of the bidisk via discrete groups constructed from quaternion algebras belong to countably many distinct Q.E.D. equivalence classes.