On the Throughput vs Accuracy Trade-Off for Streaming Unsupervised Classification

Sanjay Shakkottai, UT Austin

We study an online and streaming unsupervised classification system. Our setting consists of a collection of classifiers (with unknown confusion matrices) each of which can classify one sample per unit time, and which are accessed by a stream of unlabeled samples. Each sample is dispatched to one or more classifiers, and depending on the labels collected from these classifiers, may be sent to other classifiers to collect additional labels. The labels are continually aggregated. Once the aggregated label has high enough accuracy (a pre-specified threshold for accuracy) or the sample is sent to all the classifiers, the now labeled sample is ejected from the system. For any given pre-specified threshold for accuracy, the objective is to sustain the maximum possible rate of arrival of new samples, such that the number of samples in memory does not grow unbounded.

In this talk, we characterize the Pareto-optimal region of accuracy and arrival rate, and discuss an algorithm that can operate at any point within this region. Our algorithm uses queueing-based routing and scheduling approaches combined with online tensor decomposition method to learn the hidden parameters, and provides Pareto-optimality guarantees. We finally verify our theoretical results through simulations on two ensembles formed using AlexNet, VGG, and ResNet deep image classifiers. Based on joint work with Soumya Basu, Steven Gutstein and Brent Lance.

Workshop on statistical Learning Theory

The field of Learning Theory has witnessed an explosive growth over the past decade. This growth has been made possible by exciting developments in the fields of applied mathematics, statistics and computer science and fueled by the need for processing modern large data sets.

This two-day workshop seeks to explore some aspects of statistical learning theory.  It will include five mini-courses and feature a couple of talks.


Dates: January 3-4, 2020

Venue: AG-66 (Lecture Theatre), Tata Institute of Fundamental Research, Mumbai.

Click here for travel information.

Participation is by invitation only.  Please contact learningtheory@tifr.res.in for further information.