Computing

New Optimization Algorithm Exponentially Speeds Computation

Finding the optimal solutions to complex problems can be dramatically faster

code on a computer screen
Image: iStockphoto

A new algorithm could dramatically slash the time it can take computers to recommend movies or route taxis.

The new algorithm, developed by Harvard University researchers, solves optimization problems exponentially faster than previous algorithms by cutting the number of steps required. Surprisingly, this approach works “without sacrificing the quality of the resulting solution,” says study senior author Yaron Singer, at Harvard University.

Optimization problems seek to find the best answer from all possible solutions, such as mapping the fastest route from point A to point B. Many algorithms designed to solve optimization problems have not changed since they were first described in the 1970s.

Previous optimization algorithms generally worked in a step-by-step process, with the number of steps proportional to the amount of the data analyzed. For example, a movie-recommendation algorithm might sequentially look at every film similar to one a person liked.

However, previous optimization algorithms had a diminishing-returns property: As they progressed, the relative gain from each step became smaller and smaller. This meant that for optimization problems involving vast amounts of data, finding the best solutions could prove extraordinarily computationally expensive.

In experiments, Singer and study coauthor Eric Balkanski found their algorithm could analyze a data set with 1 million ratings of 4,000 movies from 6,000 users and give similar movie recommendations to state-of-the-art algorithms while working 20 times faster. In addition, using a data set of 2 million taxi trips from the New York City Taxi and Limousine Commission, the new algorithm could pick the best locations for taxis to cover the maximum number of potential customers six times faster than previous algorithms.

Whereas prior optimization algorithms solved problems by progressing step-by-step in a single direction, the new algorithm works by sampling a variety of directions in parallel. Based on that sample, it discards less optimal directions and chooses the most valuable directions to progress toward solutions. This act of adaptively evolving what data the algorithm works on helps solve the problem of diminishing returns.

This strategy works given two different aspects of the algorithm’s objectives. The researchers called these aspects curvature and homogeneity.

With the movie-recommendation problem, objectives with high curvatures are films that are very similar to ones a person has watched—for instance, if you enjoyed Die Hard, recommendations will likely include its sequels. With the taxi-dispatch problem, objectives with high curvatures are locations where taxis could respond to customers within 30 seconds. The milder the curvature —for instance, a taxi response time of five minutes instead of 30 seconds—the faster the algorithm could work.

With the movie-recommendation problem, objectives with high homogeneity assume there are many films that one could recommend—for example, if you enjoyed Die Hard, high homogeneity assumes similar action movies such as Lethal Weapon would make good recommendations. With the taxi-dispatch problem, high homogeneity assumes customers are distributed relatively equally across locations. The greater the homogeneity, the faster the algorithm could work.

This new approach could work on other problems, including identifying new drugs, discovering drug-drug interactions from online health forums, and developing sensor arrays for medical imaging.

“The fact that we can literally get exponential speedups in running time opens opportunities for applications in health care, computational biology, machine learning, and data mining that were too costly to consider before,” Singer says.

Balkanski and Singer are now exploring optimization problems on which their strategy can apply. They also plan to write code for GPUs so that others can implement their work. “In general, the algorithms are extremely simple and are implementable in a few lines of code,” Singer says.

The scientists detailed their findings at the Association for Computing Machinery’s Symposium on Theory of Computing (STOC) in Los Angeles on 28 June. They will also present their work at the International Conference on Machine Learning (ICML) in Stockholm on 12 July.