In this paper, we introduce a novel framework following an upstreamdownstream paradigm to construct user and item (Pin) embeddings from diverse data sources, which are essential for Pinterest to deliver personalized Pins and ads effectively.Our upstream models are trained on extensive data sources featuring varied signals, utilizing complex architectures to capture intricate relationships between users and Pins on Pinterest.To ensure scalability of the upstream models, entity embeddings are learned, and regularly refreshed, rather than real-time computation, allowing for asynchronous interaction between the upstream and downstream models.These embeddings are then integrated as input features in numerous downstream tasks, including ad retrieval and ranking models for CTR and CVR predictions.We demonstrate that our framework achieves notable performance improvements in both offline and online settings across various downstream tasks.This framework

The Age-of-Information is an important metric for investigating the timeliness performance in information-update systems. In this paper, we study the AoI minimization problem under a new Pull model with replication schemes, where a user proactively sends a replicated request to multiple servers to “pull” the information of interest. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different values of the AoI across the servers (due to the random updating processes) and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the AoI-based utility, which represents the user's satisfaction level with respect to freshness of the received information. Furthermore, we consider a more realistic scenario where the user has no prior knowledge of the system. In this case, we reformulate the utility maximization problem as a stochastic Multi-Armed Bandit problem with side observations and leverage a special linear structure of side observations to design learning algorithms with improved performance guarantees. Finally, we conduct extensive simulations to elucidate our theoretical results and compare the performance of different algorithms. Our findings reveal that under the Pull model, waiting does not necessarily lead to aging; waiting for more than one response can often significantly reduce the AoI and improve the AoI-based utility in most scenarios.

In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptimal network configuration). Therefore, intuitively, we could explore more when the load/price is low and exploit more when the load/price is high. Inspired by this intuition, we propose an Adaptive Upper-Confidence-Bound (AdaUCB) algorithm to adaptively balance the exploration-exploitation tradeoff for opportunistic bandits. We prove that AdaUCB achieves O(log T) regret with a smaller coefficient than the traditional UCB algorithm. Furthermore, AdaUCB achieves O(1) regret with respect to T if the exploration cost is zero when the load level is below a certain threshold. Last, based on both synthetic data and real-world traces, experimental results show that AdaUCB significantly outperforms other bandit algorithms, such as UCB and TS (Thompson Sampling), under large load/price fluctuations.

360-degree video is on the cusp of going mainstream. Such videos have a large size (4-5⌉ the size of a regular one). Since each viewer has to wear Head-Mounted Display (HMD), screen sharing is impossible when a group is watching the same content. Multiple parallel video-streams will be required to serve a group of viewers along the last mile (think of a family or a group of friends watching Super Bowl in their HMDs). This would end up quickly choking the entire network. In this paper, we present a scheme to optimize the network bandwidth using motion-prediction-based multicast to serve concurrent viewers. Based on empirical evaluation of more than 150 viewers watching our pool of sixteen 360-degree videos, we observe that most viewers follow similar motion patterns when watching the same video. We present a data- driven scheme for temporal prediction of viewer motion from previous states, and hence optimize the multicast bandwidth consumption by sending only the portion likely to be watched by a group of viewers. Our evaluations with real viewer motion traces show a bandwidth saving of over 50%, compared to full frame video multicast, and significant bandwidth reduction compared to unicast.

Driven by the desire for a better user experience and enabled by improved data storage and processing, much of the recent work has studied user experience prediction in cellular networks. In this paper, moving beyond the prediction-only approach, we propose a data-driven resource allocation framework that uses data-generated prediction models to explicitly guide resource allocation for user experience improvement. In a closed-loop fashion, it further leverages and verifies the causal relation that often exists between certain feature values (e.g., bandwidth) and user experience in computer networks. As a case study, we consider how to reduce the number of user complaints in cellular networks. Our approach consists of three components: we train a logistic regression classifier to predict user experience, utilize the trained likelihood as the objective function to allocate network resource, and then evaluate user experience with allocated resource to (in)validate and adjust the original model. We design a DualHet algorithm to tackle the problem of multi-dimensional resource optimization with heterogeneous users. Numerical simulations based on both synthetic and real network data sets demonstrate the effectiveness of the proposed algorithms. In particular, the simulations based on real data demonstrate up to $2\times $ performance improvement compared with the baseline algorithm.

Enabled by the rapid development of virtual reality hardware and software, 360-degree video content has proliferated. From the network perspective, 360-degree video transmission imposes significant challenges because it consumes 4 6χ the bandwidth of a regular video with the same resolution. To address these challenges, in this paper, we propose a motion-prediction-based transmission mechanism that matches network video transmission to viewer needs. Ideally, if viewer motion is perfectly known in advance, we could reduce bandwidth consumption by 80%. Practically, however, to guarantee the quality of viewing experience, we have to address the random nature of viewer motion. Based on our experimental study of viewer motion (comprising 16 video clips and over 150 subjects), we found the viewer motion can be well predicted in 100~500ms. We propose a machine learning mechanism that predicts not only viewer motion but also prediction deviation itself. The latter is important because it provides valuable input on the amount of redundancy to be transmitted. Based on such predictions, we propose a targeted transmission mechanism that minimizes overall bandwidth consumption while providing probabilistic performance guarantees. Real-data-based evaluations show that the proposed scheme significantly reduces bandwidth consumption while minimizing performance degradation, typically a 45% bandwidth reduction with less than 0.1% failure ratio.

360-degree video transmission consumes 4∼6× the bandwidth of a regular video, and thus imposes significant challenges to networks. To address this challenge, in this paper, we propose a motion-prediction-based transmission mechanism that matches network video transmission to viewer needs. Ideally, if viewer motion is perfectly known in advance, we could reduce bandwidth consumption by 80%. Practically, however, we have to address the random nature of viewer motion, in order to guarantee the quality of the viewing experience. Based on our experimental study of viewer motion (comprising 16 video clips and over 150 subjects), we propose a machine learning mechanism that predicts viewer motion. Based on such predictions, we propose a partial-content-transmission mechanism that reduces the overall bandwidth consumption while providing probabilistic performance guarantees. Real-trace-based evaluations show that the proposed scheme significantly reduces bandwidth consumption with negligible performance degradation. For example, given a failure ratio of 0.1%, we can reduce bandwidth consumption by more than 40%.

Machine learning methods have been widely used in modeling and predicting network user experience. In this paper, moving beyond user experience prediction, we propose a closed-loop approach that uses data-generated prediction models to explicitly guide resource allocation for user experience improvement. The closed-loop approach leverages and verifies the causal relation that often exists between certain feature values (e.g., bandwidth) and user experience in computer networks. The approach consists of three components: we train a neural network classifier to predict user experience, utilize the trained neural network classifier as the objective function to allocate network resource, and then evaluate user experience with allocated resource to (in)validate and adjust the original model. Specifically, we propose a dual decomposition algorithm to solve the neural network-based resource optimization problem, which is complex and non-convex. We further develop an iterative mechanism for classifier optimization. Numerical results show that the dual algorithm reduces the expected number of unsatisfied users by up to 2x compared with the baseline, and the optimized classifier further improves the performance by 50%.

In this paper, we propose a Double Thompson Sampling (D-TS) algorithm for dueling bandit problems. As its name suggests, D-TS selects both the first and the second candidates according to Thompson Sampling. Specifically, D-TS maintains a posterior distribution for the preference matrix, and chooses the pair of arms for comparison according to two sets of samples independently drawn from the posterior distribution. This simple algorithm applies to general Copeland dueling bandits, including Condorcet dueling bandits as its special case. For general Copeland dueling bandits, we show that D-TS achieves $O(K^2 \log T)$ regret. Moreover, using a back substitution argument, we refine the regret to $O(K \log T + K^2 \log \log T)$ in Condorcet dueling bandits and many practical Copeland dueling bandits. In addition, we propose an enhancement of D-TS, referred to as D-TS+, that reduces the regret by carefully breaking ties. Experiments based on both synthetic and real-world data demonstrate that D-TS and D-TS$^+$ significantly improve the overall performance, in terms of regret and robustness.

Mobile Virtual Network Operators (MVNOs) serve their customers by leasing resource from physical Mobile Network Operators (MNOs). Guaranteeing service quality by connecting customers to appropriate MNOs based on their performance is important for MVNOs, but obtaining accurate statistics of performance for all MNOs is costly. In this paper, we study the scheduling problem with QoS constraints for MVNOs without a priori knowledge on the system statistics such as traffic and service quality. We propose a Learning-Aided Scheduling (LSchd) algorithm based on Lyapunov optimization approaches. We show that LSchd achieves near-optimal network utility subject to average QoS constraints. Further, we propose a Dual-Learning-Aided Scheduling (DSchd) algorithm to accelerate the convergence speed. The proposed algorithms are evaluated by simulations based on real network traces. The simulation results show that even when the system statistics are non-stationary, the proposed algorithms achieve near-optimal utilities and the DSchd algorithm quickly approaches the near-optimal performance.

Although cellular networks can be provisioned according to the peak demand, they usually experience large fluctuations in both channel conditions and traffic load level. Scheduling with both channel and load awareness allows us to exploit the delay tolerance of data traffic to alleviate network congestion, and thus reduce the peak. However, solving the optimal scheduling problem leads to a large-scale Markov decision process (MDP) with extremely high complexity. In this paper, we propose a scalable and distributed approach to this problem, called Coordinated Scheduling (CoSchd). CoSchd decomposes the large-scale MDP problem into many individual MDP problems, each of which can be solved independently by each user under a limited amount of coordination signals from the base station (BS). We show that CoSchd is close to optimal when the number of users becomes large. Furthermore, we propose an approximation of CoSchd that iteratively updates the scheduling policy based on online measurements. Simulation results demonstrate that exploiting channel and load awareness with CoSchd can effectively alleviate cellular network congestion.

Opportunistic scheduling of delay-tolerant traffic has been shown to substantially improve spectrum efficiency. To encourage users to adopt delay-tolerant scheduling for capacity -improvement, it is critical to provide guarantees in terms of completion time. In this paper, we study application-level scheduling with deadline constraints, where the deadline is pre-specified by users/applications and is associated with a deadline violation probability. To address the exponentially-high complexity due to temporally-varying channel conditions and deadline constraints, we develop a novel asymptotic approach that exploits the largeness of the network to our advantage. Specifically, we identify a lower bound on the deadline violation probability, and propose simple policies that achieve the lower bound in the large-system regime. The results in this paper thus provide a rigorous analytical framework to develop and analyze policies for application-level scheduling under very general settings of channel models and deadline requirements. Further, based on the asymptotic approach , we propose the notion of Application-Level Effective Capacity region, i.e., the throughput region that can be supported subject to deadline constraints, which allows us to quantify the potential gain of application-level scheduling. Simulation results show that application-level scheduling can improve the system capacity significantly while guaranteeing the deadline constraints.

We study contextual bandits with budget and time constraints under discrete contexts, referred to as constrained contextual bandits. The time and budget constraints significantly complicate the exploration and exploitation tradeoff because they introduce complex coupling among contexts over time. To gain insight, we first study unit-cost systems with known context distribution. When the expected rewards are known, we develop an approximation of the oracle, referred to Adaptive-Linear-Programming(ALP), which achieves near-optimality and only requires the ordering of expected rewards. With these highly desirable features, we then combine ALP with the upper-confidence-bound (UCB) method in the general case where the expected rewards are unknown a priori. We show that the proposed UCB-ALP algorithm achieves logarithmic regret except in certain boundary cases.Further, we design algorithms and obtain similar regret analysis results for more general systems with unknown context distribution or heterogeneous costs. To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits. Moreover, this work also sheds light on the study of computationally efficient algorithms for general constrained contextual bandits.

Opportunistic scheduling of delay-tolerant traffic has been shown to substantially improve spectrum efficiency. To encourage users to adopt delay-tolerant scheduling for capacity-improvement, it is critical to provide guarantees in terms of completion time. In this paper, we study application-level scheduling with deadline constraints, where the deadline is pre-specified by users/applications and is associated with a deadline violation probability. To address the exponentially-high complexity due to temporally-varying channel conditions and deadline constraints, we develop a novel asymptotic approach that exploits the largeness of the network to our advantage. Specifically, we identify a lower bound on the deadline violation probability, and propose simple policies that achieve the lower bound in the large-system regime. The results in this paper thus provide a rigorous analytical framework to develop and analyze policies for application-level scheduling under very general settings of channel models and deadline requirements. Further, based on the asymptotic approach, we propose the notion of Application-Level Effective Capacity region, i.e., the throughput region that can be supported subject to deadline constraints, which allows us to quantify the potential gain of application-level scheduling.

Many data applications in the next generation cellular networks, such as content precaching and video progressive downloading, require flow-level quality of service (QoS) guarantees. One such requirement is deadline, where the transmission task needs to be completed before the application-specific time. To minimize the number of uncompleted transmission tasks, we study laxity-based scheduling policies in this paper. We propose a Less-Laxity-Higher-Possible-Rate (L2HPR) policy and prove its asymptotic optimality in underloaded identical-deadline systems. The asymptotic optimality of L2HPR can be applied to estimate the schedulability of a system and provide insights on the design of scheduling policies for general systems. Based on it, we propose a framework and three heuristic policies for practical systems. Simulation results demonstrate the asymptotic optimality of L2HPR and performance improvement of proposed policies over greedy policies.

Supporting massive device transmission is challenging in machine-to-machine (M2M) communications. Particularly, in event-driven M2M communications, a large number of devices become activated within a short period of time, which in turn causes high radio congestions and severe access delay. To address this issue, we propose a Fast Adaptive S-ALOHA (FASA) scheme for random access control of M2M communication systems with bursty traffic. Instead of the observation in a single slot, the statistics of consecutive idle and collision slots are used in FASA to accelerate the tracking process of network status that is critical for optimizing S-ALOHA systems. With a design based on drift analysis, the estimate of the number of the active devices under FASA converges fast to the true value. Furthermore, by examining the T-slot drifts, we prove that the proposed FASA scheme is stable as long as the average arrival rate is smaller than e-1, in the sense that the Markov chain derived from the scheme is geometrically ergodic. Simulation results demonstrate that under highly bursty traffic, the proposed FASA scheme outperforms traditional additive schemes such as PB-ALOHA and achieves near-optimal performance in reducing access delays. Moreover, compared to multiplicative schemes, FASA shows its robustness under heavy traffic load in addition to better delay performance.

In this paper, the power optimization of the multicarrier cognitive system underlying the primary network is investigated. We consider the interference coupled cognitive network under individual secondary user's power constraint and primary user's rate constraint. A multicarrier discrete distributed (MCDD) algorithm based on Gibbs sampler is proposed. Although the problem is nonconcave, MCDD is proved to converge to the global optimal solution. To reduce the computational complexity and convergence time, the Gibbs sampler based Lagrangian algorithm (GSLA) is proposed to get a near optimal solution. We also provide simulation results to show the effectiveness of the proposed algorithms.

Machine-to-Machine (M2M) communication is now playing a market-changing role in a wide range of business world. However, in event-driven M2M communications, a large number of devices activate within a short period of time, which in turn causes high radio congestions and severe access delay. To address this issue, we propose a Fast Adaptive S- ALOHA (FASA) scheme for M2M communication systems with bursty traffic. The statistics of consecutive idle and collision slots, rather than the observation in a single slot, are used in FASA to accelerate the tracking process of network status. Furthermore, the fast convergence property of FASA is guaranteed by using drift analysis. Simulation results demonstrate that the proposed FASA scheme achieves near-optimal performance in reducing access delay, which outperforms that of traditional additive schemes such as PB-ALOHA. Moreover, compared to multiplicative schemes, FASA shows its robustness even under heavy traffic load in addition to better delay performance.