{"id":2214,"date":"2015-01-22T09:43:45","date_gmt":"2015-01-22T09:43:45","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=2214"},"modified":"2015-01-22T09:43:45","modified_gmt":"2015-01-22T09:43:45","slug":"optimizing-optimization-algorithms","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/optimizing-optimization-algorithms\/","title":{"rendered":"Optimizing optimization algorithms"},"content":{"rendered":"

Analysis shows how to get the best results when approximating solutions to complex engineering problems.<\/strong><\/em><\/span><\/p>\n

\"This<\/a>
This sequence of graphs illustrates the application of the researchers’ technique to a real-world computer vision problem. The solution to each successive problem (red balls) is used to initialize (green arrows) the search for a solution to the next.<\/figcaption><\/figure>\n

CAMBRIDGE, Mass. —\u00a0Optimization algorithms, which try to find the minimum values of mathematical functions, are everywhere in engineering. Among other things, they\u2019re used to evaluate design tradeoffs, to assess control systems, and to find patterns in data.<\/span><\/p>\n

One way to solve a difficult optimization problem is to first reduce it to a related but much simpler problem, then gradually add complexity back in, solving each new problem in turn and using its solution as a guide to solving the next one. This approach seems to work well in practice, but it\u2019s never been characterized theoretically.<\/span><\/p>\n

This month, at the International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, Hossein Mobahi, a postdoc at MIT\u2019s Computer Science and Artificial Intelligence Laboratory (CSAIL), and John Fisher, a senior research scientist at CSAIL, describe a way to generate that sequence of simplified functions that guarantees the best approximation that the method can offer.<\/span><\/p>\n

\u201cThere are some fundamental questions about this method that we answer for the first time,\u201d Mobahi says. \u201cFor example, I told you that you start from a simple problem, but I didn\u2019t tell you how you choose that simple problem. There are infinitely many functions you can start with. Which one is good? Even if I tell you what function to start with, there are infinitely many ways to transform that to your actual problem. And that transformation affects what you get at the end.\u201d<\/span><\/p>\n

Bottoming out<\/strong><\/span><\/p>\n

To get a sense of how optimization works, suppose that you\u2019re a canned-food retailer trying to save money on steel, so you want a can design that minimizes the ratio of surface area to volume. That ratio is a function of the can\u2019s height and radius, so if you can find the minimum value of the function, you\u2019ll know the can\u2019s optimal dimensions. If you\u2019re a car designer trying to balance the costs of components made from different materials with the car\u2019s weight and wind resistance, your function \u2014 known in optimization as a \u201ccost function\u201d \u2014 will be much more complex, but the principle is the same.<\/span><\/p>\n

Machine-learning algorithms frequently attempt to identify features of data sets that are useful for classification tasks \u2014 say, visual features characteristic of cars. Finding the smallest such set of features with the greatest predictive value is also an optimization problem.<\/span><\/p>\n

\u201cMost of the efficient algorithms that we have for solving optimization tasks work based on local search, which means you initialize them with some guess about the solution, and they try to see in which direction they can improve that, and then they take that step,\u201d Mobahi says. \u201cUsing this technique, they can converge to something called a local minimum, which means a point that compared to its neighborhood is lower. But it may not be a global minimum. There could be a point that is much lower but farther away.\u201d<\/span><\/p>\n

A local minimum is guaranteed to be a global minimum, however, if the function is convex, meaning that it slopes everywhere toward its minimum. The function y = x2<\/sup>\u00a0is convex, since it describes a parabola centered at the origin. The function y = sin x is not, since it describes a sine wave that undulates up and down.<\/span><\/p>\n

Smooth sailing<\/strong><\/span><\/p>\n

Mobahi and Fisher\u2019s method begins by trying to find a convex approximation of an optimization problem, using a technique called Gaussian smoothing. Gaussian smoothing converts the cost function into a related function that gives not the value that the cost function would, but a weighted average of all the surrounding values. This has the effect of smoothing out any abrupt dips or ascents in the cost function\u2019s graph.<\/span><\/p>\n

The weights assigned the surrounding values are determined by a Gaussian function, or normal distribution \u2014 the bell curve familiar from basic statistics. Nearby values count more toward the average than distant values do.<\/span><\/p>\n

A Gaussian function is defined by a single parameter, which determines its width. Mobahi and Fisher begin with a very wide Gaussian, which, under certain conditions, yields a convex function. Then they steadily contract the width of the Gaussian, generating a series of intermediary problems. At each stage, they use the solution to the last problem to initialize the search for a solution to the next one. By the time the width of the distribution has shrunk to zero, they\u2019ve recovered the original cost function, since every value is simply the average of itself.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Analysis shows how to get the best results when approximating solutions to complex engineering problems. CAMBRIDGE, Mass. —\u00a0Optimization algorithms, which try to find the minimum values of mathematical functions, are everywhere in engineering. Among other things, they\u2019re used to evaluate design tradeoffs, to assess control systems, and to find patterns in data. One way to […]<\/p>\n","protected":false},"author":6,"featured_media":2219,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[43],"tags":[],"class_list":["post-2214","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computer-science"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/01\/MIT-Nonconvex-Optimization-01_0.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"Computer Science<\/a>","tag_info":"Computer Science","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/2214","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=2214"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/2214\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/2219"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=2214"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=2214"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=2214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}