Statistics/Machine Learn Thesis Defense

  • Gates Hillman Centers
  • Traffic21 Classroom 6501
  • Ph.D. Student
  • Joint Ph.D. Program in Statistics & Machine Learning
  • Department of Machine Learning, and Department of Statistics and Data Science, Carnegie Mellon University
Thesis Orals

Competitive Analysis for Machine Learning and Data Science

Statistical machines learn from regularity in data and are often designed for stationary or even independent and identically distributed (IID) processes.  However, in most real-world applications it is not known how close the data process is to being IID.  Moreover, this is impossible to learn when past data may be misleading or otherwise unrepresentative of the future.  An adversarial data process, on the other hand, is not subject to probabilistic constraints; instead an adversary can deterministically attempt to mislead or otherwise confuse the machine.  Of course designing for an adversary has its own limitation: that of being pessimistic.  Despite the disparity between IIDness and adversarialism, for a given application, it may not be known which will better approximate the data.  Fortunately, in many supervised settings, learning from data that is generated by an adaptive adversary is not much harder (statistically) than if it were generated by a static distribution.  More precisely, the minimax expected regret values differ by a constant factor.  In that case, a machine optimally designed for an adversary is necessarily competitive with any other, even when the data process is IID.

My talk will be focused on sketching some machinery for showing as much and applying it to high-dimensional experts under a loss that is a metric.  In that (sequential) setting, the only apparent limitation to designing against an adversary is that it requires a linear proportion of the available periods to learn, whereas IID data requires only a sublinearly-sized sample.

More generally (and outside of my talk in the interest of time), this idea of being competitive in the worst-case (and therefore all cases) arises in other problems besides unknown regularity, such as regret or excess risk minimization under a given regularity regime.  My dissertation (i) defines competitive difference as the objective of an algorithm or system designer and (ii) prescribes analysis thereon as a way of characterizing how well otherwise-unquantifiable uncertainty can be dealt with.  In each of several examples ranging from competitive ratios and constant factor approximations in computer science to prices of stability and anarchy in game theory, an algorithm or designer must cope with incomplete information about the problem or system it is trying to address, such as what is the optimal assumption or decision.  This incompleteness impedes an unambiguous objective; the competitive difference provides clarity by furnishing a (fully specified) objective on the basis of which an optimal decision can be formulated.  After presenting the above framework and its application to unknown regularity, a case study of time series forecasting is given.

Thesis Committee:
Cosma Shalizi (Chair)
Joseph Kadane
Barnabás Póczos
Pradeep Ravikumar
Aarti Singh
Larry Wasserman

Copy of Draft Thesis Document

For More Information, Please Contact: