Noticias en español
Pacing Mechanisms For Ad Auctions.
Abstract: Budgets play a significant role in real-world sequential auction markets such as those implemented by Internet companies. To maximize the value provided to auction participants, spending is smoothed across auctions so budgets are used for the best opportunities. Motivated by pacing mechanisms used in practice by online ad auction platforms, we discuss smoothing procedures that ensure that campaign daily budgets are consistent with maximum bids. Reinterpreting this process as a game between bidders, we introduce the notion of pacing equilibrium, and study properties such as...
Read MoreCombinatorial Optimization Augmented with Machine Learning.
Abstract: Combinatorial optimization often focuses on optimizing for the worst-case. However, the best algorithm to use depends on the “relative inputs”, which is application specific and often does not have a formal definition. The talk gives a new theoretical model for designing algorithms that are tailored to inputs for the application at hand. In the model, learning is performed on past problem instances to make predictions on future instances. These predictions are incorporated into the design and analysis of the algorithm. The predictions can be used to achieve...
Read MoreOnline assortment optimization for two-sided matching platforms.
Abstract: Motivated by online labor markets, we consider the online assortment optimization problem faced by a two-sided matching platform that hosts a set of suppliers waiting to match with a customer. Arriving customers are shown an assortment of suppliers, and may choose to issue a match request to one of them. Before leaving the platform, each supplier reviews all the match requests he has received, and based on his preferences, he chooses whether to match with a customer or to leave unmatched. We study how platforms should design online assortment algorithms to maximize the expected...
Read MoreA Tight (3/2+ε)-Approximation for Skewed Strip Packing.
Abstract: In the Strip Packing problem, we are given a vertical half-strip [0,W] × [0,+∞) and a collection of open rectangles of width at most W. Our goal is to find an axis-aligned (non-overlapping) packing of such rectangles into the strip such that the maximum height OPT spanned by the packing is as small as possible. Strip Packing generalizes classical well-studied problems such as Makespan Minimization on identical machines (when rectangle widths are identical) and Bin Packing (when rectangle heights are identical). It has applications in manufacturing, scheduling and energy consumption...
Read MoreStability of Stochastic Gradient Descent on Nonsmooth Convex Losses.
Abstract: Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. An influential work of Hardt, Recht & Singer (ICML’16) provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses. Our work is...
Read More