Weighted SGD for ℓ Regression with Randomized Preconditioning

Area of Science:

• Machine Learning
• Optimization
• Numerical Analysis

Background:

• Stochastic Gradient Descent (SGD) methods are widely used for large-scale machine learning and convex optimization due to their implementation simplicity.
• Randomized Linear Algebra (RLA) algorithms offer stronger performance guarantees but are limited to a narrower problem scope.
• Bridging the gap between SGD and RLA is crucial for solving complex, constrained overdetermined linear regression problems.

Purpose of the Study:

• To develop a hybrid algorithm, pwSGD, that integrates RLA techniques with SGD for constrained linear regression.
• To achieve faster convergence rates and maintain low computational complexity for L2 and L1 regression problems.
• To outperform existing SGD and RLA methods in terms of efficiency and accuracy.

Main Methods:

• Developed pwSGD, a novel algorithm utilizing RLA for preconditioning and importance sampling in an SGD-like iterative process.
• Rewrote deterministic L_p regression problems as stochastic optimization problems to connect pwSGD with existing solvers.
• Analyzed convergence rates and computational complexity for L1 and L2 regression.

Main Results:

• pwSGD demonstrates faster convergence rates dependent on the lower dimension of the linear system, outperforming other SGD algorithms.
• For L1 regression, pwSGD achieves a relative error in objective value with complexity O(log n·nnz(A)+poly(d)/ε^2).
• For L2 regression, pwSGD achieves a relative error in objective value and solution vector with complexity O(log n·nnz(A)+poly(d)log(1/ε)/ε), comparable to RLA.

Conclusions:

• pwSGD effectively bridges the gap between SGD and RLA for constrained linear regression.
• The algorithm offers superior computational efficiency and convergence rates compared to existing methods for L1 and L2 regression.
• Numerical results validate the theoretical findings, showing faster convergence of pwSGD to medium-precision solutions.