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.
|Commitee:||Cortes, Corinna, Gentile, Claudio, Kohn, Robert, Mansour, Yishay, Tabak, Esteban|
|School:||New York University|
|School Location:||United States -- New York|
|Source:||DAI-B 77/05(E), Dissertation Abstracts International|
|Subjects:||Mathematics, Computer science|
|Keywords:||Auctions, Domain adaptation, Game theory, Machine learning, Revenue optimization, Statistical learning theory|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be