Agree about the downside of fragmented discussion, I left some time for MO discussion before posting the bounty but I don’t know how much it helped.
I agree that some approach like that seems like it could work for O(nω). I’m not familiar with those techniques and so don’t know a technique that needs O(logϵ) iterations rather than O(√m) or O(ϵ−1). For Newton iteration it seems like you need some kind of bound on the condition number.
But I haven’t thought about it much, since it seems like something fundamentally different is needed to break O(nω). I believe that one of those might just work out of the box.
Agree about the downside of fragmented discussion, I left some time for MO discussion before posting the bounty but I don’t know how much it helped.
I agree that some approach like that seems like it could work for O(nω). I’m not familiar with those techniques and so don’t know a technique that needs O(logϵ) iterations rather than O(√m) or O(ϵ−1). For Newton iteration it seems like you need some kind of bound on the condition number.
But I haven’t thought about it much, since it seems like something fundamentally different is needed to break O(nω). I believe that one of those might just work out of the box.