ICML: “Test of time” paper shows how times have changed

Amazon scientist’s award-winning paper predates — but later found applications in — the deep-learning revolution.

Amazon researchers have nine new papers at this year’s International Conference on Machine Learning (ICML), one of the top conferences in AI. Matthias Seeger, a principal applied scientist with Amazon Web Services (AWS), is a coauthor on one of them, which reports work led by AWS applied scientist Cuong Nguyen.

But it’s a paper that Seeger cowrote ten years ago that’s one of the conference highlights. On July 1, the ICML awards committee announced that Seeger and his colleagues’ 2010 paper “Gaussian process optimization in the bandit setting: no regret and experimental design” had won the conference’s Test of Time Award, which honors “a paper from ICML ten years ago that has had substantial impact on the field of machine learning, including both research and practice.”

The citation from the award committee begins, “This paper brought together the fields of Bayesian optimization, bandits, and experimental design,” and it “has since cross-fertilized these separate research domains,” Seeger adds.

Matthias Seeger
Matthias Seeger, principal applied scientist

Bayesian-optimization and bandit problems have the same general structure, Seeger explains, but “Bayesian optimization is generally done over continuous input spaces and more complicated functions,” he says. “Multi-armed bandits would normally assume finite spaces and linear or otherwise strongly restricted payoff functions. Maybe because Bayesian optimization is more flexible in this sense, it comes with a lot less solid theory. Multi-armed bandits is a more theoretically grounded area.”

Seeger and his colleagues’ 2010 paper generalized theoretical findings from the multi-armed bandit setting to Bayesian optimization (BO), providing strong performance bounds given particular choices of statistical models. This gave machine learning practitioners greater confidence in techniques they’d arrived at empirically and helped them identify circumstances in which those techniques might be less successful.

In the context of deep learning — which now dominates the field of artificial intelligence — BO is used for hyperparameter tuning, or optimizing structural features of the deep-learning model and parameters of the learning algorithm to maximize the efficacy of training on particular data.

To prove their result for BO, Seeger and his colleagues extended techniques borrowed from a third related field, experimental design. The tools they devised to bridge the related disciplines of BO, multi-armed bandits, and experimental design have proved useful to researchers working in all three; the paper has more than 1,000 citations on Google Scholar, which have helped make Seeger the fourth most highly cited researcher in the field of Bayesian optimization.

Seeger’s coauthors on the 2010 paper are Niranjan Srinivas, now a computational biologist at 10xGenomics; Andreas Krause, now a professor of computer science at ETH Zurich; and Sham Kakade, now a professor in the departments of computer science and statistics at the University of Washington.

With Bayesian optimization, Seeger explains, “you are essentially optimizing a function over some search space without actually knowing what this function looks like. You have to learn about that function as you sample it. But your real goal is finding the function’s maximum, or to sample it nearby.”

“If you sample forever, at some point you will find its optima” he adds. “But since sampling is expensive and takes time, you want to finish as rapidly as possible. So what you are really interested in is to spend as few samples as possible before you converge to something useful, very close to the optimum.”

Temperature samples.png
An example of Seeger and his colleagues’ sample selection procedure, taken from their 2010 paper. The first image (a) represents temperatures in different parts of a building; the two images at right (b and c) represent successive iterations of the procedure, in which individual sensors are briefly activated to take temperature readings (red circles). The black line represents the true temperatures, and the grey areas represent the method’s latest inference of the range of possible temperatures in each region. Crosses indicate points at which readings have already been taken. The procedure selects new sample points with the goal of either maximizing information gain (b) or finding optima (c).

Seeger and his colleagues proved that, under conditions that frequently hold for machine learning problems, the sampling process is guaranteed to converge. But they also showed that the convergence rate depends on specific problem parameters.

In BO, the function that you’re trying to optimize is a random function, Seeger explains. “Every time you plug in a point x, you get a random value f(x),” he says. A standard way to do BO is to model the outputs of the function using a probability distribution. If that distribution is Gaussian — the standard bell curve — then Bayesian optimization is said to use a Gaussian process as a surrogate model.

One of the parameters of the surrogate model is its covariance function, which describes the correlation between changes to function inputs (the x’s) and the resulting changes to the outputs (the f(x)’s). There are several families of covariance function, with an infinite range of functions within each family.

Seeger and his colleagues’ paper quantitatively relates the convergence rate of the function-sampling procedure to the specific choice of covariance function.

“Some choices of covariance function imply smooth functions, which can faithfully be interpolated from measurements nearby,” Seeger says. “Others result in rough functions, for which interpolating even across short distances is an uncertain exercise.”

From theory to practice

Machine learning researchers had conjectured that rougher covariance functions, although they may model reality better, imply slower convergence on an optimum. Seeger and his colleagues’ paper quantified this trade-off precisely. It enabled researchers to decide how much roughness they were willing to sacrifice for faster convergence.

To bound convergence rates, Seeger and his colleagues borrowed techniques from experimental design. “Here you are interested in learning about a function, but not just where its maximum is — learning about it globally, or learning about a model everywhere,” Seeger explains.

A central concept in experimental design is information gain, a quantification of how much information about a function each new sample — each new experiment — confers. Seeger and his colleagues quantified the convergence rate in BO by framing the question in terms of information gain.

“It’s pretty theoretical work,” Seeger says. “It led to a lot of follow-up work because of the links that we could show. There is quite a bit of Gaussian-process theory being brought together here, which partly fuses the different themes together.”

At Amazon, Seeger says, his work on meta-learning and automated machine learning is less theoretical, but his training still stands him in good stead. “I do think that the background that I have from back then is quite useful for me to plan ahead, in a way, and to see whether something looks right or not,” Seeger says. “I think this is quite important, because due to the explosive growth of our field, there are now so many options you can pursue. You really cannot implement all of them and try them out. You need to have some guiding principles.”

Seeger’s transition from more theoretical to more applied work mirrors that of the field itself. In the ten years since he cowrote this award-winning paper, he says, “there’s been a huge change, with the size of the field, the practical applications, the size of the models, the size of the data sets.”

“Back then, maybe because it was smaller, there were ideas being followed that wouldn’t immediately have an application, and you were actually looking into theory quite a bit,” he says. “These days, it’s a lot more driven by empirical applications and empirical work. The field has matured and is very successful in some applications, so obviously you want to focus more on whether an idea is useful in the current context or not. And that’s certainly something that I’ve learned to do a lot more since I joined Amazon.”

Research areas

Related content

US, WA, Seattle
The Global Media Entertainment Science team uses state of the art economics and machine learning models to provide Amazon’s entertainment businesses guidance on strategically important questions. We are looking for detail-oriented, organized, and responsible individuals who are eager to learn how to work with large and complicated data sets. Some knowledge of econometrics, as well as basic familiarity with Python is necessary, and experience with SQL and UNIX would be a plus. These are full-time positions at 40 hours per week, with compensation being awarded on an hourly basis. You will learn how to build data sets and perform applied econometric analysis at Internet speed collaborating with economists, scientists, and product managers. These skills will translate well into writing applied chapters in your dissertation and provide you with work experience that may help you with placement. Roughly 85% of previous cohorts have converted to full time scientist employment at Amazon. If you are interested, please send your CV to our mailing list at econ-internship@amazon.com. Key job responsibilities
US, CA, Palo Alto
The Amazon Search team creates powerful, customer-focused search solutions and technologies. Whenever a customer visits an Amazon site worldwide and types in a query or browses through product categories, Amazon Product Search services go to work. We design, develop, and deploy high performance, fault-tolerant distributed search systems used by millions of Amazon customers every day. Our Search Relevance team works to maximize the quality and effectiveness of the search experience for visitors to Amazon websites worldwide. The Search Relevance team focuses on several technical areas for improving search quality. In this role, you will invent universally applicable signals and algorithms for training machine-learned ranking models. The relevance improvements you make will help millions of customers discover the products they want from a catalog containing millions of products. You will work on problems such as predicting the popularity of new products, developing new ranking features and algorithms that capture unique characteristics, and analyzing the differences in behavior of different categories of customers. The work will span the whole development pipeline, including data analysis, prototyping, A/B testing, and creating production-level components. Joining this team, you’ll experience the benefits of working in a dynamic, entrepreneurial environment, while leveraging the resources of Amazon.com (AMZN), one of the world’s leading Internet companies. We provide a highly customer-centric, team-oriented environment in our offices located in Palo Alto, California. Please visit https://www.amazon.science for more information
US, WA, Seattle
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. Do you have a strong machine learning background and want to help build new speech and language technology? Amazon is looking for PhD students who are ready to tackle some of the most interesting research problems on the leading edge of natural language processing. We are hiring in all areas of spoken language understanding: NLP, NLU, ASR, text-to-speech (TTS), and more! A successful candidate will be a self-starter comfortable with ambiguity, strong attention to detail, and the ability to work in a fast-paced, ever-changing environment. As an Applied Science Intern, you will develop and implement novel scalable algorithms and modeling techniques to advance the state-of-the-art in technology areas at the intersection of ML, NLP, search, and deep learning. You will work side-by-side with global experts in speech and language to solve challenging groundbreaking research problems on production scale data. The ideal candidate must have the ability to work with diverse groups of people and cross-functional teams to solve complex business problems. Amazon has positions available for Natural Language Processing & Speech Intern positions in multiple locations across the United States. Amazon fundamentally believes that scientific innovation is essential to being the most customer-centric company in the world. Please visit our website to stay updated with the research our teams are working on: https://www.amazon.science/research-areas/conversational-ai-natural-language-processing
US, WA, Seattle
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. The Research team at Amazon works passionately to apply cutting-edge advances in technology to solve real-world problems. Do you have a strong machine learning background and want to help build new speech and language technology? Do you welcome the challenge to apply optimization theory into practice through experimentation and invention? Would you love to help us develop the algorithms and models that power computer vision services at Amazon, such as Amazon Rekognition, Amazon Go, Visual Search, etc? At Amazon we hire research science interns to work in a number of domains including Operations Research, Optimization, Speech Technologies, Computer Vision, Robotics, and more! As an intern, you will be challenged to apply theory into practice through experimentation and invention, develop new algorithms using mathematical programming techniques for complex problems, implement prototypes and work with massive datasets. Amazon has a culture of data-driven decision-making, and the expectation is that analytics are timely, accurate, innovative and actionable. Amazon Science gives insight into the company’s approach to customer-obsessed scientific innovation. Amazon fundamentally believes that scientific innovation is essential to being the most customer-centric company in the world. It’s the company’s ability to have an impact at scale that allows us to attract some of the brightest minds in artificial intelligence and related fields. Amazon Scientist use our working backwards method to enrich the way we live and work. For more information on the Amazon Science community please visit https://www.amazon.science.
US, WA, Seattle
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. The Research team at Amazon works passionately to apply cutting-edge advances in technology to solve real-world problems. Do you have a strong machine learning background and want to help build new speech and language technology? Do you welcome the challenge to apply optimization theory into practice through experimentation and invention? Would you love to help us develop the algorithms and models that power computer vision services at Amazon, such as Amazon Rekognition, Amazon Go, Visual Search, etc? At Amazon we hire research science interns to work in a number of domains including Operations Research, Optimization, Speech Technologies, Computer Vision, Robotics, and more! As an intern, you will be challenged to apply theory into practice through experimentation and invention, develop new algorithms using mathematical programming techniques for complex problems, implement prototypes and work with massive datasets. Amazon has a culture of data-driven decision-making, and the expectation is that analytics are timely, accurate, innovative and actionable. Amazon Science gives insight into the company’s approach to customer-obsessed scientific innovation. Amazon fundamentally believes that scientific innovation is essential to being the most customer-centric company in the world. It’s the company’s ability to have an impact at scale that allows us to attract some of the brightest minds in artificial intelligence and related fields. Amazon Scientist use our working backwards method to enrich the way we live and work. For more information on the Amazon Science community please visit https://www.amazon.science.
CA, ON, Toronto
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. Are you a Masters student interested in machine learning, natural language processing, computer vision, automated reasoning, or robotics? We are looking for skilled scientists capable of putting theory into practice through experimentation and invention, leveraging science techniques and implementing systems to work on massive datasets in an effort to tackle never-before-solved problems. A successful candidate will be a self-starter comfortable with ambiguity, strong attention to detail, and the ability to work in a fast-paced, ever-changing environment. As an Applied Science Intern, you will own the design and development of end-to-end systems. You’ll have the opportunity to create technical roadmaps, and drive production level projects that will support Amazon Science. You will work closely with Amazon scientists, and other science interns to develop solutions and deploy them into production. The ideal scientist must have the ability to work with diverse groups of people and cross-functional teams to solve complex business problems. Amazon Science gives insight into the company’s approach to customer-obsessed scientific innovation. Amazon fundamentally believes that scientific innovation is essential to being the most customer-centric company in the world. It’s the company’s ability to have an impact at scale that allows us to attract some of the brightest minds in artificial intelligence and related fields. Our scientists use our working backwards method to enrich the way we live and work. For more information on the Amazon Science community please visit https://www.amazon.science.
CA, ON, Toronto
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. Are you a PhD student interested in machine learning, natural language processing, computer vision, automated reasoning, or robotics? We are looking for skilled scientists capable of putting theory into practice through experimentation and invention, leveraging science techniques and implementing systems to work on massive datasets in an effort to tackle never-before-solved problems. A successful candidate will be a self-starter comfortable with ambiguity, strong attention to detail, and the ability to work in a fast-paced, ever-changing environment. As an Applied Science Intern, you will own the design and development of end-to-end systems. You’ll have the opportunity to create technical roadmaps, and drive production level projects that will support Amazon Science. You will work closely with Amazon scientists, and other science interns to develop solutions and deploy them into production. The ideal scientist must have the ability to work with diverse groups of people and cross-functional teams to solve complex business problems. Amazon Science gives insight into the company’s approach to customer-obsessed scientific innovation. Amazon fundamentally believes that scientific innovation is essential to being the most customer-centric company in the world. It’s the company’s ability to have an impact at scale that allows us to attract some of the brightest minds in artificial intelligence and related fields. Our scientists use our working backwards method to enrich the way we live and work. For more information on the Amazon Science community please visit https://www.amazon.science.
US, WA, Seattle
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. We are looking for Masters or PhD students excited about working on Automated Reasoning or Storage System problems at the intersection of theory and practice to drive innovation and provide value for our customers. AWS Automated Reasoning teams deliver tools that are called billions of times daily. Amazon development teams are integrating automated-reasoning tools such as Dafny, P, and SAW into their development processes, raising the bar on the security, durability, availability, and quality of our products. AWS Automated Reasoning teams are changing how computer systems built on top of the cloud are developed and operated. AWS Automated Reasoning teams work in areas including: Distributed proof search, SAT and SMT solvers, Reasoning about distributed systems, Automating regulatory compliance, Program analysis and synthesis, Security and privacy, Cryptography, Static analysis, Property-based testing, Model-checking, Deductive verification, compilation into mainstream programming languages, Automatic test generation, and Static and dynamic methods for concurrent systems. AWS Storage Systems teams manage trillions of objects in storage, retrieving them with predictable low latency, building software that deploys to thousands of hosts, achieving 99.999999999% (you didn’t read that wrong, that’s 11 nines!) durability. AWS storage services grapple with exciting problems at enormous scale. Amazon S3 powers businesses across the globe that make the lives of customers better every day, and forms the backbone for applications at all scales and in all industries ranging from multimedia to genomics. This scale and data diversity requires constant innovation in algorithms, systems and modeling. AWS Storage Systems teams work in areas including: Error-correcting coding and durability modeling, system and distributed system performance optimization and modeling, designing and implementing distributed, multi-tenant systems, formal verification and strong, practical assurances of correctness, bits-IOPS-Watts: the interplay between computation, performance, and energy, data compression - both general-purpose and domain specific, research challenges with storage media, both existing and emerging, and exploring the intersection between storage and quantum technologies. As an Applied Science Intern, you will work closely with Amazon scientists and other science interns to develop solutions and deploy them into production. The ideal scientist must have the ability to work with diverse groups of people and cross-functional teams to solve complex business problems. A successful candidate will be a self-starter with strong attention to detail and the ability to thrive in a fast-paced, ever-changing environment who is comfortable with ambiguity. Amazon believes that scientific innovation is essential to being the world’s most customer-centric company. Our ability to have impact at scale allows us to attract some of the brightest minds in Automated Reasoning and related fields. Our scientists work backwards to produce innovative solutions that delight our customers. Please visit https://www.amazon.science (https://www.amazon.science/) for more information.
US, WA, Seattle
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. We are looking for PhD students excited about working on Automated Reasoning or Storage System problems at the intersection of theory and practice to drive innovation and provide value for our customers. AWS Automated Reasoning teams deliver tools that are called billions of times daily. Amazon development teams are integrating automated-reasoning tools such as Dafny, P, and SAW into their development processes, raising the bar on the security, durability, availability, and quality of our products. AWS Automated Reasoning teams are changing how computer systems built on top of the cloud are developed and operated. AWS Automated Reasoning teams work in areas including: Distributed proof search, SAT and SMT solvers, Reasoning about distributed systems, Automating regulatory compliance, Program analysis and synthesis, Security and privacy, Cryptography, Static analysis, Property-based testing, Model-checking, Deductive verification, compilation into mainstream programming languages, Automatic test generation, and Static and dynamic methods for concurrent systems. AWS Storage Systems teams manage trillions of objects in storage, retrieving them with predictable low latency, building software that deploys to thousands of hosts, achieving 99.999999999% (you didn’t read that wrong, that’s 11 nines!) durability. AWS storage services grapple with exciting problems at enormous scale. Amazon S3 powers businesses across the globe that make the lives of customers better every day, and forms the backbone for applications at all scales and in all industries ranging from multimedia to genomics. This scale and data diversity requires constant innovation in algorithms, systems and modeling. AWS Storage Systems teams work in areas including: Error-correcting coding and durability modeling, system and distributed system performance optimization and modeling, designing and implementing distributed, multi-tenant systems, formal verification and strong, practical assurances of correctness, bits-IOPS-Watts: the interplay between computation, performance, and energy, data compression - both general-purpose and domain specific, research challenges with storage media, both existing and emerging, and exploring the intersection between storage and quantum technologies. As an Applied Science Intern, you will work closely with Amazon scientists and other science interns to develop solutions and deploy them into production. The ideal scientist must have the ability to work with diverse groups of people and cross-functional teams to solve complex business problems. A successful candidate will be a self-starter with strong attention to detail and the ability to thrive in a fast-paced, ever-changing environment who is comfortable with ambiguity. Amazon believes that scientific innovation is essential to being the world’s most customer-centric company. Our ability to have impact at scale allows us to attract some of the brightest minds in Automated Reasoning and related fields. Our scientists work backwards to produce innovative solutions that delight our customers. Please visit https://www.amazon.science (https://www.amazon.science/) for more information.
US, WA, Seattle
To ensure a great internship experience, please keep these things in mind. This is a full time internship and requires an individual to work 40 hours a week for the duration of the internship. Amazon requires an intern to be located where their assigned team is. Amazon is happy to provide relocation and housing assistance if you are located 50 miles or further from the office location. Help us develop the algorithms and models that power computer vision services at Amazon, such as Amazon Rekognition, Amazon Go, Visual Search, and more! We are combining computer vision, mobile robots, advanced end-of-arm tooling and high-degree of freedom movement to solve real-world problems at huge scale. As an intern, you will help build solutions where visual input helps the customers shop, anticipate technological advances, work with leading edge technology, focus on highly targeted customer use-cases, and launch products that solve problems for Amazon customers. A successful candidate will be a self-starter comfortable with ambiguity, strong attention to detail, and the ability to work in a fast-paced, ever-changing environment. You will own the design and development of end-to-end systems and have the opportunity to write technical white papers, create technical roadmaps, and drive production level projects that will support Amazon Science. You will work closely with Amazon scientists, and other science interns to develop solutions and deploy them into production. The ideal scientist must have the ability to work with diverse groups of people and cross-functional teams to solve complex business problems. Amazon Science gives insight into the company’s approach to customer-obsessed scientific innovation. Amazon fundamentally believes that scientific innovation is essential to being the most customer-centric company in the world. It’s the company’s ability to have an impact at scale that allows us to attract some of the brightest minds in artificial intelligence and related fields. Amazon Scientist use our working backwards method to enrich the way we live and work. For more information on the Amazon Science community please visit https://www.amazon.science