The December 2022 issue of IEEE Spectrum is here!

Close bar

New Optimization Algorithm Exponentially Speeds Computation

Finding the optimal solutions to complex problems can be dramatically faster

3 min read
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.

The Conversation (0)

Why Functional Programming Should Be the Future of Software Development

It’s hard to learn, but your code will produce fewer nasty surprises

11 min read
A plate of spaghetti made from code
Shira Inbar

You’d expectthe longest and most costly phase in the lifecycle of a software product to be the initial development of the system, when all those great features are first imagined and then created. In fact, the hardest part comes later, during the maintenance phase. That’s when programmers pay the price for the shortcuts they took during development.

So why did they take shortcuts? Maybe they didn’t realize that they were cutting any corners. Only when their code was deployed and exercised by a lot of users did its hidden flaws come to light. And maybe the developers were rushed. Time-to-market pressures would almost guarantee that their software will contain more bugs than it would otherwise.

Keep Reading ↓Show less