Algorithms and Theory

Contextual bandit algorithms are commonly used in recommender systems, where content popularity can change rapidly. These algorithms continuously learn good mappings between users and items, based on contexts associated with both the users and items. Recent recommendation algorithms that learn clustering or social structures between users have exhibited higher recommendation accuracy. However,...

We consider the active learning problem for a supervised learning model: That is, after training a black box model on a given dataset, we determine which (large batch of) unlabeled candidates to label in order to improve the model further. We concentrate on the large-batch case, because this is most aligned with most machine learning applications, and because it is more theoretically rich. Our...

This paper proposes an extension to the actionable reach modeling for cross-media audiences, whereTV audiences are measured via extrapolation from a panel or partial set-top-box data. In essence, a set of TV Virtual People are exclusively associated with, or represented by, a TV panelist q via an HR sketch s, which is an extension to an HLL sketch. We extrapolate q’s TV activity to this set of...

We construct a family of functions suitable for establishing lower bounds on the oracle complexity of first-order minimization of smooth strongly-convex functions. Based on this construction, we derive new lower bounds on the complexity of strongly-convex minimization under various accuracy criteria. The new bounds match the known upper bounds up to a constant factor, and when the accuracy of a...