A multilevel sketch-and-solve method for overdetermined least squares problems

Technical Summary: A Multilevel Sketch-and-Solve Method for Overdetermined Least Squares Problems

Problem Statement
The paper addresses the computational challenge of solving large-scale, heavily overdetermined linear least squares problems of the form $\min_x \|Ax - b\|_2$, where $A \in \mathbb{R}^{m \times n}$ and $m \gg n$. Classical solutions via QR decomposition incur a cost of $O(mn^2)$, which is prohibitive for massive $m$. The standard approach to reduce cost is the Sketch-and-Solve (SAS) paradigm, which projects the problem to a smaller size $s \times n$ using a random sketching matrix $S$. While SAS provides a good estimate with high probability, the residual error depends on the sketch size $s$ and the subspace embedding constant $\eta$. To improve accuracy, existing literature suggests averaging multiple independent SAS estimators (Simple Monte Carlo). The authors investigate whether a Multilevel Monte Carlo (MLMC) framework, which combines estimators from different levels of resolution, can further improve efficiency or accuracy for this specific problem class.

Methodology: Multilevel Sketch-and-Solve (MLSAS)
The authors propose the Multilevel Sketch-and-Solve (MLSAS) estimator, adapting the MLMC paradigm from stochastic differential equations (SDEs) to least squares.

• Levels: The method defines $L+1$ levels $\ell \in \{0, \dots, L\}$ with sketch sizes $s_\ell = 2^{(\ell+1)}n$.
• Estimator Construction: The solution $x^*$ is approximated by summing corrections across levels:
  $$x_{MLMC} = \sum_{\ell=0}^L \frac{1}{N_\ell} \sum_{i=1}^{N_\ell} \Delta x^{(\ell)}_i$$
  where $\Delta x^{(\ell)} = x^{(\ell)} - x^{(\ell-1)}$ represents the difference between a fine-level solution and a coarse-level solution.
• Antithetic Variables: A key methodological feature is the use of "antithetic variables" to reduce variance. For a level $\ell$, the sketch matrix $S_\ell$ is constructed by concatenating two independent sub-sketches, $S_a$ and $S_b$. The coarse solution $x^{(\ell-1)}$ is defined as the average of the solutions obtained from $S_a$ and $S_b$ individually. The fine solution $x^{(\ell)}$ is obtained using the combined matrix $S_\ell = \frac{1}{\sqrt{2}}[S_a; S_b]$. This coupling ensures that the difference term $\Delta x^{(\ell)}$ has a smaller norm than in the standard independent sampling case.
• Cost Optimization: The authors explore reusing samples from lower levels to compute higher-level corrections to reduce the per-sample cost $C_\ell$, noting that standard MLMC assumptions of independence between levels are relaxed in this specific implementation.

Key Contributions and Analysis

1. Variance Analysis: The paper provides a theoretical and numerical analysis of the level variance $V_\ell = \text{Var}[A\Delta x^{(\ell)}]$.
   • Without antithetic variables, the variance scales as $O(1/s_\ell)$.
   • With antithetic variables, the authors prove analytically and demonstrate numerically that the variance scales as $O(1/s_\ell^2)$. This is attributed to the cancellation of terms in the difference expression $A\Delta x^{(\ell)}$ when using the specific structure of $S_\ell$ derived from $S_a$ and $S_b$.
2. Bias Analysis: The bias of the estimator is bounded by the bias of the finest level $L$, which decreases as the sketch size $s_L$ increases.
3. Complexity and Cost Comparison: The central contribution is a rigorous cost analysis comparing MLSAS against Simple Monte Carlo (averaging $N$ independent SAS solutions).
   • In standard SDE applications, MLMC reduces complexity from $O(\epsilon^{-3})$ to $O(\epsilon^{-2})$ because the variance of the finest level remains constant while the cost increases.
   • In the least squares context, the authors show that the variance of the simple Monte Carlo estimator already decreases with the sketch size ($O(1/s)$), while the cost increases linearly with $s$. Consequently, the total cost of Simple Monte Carlo to achieve a target variance $\epsilon^2$ is $O(\epsilon^{-2})$ and is independent of the maximum level $L$.
   • The authors derive that the total cost of the MLSAS estimator, even with optimized sample reuse and antithetic variance reduction, remains strictly higher than that of the Simple Monte Carlo estimator.

Results

• Variance Reduction: Numerical experiments confirm that using antithetic variables significantly reduces the slope of the variance decay, achieving $V_\ell \propto 4^{-\ell}$ (or $O(1/s^2)$) compared to $O(1/s)$ for standard sampling.
• Cost Inefficiency: Despite the superior variance reduction per level, the computational cost of generating samples (dominated by QR factorization) does not decrease fast enough in the lower levels to offset the overhead of the multilevel structure. The total cost of MLSAS is found to be slightly higher than the cost of simply averaging independent SAS samples.
• Correlation: The authors investigated the correlation introduced by reusing samples across levels and found it to be negligible ($\rho < 10^{-2}$), justifying the neglect of covariance terms in the variance estimation for practical purposes, though this does not alter the cost conclusion.

Significance and Claims
The paper concludes that while the Multilevel Monte Carlo framework is a powerful variance reduction technique for stochastic path simulation, its direct application to overdetermined least squares problems via sketching is unattractive from a computational cost perspective.

• The primary reason is that the "coarse" levels in least squares sketching are not sufficiently cheap relative to their variance contribution to justify the multilevel overhead, unlike in SDEs where coarse steps are extremely cheap.
• The authors state that "a naive application of multilevel methods appears unattractive for least squares problems."
• The paper claims to be the first to study a Multilevel Monte Carlo approach specifically for least squares problems.
• The authors modestly suggest that the multilevel approach might still offer value in terms of parallelization potential, though this is noted as outside the scope of the current analysis.

In summary, the work provides a rigorous negative result: for the specific goal of minimizing computational cost to achieve a given accuracy in least squares problems, simple averaging of sketch-and-solve solutions outperforms the proposed multilevel strategy, despite the latter's theoretical advantages in variance reduction.