Online Learning of Assignments
Which ads should we display in sponsored search in order to maximize our revenue? How should we dynamically rank information sources to maximize value of information? These applications exhibit strong diminishing returns: Selection of redundant ads and information sources decreases their marginal utility. We show that these and other problems can be formalized as repeatedly selecting an assignment of items to positions to maximize a sequence of monotone submodular functions that arrive one by one. We present an efficient algorithm for this general problem and analyze it in the no-regret model. Our algorithm is equipped with strong theoretical guarantees, with a performance ratio that converges to the optimal constant of 1-1/e. We empirically evaluate our algorithms on two real-world online optimization problems on the web: ad allocation with submodular utilities, and dynamically ranking blogs to detect information cascades.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Behavior Pattern and Compiled Information Based Performance Prediction in MOOCs
With the development of MOOCs massive open online courses, increasingly more subjects can be studied online. Researchers currently show growing interest in the field of MOOCs, including dropout prediction, cheating detec…
PredictionAggregating partial rankings with applications to peer grading in massive online open courses
We investigate the potential of using ordinal peer grading for the evaluation of students in massive online open courses (MOOCs). According to such grading schemes, each student receives a few assignments (by other stude…
Conversational Structure Aware and Context Sensitive Topic Model for Online Discussions
Millions of online discussions are generated everyday on social media platforms. Topic modelling is an efficient way of better understanding large text datasets at scale. Conventional topic models have had limited succes…
Topic ModelsLarge-scale Online Ridesharing: The Effect of Assignment Optimality on System Performance
Mobility-on-demand (MoD) systems consist of a fleet of shared vehicles that can be hailed for one-way point-to-point trips. The total distance driven by the vehicles and the fleet size can be reduced by employing ridesha…
Efficient Unsupervised Visual Representation Learning with Explicit Cluster Balancing
Self-supervised learning has recently emerged as the preeminent pretraining paradigm across and between modalities, with remarkable results. In the image domain specifically, group (or cluster) discrimination has been on…
Representation LearningSelf-Supervised Learning