Efficiency of First-Order Methods for Low-Rank Tensor Recovery with the
  Tensor Nuclear Norm Under Strict Complementarity
Dan Garber Atara Kaplan
We consider convex relaxations for recovering low-rank tensors based on
constrained minimization over a ball induced by the tensor nuclear norm,
recently introduced in \cite{tensor_tSVD}. We build on a recent line of results
that considered convex relaxations for the recovery of low-rank matrices and
established that under a strict complementarity condition (SC), both the
convergence rate and per-iteration runtime of standard gradient methods may
improve dramatically. We develop the appropriate strict complementarity
condition for the tensor nuclear norm ball and obtain the following main
results under this condition: 1. When the objective to minimize is of the form
$f(\mX)=g(\mA\mX)+\langle{\mC,\mX}\rangle$ , where $g$ is strongly convex and
$\mA$ is a linear map (e.g., least squares), a quadratic growth bound holds,
which implies linear convergence rates for standard projected gradient methods,
despite the fact that $f$ need not be strongly convex. 2. For a smooth
objective function, when initialized in certain proximity of an optimal
solution which satisfies SC, standard projected gradient methods only require
SVD computations (for projecting onto the tensor nuclear norm ball) of rank
that matches the tubal rank of the optimal solution. In particular, when the
tubal rank is constant, this implies nearly linear (in the size of the tensor)
runtime per iteration, as opposed to super linear without further assumptions.
3. For a nonsmooth objective function which admits a popular smooth
saddle-point formulation, we derive similar results to the latter for the well
known extragradient method. An additional contribution which may be of
independent interest, is the rigorous extension of many basic results regarding
tensors of arbitrary order, which were previously obtained only for third-order
tensors.