Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Finding Low-Rank Solutions via Non-Convex Matrix Factorization,
  Efficiently and Provably   A rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ can be written as a product
$U V^\top$, where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n
\times r}$. One could exploit this observation in optimization: e.g., consider
the minimization of a convex function $f(X)$ over rank-$r$ matrices, where the
set of rank-$r$ matrices is modeled via the factorization $UV^\top$. Though
such parameterization reduces the number of variables, and is more
computationally efficient (of particular interest is the case $r \ll \min\{m,
n\}$), it comes at a cost: $f(UV^\top)$ becomes a non-convex function w.r.t.
$U$ and $V$.
  We study such parameterization for optimization of generic convex objectives
$f$, and focus on first-order, gradient descent algorithmic solutions. We
propose the Bi-Factored Gradient Descent (BFGD) algorithm, an efficient
first-order method that operates on the $U, V$ factors. We show that when $f$
is (restricted) smooth, BFGD has local sublinear convergence, and linear
convergence when $f$ is both (restricted) smooth and (restricted) strongly
convex. For several key applications, we provide simple and efficient
initialization schemes that provide approximate solutions good enough for the
above convergence results to hold.

36
The categories of this paper are: cmp-lg
37
The categories of this paper are: supr-con
18
The categories of this paper are: econ
32
The categories of this paper are: atom-ph
8
The categories of this paper are: hep-ex
14
The categories of this paper are: math-ph
7
The categories of this paper are: hep-th
9
The categories of this paper are: nlin
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
0
The categories of this paper are: hep-ph
13
The categories of this paper are: quant-ph
20
The categories of this paper are: acc-phys
28
The categories of this paper are: alg-geom
6
The categories of this paper are: astro-ph
23
The categories of this paper are: solv-int