  In this paper we study proximal conditional-gradient (CG) and proximal
gradient-projection type algorithms for a block-structured constrained
nonconvex optimization model, which arises naturally from tensor data analysis.
First, we introduce a new notion of $\epsilon$-stationarity, which is suitable
for the structured problem under consideration. %, compared with other similar
solution concepts. We then propose two types of first-order algorithms for the
model based on the proximal conditional-gradient (CG) method and the proximal
gradient-projection method respectively. If the nonconvex objective function is
in the form of mathematical expectation, we then discuss how to incorporate
randomized sampling to avoid computing the expectations exactly. For the
general block optimization model, the proximal subroutines are performed for
each block according to either the block-coordinate-descent (BCD) or the
maximum-block-improvement (MBI) updating rule. If the gradient of the nonconvex
part of the objective $f$ satisfies $\| \nabla f(x) - \nabla f(y)\|_q \le M
\|x-y\|_p^\delta$ where $\delta=p/q$ with $1/p+1/q=1$, then we prove that the
new algorithms have an overall iteration complexity bound of $O(1/\epsilon^q)$
in finding an $\epsilon$-stationary solution. If $f$ is concave then the
iteration complexity reduces to $O(1/\epsilon)$. Our numerical experiments for
tensor approximation problems show promising performances of the new solution
algorithms.
