TL;DR
This paper introduces the "Common-directions Method," a novel optimization algorithm that bridges the gap between first-order (fast linear convergence) and second-order (fast quadratic convergence) methods. By intelligently combining multiple update directions, it achieves both optimal linear convergence and local quadratic convergence, outperforming existing methods in data access efficiency while remaining competitive in training time.
What Problem Does This Paper Address?
In the realm of optimization, particularly for large-scale machine learning problems like regularized empirical risk minimization (ERM), there's a persistent trade-off: first-order methods (like gradient descent) are computationally efficient per iteration but converge slowly, while second-order methods (like Newton's method) converge much faster quadratically but are computationally expensive per iteration. The challenge is to develop a method that can achieve the best of both worlds – fast convergence rates without prohibitive computational costs per step. Existing methods often sacrifice one for the other, leaving room for improvement.
Methods
The core innovation is the Common-directions Method. Instead of discarding previous update directions, it stores them and uses them to form an orthonormal basis. At each iteration, it solves a subproblem that seeks the best linear combination of these stored directions to minimize a second-order Taylor approximation of the objective function. This subproblem is solved by a linear system involving the Hessian projected onto the subspace spanned by the common directions.
Key aspects of the method include:
- Interpolation: It acts as an interpolation between first- and second-order methods.
- Reusing Directions: It leverages past update directions, which is crucial for efficiency.
- Subproblem Solving: A key step involves solving a smaller-scale optimization problem within the span of previous directions.
- Gram-Schmidt Orthogonalization: New directions (typically the steepest descent direction) are added to the basis using Gram-Schmidt.
- Efficient Hessian-Vector Products: For specific ERM problems, the paper shows how to compute Hessian-vector products efficiently, which is critical for the method's performance.
- Two Variants: The paper presents a basic version (Algorithm 1) and a variant with multiple inner iterations (Algorithm 4) for solving the subproblem.
Datasets
The paper evaluates its method on several standard benchmark datasets for machine learning tasks, specifically for logistic regression and L2-loss SVM. These include:
- a9a
- covtype
- news20
- url
- epsilon
- webspam
- yahoo-japan
- yahoo-korea
- rcv1
- KDD2010-b
The paper also mentions that the datasets except for yahoo-japan and yahoo-korea are publicly available.
Key Insights and Ideas
- The Power of Reusing Directions: The most significant insight is that by intelligently reusing past update directions, one can achieve convergence rates that are typically associated with more computationally expensive methods.
- Bridging the Convergence Gap: The method effectively bridges the gap between linear and quadratic convergence, offering a more balanced approach.
- Exploiting Problem Structure: For ERM problems, the paper demonstrates how to exploit the structure of the Hessian to make the subproblem computationally tractable.
- Data Access Efficiency: The method's ability to reduce data passes is a critical advantage, especially for large-scale or disk-based learning scenarios.
Key Results
- Theoretical Guarantees: The Common-directions Method is proven to achieve global linear convergence and local quadratic convergence under standard assumptions.
- Empirical Performance:
- Data Passes: The method consistently outperforms state-of-the-art first- and second-order methods in terms of the number of data passes required to reach a certain accuracy across various datasets and regularization parameters. This is a key advantage for large-scale problems.
- Training Time: While not always the fastest, the method is competitive in training time, often performing comparably to or better than other advanced methods.
- Single vs. Multiple Inner Iterations: The single inner iteration variant of the method generally performs similarly to or slightly better than the multiple inner iteration variant in terms of training time, suggesting a good balance between subproblem accuracy and overall efficiency.
Limitations and Future Work
- Memory Consumption: The paper acknowledges that storing previous directions can lead to memory consumption issues, especially for a very large number of iterations. However, they note that in practice, this is often manageable because their method converges quickly. They also suggest their method might be less memory-intensive than BFGS in some scenarios.
- Computational Cost per Iteration: While efficient in data passes, the cost per iteration can be higher than simple first-order methods due to the subproblem solving and projection operations. For very sparse data or when the number of dimensions
nis small relative to the number of data pointsl, theO(lm^2 + mn)cost per iteration might be significant. - Future Work: The authors mention studying other choices of common directions beyond gradients for distributed training. They also suggest that the theoretical convergence rate of O(√klog(1/ε)) for their Algorithm 4 could potentially be guaranteed with a practical inner stopping condition.
Summary updated