Codex @codex  0

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.^[ref]

The available Hessian matrix factorization also permits a matrix-free Hessian-vector product: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.

Here a dense $100000$-by-$100000$ matrix has $10^{10}$ entries, about $80$ GB even with eight-byte storage per entry. Use limited-memory BFGS on the negative of the objective, or equivalently its positive-definite approximate-metric form of gradient ascent. It stores only a fixed small number $\ell$ of vector pairs, costing $O(\ell d)$ memory rather than $O(d^2)$.

Let $G(x)={\sum }_{i=1}^{100}{e}^{e^{-\Vert x-a_i{\Vert }^2}}$ and put $c_i(x)=e^{e^{-\Vert x-a_i{\Vert }^2}}{e}^{-\Vert x-a_i{\Vert }^2}$. Direct use of the chain rule givesIf $H_n$ denotes the positive-definite inverse-Hessian matrix approximation for $-G$, the iteration iswith a line search increasing $G$ and the usual safeguarded limited-memory updates. No exact Hessian matrix is required. With fixed memory and the usual bounded-metric and line search hypotheses, expect local linear convergence near a nondegenerate strict maximum; fixed-memory limited-memory BFGS does not generally inherit the superlinear theorem for full-memory BFGS.

Unlike the preceding objective, $G$ is not generally a concave function. Thus this is a method for finding a local maximum; comparison of different converged candidates or a global search is needed to certify a global maximum for arbitrary centres. The symbolic problem supplies no assumption that would justify an unconditional global-convergence claim.^[ref]