Dissertation/Thesis Abstract

Learning Theory and Algorithms for Auctioning and Adaptation Problems
by Munoz Medina, Andres, Ph.D., New York University, 2015, 260; 3740907
Abstract (Summary)

A common assumption in machine learning is that training and testing data are i.i.d. realizations of the same distribution. However, this assumption is often violated in practice: the training and test distributions are often somewhat related but different. For example, the training sample for a face recognition system may be a carefully curated data set in general different from the full face data found on online. Similarly, spam email messages change over time and thus the training sample for a spam classifier at any time differs from the test data. The first problem described above is known as domain adaptation and the second known as learning under drifting distributions. The first part of this thesis presents theory and algorithms for these problems. For domain adaptation, we provide tight learning bounds based on the novel concept of generalized discrepancy. These bounds strongly motivate our learning algorithm and it is shown, both theoretically and empirically, that this algorithm can significaly improve upon the current state-of-the-art. We extend the theoretical results of domain adaptation to the more challenging scenario of learning under drifting distributions. Moreover, we establish a deep connection between on-line learning and this problem. In particular, we provide a novel on-line to batch conversion that motivates a learning algorithm with very favorable empirical performance. The second part of this thesis studies a crucial problem at the intersection of learning and game theory: revenue optimization in repeated auctions. More precisely, we study second-price and generalized second-price auctions with reserve. These auction mechanisms have become extremely popular in recent years due to the advent of online advertisement. Both type of auctions are characterized by a reserve price representing the minimum value at which the seller is willing to forego of the object in question. Therefore, selecting an optimal reserve price is crucial in achieving the largest possible revenue. We cast this problem as a learning problem and provide the first theoretical analysis for learning optimal reserve prices from samples for both second-price and generalized second-price auctions. These results, however, assume that buyers do not react strategically to changes in reserve prices. In the last chapter of this thesis, we analyze the possible strategies for the buyers and show that, if the seller is more patient than the buyer, it is not in the best interest of the buyer to behave strategically.

Indexing (document details)
Advisor: Mohri, Mehryar
Commitee: Cortes, Corinna, Gentile, Claudio, Kohn, Robert, Mansour, Yishay, Tabak, Esteban
School: New York University
Department: Mathematics
School Location: United States -- New York
Source: DAI-B 77/05(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Mathematics, Computer science
Keywords: Auctions, Domain adaptation, Game theory, Machine learning, Revenue optimization, Statistical learning theory
Publication Number: 3740907
ISBN: 9781339330358
Copyright © 2019 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest