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.
展开▼
