There is increasing attention toward search indexes based on dense vector representations as they can encode latent semantic features and can be generated efficiently, thanks to the advances in representation learning. Building an index on vectors was addressed by methods like locality-sensitive hashing (LSH), Inverted File Index (IVF), and near-neighbor graphs and perfected for high performance. However, the current near-neighbor (NN) indexes cannot be directly used in a real recommendation engine where both learned dense features and the constraints-attributes are used. The existing methods are cascaded index with vector search followed by a naive matching or inverted index for filtering on attribute tokens. This filtering on post-vector search matched sets often limits the control on output size and adds latency due to repeated calls to the NN engine. We aim to make a single-stage retrieval model that can retrieve in a single pass and control the output size without compromising on latency. An NN index amenable to this should have a very similar structure to the attribute token-based inverted index. Hence, we develop an efficient constraint search engine based on the high dimensional sparse embeddings of semantic features added with attribute tokens. With this, we get an Inverted index-based Constraint Near Neighbor search-ICONN, where we retrieve search results with 100% match on query attributes and close to its semantic features. We achieve a better latency vs recall10@10 tradeoff compared to the standard NN search followed by attribute filtering.

In this paper, we consider a heavy inner product identification problem, which generalizes the Light Bulb problem ([1]): Given two sets $A \subset\{-1,+1\}^{d}$ and $B \subset\{-1,+1\}^{d}$ with $|A|=|B|=n$, if there are exact k pairs whose inner product passes a certain threshold, i.e., $\{\left(a_{1}, b_{1}\right), \cdots,\left(a_{k}, b_{k}\right)\} \subset A \times B$ such that $\forall i \in[k],\left\langle a_{i}, b_{i}\right\rangle \geq \rho \cdot d$, for a threshold $\rho \in(0,1)$, the goal is to identify those k heavy inner products. We provide an algorithm that runs in $O(n^{2 \omega / 3+o(1)})$ time to find the k inner product pairs that surpass $\rho \cdot d$ threshold with high probability, where $\omega$ is the current matrix multiplication exponent. By solving this problem, our method speed up the training of neural networks with ReLU activation function.

Vanilla federated learning does not support learning in an online environment, learning a personalized model on each client, and learning in a decentralized setting. There are existing methods extending federated learning in each of the three aspects. However, some important applications on enterprise edge servers (e.g. online item recommendation at global scale) involve the three aspects at the same time. Therefore, we propose a new learning setting Decentralized Personalized Online Federated Learning that considers all the three aspects at the same time.In this new setting for learning, the first technical challenge is how to aggregate the shared model parameters from neighboring clients to obtain a personalized local model with good performance on each client. We propose to directly learn an aggregation by optimizing the performance of the local model with respect to the aggregation weights. This not only improves personalization of each local model but also helps the local model adapting to potential data shift by intelligently incorporating the right amount of information from its neighbors. The second challenge is how to select the neighbors for each client. We propose a peer selection method based on the learned aggregation weights enabling each client to select the most helpful neighbors and reduce communication cost at the same time. We verify the effectiveness and robustness of our proposed method on three real-world item recommendation datasets and one air quality prediction dataset.

Consider two brands that want to jointly test alternate web experiences for their customers with an A/B test. Such collaborative tests are today enabled usingthird-party cookies, where each brand has information on the identity of visitors to another website, ensuring a consistent treatment experience. With the imminent elimination of third-party cookies, such A/B tests will become untenable. We propose a two-stage experimental design, where the two brands only need to agree on high-level aggregate parameters of the experiment to test the alternate experiences. Our design respects the privacy of customers. We propose an unbiased estimator of the Average Treatment Effect (ATE), and provide a way to use regression adjustment to improve this estimate. On real and simulated data, we show that the approach provides valid estimate of the ATE and is robust to the proportion of visitors overlapping across the brands. Our demonstration describes how a marketer can design such an experiment and analyze the results.

Earlier recommendation techniques, such as Collaborative Filtering (CF), assume the users’ preferences do not change over time and strive to maximize the immediate reward. In recent studies, Reinforcement Learning (RL) has been used to make interactive recommendation systems that capture users’ preferences over time and maximize the long-term reward. However, these methods have two limitations. First, they assume that items are independently distributed and do not consider the relations between items. This assumption ignores the power of the relations between items for recommendation systems, as demonstrated by CF. RL-based methods rely primarily on users’ positive feedback to understand their preferences, and sampling is used to incorporate their negative feedback. In a practical setting, users’ negative feedback is just as crucial as their positive feedback for understanding their preferences. We present a novel Deep Reinforcement Learning (DRL) recommendation framework to address the limitations above. We specifically utilize the actor-critic paradigm, which considers the recommendation problem a sequential decision-making process to adapt to users’ behaviors and maximize the long-term reward. Motivated by the intuition that similar users like similar items, we extract the relations between items using CF and integrate it into our framework to boost overall performance. Instead of negative sampling, our proposed framework relies on all users’ positive and negative feedback to understand users’ preferences more accurately. Extensive experiments with our dataset and two public datasets demonstrate the effectiveness of our proposed framework.

Maximizing utility with a budget constraint is the primary goal for advertisers in real-time bidding (RTB) systems. The policy maximizing the utility is referred to as the optimal bidding strategy. Earlier works on optimal bidding strategy apply model-based batch reinforcement learning methods which can not generalize to unknown budget and time constraint. Further, the advertiser observes a censored market price which makes direct evaluation infeasible on batch test datasets. Previous works ignore the losing auctions to alleviate the difficulty with censored states; thus significantly modifying the test distribution. We address the challenge of lacking a clear evaluation procedure as well as the error propagated through batch reinforcement learning methods in RTB systems. We exploit two conditional independence structures in the sequential bidding process that allow us to propose a novel practical framework using the maximum entropy principle to imitate the behavior of the true distribution observed in real-time traffic. Moreover, the framework allows us to train a model that can generalize to the unseen budget conditions than limit only to those observed in history. We compare our methods on two real-world RTB datasets with several baselines and demonstrate significantly improved performance under various budget settings.

Predicting user engagement (e.g., click-through rate, conversion rate) on the display ads plays a critical role in delivering the right ad to the right user in online advertising. Existing techniques spanning Logistic Regression to Factorization Machines and their derivatives, focus on modeling the interactions among handcrafted features to predict the user engagement. Little attention has been paid on how the ad fits with the context (e.g., hosted webpage, user demographics). In this paper, we propose to include the metadata feature, which captures the visual appearance of the ad, in the user engagement prediction task. In particular, given a data sample, we combine both the basic context features, which have been widely used in existing prediction models, and the metadata feature, which is extracted from the ad using a state-of-the-art deep learning framework, to predict user engagement. To demonstrate the effectiveness of the proposed metadata feature, we compare the performance of the widely used prediction models before and after integrating the metadata feature. Our experimental results on a real-world dataset demonstrate that the metadata feature is able to further improve the prediction performance.

In programmatic advertising, ad slots are usually sold using second-price (SP) auctions in real-time. The highest bidding advertiser wins but pays only the second-highest bid (known as the winning price). In SP, for a single item, the dominant strategy of each bidder is to bid the true value from the bidder's perspective. However, in a practical setting, with budget constraints, bidding the true value is a sub-optimal strategy. Hence, to devise an optimal bidding strategy, it is of utmost importance to learn the winning price distribution accurately. Moreover, a demand-side platform (DSP), which bids on behalf of advertisers, observes the winning price if it wins the auction. For losing auctions, DSPs can only treat its bidding price as the lower bound for the unknown winning price. In literature, typically censored regression is used to model such partially observed data. A common assumption in censored regression is that the winning price is drawn from a fixed variance (homoscedastic) uni-modal distribution (most often Gaussian). However, in reality, these assumptions are often violated. We relax these assumptions and propose a heteroscedastic fully parametric censored regression approach, as well as a mixture density censored network. Our approach not only generalizes censored regression but also provides flexibility to model arbitrarily distributed real-world data. Experimental evaluation on the publicly available dataset for winning price estimation demonstrates the effectiveness of our method. Furthermore, we evaluate our algorithm on one of the largest demand-side platforms and significant improvement has been achieved in comparison with the baseline solutions.

Factorization Machines (FM) have been widely applied in industrial applications for recommendations. Traditionally FM models are trained in batch mode, which entails training the model with large datasets every few hours or days. Such training procedure cannot capture the trends evolving in real time with large volume of streaming data. In this paper, we propose an online training scheme for FM with the alternating least squares (ALS) technique, which has comparable performance with existing batch training algorithms. We incorporate an online update mechanism to the model parameters at the cost of storing a small cache. The mechanism also stabilizes the training error more than a traditional online training technique like stochastic gradient descent (SGD) as data points come in, which is crucial for real-time applications. Experiments on large scale datasets validate the efficiency and robustness of our method.

Most of existing digital content recommendation systems use explicit feedback data like user's ratings. While such systems rely on user input, those do not sense the context. In this paper, we propose a framework for digital content recommendation using only implicit feedback data (i.e., information collected from session usage without any direct feedback from user), which not only considers interactions among users and contents but also various other implicit information available during a video session. To capture interactions among such attributes, we choose Higher-Order Factorization Machines (HoFM) as our predictor and test our approach on real-world video usage data. In the experiments we explore different possible factors that may affect the performance of HoFM predictor. We observe that increasing the number of sessions of users considered to build the predictor significantly improves prediction accuracy, whereas increasing the order or depth of interactions may not. We also present an application of our work to a video recommendation system.

We present a goal-directed, local and on-the-fly algorithm for verifying the existence and synthesizing a choreographer forWeb service composition. We use i/o-automata to represent services, the desired functionality of the composition, and a choreographer to achieve the desired service by composing the existing ones. Choreographer existence and synthesis are typically performed by identifying all possible compositions realizable from the existing services and verifying whether one such composition conforms to the desired required functionality. Such a technique is subject to state-space explosion. In light of this, we have developed a tabled-logic programming technique which generates and explores compositions in a goal-directed fashion to prove/disprove the existence of choreographer and to infer whether the desired functionality is realizable. We present a prototype implementation and show the practical applicability of our technique using a variety of composition problems with the corresponding computational savings in terms of number of states and transitions explored.