Simpler Implementation of Advanced Optimization Algorithms for Machine Learning

As machine learning models grow in size and complexity, efficient optimization algorithms become critical for training them in a reasonable amount of time. While gradient descent is the go-to algorithm for many applications, it can struggle with very large-scale problems involving millions or even billions of parameters.

Fortunately, a variety of more advanced optimization algorithms have been developed that can converge much faster than gradient descent while still being relatively simple to implement using common software libraries. In this post, we‘ll take a closer look at three of the most popular algorithms—conjugate gradient, BFGS, and L-BFGS—and walk through an example of how to apply them in Python.

The Need for Speed: When Gradient Descent Falls Short

Gradient descent is an iterative algorithm that takes steps in the direction of the negative gradient of the cost function in order to locate the minimum. It‘s intuitive, easy to implement, and guaranteed to converge to a local minimum given a sufficiently small learning rate.

However, the learning rate is a double-edged sword. If it‘s too large, gradient descent will overshoot the minimum and diverge. If it‘s too small, it will plod along at a snail‘s pace, requiring a huge number of iterations to converge. Finding the Goldilocks learning rate that‘s "just right" can be tricky and may require painstaking trial and error.

Moreover, gradient descent becomes sluggish when the cost function contours are highly eccentric, forming long narrow valleys. In this ill-conditioned scenario, gradient descent oscillates back and forth across the valley, making frustratingly slow progress to the minimum.

These challenges are exacerbated in large-scale machine learning problems with millions of parameters. The computational cost of each gradient descent step grows with the number of parameters, so training can grind to a halt. Advanced optimization algorithms promise a way out of this quagmire.

A Family of Faster Algorithms

The algorithms we‘ll highlight here belong to a class of optimization methods called quasi-Newton methods. Unlike gradient descent, which only uses first-order gradient information, quasi-Newton methods approximate the second-order Hessian matrix to more intelligently choose the step direction and size. This allows them to navigate narrow valleys more gracefully and converge in fewer iterations.

Conjugate Gradient

The conjugate gradient method is well-suited for solving large systems of linear equations Ax=b. To apply it to optimization, we can think of the gradient as a linear operator and minimize it in successive conjugate directions that are orthogonal to all previous step directions.

Compared to gradient descent, conjugate gradient can converge much faster, in only a small multiple of the problem dimension many iterations. It‘s a good general-purpose large-scale optimizer.

BFGS

The Broyden–Fletcher–Goldfarb–Shanno (BFGS) algorithm directly approximates the inverse Hessian matrix, building up curvature information as the iterations progress to steer more decisively towards the minimum.

BFGS often exhibits superlinear convergence, meaning it picks up speed as it hones in on the solution, delivering answers in even fewer steps than conjugate gradient. It‘s an excellent choice when the full Hessian is too costly to compute or store.

L-BFGS

The limited-memory BFGS (L-BFGS) algorithm is a low-memory approximation to BFGS for optimization problems with a very large number of variables, potentially over a million. As its name suggests, it avoids storing the full inverse Hessian approximation, instead updating a short history of past updates to economize on memory.

L-BFGS is the go-to algorithm for training machine learning models with tens of millions of parameters. It combines the fast convergence of BFGS with the memory efficiency of conjugate gradient, making it feasible to tackle truly massive optimization challenges.

Under the Hood: How the Algorithms Work

The mathematical underpinnings of these algorithms fill textbooks, involving concepts like conjugacy, line searches, secant equations, and trust regions. Fortunately, most data scientists can blissfully ignore these details and invoke the algorithms through high-level Python libraries like SciPy and TensorFlow that abstract away the difficult parts.

Nevertheless, here‘s a high-level sketch of how they work:

1. Choose an initial guess for the optimal parameters.

2. Compute the cost function and its gradient at the current point.

3. Feed the calculated values into the optimizer, which returns a step direction and size.

4. Update the parameters by taking a step in the indicated direction.

5. Check for convergence by monitoring the change in the cost function or parameters. If not converged, return to step 2.

The crux of the algorithms lies in step 3—how exactly do they divine the optimal step direction and size using the gradient information? This is where the mathematical magic happens, but end users need only provide a way to compute the cost function and gradient and let the optimizer do the rest.

Hands-On Example: Logistic Regression in Python

To illustrate these ideas, let‘s walk through a realistic example of applying the BFGS algorithm to train a logistic regression model in Python using SciPy. Logistic regression is a popular choice for binary classification problems.

We‘ll start by importing the required libraries and generating a synthetic dataset with 100,000 samples and 500 features using Scikit-Learn‘s make_classification function:

from sklearn.datasets import make_classification
from scipy.optimize import minimize
import numpy as np

# Generate a synthetic dataset  
X, y = make_classification(n_samples=100000, n_features=500, 
                           n_informative=50, n_redundant=0, 
                           n_repeated=0, n_classes=2,
                           random_state=42)

Next, we‘ll define the logistic regression cost function and its gradient. The cost function J(θ) is the average logarithmic loss over all the training examples:

J(θ) = -1/m ∑ [y(i) log(hθ(x(i))) + (1-y(i)) * log(1-hθ(x(i)))]

where m is the number of training examples, x(i) is the i-th feature vector, y(i) is the corresponding binary label, and hθ(x(i)) is the logistic regression hypothesis function:

hθ(x) = 1 / (1 + e^(-θ^T x))

The gradient of the cost function, ∇J(θ), turns out to have a tidy closed-form solution:

∇J(θ) = 1/m X^T (hθ(X) – y)

Armed with these expressions, we can code up the cost function and gradient like so:

def lr_cost_function(theta, X, y):
    m = len(y)
    h = 1 / (1 + np.exp(-X.dot(theta)))
    cost = -1/m * np.sum(y * np.log(h) + (1-y) * np.log(1-h)) 
    grad = 1/m * X.T.dot(h - y)
    return cost, grad

Finally, we‘ll call SciPy‘s minimize function, passing in our cost function, initial guess for θ, and specifying the ‘BFGS‘ method:

# Initialize theta 
theta_0 = np.zeros(X.shape[1])

# Call the BFGS optimizer
result = minimize(lr_cost_function, theta_0, args=(X, y), method=‘BFGS‘, jac=True)

print(result)

The jac=True argument indicates that our cost function returns both the cost and gradient, enabling BFGS to work its magic. After a few seconds, the optimization should converge and print the final cost and θ values:

 fun: 0.10696585205714128
 hess_inv: <500x500 LbfgsInvHessProduct with dtype=float64>
 jac: array([-1.31072976e-06, -1.36592090e-06, -2.79766380e-06, ...,
        5.79123126e-06,  6.76096661e-06, -1.19293140e-06])
 message: ‘CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH‘
 nfev: 112
 nit: 111
 njev: 112
 status: 0
 success: True
 x: array([-0.99707001,  0.85035528,  1.7165269 , ..., -1.31319577,
       -1.53352843,  0.27238294])

The ‘success: True‘ line indicates that BFGS converged successfully, taking only 112 iterations. We can extract the final optimized θ parameters from result.x and use them to make predictions on new data.

Trying this with the standard gradient descent optimizer would take thousands of iterations to converge and possibly get stuck in the process. BFGS is able to navigate the cost function landscape much more efficiently by approximating the curvature and decisively marching towards the minimum.

Tips for Choosing the Right Algorithm

We‘ve seen three powerful optimization algorithms—conjugate gradient, BFGS, and L-BFGS—that can speed up training of machine learning models compared to vanilla gradient descent. How do we decide which one to use for a given problem? Here are some general guidelines:

• For small to medium-sized problems with less than 1000 parameters, BFGS is usually the best choice. Its superlinear convergence rate is hard to beat.

• For larger problems with up to 10,000 or so parameters, conjugate gradient is preferred. It‘s a good tradeoff between convergence speed and memory usage.

• For very large problems with over 10,000 parameters, L-BFGS is the clear winner. It‘s the only feasible choice for truly high-dimensional optimization.

• If you‘re not sure, try BFGS first and see how it performs. If it‘s too slow or runs out of memory, switch to conjugate gradient or L-BFGS.

Of course, these are just rules of thumb and your mileage may vary depending on the specific characteristics of your problem. It‘s always a good idea to experiment with different optimizers and hyperparameters to see what works best.

Other factors to consider are the sparsity of the data (L-BFGS handles dense problems better than conjugate gradient), the noise level (conjugate gradient is more robust to noisy gradients), and the available computing resources.

Conclusion

In this post, we‘ve taken a whirlwind tour of three powerful optimization algorithms that can dramatically speed up training of machine learning models compared to gradient descent. We‘ve seen how they work under the hood, walked through a realistic logistic regression example in Python, and discussed some guidelines for choosing the right algorithm for a given problem.

While the mathematical details can be daunting, modern machine learning libraries make these algorithms extraordinarily easy to use—often just a single function call. This is a prime example of how the right abstractions can democratize access to advanced technologies.

Whether you‘re training a small model on your laptop or a giant neural network in the cloud, having a solid grasp of optimization algorithms is an essential part of a machine learning engineer‘s toolbox. By understanding their strengths and weaknesses, you‘ll be able to train models faster, tackle larger problems, and iterate more quickly.

So the next time you‘re stuck in the optimization doldrums, consider giving one of these advanced algorithms a try. You might just be surprised at how quickly you reach your destination.