Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Diagonal Preconditioning: Theory and Algorithms   Diagonal preconditioning has been a staple technique in optimization and
machine learning. It often reduces the condition number of the design or
Hessian matrix it is applied to, thereby speeding up convergence. However,
rigorous analyses of how well various diagonal preconditioning procedures
improve the condition number of the preconditioned matrix and how that
translates into improvements in optimization are rare. In this paper, we first
provide an analysis of a popular diagonal preconditioning technique based on
column standard deviation and its effect on the condition number using random
matrix theory. Then we identify a class of design matrices whose condition
numbers can be reduced significantly by this procedure. We then study the
problem of optimal diagonal preconditioning to improve the condition number of
any full-rank matrix and provide a bisection algorithm and a potential
reduction algorithm with $O(\log(\frac{1}{\epsilon}))$ iteration complexity,
where each iteration consists of an SDP feasibility problem and a Newton update
using the Nesterov-Todd direction, respectively. Finally, we extend the optimal
diagonal preconditioning algorithm to an adaptive setting and compare its
empirical performance at reducing the condition number and speeding up
convergence for regression and classification problems with that of another
adaptive preconditioning technique, namely batch normalization, that is
essential in training machine learning models.

26
The categories of this paper are: bayes-an
11
The categories of this paper are: hep-lat
21
The categories of this paper are: adap-org
22
The categories of this paper are: chao-dyn
6
The categories of this paper are: astro-ph
37
The categories of this paper are: supr-con
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
31
The categories of this paper are: ao-sci
9
The categories of this paper are: nlin
17
The categories of this paper are: q-fin
4
The categories of this paper are: cond-mat
14
The categories of this paper are: math-ph
25
The categories of this paper are: patt-sol
29
The categories of this paper are: funct-an
34
The categories of this paper are: chem-ph