  Semidefinite programs (SDPs) and their solvers are powerful tools with many
applications in machine learning and data science. Designing scalable SDP
solvers is challenging because by standard the positive semidefinite decision
variable is an $n \times n$ dense matrix, even though the input is often $n
\times n$ sparse matrices. However, the information in the solution may not
correspond to a full-rank dense matrix as shown by Barvinok and Pataki. Two
decades ago, Burer and Monteiro developed an SDP solver $\texttt{SDPLR}$ that
optimizes over a low-rank factorization instead of the full matrix. This
greatly decreases the storage cost and works well for many problems. The
original solver $\texttt{SDPLR}$ tracks only the primal infeasibility of the
solution, limiting the technique's flexibility to produce moderate accuracy
solutions. We use a suboptimality bound for trace-bounded SDP problems that
enables us to track the progress better and perform early termination. We then
develop $\texttt{SDPLR+}$, which starts the optimization with an extremely
low-rank factorization and dynamically updates the rank based on the primal
infeasibility and suboptimality. This further speeds up the computation and
saves the storage cost. Numerical experiments on Max Cut, Minimum Bisection,
Cut Norm, and Lov\'{a}sz Theta problems with many recent memory-efficient
scalable SDP solvers demonstrate its scalability up to problems with
million-by-million decision variables and it is often the fastest solver to a
moderate accuracy of $10^{-2}$.
