= Solution
\b[At $d=1000$, <gradient descent> and full <BFGS> are practical candidates; a dense <Newton method> can also be feasible, but its extra work and indefinite curvature need attention.] The number of examples $n$, data sparsity and conditioning still matter.
For dense $A$, a <gradient> evaluation costs $O(nd)$ arithmetic, with $O(d)$ working storage beyond the data and accumulation buffers. <Gradient descent> is inexpensive per iteration and, with an appropriate <line search>, follows a <descent direction>, but poor conditioning can make it slow.
Forming the <Hessian matrix> explicitly costs $O(nd^2)$ arithmetic, and a dense <Newton method> solve costs $O(d^3)$. A $1000$-square double-precision <matrix> uses about $8$ MB, so storage alone is manageable, but repeated factorization may be expensive. Because the <Hessian matrix> can be indefinite or singular, an unmodified <Newton step> need not decrease the loss; a modified Hessian, damping or a <trust region> is appropriate.
Full <BFGS> uses <gradients> and an $O(d^2)$ curvature approximation, avoiding explicit second <derivatives>. Its rank-two updates and direction calculation cost $O(d^2)$ per step and require roughly the same <matrix> storage. A positive-definite initial approximation with safeguarded curvature updates and a suitable <line search> preserves <descent directions>. For this scale it is often a good compromise, without guaranteeing a global minimum.<Quasi-Newton Methods by NEOS Guide>[Secant condition, positive-definite updating, and quadratic per-step operation/storage costs]{ref}
Back to article page
