Suppose I'm solving $Ax=b$ for dense $m\times d$ matrix $A$. For which $A$ is this hard to do?
More concretely, is there any work on estimating the error after $k$ steps of iterative solver, $k\le d$, for some specific solvers, based on properties of $A$? For random isotropic vector $x$ and large $d$, a useful property proved here is that
$$T^k x \approx c \operatorname{Tr}(T^k)$$
Hence this comes down to understanding how fast $\operatorname{Tr}(T^k)$ decays where $T$ is the iteration matrix of corresponding solver. Which properties of $A$ result in $\operatorname{Tr}(T^d)$ being large?
Classical approach formulates difficulty in terms of condition number $\kappa(A)$, but this comes into play after many steps, ie $k>d^2$. When $d$ is huge, we can only afford $k=O(d)$ steps. For instance, modern language model might have $d\approx$10B and be trained for 1B steps. A linear analogue of this problem is to solve $Ax=b$ where $A$ is a dense $10B\times200B$ matrix, in less time than it takes to read the matrix $A$.
For "single step gradient descent", you can show that an expression involving second/third moments of the matrix determine the difficulty of approximate inversion for gradient descent using $k=1$, but I feel like I'm reinventing the wheel here
$$\frac{\text{loss}_1}{\text{loss}_0}\approx1-\frac{\operatorname{Tr}(H^2)^2}{\operatorname{Tr}(H^3)\operatorname{Tr}H}$$
where $H=A^TA$
