  We provide several algorithms for constrained optimization of a large class
of convex problems, including softmax, $\ell_p$ regression, and logistic
regression. Central to our approach is the notion of width reduction, a
technique which has proven immensely useful in the context of maximum flow
[Christiano et al., STOC'11] and, more recently, $\ell_p$ regression [Adil et
al., SODA'19], in terms of improving the iteration complexity from $O(m^{1/2})$
to $\tilde{O}(m^{1/3})$, where $m$ is the number of rows of the design matrix,
and where each iteration amounts to a linear system solve. However, a
considerable drawback is that these methods require both problem-specific
potentials and individually tailored analyses.
  As our main contribution, we initiate a new direction of study by presenting
the first unified approach to achieving $m^{1/3}$-type rates. Notably, our
method goes beyond these previously considered problems to more broadly capture
quasi-self-concordant losses, a class which has recently generated much
interest and includes the well-studied problem of logistic regression, among
others. In order to do so, we develop a unified width reduction method for
carefully handling these losses based on a more general set of potentials.
Additionally, we directly achieve $m^{1/3}$-type rates in the constrained
setting without the need for any explicit acceleration schemes, thus naturally
complementing recent work based on a ball-oracle approach [Carmon et al.,
NeurIPS'20].
