Project

Back to overview

Scaling Up by Scaling Down: Big ML via Small Coresets

Applicant Krause Andreas
Number 167212
Funding scheme NRP 75 Big Data
Research institution Departement Informatik ETH Zürich
Institution of higher education ETH Zurich - ETHZ
Main discipline Information Technology
Start/End 01.05.2017 - 30.04.2021
Approved amount 490'108.00
Show all

Keywords (4)

coresets; adaptive sampling; machine learning; statistical models

Lay Summary (German)

Lead
Durch die zunehmende Digitalisierung in der Gesellschaft und Wissenschaft entstehen massive Datenmengen. In diesem Projekt entwickeln wir effiziente Algorithmen, um Daten so komprimieren zu können, dass auch die komprimierten Datensätze immer noch hinreichend genau analysiert werden können.
Lay summary

Unser Ansatz erweitert bereits bestehende mathematische Optimierungsverfahren, um sie auf komplexe Aufgaben und reichhaltige Modelle des maschinellen Lernens anwenden zu können. Wir untersuchen auch Verbindungen zur statistischen Lerntheorie um die Vorhersagegenauigkeit der Ergebnisse abschätzen zu können. Unsere Arbeit ist einerseits theoretisch: Wir entwickeln neuartige Algorithmen und beweisen ihre Eigenschaften und die Genauigkeit ihrer Resultate mathematisch. Andererseits implementieren wir die Algorithmen, und stellen sie als Open-Source-Software zur Verfügung. Dabei berücksichtigen wir sowohl Architekturen von modernen Datenzentren als auch mobile Plattformen.

Immense Datenmengen entstehen in unterschiedlichsten Bereichen von Wissenschaft und Gesellschaft. Das maschinelle Lernen bietet vielerlei Techniken, nützliche Muster zu erkennen sowie datenbasiert Entscheidungen zu unterstützen und zu automatisieren. Je grösser allerdings die Datenmenge, desto schwieriger ist es, die resultierenden Rechenaufgaben effizient zu lösen.

Wir entwickeln neuartige Algorithmen zur effizienten Analyse von grossen Datenmengen. Hierbei ist das Ziel, die Daten so zusammenzufassen oder zu komprimieren, dass die Genauigkeit von wichtigen statistischen Analysen und Lernverfahren nur minimal reduziert wird. Die bei der Komprimierung entstehenden so genannten Coresets können auch von komplexen Lösungsverfahren mit hoher Robustheit und Genauigkeit bearbeitet werden, weil sie erheblich kleiner sind als die ursprünglichen Daten.

Unsere Ergebnisse werden es auch Forschungsgruppen und Unternehmen ohne riesige Rechen- und Datenzentren erlauben, mit dem rasanten Wachstum an Daten besser Schritt halten zu können. Potenzielle Anwendungen reichen von Online-Empfehlungsdiensten über die Robotik bis zum Internet der Dinge.

Direct link to Lay Summary Last update: 16.08.2017

Lay Summary (French)

Lead
La numérisation croissante de la société et de la science engendre d’énormes quantités de données. Dans ce projet, nous développons des algorithmes efficaces de compression des données de façon à pouvoir les analyser de façon suffisamment précise.
Lay summary

Notre approche complète des techniques d’optimisations mathématiques déjà existantes afin de les adapter aux tâches complexes et aux modèles variés de l’apprentissage automatique. Nous étudions aussi des liens avec la théorie de l'apprentissage statistique afin d’estimer la précision de la prévision des résultats. Nous développons, au niveau théorique, de nouveaux algorithmes et nous apportons la preuve mathématique de leurs propriétés et de l’exactitude de leurs résultats. Au niveau pratique, nous implémentons les algorithmes et les mettons à disposition sous forme de logiciel libre, tenant en compte aussi bien des architectures de centres de données modernes que des plateformes mobiles.

L’apprentissage automatique offre diverses techniques pour détecter des modèles utiles ainsi que pour étayer et automatiser des décisions sur la base de données. Mais plus leur volume est important, plus il est difficile de résoudre efficacement les problèmes de calcul qui en découlent.

Nous développons de nouveaux algorithmes pour analyser efficacement de gros volumes de données. L’objectif est de synthétiser ou de comprimer ces dernières de manière à réduire de façon minimale la précision des analyses statistiques et des processus d’apprentissage. Les "core sets" (ensembles de base) générés lors de la compression se traitent aussi de manière robuste et précise au moyen de méthodes de résolution complexes parce qu’ils sont considérablement plus petits que les données d’origine.

Nos résultats permettront à des groupes de recherche et à des entreprises qui ne possèdent pas de très grands centres de calcul et de données de mieux faire face à leur croissance rapide. Les domaines d’application potentiels vont des systèmes de recommandation en ligne à l’Internet des objets en passant par la robotique.

Direct link to Lay Summary Last update: 16.08.2017

Lay Summary (English)

Lead
Increasing digitalisation in society and science is resulting in massive amounts of data. In the present project, we are developing efficient algorithms that allow data to be compressed in such a way that the compressed data sets can still be analysed with satisfactory accuracy.
Lay summary

Our approach enhances existing mathematical optimisation techniques so that they can be applied to complex tasks and models arising in machine learning. We will also be examining connections with statistical learning theory in order to evaluate the predictive accuracy of the results. Our work is partly theoretical: we are developing novel algorithms and provide mathematical proof of their properties and the accuracy of their results. At the same time, we will implement the algorithms and release them as open source software compatible both with the architectures of modern data centres and with mobile platforms.

Science and society are generating huge amounts of data in a wide range of areas. Machine learning provides numerous techniques for identifying useful patterns as well as supporting and automating data-based decisions. However, the larger the data volume, the more difficult it is to efficiently solve the resulting computational tasks.

We are developing novel algorithms for the efficient analysis of large data volumes. The objective is to summarise or compress the data such that the accuracy of key statistical analyses and learning processes is only minimally reduced. Since they are considerably smaller than the original data, the so-called coresets that are created during compression can be processed with a high degree of robustness and accuracy.

Our findings will also allow research groups and companies that do not have giant computer and data centres to keep pace more effectively with the rapid growth of data. Potential applications range from online recommendation services and robotics to the Internet of Things.

Direct link to Lay Summary Last update: 16.08.2017

Responsible applicant and co-applicants

Employees

Publications

Publication
Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces
KirschnerJohannes, MutnyMojmir, HillerNicole, IschebeckRasmus, KrauseAndreas (2019), Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces, arXiv, USA.
Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features
MutnyMojmir (2018), Efficient High Dimensional Bayesian Optimization with Additivity and Quadrature Fourier Features, in Proc. Neural Information Processing Systems, MontrealAdvances in Neural Information Processing Systems, USA.
One-Shot Coresets: The Case of k-Clustering
Bachem Olivier, Lucic Mario, Lattanzi Silvio (2018), One-Shot Coresets: The Case of k-Clustering, in Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), LanzaroteProceedings of Machine Learning Research, USA.
Online Variance Reduction for Stochastic Optimization
Borsos Zalan, Krause Andreas, Levy Kfir (2018), Online Variance Reduction for Stochastic Optimization, in Prof. Conference on Learning Theory (COLT), Proceedings of Machine Learning Research, USA.
Training Gaussian Mixture Models at Scale via Coresets
LucicMario, FaulknerMatthew, KrauseAndreas, FeldmanDan (2018), Training Gaussian Mixture Models at Scale via Coresets, in Journal of Machine Learning Research, 18, 1-25.
Distributed and Provably Good Seedings for k-Means in Constant Rounds
Bachem Olivier, Lucic Mario, Krause Andreas (2017), Distributed and Provably Good Seedings for k-Means in Constant Rounds, in Proc. International Conference on Machine Learning (ICML), Proceedings of Machine Learning Research, USA.
Uniform Deviation Bounds for k-Means Clustering
Bachem Olivier, Lucic Mario, Hassani S. Hamed, Krause Andreas (2017), Uniform Deviation Bounds for k-Means Clustering, in Proc. International Conference on Machine Learning Research (ICML), Proceedings of Machine Learning Research, USA.
Variational Inference for DPGMM with Coresets
Borsos Zalan, Bachem Olivier, Krause Andreas (2017), Variational Inference for DPGMM with Coresets, NIPS Workshop on Approximate Bayesian Inference, Long Beach, CA.

Collaboration

Group / person Country
Types of collaboration
Robotics and Big Data Lab at the University of Haifa Israel (Asia)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
Inference, Information and Decision Systems Group at Yale University United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
Prof. Hamed Hassani, University of Pennsylvania United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
- Publication

Scientific events



Self-organised

Title Date Place
New Architectures and Algorithms 26.11.2018 Los Angeles, United States of America
NIPS Workshop on Discrete Structures in Machine Learning 08.12.2017 Long Beach, United States of America
Workshop on Data Driven Algorithmics 05.11.2017 Bertinoro, Italy

Use-inspired outputs

Associated projects

Number Title Start Funding scheme
159557 Explore-exploit with Gaussian Processes under Complex Constraints 01.04.2015 Project funding (Div. I-III)

Abstract

We aim to advance the state of the art in large scale machine learning (ML): Instead of scaling up learning algorithms, we want to scale down the data. Our approach builds on coresets: small weighted subsets of a big data set, guaranteeing that models fitted on them are provably competitive with those trained on the full data. We aim to systematically address the shortcomings of existing approaches that currently preclude them from being used in modern large-scale ML. We seek to 1) generalize coresets towards fitting rich statistical latent variable models; 2) connect coreset approximation guarantees to statistical learning theory to obtain predictive summaries; and 3) generalize the coreset approach via multi-stage adaptive sampling as well as multi-fidelity representations. Beyond developing and theoretically analyzing new algorithms, we will develop open source implementations of coreset-based analytics, both on distributed compute clusters and mobile devices.
-