Abstract
In recent years, stochastic gradient descent (SGD) methods and randomized linear algebra (RLA) algorithms have been applied to many large-scale problems in machine learning and data analysis. We aim to bridge the gap between these two methods in solving constrained overdetermined linear regression problems---e.g., $\ell_2$ and $\ell_1$ regression problems. We propose a hybrid algorithm named pwSGD that uses RLA techniques for preconditioning and constructing an importance sampling distribution, and then performs an SGD-like iterative process with weighted sampling on the preconditioned system. We prove that pwSGD inherits faster convergence rates that only depend on the lower dimension of the linear system, while maintaining low computation complexity. Particularly, when solving $\ell_1$ regression with size $n$ by $d$, pwSGD returns an approximate solution with $ε$ relative error in the objective value in $\mathcal{O}(\log n \cdot \text{nnz}(A) + \text{poly}(d)/ε^2)$ time. This complexity is uniformly better than that of RLA methods in terms of both $ε$ and $d$ when the problem is unconstrained. For $\ell_2$ regression, pwSGD returns an approximate solution with $ε$ relative error in the objective value and the solution vector measured in prediction norm in $\mathcal{O}(\log n \cdot \text{nnz}(A) + \text{poly}(d) \log(1/ε) /ε)$ time. We also provide lower bounds on the coreset complexity for more general regression problems, indicating that still new ideas will be needed to extend similar RLA preconditioning ideas to weighted SGD algorithms for more general regression problems. Finally, the effectiveness of such algorithms is illustrated numerically on both synthetic and real datasets.
Introduction
In large-scale optimization, Stochastic Gradient Descent (SGD) and Randomized Linear Algebra (RLA) are two dominant paradigms. While SGD is highly scalable and simple to implement, it often requires extensive hyperparameter tuning and struggles with ill-conditioned data. Conversely, RLA offers strong theoretical guarantees through data sketching but is often limited to specific problem types and handles constraints poorly.
This paper introduces PWSGD (Preconditioned Weighted SGD), a hybrid algorithm designed to bridge this gap. By utilizing RLA to "prep" the optimization landscape, PWSGD enables SGD to converge rapidly, even on massive, poorly conditioned datasets.
Methodology: The PWSGD Framework
PWSGD targets overdetermined linear regression problems ($\|Ax - b\|_p$) where the number of observations $n$ far exceeds the number of features $d$. The algorithm operates in two distinct phases:
- The RLA Phase (Preconditioning & Sampling): The algorithm uses random projections (e.g., Sparse Cauchy Transform) to create a summary of the matrix $A$. From this, it computes a preconditioning matrix $R$ to "straighten" the optimization landscape. Simultaneously, it calculates leverage scores to perform importance sampling, ensuring influential data points are prioritized.
- The SGD Phase (Iterative Refinement): A weighted version of SGD is executed on the preconditioned system. Due to the improved conditioning and smart sampling, the iteration count becomes independent of $n$ and depends only on $d$.
Key Insights and Theoretical Results
The primary innovation of PWSGD is its $n$-independence. After RLA preconditioning, the complexity of the data is effectively capped by $d$. This means that adding redundant rows to a dataset does not significantly increase the iterations required for convergence.
For $\ell_1$ problems, PWSGD is particularly efficient. Traditional RLA methods often require solving sub-problems with slow interior-point methods; PWSGD replaces these with cheap SGD updates. As shown in the complexity analysis, PWSGD achieves a superior runtime for $\ell_1$ regression compared to standard RLA and randomized IPCM methods.
Empirical Performance
The authors evaluated PWSGD on synthetic and real-world datasets, including the Million Song Dataset and Buzz in Social Media. On the notoriously ill-conditioned Buzz dataset, vanilla SGD and other competitors struggled to converge, while PWSGD achieved significant error reduction almost immediately. The algorithm proves most dominant in the "medium precision" regime (e.g., $10^{-3}$ error), reaching target accuracy much faster than state-of-the-art solvers.
Conclusion and Future Work
While PWSGD excels at $\ell_p$ regression, the authors identify limitations for more general loss functions, such as hinge loss. They prove that for certain problems, the "total sensitivity" can grow exponentially with $d$, suggesting that current coreset approaches may not easily generalize. Future research will focus on extending RLA-style preconditioning to broader classes of convex optimization where current sampling techniques remain inefficient.
Summary updated