Sure, or Nesterov's accelerated gradient descent or something. I'm just not sure what the authors mean by "cheap iterations".

Update: your other comment clarified this for me. It's cheap relative to other methods that work with non-self-concordant objectives.