Homec4science
Diffusion Nonlinear (master) Browse

R7172/NeurIPS 19/sections/introduction.tex
a9139225ce70master

Last Change
Raw File

introduction.tex
View Options

%!TEX root = ../main.tex
\vspace{-5mm}
\section{Introduction}
\label{intro}
We study the nonconvex optimization problem
%
\begin{equation}
\label{prob:01}
%\begin{cases}
\underset{x\in \mathbb{R}^d}{\min}\,\, f(x)+g(x) \subjto A(x) = 0,
%\end{cases}
\end{equation}
%
where $f:\mathbb{R}^d\rightarrow\mathbb{R}$ is a {continuously-differentiable} nonconvex function and $A:\mathbb{R}^d\rightarrow\mathbb{R}^m$ is a nonlinear operator.
%For clarity of notation, we take $b=0$ in the sequel, the extension to any $b$ is trivial.
%We assume that $g:\mathbb{R}^d\rightarrow\mathbb{R}$ is a possibly nonsmooth but proximal-friendly convex function \cite{parikh2014proximal}.
We assume that $g:\mathbb{R}^d\rightarrow\mathbb{R}$ is a proximal-friendly convex function \cite{parikh2014proximal}.
% (not necessarily smooth).
%For instance, for a convex set $\mathcal{X}\subset\RR^d$, letting $g=\delta_\mathcal{X}$ to be the indicator function on $\mathcal{X}$, ~\eqref{prob:01} is a nonconvex optimization problem with the convex constraint $x\in \mathcal{X}$.
%Our other requirement for $g$ is that computing its proximal operator is inexpensive, see Section~\ref{sec:preliminaries}.
A host of problems in computer science \cite{khot2011grothendieck, lovasz2003semidefinite, zhao1998semidefinite}, machine learning \cite{mossel2015consistency, song2007dependence}, and signal processing~\cite{singer2011angular, singer2011three} naturally fall under the template~\eqref{prob:01}, including max-cut, clustering, generalized eigenvalue decomposition, as well as the {quadratic assignment problem (QAP) \cite{zhao1998semidefinite}}.% \textbf{AE: We need to add some more specifics to this paragraph to convince people that this is an important template. What are the names of the problems you're citing? Max-cut, sparse regression, statistical learning with deep networks as prior \cite{Bora2017}, what else we can think of?}
To solve \eqref{prob:01}, this paper
%builds up on the vast literature on the classical inexact augmented Lagrangian framework and
proposes an intuitive and easy-to-implement {augmented Lagrangian} algorithm, and provides its total iteration complexity under an interpretable geometric condition. Before we elaborate on the results, let us first motivate~\eqref{prob:01} with an application to semidefinite programming (SDP):
\vspace{-3mm}
\paragraph{Vignette: Burer-Monteiro splitting.}
A powerful convex relaxation for max-cut, clustering, and many others is provided by the SDP
\begin{equation}
\label{eq:sdp}
%\begin{cases}
\underset{X\in\mathbb{S}^{d \times d}}{\min} \langle C, X \rangle \subjto B(X) = b, \,\, X \succeq 0,
%\end{cases}
\end{equation}
%
where $C\in \RR^{d\times d}$, $X$ is a positive semidefinite $d\times d$ matrix,
%$\mathbb{S}^{d \times d}$ denotes the set of real symmetric matrices,
and ${B}: \mathbb{S}^{d\times d} \to \mathbb{R}^m$ is a linear operator. If the unique-games conjecture is true, SDPs achieve the best approximation for the underlying discrete problem~\cite{raghavendra2008optimal}.
Since $d$ is often large, many first- and second-order methods for solving such SDP's are immediately ruled out, not only due to their high computational complexity, but also due to their storage requirements, which are $\mathcal{O}(d^2)$.
A contemporary challenge in optimization is therefore to solve SDPs using little space and in a scalable fashion. The recent homotopy conditional gradient method, which is based on linear minimization oracles (LMOs), can solve \eqref{eq:sdp} in a small space via sketching \cite{yurtsever2018conditional}. However, such LMO-based methods are extremely slow in obtaining accurate solutions.
%In practice, $d$ is often very large which makes interior point methods, with their poor scaling in $d$, an unattractive option for solving ~\eqref{eq:sdp}. Attempts to resolve this issue prompted extensive research in computationally- and memory-efficient SDP solvers. The first such solvers relied on the so-called Linear Minimization Oracle (LMO), reviewed in Section~\ref{sec:related work}, alongside other scalabe SDP solvers.
A different approach for solving \eqref{prob:01}, dating back to~\cite{burer2003nonlinear, burer2005local}, is the so-called Burer-Monteiro (BM) factorization $X=UU^\top$, where $U\in\mathbb{R}^{d\times r}$ and $r$ is selected according to the guidelines in~\cite{pataki1998rank, barvinok1995problems}, which are shown to be optimal~\cite{waldspurger2018rank}.
%It has been shown that these bounds on the rank, which are shown to be optimal~\cite{waldspurger2018rank}, under some assumptions removing the spurious local minima of the nonconvex factorized problem~\cite{boumal2016non}.
%so as to remove spurious local minima of the nonconvex factorized problem. Evidently, BR splitting has the advantage of lower storage and faster iterations.
This factorization leads to the nonconvex problem
\begin{equation}
\label{prob:nc}
%\begin{cases}
\underset{U\in\mathbb{R}^{d \times r}}{\min} \langle C, UU^\top \rangle \subjto B(UU^\top) = b,
%\end{cases}
\end{equation}
which can be easily written in the form of~\eqref{prob:01}.
\editf{This factorization does not introduce any extraneous local minima~\cite{burer2005local} and, moreover, ~\cite{boumal2016non} established the connection between the local minimizers of the factorized problem~\eqref{prob:nc} and the global minimizers for~\eqref{eq:sdp}. }
%\textbf{Vignette 2: Latent group lasso}
%See Section ? for several examples. \textbf{We should explain this better and give more high level examples to motivate this .}
%An example of our template in \eqref{prob:01} is semi-definite ming which provides powerful relaxations to above problems. Denote the space of $d'\times d'$ symmetric matrices by $\mathbb{S}^{d'\times d'}$ and consider
%
%\begin{equation}
% \label{sdp}
% \min_x \{h'(x): A'(x) = b', ~~x \in \mathcal{C'}~~\text{and}~~x\succeq0 \}
%\end{equation}
%
%where $h': \mathbb{S}^{d'\times d'} \to \RR$, $A'\colon\mathbb{S}^{d'\times d'}\to\RR^m$, $b'\in\RR^m$, and $C' \subseteq \mathbb{R}^{d'\times d'}$. This template clearly can be put to the form of \eqref{prob:01} by using \emph{Burer-Monteiro factorization} \cite{burer2003nonlinear, burer2005local}.
To solve \eqref{prob:nc}, the inexact Augmented Lagrangian method (iALM) is widely used~\cite{burer2003nonlinear, burer2005local, kulis2007fast}, due to its cheap per iteration cost and its empirical success. Every (outer) iteration of iALM calls a solver to solve an intermediate augmented Lagrangian subproblem to near stationarity. The user is free in the choice of this solver, which could use first-order, such as the proximal gradient descent \cite{parikh2014proximal}, or second-order information, such as the trust region method and BFGS~\cite{nocedal2006numerical}.\footnote{Strictly speaking, BFGS is in fact a quasi-Newton method that emulates second-order information.}
Unlike its convex counterpart~\cite{nedelcu2014computational,lan2016iteration,xu2017inexact}, the convergence rate and the complexity of iALM for ~\eqref{prob:nc} are not well-understood, see Section~\ref{sec:related work} for a review of the related literature. Indeed, addressing this important theoretical gap is one of the contributions of our work. \editf{To summarize;}
{
%{\textbf{Summary of contributions:} \\[2mm]
$\triangleright$ {
We derive the convergence rate of iALM for solving \eqref{prob:01} to first- or second-order optimality, and find the total iteration complexity of iALM using different solvers for the augmented Lagrangian subproblems. Our complexity bounds match the best theoretical results in optimization, see Section~\ref{sec:related work}.} \\[2mm]
$\triangleright$ Our results are future-proof in the sense that they are independent of the choice of solver called by iALM. \\[2mm]
$\triangleright$ We propose a geometric condition that simplifies the algorithmic analysis for iALM, and clarify its connection to well-known Polyak-Lojasiewicz \cite{karimi2016linear} and Mangasarian-Fromovitz \cite{bertsekas1982constrained} conditions.
%\edita{please add citations for these conditions here.}
We also verify this condition for key problems in Section~\ref{sec:experiments}.
%\edita{how about the KL condition spars'19 reviewers pointed out?}
%\textbf{Roadmap.} Section~\ref{sec:preliminaries} collects the main tools and our notation. % that we utilize.
%We present the iALM in Section~\ref{sec:AL algorithm} and obtain its convergence rate to first- and second-order stationary points in Section~\ref{sec:cvg rate}, alongside their iteration complexities.
%We provide a comprehensive review of the literature and highlight our key differences in % with the precedents in
%Section~\ref{sec:related work}.
%Section~\ref{sec:experiments} presents the numerical evidence and comparisons with the state-of-the-art techniques. % methods.
c4science · Help