Parallel Coordinate Descent Newton Method for Efficient L₁ -Regularized Loss Minimization.

Area of Science:

• Optimization Algorithms
• Machine Learning
• Parallel Computing

Background:

• Advances in parallel algorithms for large-scale optimization exist.
• Existing feature-parallel algorithms face divergence issues or require data preprocessing.
• Need for robust parallel optimization methods that avoid preprocessing.

Purpose of the Study:

• To propose a novel Parallel Coordinate Descent algorithm using approximate Newton steps (PCDN).
• To ensure global convergence without data preprocessing, even with high parallelism.
• To improve efficiency and performance over existing state-of-the-art methods.

Main Methods:

• Developed a Parallel Coordinate Descent algorithm using approximate Newton steps (PCDN).
• Introduced a high-dimensional line search as a key component for global convergence.
• Randomly partitioned feature sets into subsets for parallel processing and sequential bundle updates.

Main Results:

• PCDN guarantees global convergence irrespective of increasing parallelism.
• PCDN converges to a specified accuracy within a limited iteration count, decreasing with parallelism.
• Minimized data transfer and synchronization costs through maintaining intermediate quantities.
• Experimental results on L1-regularized logistic regression and L1-regularized L2-loss SVM show superior performance.

Conclusions:

• The PCDN algorithm effectively exploits parallelism for large-scale optimization.
• PCDN offers a robust and efficient alternative to existing parallel optimization methods.
• The proposed method demonstrates significant improvements over state-of-the-art techniques.