[SPARK-17748] One-pass algorithm for linear regression with L1 and elastic-net penalties

• Type: New Feature
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 2.1.0
• Component/s: ML
• Target Version/s: 2.1.0
• Assignee: Seth Hendrickson Assign to me
• Reporter: Seth Hendrickson
• Shepherd: Yanbo Liang
• Created: 30/Sep/16 19:08
• Updated: 04/Dec/16 13:42
• Resolved: 25/Oct/16 06:50

Description

Currently linear regression uses weighted least squares to solve the normal equations locally on the driver when the dimensionality is small (<4096). Weighted least squares uses a Cholesky decomposition to solve the problem with L2 regularization (which has a closed-form solution). We can support L1/elasticnet penalties by solving the equations locally using OWL-QN solver.

Also note that Cholesky does not handle singular covariance matrices, but L-BFGS and OWL-QN are capable of providing reasonable solutions. This patch can also add support for solving singular covariance matrices by also adding L-BFGS.

Issue Links

• Is contained by: SPARK-17692 Document ML/MLlib behavior changes in Spark 2.1
• is depended upon by: SPARK-17824 QR solver for WeightedLeastSquares
• is related to: SPARK-18705 Docs for one-pass solver for linear regression with L1 and elastic-net penalties
• relates to: SPARK-18341 Eliminate use of SingularMatrixException in WeightedLeastSquares logic
• links to: [Github] Pull Request #15394 (sethah)
• links to: [Github] Pull Request #15621 (yanboliang)
• links to: [Github] Pull Request #15625 (yanboliang)
• links to: [Github] Pull Request #15779 (jkbradley)