Fast and Near-Optimal Diagonal Preconditioning
  The convergence rates of iterative methods for solving a linear system
$\mathbf{A} x = b$ typically depend on the condition number of the matrix
$\mathbf{A}$. Preconditioning is a common way of speeding up these methods by
reducing that condition number in a computationally inexpensive way. In this
paper, we revisit the decades-old problem of how to best improve $\mathbf{A}$'s
condition number by left or right diagonal rescaling. We make progress on this
problem in several directions.
  First, we provide new bounds for the classic heuristic of scaling
$\mathbf{A}$ by its diagonal values (a.k.a. Jacobi preconditioning). We prove
that this approach reduces $\mathbf{A}$'s condition number to within a
quadratic factor of the best possible scaling. Second, we give a solver for
structured mixed packing and covering semidefinite programs (MPC SDPs) which
computes a constant-factor optimal scaling for $\mathbf{A}$ in
$\widetilde{O}(\text{nnz}(\mathbf{A}) \cdot \text{poly}(\kappa^\star))$ time;
this matches the cost of solving the linear system after scaling up to a
$\widetilde{O}(\text{poly}(\kappa^\star))$ factor. Third, we demonstrate that a
sufficiently general width-independent MPC SDP solver would imply near-optimal
runtimes for the scaling problems we consider, and natural variants concerned
with measures of average conditioning.
  Finally, we highlight connections of our preconditioning techniques to
semi-random noise models, as well as applications in reducing risk in several
statistical regression models.
