= Solution
\b[At $d=10^6$, <gradient descent> remains a plausible large-scale choice; dense <Newton method> and full-memory <BFGS> are generally impractical.] A dense $d\times d$ double-precision <matrix> alone contains $10^{12}$ entries, about $8$ TB. Dense factorization also has order $10^{18}$ arithmetic work. Full <BFGS> avoids factorization but retains quadratic storage and update work, so it does not solve that scaling problem.
<Gradient descent> uses linear working storage in $d$, though the cost of reading the data and evaluating the <gradient> is still $O(nd)$ for dense $A$. Sparsity or streaming can be important. <Limited-memory BFGS>, a distinct limited-memory variant, stores only a fixed number $m$ of recent update pairs and uses $O(md)$ storage and update work, making it a realistic alternative to full <BFGS>.<Quasi-Newton Methods by NEOS Guide>[Final paragraphs: implicit inverse-Hessian products and stored-pair limited-memory methods]{ref}
The available <Hessian matrix> factorization also permits a <matrix-free Hessian-vector product>:
$$
Hv=A^{\mathsf T}\bigl(\Delta(Av)\bigr).
$$
It costs $O(nd)$ for dense data without forming $H$. A suitable iterative, safeguarded <Newton method> can exploit this structure, so the conclusion rules out the dense implementation rather than every possible second-order algorithm.
These methods seek a local solution and require convergence checks appropriate to nonconvex <optimization>. The formula does not even ensure a finite minimizer exists: with one positive coefficient and nonzero $\mathbf a$, the positive exponential loss approaches zero along an unbounded direction without attaining it. Dimension alone cannot supply a convergence guarantee.
Back to article page
