For a least-squares fit with 10^7 rows and 10^5 features, do you solve in closed form or iterate?

principalnice to knowfreq 40%

answer

the deciding dimension is the feature count
one route squares that dimension
count memory before counting operations
cost per step versus cost per solve
squared error is the only closed-form case

basics

~20 s

Iterate. The closed-form route needs a 100,000 by 100,000 cross-product matrix — around 80 GB dense — costing on the order of 10^17 operations to form and 10^15 to factorise, while gradient steps cost one pass over the data each and store only the parameter vector.

solid answer

~50 s

At this size the decision is made by cost, not by preference. The closed-form solve requires forming a p by p cross-product matrix, which is O(n * p^2) work — about 10^17 operations here — plus O(p^3) to factorise, and 10^10 entries of storage, roughly 80 GB in double precision. That is infeasible on any single machine. A gradient step costs O(n * p) for a full pass, or O(b * p) per mini-batch, and needs only O(p) memory for the parameters, with sparse features cutting that further to the number of non-zeros. So you iterate. The trade you accept is a step size and a stopping rule to tune, and an iteration count driven by conditioning. The direct solve wins when p is small — tens to low thousands — and the data fits: it is exact, deterministic, and has no hyperparameters. And for most objectives other than squared error there is no closed form at all.

At this size the decision is made by cost, not by preference. The closed-form solve requires forming a `p` by `p` cross-product matrix, which is `O(n * p^2)` work — about 10^17 operations here — plus `O(p^3)` to factorise, and 10^10 entries of storage, roughly 80 GB in double precision. That is infeasible on any single machine. A gradient step costs `O(n * p)` for a full pass, or `O(b * p)` per mini-batch, and needs only `O(p)` memory for the parameters, with sparse features cutting that further to the number of non-zeros. So you iterate. The trade you accept is a step size and a stopping rule to tune, and an iteration count driven by conditioning. The direct solve wins when p is small — tens to low thousands — and the data fits: it is exact, deterministic, and has no hyperparameters. And for most objectives other than squared error there is no closed form at all.

go deeper

for a junior

Recall that a direct algebraic solve exists for squared-error fitting but becomes impossible when the number of features is very large, at which point you iterate instead.

for a middle

Compare the cost profiles explicitly: forming and factorising scale with the feature count squared and cubed, while a gradient pass scales with rows times features and stores only the parameters.

for a senior

Pick the route from real constraints — memory, sparsity, whether data streams, how often the fit reruns — and be able to defend where you put the crossover for your own workloads.

for a principal

Own the trade as a total cost decision: compute saved against tuning, monitoring and reproducibility given up, and set the accuracy target from statistical uncertainty rather than from solver precision.

Frame it as a cost model, not a preference

Both routes minimise the same sum of squared residuals, and for a full-rank problem they target the same answer. What differs is the resource profile, so the correct interview answer walks through the arithmetic rather than asserting a rule.

Direct route. Solving in closed form means forming the p by p cross-product of the design matrix and then factorising it. The first stage costs on the order of n * p^2 arithmetic operations; the second on the order of p^3. Storage for the dense matrix is p^2 numbers.

Iterative route. One full-batch gradient of the squared-error loss costs on the order of n * p — a single pass over the data, or on the order of the number of non-zeros if the features are sparse. A mini-batch step costs b * p. Persistent memory is O(p) for the parameter vector plus whatever slice of data is in flight.

Plugging in the numbers

With n = 10^7 and p = 10^5:

Forming the cross-product: n * p^2 = 10^7 * 10^10 = 10^17 operations. Even at 10^11 useful operations per second that is on the order of ten days of pure arithmetic.
Factorising: p^3 = 10^15 operations.
Storing it: 10^10 entries at 8 bytes each is 8 * 10^10 bytes, about 80 GB, before any working copies.
One gradient pass: n * p = 10^12 operations, a thousand times cheaper than a single cross-product formation, and you may only need a few hundred passes — or far fewer, if you use mini-batches and stop early.

The conclusion is not close: iterate. And notice the deciding factor is p, not n. A hundred million rows with fifty features is a comfortable direct solve; ten thousand rows with a hundred thousand features is not.

When the direct solve is the right call

It is genuinely the better engineering choice, and answering with a blanket always iterate is a weaker answer than answering with the boundary:

p is small and the data fits. Tens to a few thousand features. The solve is one deterministic call with no step size, no stopping rule, no learning-rate sweep and no run-to-run variation. That operational simplicity is worth real money.
You want an exact, reproducible answer. Two runs give bit-comparable results. An iterative fit gives whatever the stopping rule allowed that day.
The fit is done once, not in a training loop that must scale later.

And when the direct route is preferable it is preferable decisively — nobody should run a thousand gradient steps to fit five coefficients.

When iterating is the only option

Huge p, as here, where the p^2 term dominates everything.
Data that does not fit in memory or arrives as a stream, since the iterative route touches examples in slices and never needs to materialise anything of size p^2.
Objectives with no closed form at all. Squared error is the exception, not the rule; most other loss functions have no algebraic minimiser, so the iterative machinery has to exist anyway. Choosing it for the least-squares case keeps one code path instead of two.

The judgment layer

Three points elevate this from a complexity recitation to a lead-level answer.

Accuracy you do not need. A direct solve gives the exact minimiser of the empirical loss to machine precision. But the coefficients are estimated from finite data and carry statistical uncertainty of their own. Optimising far below that uncertainty buys nothing you can act on. Recognising that the required optimisation accuracy is set by the statistical noise, not by the solver, is what licenses early stopping without guilt.

Where the cost really lands. The iterative route trades compute for tuning and monitoring: a step size to choose, a stopping rule to justify, an iteration count that depends on the conditioning of the problem, and a run that can silently under-converge. Those costs are borne by people, not by the cluster, and they recur on every retrain. Budget them explicitly rather than pretending the iterative route is free.

Conditioning is the hidden multiplier. The number of iterations is driven by how elongated the loss surface is. Investing in feature scaling and sensible parametrisation up front can cut iteration counts by an order of magnitude, which is usually a far better return than a faster machine.

The one-line answer

Iterate, because the p^2 memory and the n * p^2 formation cost are both out of reach at a hundred thousand features, while gradient steps scale as n * p with O(p) memory — and be ready to say precisely where the boundary sits, because for small p the closed form is the better engineering decision.

## Frame it as a cost model, not a preference Both routes minimise the same sum of squared residuals, and for a full-rank problem they target the same answer. What differs is the resource profile, so the correct interview answer walks through the arithmetic rather than asserting a rule. **Direct route.** Solving in closed form means forming the `p` by `p` cross-product of the design matrix and then factorising it. The first stage costs on the order of `n * p^2` arithmetic operations; the second on the order of `p^3`. Storage for the dense matrix is `p^2` numbers. **Iterative route.** One full-batch gradient of the squared-error loss costs on the order of `n * p` — a single pass over the data, or on the order of the number of non-zeros if the features are sparse. A mini-batch step costs `b * p`. Persistent memory is `O(p)` for the parameter vector plus whatever slice of data is in flight. ## Plugging in the numbers With `n = 10^7` and `p = 10^5`: - Forming the cross-product: `n * p^2 = 10^7 * 10^10 = 10^17` operations. Even at 10^11 useful operations per second that is on the order of ten days of pure arithmetic. - Factorising: `p^3 = 10^15` operations. - Storing it: `10^10` entries at 8 bytes each is `8 * 10^10` bytes, about **80 GB**, before any working copies. - One gradient pass: `n * p = 10^12` operations, a thousand times cheaper than a single cross-product formation, and you may only need a few hundred passes — or far fewer, if you use mini-batches and stop early. The conclusion is not close: iterate. And notice the deciding factor is `p`, not `n`. A hundred million rows with fifty features is a comfortable direct solve; ten thousand rows with a hundred thousand features is not. ## When the direct solve is the right call It is genuinely the better engineering choice, and answering with a blanket always iterate is a weaker answer than answering with the boundary: - **p is small and the data fits.** Tens to a few thousand features. The solve is one deterministic call with no step size, no stopping rule, no learning-rate sweep and no run-to-run variation. That operational simplicity is worth real money. - **You want an exact, reproducible answer.** Two runs give bit-comparable results. An iterative fit gives whatever the stopping rule allowed that day. - **The fit is done once**, not in a training loop that must scale later. And when the direct route is preferable it is preferable decisively — nobody should run a thousand gradient steps to fit five coefficients. ## When iterating is the only option - **Huge p**, as here, where the `p^2` term dominates everything. - **Data that does not fit in memory or arrives as a stream**, since the iterative route touches examples in slices and never needs to materialise anything of size `p^2`. - **Objectives with no closed form at all.** Squared error is the exception, not the rule; most other loss functions have no algebraic minimiser, so the iterative machinery has to exist anyway. Choosing it for the least-squares case keeps one code path instead of two. ## The judgment layer Three points elevate this from a complexity recitation to a lead-level answer. **Accuracy you do not need.** A direct solve gives the exact minimiser of the *empirical* loss to machine precision. But the coefficients are estimated from finite data and carry statistical uncertainty of their own. Optimising far below that uncertainty buys nothing you can act on. Recognising that the required optimisation accuracy is set by the statistical noise, not by the solver, is what licenses early stopping without guilt. **Where the cost really lands.** The iterative route trades compute for tuning and monitoring: a step size to choose, a stopping rule to justify, an iteration count that depends on the conditioning of the problem, and a run that can silently under-converge. Those costs are borne by people, not by the cluster, and they recur on every retrain. Budget them explicitly rather than pretending the iterative route is free. **Conditioning is the hidden multiplier.** The number of iterations is driven by how elongated the loss surface is. Investing in feature scaling and sensible parametrisation up front can cut iteration counts by an order of magnitude, which is usually a far better return than a faster machine. ## The one-line answer Iterate, because the `p^2` memory and the `n * p^2` formation cost are both out of reach at a hundred thousand features, while gradient steps scale as `n * p` with `O(p)` memory — and be ready to say precisely where the boundary sits, because for small p the closed form is the better engineering decision.

At roughly what feature count does the closed-form route stop being attractive?
There is no sharp line, but the p-squared storage is the first wall: a few thousand features is a matrix of tens of millions of entries, still trivial; a hundred thousand is 10^10 entries and tens of gigabytes, clearly not. In practice teams solve directly into the low thousands of features and iterate above that, with the exact crossover set by memory, sparsity and how often the fit is rerun.
How do you justify stopping the iteration early rather than driving the gradient to zero?
Coefficients estimated from finite data carry sampling uncertainty, so optimising far below that uncertainty changes no decision anyone will make. Set the tolerance by what the downstream use needs — prediction error stability, or a change in coefficients small relative to their standard errors — and stop there. Report which criterion fired, so a timeout is never mistaken for convergence.
Does sparsity in the features change the recommendation?
It strengthens it. A gradient pass costs on the order of the number of non-zero entries, which for sparse data can be orders of magnitude below n times p. The cross-product, by contrast, tends to fill in: products of sparse columns produce a far denser matrix, so the direct route loses the sparsity advantage exactly where it needs it most.

saying these in an interview costs you the question

Says the closed form is always preferable because it is exact
Ignores the p-squared memory cost and quotes only operation counts
Thinks the row count is what makes the direct solve infeasible
Assumes every loss function has a closed-form minimiser
Treats the iterative route as free, with no tuning or monitoring cost

For a least-squares fit with 10^7 rows and 10^5 features, do you solve in closed form or iterate?

§ answer

basics

solid answer

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Frame it as a cost model, not a preference

Plugging in the numbers

When the direct solve is the right call

When iterating is the only option

The judgment layer

The one-line answer

▾common follow-ups3 questions

▾red flags5 flags

§ context

▾related questions8 questions

▾related topics4 topics

Frame it as a cost model, not a preference

Plugging in the numbers

When the direct solve is the right call

When iterating is the only option

The judgment layer

The one-line answer

answer

go deeper

context