Vision Transformers (ViTs) have gained significant attention and widespread adoption due to their impressive performance in various computer vision tasks. However, in practice, their substantial computational overhead often leads to high inference latency and increased overheads when deployed on resource-constrained edge devices like smartphones, autonomous vehicles, and robots. To address these challenges, Early Exit (EE) has emerged as a promising approach for lightweight inference on edge devices. It accelerates inference and reduces computational overhead by adaptively producing predictions through early exits based on sample complexity. Existing EE methods typically suffer from substantial accuracy decreases in late exits while providing only marginal accuracy improvements to early exits. This paper presents EnViT, an exit-aware structured dropout-enabled self-distillation approach that enhances the performance of early exits without compromising late exits. EnViT leverages structured dropout to enable self-distillation, where the full model serves as the teacher and its own virtual sub-models generated by structured dropout as students. This mechanism effectively distills knowledge from the full model to early exits and avoids performance degradation in late exits by mitigating parameter conflicts across exits during training. Evaluation on five datasets shows that our EnViT achieves accuracy improvements ranging from 0.36% to 7.92% while maintaining competitive speed-up ratios of 1.72x to 2.23x.

In the user growth scenario, Internet companies invest heavily in paid acquisition channels to acquire new users. But sustainable growth depends on acquired users' generating lifetime value (LTV) exceeding customer acquisition cost (CAC). In order to maximize LTV/CAC ratio, it is crucial to predict channel-level LTV in an early stage for further optimization of budget allocation. The LTV forecasting problem is significantly different from traditional time series forecasting problems, and there are three main challenges. Firstly, it is an unaligned multi-time series forecasting problem that each channel has a number of LTV series of different activation dates. Secondly, to predict in the early stage, it faces the imbalanced short-input long-output (SILO) challenge. Moreover, compared with the commonly used time series datasets, the real LTV series are volatile and non-stationary, with more frequent fluctuations and higher variance. In this work, we propose a novel framework called Trapezoidal Temporal Fusion (TTF) to address the above challenges. We introduce a trapezoidal multi-time series module to deal with data unalignment and SILO challenges, and output accurate predictions with a multi-tower structure called MT-FusionNet. The framework has been deployed to the online system for Douyin. Compared to the previously deployed online model, MAPE_p decreased by 4.3%, and MAPE_a decreased by 3.2%, where MAPE_p denotes the point-wise MAPE of the LTV curve and MAPE_a denotes the MAPE of the aggregated LTV.

Zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are a key technology to privacy-preserving applications today. The complexity of proof generation, however, heavily constrains throughput in latency-sensitive environments. The computational burden primarily stems from two fundamental algorithms: Multi-Scalar Multiplication (MSM) and the Number Theoretic Transform (NTT). We propose a series of optimizations for these two kernels, including computation-transfer pipelining, load balancing, and memory access fusion, achieving 1.97 × to 2.16 × proof generation speedup over a state-of-the-art open source GPU acceleration library. Our design also supports out-of-core computation, enabling the generation of large-scale ZKP proofs.

Machine learning models are widely integrated into modern mobile apps to analyze user behaviors and deliver personalized services. Ensuring low-latency on-device model execution is critical for maintaining high-quality user experiences. While prior research has primarily focused on accelerating model inference with given input features, we identify an overlooked bottleneck in real-world on-device model execution pipelines: extracting input features from raw application logs. In this work, we explore a new direction of feature extraction optimization by analyzing and eliminating redundant extraction operations across different model features and consecutive model inferences. We then introduce AutoFeature, an automated feature extraction engine designed to accelerate on-device feature extraction process without compromising model inference accuracy. AutoFeature comprises three core designs: (1) graph abstraction to formulate the extraction workflows of different input features as one directed acyclic graph, (2) graph optimization to identify and fuse redundant operation nodes across different features within the graph; (3) efficient caching to minimize operations on overlapping raw data between consecutive model inferences. We implement a system prototype of AutoFeature and integrate it into five industrial mobile services spanning search, video and e-commerce domains. Online evaluations show that AutoFeature reduces end-to-end on-device model execution latency by 1.33 × -3.93 × during daytime and 1.43 × -4.53 × at night.

Embedded AI applications usually require compact on-device models that can continually adapt to new tasks. However, recent studies have revealed that neural networks trained on non-stationary data streams gradually lose their ability to adapt to new tasks, a phenomenon known as plasticity loss. Moreover, to enable neural networks to run on resource-constrained embedded devices, model pruning is commonly applied for model compression, which may further affect their plasticity. To conduct efficient model adaptation on new tasks on embedded devices, we propose Plasticity-aware Continual Pruning (PaCP), a novel framework that operates in two stages. First, a pre-deployment stage uses a plasticity-aware strategy to prune the model while optimizing its initial structure for future adaptability. Second, during continual learning, the model's capacity is temporarily expanded at task boundaries to efficiently learn new information, before plasticity-aware pruning restores its compact form. Extensive experiments on multiple continual learning benchmarks demonstrate that PaCP significantly outperforms existing plasticity-maintenance methods and, remarkably, even surpasses non-pruned models lacking explicit plasticity preservation.

Collaborative learning between edge servers (e.g., base stations) and end devices (e.g., drones) enables simultaneous model training in web applications through knowledge sharing. The resulting models effectively reduce service latency. However, existing approaches either assume isomorphic models on edge servers and end devices or incur substantial transmission overhead when training. Moreover, edge servers are often unable to access data from end devices on time due to long-distance constraints or strict data privacy regulations. This paper proposes a Prototype Augmentation-based Edge-end Collaborative Learning method (PAECL). It simultaneously trains heterogeneous edge and end models in the absence of data on edge servers by transmitting only augmented class-wise feature vectors (prototypes), significantly reducing communication overhead compared to sharing models, data, or logits. Specifically, on end devices, prototype-implied latent knowledge is augmented via local prototype contrast and global prototype alignment. On edge servers, prototypes are further augmented to produce bounded virtual vectors by mixing them with random noise, and the augmented prototypes are then delivered to generative models to provide data during edge model training. Through simulations and field experiments, PAECL achieves the highest accuracy for edge and end models under limited training resources and reduces the transmission burden by at least 297 times compared to existing edge-end heterogeneous learning methods.

This paper addresses theJoint deployment ofUnmanned aerial vehicles (UAVs) and surveillance caMeras withPath planning (JUMP), aiming to deploy a fixed number of UAVs and budget-limited surveillance cameras, to achieve continuous omnidirectional monitoring. Specifically, the objective is to maximize the monitoring durations of target objects in each of all horizontal directions within a given task duration. We propose an approach for JUMP, which is proved to be NP-hard. Our approach achieves a$\frac{1}{6}-\varepsilon _{1}$approximation ratio in general and$\frac{1}{4}-\varepsilon _{1}$when camera costs are uniform. Firstly, we introduce spatio-temporal discretization to approximate JUMP. Secondly, we partition the solution space of JUMP from spatial perspective and refine the space by addressing a variant of obstacle-avoiding shortest path problem spatio-temporal perspective. Thirdly, we reformulate the problem as a classical problem of Monotone Submodular set function Maximization with one partition Matroid and two Knapsack constraints (MSMMK). To address MSMMK, we propose a$\frac{1}{6(1+\varepsilon )}$approximation algorithm, which outperforms the state-of-the-art with the same time complexity in general. Specifically, our algorithm achieves a$\frac{1}{4(1+\varepsilon )}$approximation ratio for special cases. Simulation results demonstrate our proposed approach outperforms five benchmark algorithms, yielding enhancements 13%-1446%. Moreover, field experiment results indicate that our approach surpasses comparison algorithms, achieving enhancements 23%-265%.

In modern mobile and edge applications, users and devices frequently encounter dynamic contexts, necessitating ondevice continual learning (CL) to ensure consistent performance of machine learning models. While existing research predominantly focused on developing lightweight CL frameworks, we identify that data scarcity is a more severe bottleneck for ondevice CL. In this work, we explore the potential of leveraging abundant cloud-side data to enrich scarce on-device data, and propose Delta, a private, efficient and effective data enrichment framework. Specifically, Delta introduces a directory dataset to decompose the data enrichment problem into device-side and cloud-side sub-problems without sharing raw sensitive data, mitigating privacy concerns and reducing communication overhead. Next, Delta designs a soft data matching strategy to effectively solve device-side sub-problem with sparse user data and an optimal data sampling scheme for cloud server to efficiently retrieve the most suitable dataset for enrichment. Further, Delta refines the data sampling scheme by jointly considering the impact of enriched data on both new and past contexts, mitigating the catastrophic forgetting issue from a new aspect. Finally, we enhance Delta’s applicability to more private and rare user contexts by integrating differential privacy and domain adaptation techniques. Comprehensive experiments across four typical edge computing tasks with varied data modalities demonstrate that Delta significantly enhances overall model accuracy by an average of 15.1%, 12.4%, 1.1% and 5.6% for visual, IMU, audio and textual tasks compared with few-shot CL. Additionally, Delta reduces communication costs by over 90% compared to federated CL, making it suitable for resource-constrained edge networks.

Considering limited on-device resources, current practices are attempting to deploy a system-level mixture-of-experts (MoE)-based foundation LLM on a mobile device to serve multiple apps and support mobile intelligence. However, mobile apps are hard to customize their services that require fine-tuning adapters associated with the LLM using private in-app data. The difficulty arises due to both the limited on-device resources and the restricted control that apps have over the foundation LLM. To address this issue, in this work, we propose LiteMoE, a novel proxy submodel tuning framework that supports mobile apps to efficiently fine-tune customized adapters on devices using proxy submodels. The key technique behind LiteMoE is a post-training submodel extraction method, whereby without additional retraining, we can identify and reserve critical experts, match and merge moderate experts, to extract a lightweight and effective proxy submodel from the foundation LLM for a specific app. To further enhance scalability and adaptability, LiteMoE incorporates adapter reuse and continuous tuning mechanisms to handle multi-task requirements and evolving user preferences. We implemented a prototype of LiteMoE and evaluated it over various MoE-based LLMs and mobile computing tasks. The results show that with LiteMoE, mobile apps are able to fine-tune customized adapters on resource-limited devices, achieving 12.7% accuracy improvement and 6.6× memory reduction compared with operating the original foundation LLM.

Edge-end collaborative learning trains models with exchanged knowledge through distributed interaction, alleviating the cloud's burden. Edge-end heterogeneous collaborative learning further enables edge servers and end devices to train models of different scales in parallel based on their computational capabilities. This technology supports various applications in different resource conditions and improves server resource utilization. However, implementing it is challenging due to heavy communication costs and high global costs (time and energy). To this end, this paper proposes a novel prototype-based edge-end heterogeneous collaborative learning method and an optimization algorithm, which improves model performance and reduces training costs. We first use prototypes to perform collaborative learning and analyze the convergence. Prototypes are computed as mean feature vectors from different classes. The aggregated prototypes help capture class information on end devices and generate data on edge servers. Then, we study how to determine prototype selection and edge association to minimize training time, energy consumption, and prototype approximation error under a limited reward budget, which is proven to be NP-hard. We split the original problem into two subproblems. The first is solved in the closed form. Through approximation and reformulation, the second is transformed into a submodular maximization problem with knapsack and matroid constraints. On this basis, we propose an approximation algorithm with a theoretical guarantee. Finally, by simulation and field experiments, our method takes 3.61% of communication costs to improve heterogeneous edge and end models' accuracy by at least 5.16% and 2.77% compared with five baselines. The proposed algorithm outperforms others by at least 9.78% in terms of global cost.

The correlation of values commonly exists in auctions, which can be further exploited to improve revenue. However, the complex correlation structure makes it hard to manually design the optimal auction mechanism. Data-driven auction mechanisms, powered by machine learning, enable to design auctions directly from historical auction data, without relying on specific value distributions. In this work, we synthesize the learning-based auction and the characteristics of strategy-proofness in the correlated value setting, and propose a new auction mechanism, namely Conditional Auction Net (CAN). The CAN can encode the correlation of values into the rank score of each bidder, and further adjust the allocation rule to approach the optimal revenue. The property of strategy-proofness is guaranteed by encoding the game theoretical condition into the neural network structure. Furthermore, all operations in the designed auctions are differentiable to enable an end-to-end training paradigm. We also present CAN can provide a large solution space to adequately encode the correlation of values. Experimental results demonstrate that the proposed auction mechanism can represent almost any strategy-proof auction mechanism, and outperforms the auction mechanisms wildly used in the correlated value settings.

Long-context large language models (LLMs) inference is increasingly critical, motivating a number of studies devoted to alleviating the substantial storage and computational costs in such scenarios. Layer-wise skipping methods are promising optimizations but rarely explored in long-context inference. We observe that existing layer-wise skipping strategies have several limitations when applied in long-context inference, including the inability to adapt to model and context variability, disregard for sublayer significance, and inapplicability for the prefilling phase. This paper proposes AdaSkip, an adaptive sublayer skipping method specifically designed for long-context inference. AdaSkip adaptively identifies less important layers by leveraging on-the-fly similarity information, enables sublayer-wise skipping, and accelerates both the prefilling and decoding phases. The effectiveness of AdaSkip is demonstrated through extensive experiments on various long-context benchmarks and models, showcasing its superior inference performance over existing baselines.

The rapid growth of deep learning has created unprecedented demand for computing resources, while many small and enterprise-level clusters remain underutilized. Computing resource exchange platforms offer a solution by aggregating these idle resources. However, effective cluster-task matching depends on accurate performance prediction. Existing approaches, which decouple prediction from matching, often lead to suboptimal decisions due to misaligned objectives. We propose a Matching-Focused Cluster Performance Predictor (MFCP), an end-to-end framework that integrates performance prediction with task matching to improve decision accuracy and resource utilization. Unlike existing methods that prioritize prediction accuracy, MFCP minimizes decision regret by aligning the predictor’s loss with optimal matching objectives. To handle non-differentiable matching optimization, we use continuous relaxation and incorporate constraints via an interior-point method, ensuring meaningful gradients for training. For non-convex optimization, we approximate optimal decisions with gradient descent and estimate gradients using zeroth-order perturbation. Experiments show that MFCP consistently outperforms existing methods across different cluster environments and scales, achieving lower matching regret and higher resource utilization.

E-bikes (EBs) are a key transportation mode in urban area, especially for couriers of delivery platforms, but underdeveloped EB systems can hinder courier's productivity due to limited battery capacity. Battery-swapping stations address this issue by enabling riders to exchange depleted batteries for fully charged ones. However, managing supply and demand (SnD) imbalances at these stations has become increasingly complex. To address this, we introduce a new approach that formulates the Battery-Swapping Problem (BSP) as a discrete-time Markov Decision Process (MDP) to capture the dynamics of SnD imbalances. Building on it, we propose a Wasserstein-enhanced Proximal Policy Optimization (W-PPO) algorithm, which integrates Wasserstein distance with reinforcement learning to improve the robustness against uncertainty in forecasting SnD. W-PPO provides a BSP-specific, accurate loss function that reflects reward variations between two policies under real-world simulation. The algorithm’s effectiveness is assessed using key metrics: Shared Battery Utilization Ratio (SBUR) and Battery Supply Ratio (BSR). Simulations on real-world datasets show that W-PPO achieves a 30.59% improvement in SBUR and a 16.09% increase in BSR ensures practical applicability. By optimizing battery utilization and improving EB delivery systems, this work highlights the potential of AI for creating efficient and sustainable urban transportation solutions.

The online advertising platform serves as the intermediary between advertisers and users to facilitate the product trading process and generate profits. While the vitality of both the user and advertiser community is crucial to the long-term development of platforms, compared with the enduring efforts to improve user experience, little attention has been given to methods for attracting or retaining advertisers. To address this oversight, in this work, we investigate the first intelligent solution to the advertiser retention problem in online advertising. Motivated by advertiser surveys and data analytics, we first define a set of short-term ad performance metrics as the key retention metrics we need to optimize for advertisers. In consideration of the desirable properties of a retention framework, we propose an Auto-Coupon module to distribute impression-level virtual coupons to selected advertisers during the bidding process. We decompose the resulted retention optimization problem into two stages, and adopt feedback control as well as reinforcement learning methods to realize personalized coupon distribution. The offline experiments demonstrate the effectiveness of our methods in boosting the ad performance of churning advertisers, and the large-scale online A/B test further justifies the improvement in advertisers' willingness to stay in the platform.

The demand for machine learning (ML) model training on edge devices is escalating due to data privacy and personalized service needs. However, we observe that current on-device model training is hampered by the under-utilization of on-device data, due to low training throughput, limited storage and diverse data importance. To improve data resource utilization, we propose a two-stage data selection framework {\sf Titan} to select the most important data batch from streaming data for model training with guaranteed efficiency and effectiveness. Specifically, in the first stage, {\sf Titan} filters out a candidate dataset with potentially high importance in a coarse-grained manner.In the second stage of fine-grained selection, we propose a theoretically optimal data selection strategy to identify the data batch with the highest model performance improvement to current training round. To further enhance time-and-resource efficiency, {\sf Titan} leverages a pipeline to co-execute data selection and model training, and avoids resource conflicts by exploiting idle computing resources. We evaluate {\sf Titan} on real-world edge devices and three representative edge computing tasks with diverse models and data modalities. Empirical results demonstrate that {\sf Titan} achieves up to $43\%$ reduction in training time and $6.2\%$ increase in final accuracy with minor system overhead, such as data processing delay, memory footprint and energy consumption.

In the field of auction design, leveraging deep learning to solve optimal auctions from sampled data has become a promising direction. However, real-world contexts often involve uncertain data, which would severely affect the auction performance, but it is lacking consideration in existing works. To address this challenge, we incorporate these uncertainties into auction design metrics, and frame this challenge as a robust data-driven auction design problem. To solve this problem, we first propose the GAT method, where we introduce the process of problem relaxation and transformation to address the non-differentiable variable presented in the original problem, and further propose an adversarial training algorithm to solve the mini-max problem after transformation. Moreover, to obtain moderately robust auctions, we propose two methods to select the robust coefficient, which provides guidance and insights for selecting robust auctions based on generalization and performance metrics. Finally, with the insights from the GAT method, we further propose the SAT method, where we employ a strict and unified IC constraint that extends from the GAT method, which provides strong IC guarantees and stable revenue in uncertain environments. Experiments on both constructed and real-world datasets show that our robust methods effectively improve the performance of auctions in terms of revenue and IC guarantees.

xisting online advertising systems generate high-quality ad recommendations through a complex online serving pipeline whenever a user's ad request arrives. However, our analyses on the display advertising system in Taobao show that this paradigm could lead to an inefficient utilization of computational resources. In this work, we propose an intelligent computation recycling framework called ComRecycle, which caches and reuses unexposed ad sets for repetitive ad requests to improve the computational resource utilization. We introduce fine-grained computation recycling strategies, and formulate the computation recycling decision as an online constrained optimization problem. Therefore, ComRecycle can achieve the goal of reducing computation costs while guaranteeing the same level of recommendation performance. Extensive offline experiments validate the correctness and effectiveness of ComRecycle. Our online A/B testing demonstrates that ComRecycle can save over 20% computational resources while maintaining the same system performance as the baseline.

As AI evolves, collaboration among heterogeneous models helps overcome data scarcity by enabling knowledge transfer across institutions and devices.Traditional Federated Learning (FL) only supports homogeneous models, limiting collaboration among clients with heterogeneous model architectures.To address this, Heterogeneous Federated Learning (HtFL) methods are developed to enable collaboration across diverse heterogeneous models while tackling the data heterogeneity issue at the same time.However, a comprehensive benchmark for standardized evaluation and analysis of the rapidly growing HtFL methods is lacking.Firstly, the highly varied datasets, model heterogeneity scenarios, and different method implementations become hurdles to making easy and fair comparisons among HtFL methods.Secondly, the effectiveness and robustness of HtFL methods are under-explored in various scenarios, such as the medical domain and sensor signal modality.To fill this gap, we introduce the first Heterogeneous Federated Learning Library (HtFLlib), an easy-to-use and extensible framework that integrates multiple datasets and model heterogeneity scenarios, offering a robust benchmark for research and practical applications.Specifically, HtFLlib integrates (1) 12 datasets spanning various domains, modalities, and data heterogeneity scenarios; (2) 40 model architectures, ranging from small to large, across three modalities;(3) a modularized and easy-to-extend HtFL codebase with implementations of 10 representative HtFL methods; and (4) systematic evaluations in terms of accuracy, convergence, computation costs, and communication costs.We emphasize the advantages and potential of state-of-the-art HtFL methods and hope that HtFLlib will catalyze advancing HtFL research and enable its broader applications.The code is released at https://github.com/TsingZ0/HtFLlib.

Online advertising has become a core revenue driver for internet industry, with ad auctions playing a crucial role in ensuring platform revenue and advertiser incentives. Classical auction mechanisms, such as GSP, rely on the independent CTR assumption and fail to account for the interplay among the displayed items, also called as externalities in economics. Recent advancements in learning-based auctions enable the encoding of high-dimensional contextual features. However, existing methods are limited by the ''prediction-before-allocation'' design paradigm, which models set-level externalities within candidate ads and fails to consider the context of the final allocation, leading to suboptimal results. In this work, we introduce Contextual Generative Auction (CGA), a novel framework that incorporates permutation-level externalities in multi-slot ad auctions. Built on the structure of our theoretically derived optimal auction, CGA decouples the optimization of allocation and payment. We construct an autoregressive generative model for allocation, and reformulate incentive compatibility (IC) constraint into minimizing ex-post regret that supports gradient computation, enabling end-to-end learning of the optimal payment rule. Extensive offline and online experiments demonstrate that CGA significantly enhances platform revenue and CTR compared to existing methods, and effectively approximates the optimal auction with nearly maximal revenue and minimal regret.

Broad adoption of Online Travel Platforms (OTPs) has led to increasing interest in accurately predicting users' hotel purchase behavior, with price being a key influencer in user decision-making and receiving significant focus. In examining the hotel purchasing process, we identify a pervasive trend that users make extensive price comparisons before making decisions. Existing research primarily focuses on a hotel's own price, neglecting the complex dynamics of market-driven price competition. In this paper, we propose the concept of Marketplace-oriented Hotel Price Competitiveness (MHPC) to model a hotel's pricing competitiveness within the marketplace. Being independent of specific user preferences, MHPC can be applied to and improve various downstream operations in the online hotel industry, such as hotel ranking and pricing, ultimately benefiting hoteliers, users, and OTPs. Furthermore, a novel Hotel Price Competitiveness-aware Purchase Prediction Model (HP3M) is constructed by incorporating MHPC and demand dynamics into a multi-task learning framework, featuring three distinct submodules to encompass the tri-dimensional facets of MHPC. Extensive offline and online experiments demonstrate HP3M's effectiveness in predicting hotel purchase probability and enhancing the performance of hotel ranking and pricing compared to the state-of-the-art methods. HP3M has been fully deployed on Fliggy, a leading OTP in China, serving thousands of hoteliers and tens of millions of users.

In creator economy, the online platform posts contract to incentivize creators for high-quality content. The creators can use human effort or Generative Artificial Intelligence (GenAI) to assist them to create content for rewards. In this work, we identify that the existing contract suffers from GenAI-Induced Effort Degradation, where creators may not try their best to create high-quality content, but instead turn to GenAI to save effort and extract additional reward. Our results show that GenAI-induced effort degradation arises from failing to provide the same profit for the creators generating the same quality content. With this observation, we design the contract for creator economy in the era of GenAI as a classical contract for human content and a reward for the GenAI content which depends on the estimation of the human effort cost required to achieve GenAI's content quality. To overcome the curse of dimensionality in learning the optimal contract that maximizes platform profit with a high-quality content guarantee, we design an adaptive action pruning method that gradually filters out contracts resulting in low quality. Simulation experiments on synthetic data demonstrate the effectiveness of our approach.

Small language models (SLMs) support efficient deployments on resource-constrained edge devices, but their limited capacity compromises inference performance. Retrieval-augmented generation (RAG) is a promising solution to enhance model performance by integrating external databases, without requiring intensive on-device model retraining. However, large-scale public databases and user-specific private contextual documents are typically located on the cloud and the device, respectively, while existing RAG implementations are primarily centralized. To bridge this gap, we propose DRAGON, a distributed RAG framework to enhance on-device SLMs through both general and personal knowledge without the risk of leaking document privacy. Specifically, DRAGON decomposes multi-document RAG into multiple parallel token generation processes performed independently and locally on the cloud and the device, and employs a newly designed Speculative Aggregation, a dual-side speculative algorithm to avoid frequent output synchronization between the cloud and device. A new scheduling algorithm is further introduced to identify the optimal aggregation side based on real-time network conditions. Evaluations on real-world hardware testbed demonstrate a significant performance improvement of DRAGON—up to 1.9X greater gains over standalone SLM compared to the centralized RAG, substantial reduction in per-token latency, and negligible Time to First Token (TTFT) overhead.

Large language model (LLM) decoding suffers from high latency due to fragmented execution across operators and heavy reliance on off-chip memory for data exchange and reduction. This execution model limits opportunities for fusion and incurs significant memory traffic and kernel launch overhead. While modern architectures such as NVIDIA Hopper provide distributed shared memory and low-latency intra-cluster interconnects, they expose only low-level data movement instructions, lacking structured abstractions for collective on-chip communication. To bridge this software-hardware gap, we introduce two cluster-level communication primitives, ClusterReduce and ClusterGather, which abstract common communication patterns and enable structured, high-speed data exchange and reduction between thread blocks within a cluster, allowing intermediate results to be on-chip without involving off-chip memory. Building on these abstractions, we design ClusterFusion, an execution framework that schedules communication and computation jointly to expand operator fusion scope by composing decoding stages such as QKV Projection, Attention, and Output Projection into a single fused kernels. Evaluations on H100 GPUs show that ClusterFusion outperforms state-of-the-art inference frameworks by $1.61\times$ on average in end-to-end latency across different models and configurations.

Online continual learning (CL) is becoming a mainstream paradigm to learn incrementally from task streams without forgetting previously learned knowledge. However, the current online CL primarily focuses on learning performance, such as avoiding catastrophic forgetting, neglecting the critical demands of system performance, such as real-time inference. As a result, the performance of real-time inference in online CL degrades significantly due to frequent data distribution variations and time-consuming model adaptation. In this work, we propose ELITE, an online CL framework with device-cloud collaboration, to realize on-device real-time inference on time-varying task streams with performance guarantee. To realize on-device real-time inference in online CL, ELITE features a new design of the model zoo comprising various pre-trained models with the assistance of the cloud, and proposes a task-oriented on-device model selection to quickly retrieve the best-fit models instead of performing time-consuming model retraining. To prevent performance degradation on new tasks not available in the cloud, we introduces a latency-aware on-device model fine-tuning strategy to adapt to new tasks with an accuracy-latency trade-off, and dynamically updates the model zoo to enhance ELITE. Extensive evaluations on five real-world datasets have been conducted, and the results demonstrate that ELITE consistently outperforms the state-of-art solutions, improving the accuracy by 16.3% on average and reducing the response latency by up to 1.98 times.

ABSTRACT Context The rise of artificial intelligence of things (AloT) has enabled smart cities and industries, and UAV‐assisted edge computing networks are an important technology to support the above scenarios. UAV‐assisted refers to leveraging UAVs as a dynamic, flexible infrastructure to assist edge network data processing and communication tasks. Multiple UAVs can use their own resources, and collaborate edge servers to train artificial intelligence (Al) models. Objective Compared with cloud‐based collaborative computing scenarios, UAV‐assisted edge collaborative learning can reduce training and inference delays and improve user satisfaction. However, UAV‐assisted edge networks scenario brings new challenges in terms of transmission burden and energy consumption. Method This paper proposes a prototype‐based joint optimization and training software system. The system consists of an optimization module and a training module. The optimization module first models an optimization problem including energy consumption and prototype error. Then it solves the optimization problem by problem transformation and plans the location of each UAV given the objects' position. After UAVs fly to the designated area and complete data collection, UAVs and the edge server train a model according to the proposed prototype‐based collaborative training module. Our training module enables multiple UAVs and an edge server to collaboratively train a model by lightweight prototype transmission and prototype aggregation. We also prove the convergence of the proposed collaborative training method. Results Results show our method reduces prototype error and energy consumption by at least 12.31% and improves model accuracy by 3.62% with a little communication burden. Conclusion Finally, we verify system performance through experiments.

Federated Foundation Models (FedFMs) represent a distributed learning paradigm that fuses general competences of foundation models as well as privacy-preserving capabilities of federated learning. This combination allows the large foundation models and the small local domain models at the remote clients to learn from each other in a teacher-student learning setting. This paper provides a comprehensive summary of the ten challenging problems inherent in FedFMs, encompassing foundational theory, utilization of private data, continual learning, unlearning, Non-IID and graph data, bidirectional knowledge transfer, incentive mechanism design, game mechanism design, model watermarking, and efficiency. The ten challenging problems manifest in five pivotal aspects: “Foundational Theory,” which aims to establish a coherent and unifying theoretical framework for FedFMs. “Data,” addressing the difficulties in leveraging domain-specific knowledge from private data while maintaining privacy; “Heterogeneity,” examining variations in data, model, and computational resources across clients; “Security and Privacy,” focusing on defenses against malicious attacks and model theft; and “Efficiency,” highlighting the need for improvements in training, communication, and parameter efficiency. For each problem, we offer a clear mathematical definition on the objective function, analyze existing methods, and discuss the key challenges and potential solutions. This in-depth exploration aims to advance the theoretical foundations of FedFMs, guide practical implementations, and inspire future research to overcome these obstacles, thereby enabling the robust, efficient, and privacy-preserving FedFMs in various real-world applications.

Large language models (LLMs) exhibit remarkable capabilities in natural language understanding and generation. However, the accuracy of the inference depends deeply on the contexts of queries, especially for personal services. Abundant mobile sensing data collected by sensors embedded in smart devices can proactively capture real-time user contexts. However, raw sensing data are low-quality (e.g., existing missing data and data redundancy) and are incapable of providing accurate contexts. In this work, we present ConGen, a user context generation framework for LLMs, aiming at prompting users’ contexts through their implicit mobile sensing information. ConGen integrates two components: refined data completion and multi-granularity context compression. Specifically, the refined data completion couples data-centric feature selection by leveraging the eXplainable AI (XAI) method into the data imputation model to generate fewer but more informative features for efficient and effective context generation. Additionally, we implement multi-granularity context compression, reducing timestep- and context-level data redundancy while further elevating context quality. Experiment results show that ConGen can generate more accurate context, surpassing competitive baselines by 1.3%-8.3% in context inference on all four datasets. Moreover, context compression significantly reduces redundancy to$1/70\sim 1/40$of the original data amount, and further improves the context accuracy. Finally, the enhanced performance of LLMs, as demonstrated by both quantitative and qualitative evaluations of prompting ConGen-generated user contexts, underscores the effectiveness of ConGen.

Federated learning (FL) can be implemented in large-scale wireless networks in a hierarchical way, introducing edge servers as relays between the cloud server and devices. These devices are dispersed within multiple clusters coordinated by edges. However, the devices are typically mobile users with unpredictable trajectories, and the impact of their mobility on the model training process is not well-studied. In this work, we propose a newMobIlity-Driven feDeratedLEarning framework, namely MIDDLE. MIDDLE addresses unbalanced model updates by capitalizing on model aggregation opportunities on mobile devices due to their mobility across edges. It consists of two components: on-device model aggregation, which aggregates models from different edges carried by mobile devices as they move across edges, and in-edge device selection, adjusting the current edge optimization direction through careful device selection. Theoretical analysis emphasizes that on-device model aggregation can reduce bias in model updating on edges and the cloud, thereby accelerating the FL model convergence. Building on this analysis, we introduce on-device global control averaging, modifying the training process on mobile devices and extending MIDDLE into$\text{MIDDLE}^{+}$. Extensive experimental results validate that MIDDLE and$\text{MIDDLE}^{+}$can reduce the time steps to reach the target accuracy by 19.44% and 20.37% at least, respectively.

Hierarchical Federated Learning (HFL) is a practical implementation of federated learning in mobile edge computing, employing edge servers as intermediaries between mobile devices and the cloud server for device coordination and cloud communication. However, the devices are usually mobile users with unpredictable mobile trajectories and statistical heterogeneity, leading to the edge models optimized along dynamic edge data distribution directions and further resulting in instability and slow convergence of the global model. In this work, we propose a Mobility-Aware deviCe sampling algorithm in HFL, namely MACH, which can dynamically maintain the device sampling strategy at each edge to accelerate the convergence of the global model. First, we analyze the convergence bound of HFL with mobile devices under arbitrary device sampling probabilities. Based on this convergence bound, we formalize the sampling optimization problem for mobility-aware device sampling, aiming to minimize the convergence error under time-averaged cost constraints, while taking the limited device-edge wireless channel capacity into account. Next, we introduce the MACH algorithm, consisting of two underlying components: experience updating and edge sampling. Experience updating utilizes an upper confidence bound method to estimate device statistical information online, and edge sampling customizes a sampling strategy on each edge based on the estimated device statistical information. Finally, extensive experimental results through real-world mobile device trajectories validate that MACH can reduce the time required to achieve a target accuracy by 25.00% - 56.86%.

To bring the great power of modern DNNs into mobile computing and distributed systems, current practices primarily employ one of the two learning paradigms: cloud-based learning or on-device learning. Despite their distinct advantages, neither of these two paradigms could effectively deal with highly dynamic edge environments reflected in quick data distribution shifts and on-device resource fluctuations. In this work, we propose Nebula, an edge-cloud collaborative learning framework to enable rapid model adaptation for changing edge environments. To achieve this, we first propose a new block-level model decomposition scheme to decompose the large cloud model into multiple combinable modules. With this design, we can agilely derive personalized sub-models with compact sizes for edge devices, and quickly aggregate the updated sub-models to integrate new knowledge learned on the edge into the cloud model. We further propose an end-to-end learning framework that incorporates the modular model design into an efficient model adaptation pipeline, including an offline on-cloud model prototyping and training stage, and an online edge-cloud collaborative adaptation stage. Extensive experiments demonstrate that Nebula improves model performance (e.g., 18.89% accuracy increase) and resource efficiency (e.g., 7.12 × communication cost reduction) in adapting models to dynamic edge environments.

Online advertising platforms leverage a two-stage auction architecture to deliver personalized ads to users with low latency. The first stage efficiently selects a small subset of promising candidates out of the complete pool of ads. In the second stage, an auction is conducted within the subset to determine the winning ad for display, using click-through-rate predictions from the second-stage machine learning model. In this work, we investigate the online learning process of the first-stage subset selection policy, while ensuring game-theoretic properties in repeated two-stage ad auctions. Specifically, we model the problem as designing a combinatorial bandit mechanism with a general reward function, as well as additional requirements of truthfulness and individual rationality (IR). We establish an O(T) regret lower bound for truthful bandit mechanisms, which demonstrates the challenge of simultaneously achieving allocation efficiency and truthfulness. To circumvent this impossibility result, we introduce truthful α-approximation oracles and evaluate the bandit mechanism through α-approximation regret. Two mechanisms are proposed, both of which are ex-post truthful and ex-post IR. The first mechanism is an explore-then-commit mechanism with regret O(T2/3 ), and the second mechanism achieves an improved O(log T /ΔΦ2) regret where ΔΦ is a distribution-dependent gap, but requires additional assumptions on the oracles and information about the strategic bidders.

In online advertising, existing auto-bidding strategies for bid shading mainly adopt the approach of first predicting the winning price distribution and then calculating the optimal bid. However, the winning price information available to the Demand Side Platforms (DSPs) is extremely limited, and the associated uncertainties make it challenging for DSPs to accurately estimate winning price distribution. To address this challenge, we conducted a comprehensive analysis of the process by which DSPs obtain winning price information, and abstracted two types of uncertainties from it: known uncertainty and unknown uncertainty. Based on these uncertainties, we proposed two levels of robust bidding strategies: Robust Bidding for Censorship (RBC) and Robust Bidding for Distribution Shift (RBDS), which offer guarantees for the surplus in the worst-case scenarios under uncertain conditions. Experimental results on public datasets demonstrate that our robust bidding strategies consistently enable DSPs to achieve superior surpluses, both on test sets and under worst-case conditions.

Vertical federated learning (VFL) is an emerging collaborative machine learning paradigm to facilitate the utilization of private features distributed across multiple parties. During the inference process of VFL, the involved parties need to upload their local embeddings to be aggregated for the final prediction. Despite its remarkable performances, the inference process of the current VFL system is vulnerable to the strategic behavior of involved parties, as they could easily change the uploaded local embeddings to exert direct influences on the prediction result. In a representative case study of federated recommendation, we find the allocation of display opportunities to be severely disrupted due to the parties' preferences in display content. In order to elicit the true local embeddings for VFL system, we propose a distribution-based penalty mechanism to detect and penalize the strategic behaviors in collaborative inference. As the key motivation of our design, we theoretically prove the power of constraining the distribution of uploaded embeddings in preventing the dishonest parties from achieving higher utility. Our mechanism leverages statistical two-sample tests to distinguish whether the distribution of uploaded embeddings is reasonable, and penalize the dishonest party through deactivating her uploaded embeddings. The resulted mechanism could be shown to admit truth-telling to converge to a Bayesian Nash equilibrium asymptotically under mild conditions. The experimental results further demonstrate the effectiveness of the proposed mechanism to reduce the dishonest utility increase of strategic behaviors and promote the truthful uploading of local embeddings in inferences.

In modern mobile applications, users frequently encounter various new contexts, necessitating on-device continual learning (CL) to ensure consistent model performance. While existing research predominantly focused on developing lightweight CL frameworks, we identify that data scarcity is a critical bottleneck for on-device CL. In this work, we explore the potential of leveraging abundant cloud-side data to enrich scarce on-device data, and propose a private, efficient and effective data enrichment framework Delta. Specifically, Delta first introduces a directory dataset to decompose the data enrichment problem into device-side and cloud-side sub-problems without sharing sensitive data. Next, Delta proposes a soft data matching strategy to effectively solve the device-side sub-problem with sparse user data, and an optimal data sampling scheme for cloud server to retrieve the most suitable dataset for enrichment with low computational complexity. Further, Delta refines the data sampling scheme by jointly considering the impact of enriched data on both new and past contexts, mitigating the catastrophic forgetting issue from a new aspect. Comprehensive experiments across four typical mobile computing tasks with varied data modalities demonstrate that Delta could enhance the overall model accuracy by an average of 15.1%, 12.4%, 1.1% and 5.6% for visual, IMU, audio and textual tasks compared with few-shot CL, and consistently reduce the communication costs by over 90% compared to federated CL.

Two-stage bandit-based algorithms have found widespread application in modern online platforms, offering a balance between cost and accuracy. The initial stage involves coarse filtering of a small candidate set of promising items from a large corpus, while the subsequent stage refines the selection and presents a single item to the user. In this work, to the best of our knowledge, we for the first time undertake a theoretical analysis of the two-stage stochastic multi-armed bandit problem. Specifically, we model the two-stage bandit problem as a two-stage online optimization, and conduct a theoretical analysis. We demonstrate that while the optimization objective of the first stage may seem intuitive, it is, in fact, non-trivial. We devise a proxy optimization objective, emphasize the importance of a carefully designed exploration strategy, and establish the theoretical analysis for the application of Upper Confidence Bound (UCB)-based algorithms in the first stage. Furthermore, we provide a regret analysis of the proposed two-stage bandit algorithm, demonstrating a gap-dependent upper bound of [EQUATION], where [EQUATION] is the largest reward gap, and a gap-independent lower bound of [EQUATION], where n represents the horizon.

Considering limited on-device resources, current practices are attempting to deploy a system-level mixture-of-experts (MoE)-based foundation LLM shared by multiple mobile apps on a device to support mobile intelligence. However, mobile apps are hard to customize their services that require tuning adapters associated with the LLM using private in-app data. The difficulty arises due to both the limited on-device resources and the restricted control that apps have over the foundation LLM. To address this issue, in this work, we propose LiteMoE, a novel proxy submodel tuning framework that supports mobile apps to efficiently fine-tune customized adapters on devices using proxy submodels. The key technique behind LiteMoE is a post-training submodel extraction method, whereby without additional re-training, we can identify and reserve critical experts, match and merge moderate experts, to extract a lightweight and effective proxy submodel from the foundation LLM for a certain app. We implemented a prototype of LiteMoE and evaluated it over various MoE-based LLMs and mobile computing tasks. The results show that with LiteMoE, mobile apps are able to fine-tune customized adapters on resource-limited devices, achieving 12.7% accuracy improvement and 6.6× memory reduction compared with operating the original foundation LLM.

A transformation from second-price auctions (SPA) to first-price auctions (FPA) has been observed in online advertising. The consequential coexistence of mixed FPA and SPA auction types has further led to the problem of mixed censorship, making bid landscape forecasting, the prerequisite for bid shading, more difficult. Our key insight is that the winning price (WP) under SPA can be effectively transferred to FPA scenarios if they share similar user groups, advertisers, and bidding environments. The full utilization of winning price under mixed censorship can effectively alleviate the FPA censorship problem and improve the performance of winning price prediction (aka. bid landscape forecasting). In this work, we propose a Multi-task Mixed Censorship Predictor (MMCP) that utilizes multi-task learning (MTL) to leverage the WP under SPA as supervised information for FPA. A Double-gate Mixture-of-Experts architecture has been proposed to alleviate the negative transfer problem of multi-task learning in our context. Furthermore, several auxiliary modules including the first-second mapping module and adaptive censorship loss function have been introduced to integrate MTL and winning price prediction. Extensive experiments on two real-world datasets demonstrate the superior performance of the proposed MMCP compared with other state-of-the-art FPA models under various performance metrics. The implementation of the code is available on github (https://github.com/Currycurrycurry/MMCP/).

As a bid optimization algorithm in the first-price auction (FPA), bid shading is used in online advertising to avoid overpaying for advertisers. However, we find the bid shading approach would incur serious local optima. This effect prevents the advertisers from maximizing long-term surplus. In this work, we identify the reasons behind this local optima - it comes from the lack of winning price information, which results in the conflict between short-term surplus and the winning rate prediction model training, and is further propagated through the over-exploitation of the model. To rectify this problem, we propose a cost-effective active learning strategy, namely CeBE, for bid exploration. Specifically, we comprehensively consider the uncertainty and density of samples to calculate exploration utility, and use a 2+ε-approximation greedy algorithm to control exploration costs. Instead of selecting bid prices that maximize the expected surplus for all bid requests, we employ the bid exploration strategy to determine the bid prices. By trading off a portion of surplus, we can train the model using higher-quality data to enhance its performance, enabling the system to achieve a long-term surplus. Our method is straightforward and applicable to real-world industrial environment: it is effective across various categories of winning rate prediction models. We conducted empirical studies to validate the efficacy of our approach. In comparison to the traditional bid shading system, CeBE can yield an average surplus improvement of 8.16% across various models and datasets.

In online advertising, advertisers participate in ad auctions to acquire ad opportunities, often by utilizing auto-bidding tools provided by demand-side platforms (DSPs). The current auto-bidding algorithms typically employ reinforcement learning (RL). However, due to safety concerns, most RL-based auto-bidding policies are trained in simulation, leading to a performance degradation when deployed in online environments. To narrow this gap, we can deploy multiple auto-bidding agents in parallel to collect a large interaction dataset. Offline RL algorithms can then be utilized to train a new policy. The trained policy can subsequently be deployed for further data collection, resulting in an iterative training framework, which we refer to as iterative offline RL. In this work, we identify the performance bottleneck of this iterative offline RL framework, which originates from the ineffective exploration and exploitation caused by the inherent conservatism of offline RL algorithms. To overcome this bottleneck, we propose Trajectory-wise Exploration and Exploitation (TEE), which introduces a novel data collecting and data utilization method for iterative offline RL from a trajectory perspective. Furthermore, to ensure the safety of online exploration while preserving the dataset quality for TEE, we propose Safe Exploration by Adaptive Action Selection (SEAS). Both offline experiments and real-world experiments on Alibaba display advertising platform demonstrate the effectiveness of our proposed method.

Federated learning is a new distributed machine learning framework, where numerous heterogeneous clients collaboratively train a model without sharing training data. In this work, we consider a practical and ubiquitous issue when deploying federated learning in mobile environments: intermittent client availability, where the set of eligible clients may change during the training process. Such intermittent client availability would seriously deteriorate the performance of the classical federated averaging algorithm (FedAvg). Thus, we propose a simple distributed nonconvex optimization algorithm, called federated latest averaging (FedLaAvg), which leverages the latest gradients of all clients, even when the clients are not available, to jointly update the global model in each iteration. Our theoretical analysis shows that FedLaAvg achieves guaranteed convergence and a sublinear speedup with respect to the total number of clients. We implement FedLaAvg along with several baselines and evaluate them over the benchmarking MNIST and Sentiment140 data sets. The evaluation results demonstrate that FedLaAvg achieves more stable training than FedAvg in both convex and nonconvex settings and reaches a sublinear speedup. Source code and online supplement are available at the IJOC GitHub site ( http://dx.doi.org/10.1287/ijoc.2022.0057.cd , https://github.com/INFORMSJoC/2022.0057 ). History: Accepted by Ram Ramesh, Area Editor for Data Science & Machine Leaning. Funding: This work was supported by the National Key R&D Program of China [Grant 2022ZD0119100], the National Natural Science Foundation of China (NSFC) [Grants 61972252, 61972254, 62072303, 62025204, 62132018, 62202296, and 62202297], the Alibaba Innovation Research (AIR) Program, and the Tencent Rhino Bird Key Research Project. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0057 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0057 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Compositional Zero-Shot Learning (CZSL) has been applied to various scenarios, including scene understanding, visual-language representation, and domain adaptation. Despite numerous endeavours and significant advancements, the crucial issues of fuzzy conceptualization of visual attributes and insufficient inter-class connectivity, have remained insufficiently addressed. To address these issues, we propose Learning Visual Attributes Representation for Compositional Zero-Shot Learning (LVAR-CZSL), which has the ability to learn visual attributes and inter-class dependencies. LVAR-CZSL is mainly composed of two key components: the Visual Attribute Representation Module (VARM) and the Connected Learning Module (CLM). Specifically, VARM extracts detailed attributes and object visual features from global visual features, resolving the issue of fuzzy visual attribute concepts. Moreover, CLM endows LVAR-CZSL with the capability to perceive connectivity between different attributes and objects, effectively enhancing inter-class connectivity. To establish a close connection between VARM and CLM and minimize the gap between image and text features, we introduce the composition-attribute-object Joint Scoring Function (JSF). Additionally, we propose Joint Loss Function (JLF) to optimize the learning process of VARM and CLM. The experiment results on four datasets show that LVAR-CZSL achieves state-of-the-art performance. The code is available athttps://github.com/mxjmxj1/LVAR-CZSL.

Mobile health (mHealth) applications, benefiting from mobile computing, have generated numerous mHealth data. However, they are dispersed across isolated devices, which hinders discovering insights underlying the aggregated data. Considering the online characteristics of mHealth, in this work, we present the first online dataVAluation andPricing mechanism, namely VAP, to incentive users to contribute mHealth data for machine learning (ML) tasks in mHealth systems. Under the Bayesian framework, we propose a new metric based on the concept of entropy to calculate data valuation during model training in an online manner. In proportion to the data valuation, we then determine payments as compensations for users to contribute their data. We formulate this pricing problem as a contextual multi-armed bandit with the goal of profit maximization and propose a new algorithm based on the characteristics of pricing. Furthermore, to tackle the budget constraint, we incorporate a two-stage multi-armed bandit with a knapsack method. We also extend VAP to advanced ML models by computing the entropy on the prediction space. Finally, we have evaluated VAP on two real-world mHealth data sets. Evaluation results show that VAP outperforms the state-of-the-art data valuation and pricing mechanisms in terms of computational complexity and extracted profit.

Data is becoming an important kind of commercial good, and many online marketplaces are set up to facilitate the exchange of data. However, most existing data market models and the corresponding pricing mechanisms fail to capture the unique economic properties of data. In this paper, we first characterize the new features of IoT data as a digital commodity, and then present a market model for IoT data exchange, from an information design perspective. We further propose a family of data pricing mechanisms for maximizing revenue under different information asymmetry settings. OurMSimplemechanism extracts full surplus for the model with one type of buyer in the market. When multiple types of buyers coexist, ourMGeneralmechanism optimally solves the problem of revenue maximization by formulating it as a convex program with polynomial size. For a more practical setting where buyers have bounded rationality, we design theMPracticalmechanism with a tight logarithmic approximation ratio. We also show that the seller can further increase revenue by offering a free data trial to the buyers. We evaluate our pricing mechanisms on a real-world ambient sound dataset. Evaluation results demonstrate that our pricing mechanisms achieve good performance and approach the optimal revenue.

Machine learning (ML) models have been deployed in mobile networks to deal with massive data from different layers to enable automated network management. To overcome high communication cost and severe privacy concerns of centralized ML, federated learning (FL) has been proposed to achieve distributed ML among numerous networked devices. While the computation and communication limitation has been widely studied, the impact of limited storage of mobile devices on the performance of FL is still not explored. Without an effective data selection policy to filter the massive streaming networked data on devices, classical FL can suffer from much longer model training time ($4\times$) and dramatic inference accuracy reduction ($7\%$), observed in our experiments. In this work, we take the first step to consider the online data selection for FL with limited on-device storage. We first define a new data valuation metric for data selection in FL with theoretical guarantee for simultaneously accelerating model convergence and enhancing final accuracy. We further design ODE, an Online Data sElection framework for FL, to coordinate networked devices to store valuable data samples collaboratively. Experimental results on one industrial dataset and three public datasets show the remarkable advantages of ODE over the state-of-the-art approaches. Particularly, on the industrial dataset, ODE achieves as high as$2.5\times$speedup of training time and$6\%$increase in final accuracy, and is robust to various factors in practical environments.

Digital advertising constitutes one of the main revenue sources for online platforms. In recent years, some advertisers tend to adopt auto-bidding tools to facilitate advertising performance optimization, making the classical utility maximizer model in auction theory not fit well. Some recent studies proposed a new model, called value maximizer, for auto-bidding advertisers with return-on-investment (ROI) constraints. However, the model of either utility maximizer or value maximizer could only characterize partial advertisers in real-world advertising platforms. In a mixed environment where utility maximizers and value maximizers coexist, the truthful ad auction design would be challenging since bidders could manipulate both their values and affiliated classes, leading to a multi-parameter mechanism design problem. In this work, we address this issue by proposing a payment rule which combines the corresponding ones in classical VCG and GSP mechanisms in a novel way. Based on this payment rule, we propose a truthful auction mechanism with an approximation ratio of 2 on social welfare, which is close to the lower bound of at least 5/4 that we also prove. The designed auction mechanism is a generalization of VCG for utility maximizers and GSP for value maximizers.

Online bidding and auction are crucial aspects of the online advertising industry. Conventionally, there is only one slot for ad display and most current studies focus on it. Nowadays, multi-slot display advertising is gradually becoming popular where many ads could be displayed in a list and shown as a whole to users. However, multi-slot display advertising leads to different cost-effectiveness. Advertisers have the incentive to adjust bid prices so as to win the most economical ad positions. In this study, we introduce bid shading into multi-slot display advertising for bid price adjustment with a Multi-task End-to-end Bid Shading~(MEBS) method. We prove the optimality of our method theoretically and examine its performance experimentally. Through extensive offline and online experiments, we demonstrate the effectiveness and efficiency of our method, and we obtain a 7.01% lift in Gross Merchandise Volume, a 7.42% lift in Return on Investment, and a 3.26% lift in ad buy count.

Repeat consumption, such as re-purchasing items and re-listening songs, is a common scenario in daily life. To model repeat consumption, the repeat-aware recommendation has been proposed to predict which item will be re-interacted based on the user-item interactions. In this paper, we investigate various inherent characteristics to enhance the performance of repeat-aware recommendation. Specifically, we explore these characteristics from two aspects: one is from the temporal aspect where we consider the time interval relationship in user behavior sequence; the other is from the sequential aspect where we consider the sequential-level relationship. Our intuition is that both thetemporal pattern andsequential pattern reflect users' intentions of repeat consumption.

Online Travel Platforms (OTPs) have been working on improving their hotel Search & Ranking (S&R) systems that facilitate efficient matching between consumers and hotels. Existing OTPs focus on improving platform revenue. In this work, we take a first step in incorporating hotel merchants' objectives into the design of hotel S&R systems to achieve an incentive loop: the OTP tilts impressions and better-ranked positions to merchants with high service quality, and in return, the merchants provide better service to consumers. Three critical design challenges need to be resolved to achieve this incentive loop: Matthew Effect in the consumer feedback-loop, unclear relation between hotel service quality and performance, and conflicts between platform revenue and consumer experience.

With increasing concern over data privacy, split learning has become a widely used distributed machine learning paradigm in practice, where two participants (namely the non-label party and the label party) own raw features and raw labels respectively, and jointly train a model. Although no raw data is communicated between the two parties during model training, several works have demonstrated that data privacy, especially label privacy, is still vulnerable in split learning, and have proposed several defense algorithms against label attacks. However, the theoretical guarantee on the privacy preservation of these algorithms is limited. In this work, we propose a novel Private Split Learning Framework (PSLF). In PSLF, the label party shares only the gradients computed by flipped labels with the non-label party, which improves privacy preservation on raw labels, and meanwhile, we further design an extra sub-model from true labels to improve prediction accuracy. We also design a Flipped Multi-Label Generation mechanism (FMLG) based on randomized response for the label party to generate flipped labels. FMLG is proven differentially private and the label party could make a trade-off between privacy and utility by setting the DP budget. In addition, we design an upsampling method to further protect the labels against some existing attacks. We have evaluated PSLF over real-world datasets to demonstrate its effectiveness in protecting label privacy and achieving promising prediction accuracy.

Broad adoption of online travel platforms (OTPs) has led to increasing focus on hotel dynamic pricing algorithms, which directly affect the revenue of platform and hotels. Existing approaches, which directly model the correlation between price and occupancy, have limitations in improving occupancy prediction accuracy while ensuring interpretability for dynamic pricing. Moreover, these methods struggle to address the significant data sparsity issue in hotel pricing scenarios. To overcome these limitations, we propose a novel Causality-driven Hotel Dynamic Pricing Model (CANDY) that captures the essential causal relationship between price and occupancy, enhancing occupancy prediction accuracy and interpretability for dynamic pricing. Specifically, we decompose confounders into three orthogonal groups of factors: characteristic factors, competitive factors, and temporal factors, and design submodules to capture the features of each dimension. To address the treatment bias and sample imbalance issues faced by existing causal inference methods in hotel pricing scenarios, we propose a novel data augmentation method based on the monotonic relationship between price and occupancy, and further design a multi-task learning framework tailored to multi-valued treatment scenarios, simultaneously alleviating the data sparsity issue. Both offline and online experiments demonstrate the effectiveness of CANDY in occupancy prediction and dynamic pricing. CANDY has been successfully deployed to provide price suggestion service at Fliggy, a leading OTP in China, serving thousands of hotel operators.

Classic contextual combinatorial multi-armed bandit problems aim to maximize the expected cumulative joint reward in the long run, where a learner plays a set of arms (i.e., a super arm) with time-invariant linear rewards of context features in each round. However, in many real-world applications, linear-reward assumptions often fail to be satisfied and the environment is in general non-stationary, leading to low performance with the bandit models above. Existing works fail to deal with non-linear rewards in the non-stationary environment and the algorithmic challenge remains. In this paper, we initiate the study of a non-stationary neural contextual combinatorial bandit problem, where the reward function of each individual arm can be estimated by a deep neural network based on boundedness assumption and a time-variant reward mapping function. Furthermore, we design an algorithm NNCMAB, which dynamically partitions the context subspace into multiple subspaces and fits reward mapping functions for each subspace by neural networks such that only the models of related subspaces are re-trained when local environment changes happen. NNCMAB can provably achieve $\tilde{O}\left(T^{\frac{3}{4}}+\sqrt{T}N_{c}\right)$ regret, where T is the number of rounds, and $N_{c}$ is a parameter associated with the distribution change. Evaluation results under synthetic and real-world LastFM datasets show that NNCMAB significantly outperforms other state-of-the-art with both linear and non-linear individual rewards under non-stationary environments.

Federated learning (FL) in large-scale wireless networks is implemented in a hierarchical way by introducing edge servers as relays between the cloud server and devices, where devices are dispersed within multiple clusters coordinated by edges. However, the devices are usually mobile users with unpredictable mobile trajectories, whose effects on the model training process are still less studied. In this work, we propose a new MobIlity-Driven feDerated LEarning framework, namely MIDDLE in wireless networks, which can relieve unbalanced and biased model updates by leveraging the new model aggregation opportunities on mobile devices due to their mobility across edges. Specifically, mobile devices can have different models while traversing across edges, and adequately aggregate these models on the device. By theoretical analysis, we can show that this on-device model aggregation can reduce the bias of model updating on edges and cloud, and then accelerate the convergence of model training in FL. Then, we define a model similarity utility to measure the difference in gradient updates among various models, which guides the adaptive on-device model aggregation and in-edge device selection to facilitate the comprehensive information sharing between edges. Extensive experiment results validate that MIDDLE can achieve 1.51 × −6.85 × speedup on the model training, compared with the state-of-the-art model training approaches in hierarchical FL.

Automated bidding, an emerging intelligent decision-making paradigm powered by machine learning, has become popular in online advertising. Advertisers in automated bidding evaluate the cumulative utilities and have private financial constraints over multiple ad auctions in a long-term period. Based on these distinct features, we consider a new ad auction model for automated bidding: the values of advertisers are public while the financial constraints, such as budget and return on investment (ROI) rate, are private types. We derive the truthfulness conditions with respect to private constraints for this multi-dimensional setting, and demonstrate any feasible allocation rule could be equivalently reduced to a series of non-decreasing functions on budget. However, the resulted allocation mapped from these non-decreasing functions generally follows an irregular shape, making it difficult to obtain a closed-form expression for the auction objective. To overcome this design difficulty, we propose a family of truthful automated bidding auction with personalized rank scores, similar to the Generalized Second-Price (GSP) auction. The intuition behind our design is to leverage personalized rank scores as the criteria to allocate items, and compute a critical ROI to transforms the constraints on budget to the same dimension as ROI. The experimental results demonstrate that the proposed auction mechanism outperforms the widely used ad auctions, such as first-price auction and second-price auction, in various automated bidding environments.

Vertical federated learning (VFL) allows multiple clients with misaligned feature spaces to collaboratively accomplish the global model training. Applying VFL to high stakes decision scenarios greatly requires model interpretation for decision reliability and diagnosis. However, the feature discrepancy in VFL raises new issues for model interpretation in distributed setting: one is from the local-global perspective, where the local importance of features is not equal to the global importance; and the other is from the local-local perspective, where information asymmetry among clients causes difficulty in identifying overlapped features. In this work, we propose a new distributed Model Interpretation method for Vertical Federated Learning with feature discrepancy, namely MI-VFL. In particular, to deal with the local-global discrepancy, MI-VFL leverages the law of total probability to adjust the local importance of features and ensures the completeness of the selected features using adversarial game. To handle the local-local discrepancy, MI-VFL builds a federated adversarial learning model to efficiently identify the overlapped features once, rather than performing client-to-client intersections multiple times. We extensively evaluate MI-VFL on six synthetic datasets and five real-world datasets. The evaluation results reveal that MI-VFL can accurately identify the important features, suppress the overlapped features, and thus improve the model performance.

Powered by machine learning techniques, online advertising platforms have launched various automated bidding strategy services to facilitate intelligent decision-making for advertisers. However, advertisers experience heterogeneous advertising environments, and thus the unified bidding strategies widely used in both academia and industry suffer from severe unfairness issues, resulting in significant ad performance disparity among advertisers. In this work, to resolve the unfairness issue and improve the overall system performance, we propose a personalized automated bidding framework, namely PerBid, shifting the classical automated bidding strategy with a unified agent to multiple context-aware agents corresponding to different advertiser clusters. Specifically, we first design an ad campaign profiling network to model dynamic advertising environments. By clustering the advertisers with similar profiles and generating context-aware automated bidding agents for each cluster, we can match advertisers with personalized automated bidding strategies. Experiments conducted on the real-world dataset and online A/B test on Alibaba display advertising platform demonstrate the effectiveness of PerBid in improving overall ad performance and guaranteeing fairness among heterogeneous advertisers.

End-to-end retrieval models, such as Tree-based Models (TDM) and Deep Retrieval (DR), have attracted a lot of attention, but they cannot handle cold-start and long-tail item recommendation scenarios well. Specifically, DR learns a compact indexing structure, enabling efficient and accurate retrieval for large recommendation systems. However, it is discovered that DR largely fails on retrieving cold-start and long-tail items. This is because DR only utilizes user-item interaction data, which is rare and often noisy for cold-start and long-tail items. Besides, end-to-end retrieval models are unable to make use of the rich item content features. To address this issue while maintaining the efficiency of DR indexing structure, we propose Full Index Deep Retrieval (FIDR) that learns indices for the full corpus items, including cold-start and long-tail items. In addition to the original structure in DR (called User Structure in FIDR) that learns with user-item interaction data (e.g., clicks), we add an Item Structure to embed items directly based on item content features (e.g., categories). With joint efforts of User Structure and Item Structure, FIDR makes cold-start items retrievable and also improves the recommendation quality of long-tail items. To our best knowledge, FIDR is the first to solve the cold-start and long-tail recommendation problem for the end-to-end retrieval models. Through extensive experiments on three real-world datasets, we demonstrate that FIDR can effectively recommend cold-start as well as long-tail items, and largely promote overall recommendation performance without sacrificing inference efficiency. According to the experiments, the recall of FIDR is improved by 8.8%~11.9%, while the inference of FIDR is as efficient as DR.

In online e-commerce platforms, sponsored ads are always mixed with non-sponsored organic content (recommended items). To guarantee user experience, online platforms always impose strict limitations on the number of ads displayed, becoming the bottleneck for advertising revenue. To boost advertising space, we introduce a novel advertising business paradigm called Augment Advertising, where once a user clicks on a leading ad on the main page, instead of being shown the corresponding products, a collection of mini-detail ads relevant to the clicked ad is displayed. A key component for augment advertising is to design ad auctions to jointly select leading ads on the main page and mini-detail ads on the augment ad page. In this work, we decouple the ad auction into a two-stage auction, including a leading ad auction and a mini-detail ad auction. We design the Potential Generalized Second Price (PGSP) auction with Symmetric Nash Equilibrium (SNE) for leading ads, and adopt GSP auction for mini-detail ads. We have deployed augment advertising on Taobao advertising platform, and conducted extensive offline evaluations and online A/B tests. The evaluation results show that augment advertising could guarantee user experience while improving the ad revenue and the PGSP auction outperforms baselines in terms of revenue and user experience in augment advertising.

Machine learning models have been deployed in mobile networks to deal with massive data from different layers to enable automated network management and intelligence on devices. To overcome high communication cost and severe privacy concerns of centralized machine learning, federated learning (FL) has been proposed to achieve distributed machine learning among networked devices. While the computation and communication limitation has been widely studied, the impact of on-device storage on the performance of FL is still not explored. Without an effective data selection policy to filter the massive streaming data on devices, classical FL can suffer from much longer model training time (4 ×) and significant inference accuracy reduction (7%), observed in our experiments. In this work, we take the first step to consider the online data selection for FL with limited on-device storage. We first define a new data valuation metric for data evaluation and selection in FL with theoretical guarantees for speeding up model convergence and enhancing final model accuracy, simultaneously. We further design ODE, a framework of Online Data sElection for FL, to coordinate networked devices to store valuable data samples. Experimental results on one industrial dataset and three public datasets show the remarkable advantages of ODE over the state-of-the-art approaches. Particularly, on the industrial dataset, ODE achieves as high as 2.5 × speedup of training time and 6% increase in inference accuracy, and is robust to various factors in practical environments.

Motivated by the collaboration with Fliggy1, a leading Online Travel Platform (OTP), we investigate an important but less explored research topic about optimizing the quality of hotel supply, namely selecting potential profitable hotels in advance to build up adequate room inventory. We formulate a WWW problem, i.e., within a specific time period (When) and potential travel area (Where), which hotels should be recommended to a certain group of users with similar travel intentions (Why). We identify three critical challenges in solving the WWW problem: user groups generation, travel data sparsity and utilization of hotel recommendation information (e.g., period, location and intention). To this end, we propose LINet, a Location and Intention-aware neural Network for hotel group recommendation. Specifically, LINet first identifies user travel intentions for user groups generalization, and then characterizes the group preferences by jointly considering historical user-hotel interaction and spatio-temporal features of hotels. For data sparsity, we develop a graph neural network, which employs long-term data, and further design an auxiliary loss function of location that efficiently exploits data within the same and across different locations. Both offline and online experiments demonstrate the effectiveness of LINet when compared with state-of-the-art methods. LINet has been successfully deployed on Fliggy to retrieve high quality hotels for business development, serving hundreds of hotel operation scenarios and thousands of hotel operators.

More and more IoT data is being traded online in cloud-based data marketplaces due to the fast-growing market demand. Within the current data selling mechanisms, data consumers have difficulties in making purchasing decisions due to uncertain IoT data quality and inflexible pricing interface. To resolve these issues, potential solutions could be to launch data demonstrations and release free sampling data to reduce the uncertainty about data quality, and to charge based on the volume of data actually used to enable flexible pricing. However, there is still no clear understanding of economic benefits of these mechanisms. In this paper, we design the optimal data selling mechanisms for IoT data exchange, and derive the following two results. First, whether to deploy a data demonstration and how much free sampling data to release depend on the extent of data consumers' inaccuracy perceptions for data quality, which varies over a wide range in IoT applications. We found that the data vendor has no incentive to conduct these strategies if data consumers extremely overestimate data quality. Second, although flexible data pricing mechanisms provide convenience for real-time and streaming IoT data exchange, it brings less economic benefits to the data vendor compared with the fixed pricing scheme, which sells the whole data set with a fixed price. We evaluate the optimal selling mechanisms on a real-world Taxi GPS data set, and evaluation results verify the insights derived from our theoretical analysis.

A contemporary feed application usually provides blended results of organic items and sponsored items~(ads) to users. Conventionally, ads are exposed at fixed positions. Such a fixed ad exposure strategy is inefficient due to ignoring users' personalized preferences towards ads. To this end,adaptive ad exposure is becoming an appealing strategy to boost the overall performance of the feed. However, existing approaches to implement the adaptive ad exposure strategy suffer from several limitations: 1) they usually fall into sub-optimal solutions because of only focusing on request-level optimization without consideration of the application-level performance and constraints, 2) they neglect the necessity of keeping the game-theoretical properties of ad auctions, and 3) they can hardly be deployed in large-scale applications due to high computational complexity. In this paper, we focus on the application-level performance optimization under hierarchical constraints in feeds and formulate adaptive ad exposure as a Dynamic Knapsack Problem. We propose Hierarchically Constrained Adaptive Ad Exposure~(HCA2E) that possesses the desirable game-theoretical properties, computational efficiency, and performance robustness. Comprehensive offline and online experiments on a leading e-commerce application demonstrate the performance superiority of HCA2E.

Mobile livestreaming ads are becoming a popular approach for brand promotion and product marketing. However, a large number of advertisers fail to achieve their desired advertising performance due to the lack of ad exposure guarantee in the dynamic advertising environment. In this work, we propose a bidding-based ad delivery algorithm for mobile livestreaming ads that can provide advertisers with bidding strategies for optimizing diverse marketing objectives under general ad performance guaranteed constraints, such as ad exposure and cost-efficiency constraints. By modeling the problem as an online integer programming and applying primal-dual theory, we can derive the bidding strategy from solving the optimal dual variables. The initialization of the dual variables is realized through a deep neural network that captures the complex relation between dual variables and dynamic advertising environments. We further propose a control-based bidding algorithm to adjust the dual variables in an online manner based on the real-time advertising performance feedback and constraints. Experiments on a real-world industrial dataset demonstrate the effectiveness of our bidding algorithm in terms of optimizing marketing objectives and guaranteeing ad constraints.

Mobile health (mHealth) applications, benefiting from mobile computing, have emerged rapidly in recent years, and generated a large volume of mHealth data. However, these valuable data are dispersed across isolated devices or organizations, which hinders discovering insights underlying the aggregated data. Considering the online characteristics of mHealth tasks, there is an urgent need for online data acquisition. In this paper, we present the first online data Valuation And Pricing mechanism, namely VAP, to incentive users to contribute mHealth data for machine learning (ML) tasks in mHealth systems. Under the framework of Bayesian ML, we propose a new metric based on the concept of entropy, to evaluate data valuation during model training in an online manner. In proportion to the data valuation, we then determine payments as compensations for users to contribute their data. We formulate this pricing problem as a contextual multi-armed bandit with the goal of profit maximization and propose a new algorithm based on the characteristics of pricing. We also extend VAP to general ML models. Finally, we have evaluated VAP on two real-world mHealth data sets. Evaluation results show that VAP outperforms the state-of-the-art valuation and pricing mechanisms in terms of computational complexity and extracted profit.

In online advertising, auto-bidding has become an essential tool for advertisers to optimize their preferred ad performance metrics by simply expressing high-level campaign objectives and constraints. Previous works designed auto-bidding tools from the view of single-agent, without modeling the mutual influence between agents. In this paper, we instead consider this problem from a distributed multi-agent perspective, and propose a general \underlineM ulti-\underlineA gent reinforcement learning framework for \underlineA uto-\underlineB idding, namely MAAB, to learn the auto-bidding strategies. First, we investigate the competition and cooperation relation among auto-bidding agents, and propose a temperature-regularized credit assignment to establish a mixed cooperative-competitive paradigm. By carefully making a competition and cooperation trade-off among agents, we can reach an equilibrium state that guarantees not only individual advertiser's utility but also the system performance (i.e., social welfare). Second, to avoid the potential collusion behaviors of bidding low prices underlying the cooperation, we further propose bar agents to set a personalized bidding bar for each agent, and then alleviate the revenue degradation due to the cooperation. Third, to deploy MAAB in the large-scale advertising system with millions of advertisers, we propose a mean-field approach. By grouping advertisers with the same objective as a mean auto-bidding agent, the interactions among the large-scale advertisers are greatly simplified, making it practical to train MAAB efficiently. Extensive experiments on the offline industrial dataset and Alibaba advertising platform demonstrate that our approach outperforms several baseline methods in terms of social welfare and revenue.

For the scalability of industrial online advertising systems, a two-stage auction architecture is widely used to enable efficient ad allocation on a large set of corpus within a limited response time. The current deployed two-stage ad auction usually retrieves an ad subset by a coarse ad quality metric in a pre-auction stage, and then determines the auction outcome by a refined metric in the subsequent stage. However, this simple and greedy solution suffers from performance degradation, as it regards the decision in each stage separately, leading to an improper ad selection metric for the pre-auction stage. In this work, we explicitly investigate the relation between the coarse and refined ad quality metrics, and design a two-stage ad auction by taking the decision interaction between the two stages into account. We decouple the design of the two-stage auction by solving a stochastic subset selection problem in the pre-auction stage and conducting a general second price (GSP) auction in the second stage. We demonstrate that this decouple still preserves the incentive compatibility of the auction mechanism. As the proposed formulation of the pre-auction stage is an NP-hard problem, we propose a scalable approximation solution by defining a new subset selection metric, namely Pre-Auction Score (PAS). Experiment results on both public and industrial dataset demonstrate the improvement on social welfare and revenue of the proposed two-stage ad auction, than the intuitive greedy two-stage auction and other baselines.

The society’s insatiable appetites for personal data are driving the emergence of data markets, allowing data consumers to launch customized queries over the datasets collected by a data broker from data owners. In this paper, we study how the data broker can maximize its cumulative revenue by posting reasonable prices for sequential queries. We thus propose a contextual dynamic pricing mechanism with the reserve price constraint, which features the properties of ellipsoid for efficient online optimization and can support linear and non-linear market value models with uncertainty. In particular, under low uncertainty, the proposed pricing mechanism attains a worst-case cumulative regret logarithmic in the number of queries. We further extend our approach to support other similar application scenarios, including hospitality service and online advertising, and extensively evaluate all three use cases over MovieLens 20M dataset, Airbnb listings in U.S. major cities, and Avazu mobile ad click dataset, respectively. The analysis and evaluation results reveal that: (1) our pricing mechanism incurs low practical regret, while the latency and memory overhead incurred is low enough for online applications; and (2) the existence of reserve price can mitigate the cold-start problem in a posted price mechanism, thereby reducing the cumulative regret.

Mobile crowdsensing has become increasingly popular due to its ability to collect a massive amount of data with the help of many individual smartphone users. A crowdsensing platform can utilize the collected data to extract effective information and provide diverse services. Designing an incentive mechanism to compensate the participants for their resources consumption is critical in attracting more participation. Offline incentive mechanism design has been widely studied in various crowdsensing applications, whereas the online scenario, is much more challenging due to the unavailability of future information when the platform makes user selection decisions. In this paper, we investigate the problem of online crowdsensing by considering a critical property that the values of users’ contributions decrease as time goes by. The time-discounting property is common in inter-temporal choice scenarios but has not been carefully addressed from the perspective of mechanism design. To handle this problem, we propose a new method to select users based on a time-dependent threshold, and present a strategy-proof framework where participants prefer to submit their true types, instead of manipulating the market by misreporting their private information. We consider two cases, one is that the total value is the summation of each participant's contributing value, the other is more general that the total value function is submodular. We call these two mechanisms TDM and TDMS, respectively. We prove that our two mechanisms can achieve computational efficiency, budget feasibility, strategy-proofness, and a constant competitive ratio, in the context of time-discounting values. By comparing our mechanisms with the state-of-the-art methods, we show that our design achieves better performance in terms of the total value.

Federated learning allows mobile clients to jointly train a global model without sending their private data to a central server. Extensive works have studied the performance guarantee of the global model, however, it is still unclear how each individual client influences the collaborative training process. In this work, we defined a new notion, called {\em Fed-Influence}, to quantify this influence over the model parameters, and proposed an effective and efficient algorithm to estimate this metric. In particular, our design satisfies several desirable properties: (1) it requires neither retraining nor retracing, adding only linear computational overhead to clients and the server; (2) it strictly maintains the tenets of federated learning, without revealing any client's local private data; and (3) it works well on both convex and non-convex loss functions, and does not require the final model to be optimal. Empirical results on a synthetic dataset and the FEMNIST dataset demonstrate that our estimation method can approximate Fed-Influence with small bias. Further, we show an application of Fed-Influence in model debugging.

In online advertising, it is important to jointly consider multiple objectives, e.g. platform revenue and display quality. The existing work only considered multi-objective optimization in each single auction stage, which can be suboptimal in the setting with multiple stages in real online advertising. In this paper, we propose a dynamic auction mechanism which can make a tradeoff between revenue and quality across a series of multiple auction stages, to further improve the performance of the Pareto frontiers from the optimal static auction mechanism in each single stage. We prove that the proposed dynamic auction mechanism satisfies dynamic incentive properties. As the exact valuation distributions are usually unavailable in practice, we further propose a practical implementation of our multi-objective dynamic auction mechanism via data-driven methods and with guarantee of approximate dynamic incentive compatibility. Finally, we confirm our theoretical results and evaluate our practical implementation via empirical study on both synthetic data and real industrial data, and observe a significant improvement on both revenue and quality than the static auction mechanism baseline.

Advertising expenditures have become the major source of revenue for e-commerce platforms. Providing good advertising experiences for advertisers by reducing their costs of trial and error in discovering the optimal advertising strategies is crucial for the long-term prosperity of online advertising. To achieve this goal, the advertising platform needs to identify the advertiser's optimization objectives, and then recommend the corresponding strategies to fulfill the objectives. In this work, we first deploy a prototype of strategy recommender system on Taobao display advertising platform, which indeed increases the advertisers' performance and the platform's revenue, indicating the effectiveness of strategy recommendation for online advertising. We further augment this prototype system by explicitly learning the advertisers' preferences over various advertising performance indicators and then optimization objectives through their adoptions of different recommending advertising strategies. We use contextual bandit algorithms to efficiently learn the advertisers' preferences and maximize the recommendation adoption, simultaneously. Simulation experiments based on Taobao online bidding data show that the designed algorithms can effectively optimize the strategy adoption rate of advertisers.

In e-commerce advertising, it is crucial to jointly consider various performance metrics, e.g., user experience, advertiser utility, and platform revenue. Traditional auction mechanisms, such as GSP and VCG auctions, can be suboptimal due to their fixed allocation rules to optimize a single performance metric (e.g., revenue or social welfare). Recently, data-driven auctions, learned directly from auction outcomes to optimize multiple performance metrics, have attracted increasing research interests. However, the procedure of auction mechanisms involves various discrete calculation operations, making it challenging to be compatible with continuous optimization pipelines in machine learning. In this paper, we design Deep Neural Auctions (DNAs) to enable end-to-end auction learning by proposing a differentiable model to relax the discrete sorting operation, a key component in auctions. We optimize the performance metrics by developing deep models to efficiently extract contexts from auctions, providing rich features for auction design. We further integrate the game theoretical conditions within the model design, to guarantee the stability of the auctions. DNAs have been successfully deployed in the e-commerce advertising system at Taobao. Experimental evaluation results on both large-scale data set as well as online A/B test demonstrated that DNAs significantly outperformed other mechanisms widely adopted in industry.

Federated learning (FL) trains a machine learning model on mobile devices in a distributed manner using each device’s private data and computing resources. A critical issues is to evaluate individual users’ contributions so that (1) users’ effort in model training can be compensated with proper incentives and (2) malicious and low-quality users can be detected and removed. The state-of-the-art solutions require a representative test dataset for the evaluation purpose, but such a dataset is often unavailable and hard to synthesize. In this paper, we propose a method called Pairwise Correlated Agreement (PCA) based on the idea of peer prediction to evaluate user contribution in FL without a test dataset. PCA achieves this using the statistical correlation of the model parameters uploaded by users. We then apply PCA to designing (1) a new federated learning algorithm called Fed-PCA, and (2) a new incentive mechanism that guarantees truthfulness. We evaluate the performance of PCA and Fed-PCA using the MNIST dataset and a large industrial product recommendation dataset. The results demonstrate that our Fed-PCA outperforms the canonical FedAvg algorithm and other baseline methods in accuracy, and at the same time, PCA effectively incentivizes users to behave truthfully.

In e-commerce advertising, the ad platform usually relies on auction mechanisms to optimize different performance metrics, such as user experience, advertiser utility, and platform revenue. However, most of the state-of-the-art auction mechanisms only focus on optimizing a single performance metric, e.g., either social welfare or revenue, and are not suitable for e-commerce advertising with various, dynamic, difficult to estimate, and even conflicting performance metrics. In this paper, we propose a new mechanism called Deep GSP auction, which leverages deep learning to design new rank score functions within the celebrated GSP auction framework. These new rank score functions are implemented via deep neural network models under the constraints of monotone allocation and smooth transition. The requirement of monotone allocation ensures Deep GSP auction nice game theoretical properties, while the requirement of smooth transition guarantees the advertiser utilities would not fluctuate too much when the auction mechanism switches among candidate mechanisms to achieve different optimization objectives. We deployed the proposed mechanisms in a leading e-commerce ad platform and conducted comprehensive experimental evaluations with both offline simulations and online A/B tests. The results demonstrated the effectiveness of the Deep GSP auction compared to the state-of-the-art auction mechanisms.

Real-time information processing is critical to the success of diverse applications from many areas. Age of Information (AoI), as a new metric, has received considerable attention to evaluate the performance of real-time information processing systems. In recent years, edge computing is becoming an efficient paradigm to reduce the AoI and to provide the real-time services. Considering the substantial deployment cost and the resulting resource limitation in edge computing, a proper pricing mechanism is highly necessary to fully utilize edge resources and then minimize the overall AoI of the whole system. However, there are two challenges to design this mechanism: 1) the priorities (or values) of the real-time computing tasks, critical to the efficient resource allocation, are usually private information of users and may be manipulated by selfish users for their own interests; 2) due to the time-varying property of AoI, the values of the tasks discount with time, making the traditional pricing mechanisms infeasible. In this paper, we extend the classical Myerson Theorem to the online setting with time discounting tasks values, and accordingly propose an online auction mechanism, called PreDisc, including an allocation rule and a payment rule. We leverage dynamic programming to greedily allocate resources in each time slot, and charge the winning user with a new critical price, extended from the classical Myerson payment rule. A preemption factor is further employed to make a trade-off between the newly arrived tasks and ongoing tasks. We prove that PreDisc guarantees the economic property of strategy-proofness and achieves a constant competitive ratio. We conduct extensive simulations and the results demonstrate that PreDisc outperforms the traditional mechanisms, in terms of both weighted AoI and revenue of edge service providers. Compared with the optimal solution in offline VCG mechanism, PreDisc has much lower computation complexity with only a slight performance loss.

With the commoditization of personal privacy, pricing private data has become an intriguing problem. In this paper, we study noisy aggregate statistics trading from the perspective of a data broker in data markets. We thus propose ERATO, which enables aggrEgate statistics pRicing over privATe cOrrelated data. On one hand, ERATO guarantees arbitrage freeness against cunning data consumers. On the other hand, ERATO compensates data owners for their privacy losses using both bottom-up and top-down designs. We further apply ERATO to three practical aggregate statistics, namely weighted sum, probability distribution fitting, and degree distribution, and extensively evaluate their performances on MovieLens dataset, 2009 RECS dataset, and two SNAP large social network datasets, respectively. Our analysis and evaluation results reveal that ERATO well balances utility and privacy, achieves arbitrage freeness, and compensates data owners more fairly than differential privacy based approaches.

In mobile crowdsensing, finding the best match between tasks and users is crucial to ensure both the quality and effectiveness of a crowdsensing system. Existing works usually assume a centralized task assignment by the crowdsensing platform, without addressing the need of fine-grained personalized task matching. In this paper, we argue that it is essential to match tasks to users based on a careful characterization of both the users' preference and reliability. To that end, we propose a personalized task recommender system for mobile crowdsensing, which recommends tasks to users based on a recommendation score that jointly takes each user's preference and reliability into consideration. We first present a hybrid preference metric to characterize users' preference by exploiting their implicit feedback. Then, to profile users' reliability levels, we formalize the problem as a semi-supervised learning model, and propose an efficient block coordinate descent algorithm to solve the problem. For some tasks that lack users' historical information, we further propose a matrix factorization method to infer the users' reliability levels on those tasks. We conduct extensive experiments to evaluate the performance of our system, and the evaluation results demonstrate that our system can achieve superior performance to the benchmarks in both user profiling and personalized task recommendation.

Bike sharing systems have been widely deployed around the world in recent years. A core problem in such systems is to reposition the bikes so that the distribution of bike supply is reshaped to better match the dynamic bike demand. When the bike-sharing company or platform is able to predict the revenue of each reposition task based on historic data, an additional constraint is to cap the payment for each task below its predicted revenue. In this paper, we propose an incentive mechanism called TruPreTar to incentivize users to park bicycles at locations desired by the platform toward rebalancing supply and demand. TruPreTar possesses four important economic and computational properties such as truthfulness and budget feasibility. Furthermore, we prove that even when the payment budget is tight, the total revenue still exceeds or equals the budget. Otherwise, TruPreTar achieves 2-approximation as compared to the optimal (revenue-maximizing) solution, which is close to the lower bound of at least √2 that we also prove. Using an industrial dataset obtained from a large bike-sharing company, our experiments show that TruPreTar is effective in rebalancing bike supply and demand and, as a result, generates high revenue that outperforms several benchmark mechanisms.

For e-commerce platforms such as Taobao and Amazon, advertisers play an important role in the entire digital ecosystem: their behaviors explicitly influence users' browsing and shopping experience; more importantly, advertiser's expenditure on advertising constitutes a primary source of platform revenue. Therefore, providing better services for advertisers is essential for the long-term prosperity for e-commerce platforms. To achieve this goal, the ad platform needs to have an in-depth understanding of advertisers in terms of both their marketing intents and satisfaction over the advertising performance, based on which further optimization could be carried out to service the advertisers in the correct direction. In this paper, we propose a novel Deep Satisfaction Prediction Network (DSPN), which models advertiser intent and satisfaction simultaneously. It employs a two-stage network structure where advertiser intent vector and satisfaction are jointly learned by considering the features of advertiser's action information and advertising performance indicators. Experiments on an Alibaba advertisement dataset and online evaluations show that our proposed DSPN outperforms state-of-the-art baselines and has stable performance in terms of AUC in the online environment. Further analyses show that DSPN not only predicts advertisers' satisfaction accurately but also learns an explainable advertiser intent, revealing the opportunities to optimize the advertising performance further.

The society's insatiable appetites for personal data are driving the emergency of data markets, allowing data consumers to launch customized queries over the datasets collected by a data broker from data owners. In this paper, we study how the data broker can maximize her cumulative revenue by posting reasonable prices for sequential queries. We thus propose a contextual dynamic pricing mechanism with the reserve price constraint, which features the properties of ellipsoid for efficient online optimization, and can support linear and non-linear market value models with uncertainty. In particular, under low uncertainty, our pricing mechanism provides a worst-case regret logarithmic in the number of queries. We further extend to other similar application scenarios, including hospitality service and online advertising, and extensively evaluate all three application instances over MovieLens 20M dataset, Airbnb listings in U.S. major cities, and Avazu mobile ad click dataset, respectively. The analysis and evaluation results reveal that our proposed pricing mechanism incurs low practical regret, online latency, and memory overhead, and also demonstrate that the existence of reserve price can mitigate the cold-start problem in a posted price mechanism, and thus can reduce the cumulative regret.

In E-commerce, advertising is essential for merchants to reach their target users. The typical objective is to maximize the advertiser’s cumulative revenue over a period of time under a budget constraint. In real applications, an advertisement (ad) usually needs to be exposed to the same user multiple times until the user finally contributes revenue (e.g., places an order). However, existing advertising systems mainly focus on the immediate revenue with single ad exposures, ignoring the contribution of each exposure to the final conversion, thus usually falls into suboptimal solutions. In this paper, we formulate the sequential advertising strategy optimization as a dynamic knapsack problem. We propose a theoretically guaranteed bilevel optimization framework, which significantly reduces the solution space of the original optimization space while ensuring the solution quality. To improve the exploration efficiency of reinforcement learning, we also devise an effective action space reduction approach. Extensive offline and online experiments show the superior performance of our approaches over state-of-the-art baselines in terms of cumulative revenue.

Bipartite b-matching is fundamental in algorithm design, and has been widely applied into diverse applications, such as economic markets, labor markets, etc. These practical problems usually exhibit two distinct features: large-scale and dynamic, which requires the matching algorithm to be repeatedly executed at regular intervals. However, existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. To address this issue, based on a key observation that the matching instances vary not too much, we propose NeuSearcher which leverage the knowledge learned from previously instances to solve new problem instances. Specifically, we design a multichannel graph neural network to predict the threshold of the matched edges, by which the search region could be significantly reduced. We further propose a parallel heuristic search algorithm to iteratively improve the solution quality until convergence. Experiments on both open and industrial datasets demonstrate that NeuSearcher can speed up 2 to 3 times while achieving exactly the same matching solution compared with the state-of-the-art approximation approaches.

A large-scale image collection is crucial to the success of 3D reconstruction. Crowdsourcing, as a new pattern, can be utilized to collect high-quality images in an efficient way. However, the sensitive information in images may be exposed during the image transmission process. The general privacy policies perhaps will cause the loss or change of critical information, which may give rise to a decline in the performance of 3D reconstruction. Hence, how to achieve image privacy-preserving while guaranteeing to reconstruct a complete 3D model is important and significant. In this paper, we propose PicPrivacy to address this problem, which consists of three parts. (1) Using a pre-trained deep convolution neural network to segment sensitive information and erase it from images. (2) Using a GAN-based image feature completion algorithm to repair blank regions and minimize the absolute information gap between generated images and raw ones. (3) Taking generated images as the input of 3D reconstruction and using a structure-from-motion algorithm to reconstruct 3D models. Finally, we extensively evaluate the performance of PicPrivacy on realworld datasets. The results demonstrate that PicPrivacy not only achieves individual privacy-preserving but also can guarantee to create complete 3D models.

Although data has become an important kind of commercial goods, there are few appropriate online platforms to facilitate the trading of mobile crowd-sensed data so far. In this paper, we present the first architecture of mobile crowd-sensed data market, and conduct an in-depth study of the design problem of online data pricing and reward sharing. To build a practical mobile crowd-sensed data market, we have to consider four major design challenges: data uncertainty, economic-robustness (arbitrage-freeness in particular), profit maximization, and fair reward sharing. By jointly considering the design challenges, we propose an online query-bAsed cRowd-sensEd daTa pricing mEchanism, namely ARETE-PR, to determine the trading price of crowd-sensed data. Our theoretical analysis shows that ARETE-PR guarantees both arbitrage-freeness and a constant competitive ratio in terms of profit maximization. Based on some fairness criterions, we further design a reward sharing scheme, namely ARETE-SH, which is closely coupled with ARETE-PR, to incentivize data providers to contribute data. We have evaluated ARETE on a real-world sensory data set collected by Intel Berkeley lab. Evaluation results show that ARETE-PR outperforms the state-of-the-art pricing mechanisms, and achieves around 90 percent of the optimal revenue. ARETE-SH distributes the reward among data providers in a fair way.

Data is becoming an important kind of commercial good, and many online data marketplaces are set up to facilitate the trading of data. However, most existing data market models and the corresponding pricing mechanisms are simple, and fail to capture the unique economic properties of data. In this paper, we first characterize the distinctive features of IoT data as a commodity, and then present a new IoT data market model from an information design perspective. We further propose a family of data pricing mechanisms for revenue maximization under different market settings. Our MSimple mechanism extracts full surplus from the market for the model with one type of buyer. When multiple types of buyers coexist, our MGeneral mechanism optimally solves the problem of revenue maximization by formulating it as a polynomial size convex program. For a more practical setting where buyers have bounded rationality, we design MPractical mechanism with a tight logarithmic approximation ratio. We evaluate our pricing mechanisms on a real-world ambient sound dataset. Evaluation results show our pricing mechanisms achieve good performance and approach the revenue upper bound.

With the commoditization of personal data, pricing privacy has become an intriguing topic. In this paper, we study time-series data trading from the perspective of a data broker in data markets. We thus propose HORAE, which is a PufferfisH privacy based framewOrk for tRAding timE-series data. HORAE first employs Pufferfish privacy to quantity privacy losses under temporal correlations, and compensates data owners with distinct privacy strategies in a satisfying way. Besides, HORAE not only guarantees good profitability at the data broker, but also ensures arbitrage freeness against cunning data consumers. We further apply HORAE to physical activity monitoring, and extensively evaluate its performance on the real-world Activity Recognition with Ambient Sensing (ARAS) dataset. Our analysis and evaluation results reveal that HORAE compensates data owners in a more fine-grained manner than entry/group differential privacy based approaches, well controls the profit ratio of the data broker, and thwarts arbitrage attacks launched by data consumers.

As a significant business paradigm, many online information platforms have emerged to satisfy society's needs for person-specific data, where a service provider collects raw data from data contributors, and then offers value-added data services to data consumers. However, in the data trading layer, the data consumers face a pressing problem, i.e., how to verify whether the service provider has truthfully collected and processed data? Furthermore, the data contributors are usually unwilling to reveal their sensitive personal data and real identities to the data consumers. In this paper, we propose TPDM, which efficiently integrates Truthfulness and Privacy preservation in Data Markets. TPDM is structured internally in an Encrypt-then-Sign fashion, using partially homomorphic encryption and identity-based signature. It simultaneously facilitates batch verification, data processing, and outcome verification, while maintaining identity preservation and data confidentiality. We also instantiate TPDM with a profile matching service and a data distribution service, and extensively evaluate their performances on Yahoo! Music ratings dataset and 2009 RECS dataset, respectively. Our analysis and evaluation results reveal that TPDM achieves several desirable properties, while incurring low computation and communication overheads when supporting large-scale data markets.

Online pricing mechanisms have been widely applied to resource allocation in multi-agent systems. However, most of the existing online pricing mechanisms assume buyers have fixed valuations over the time horizon, which cannot capture the dynamic nature of valuation in emerging applications. In this paper, we study the problem of revenue maximization in online auctions with unknown time discounting valuations, and model it as non-stationary multi-armed bandit optimization. We design an online pricing mechanism, namely Biased-UCB, based on unique features of the discounting valuations. We use competitive analysis to theoretically evaluate the performance guarantee of our pricing mechanism, and derive the competitive ratio. Numerical results show that our design achieves good performance in terms of revenue maximization on a real-world bidding dataset.

In mobile crowdsensing, finding the best match between tasks and users is crucial to ensure both the quality and effectiveness of a crowdsensing system. Existing works usually assume a centralized task assignment by the platform, without addressing the need of fine-grained personalized task matching. In this paper, we argue that it is essential to match tasks to users based on a careful characterization of both the users' preferences and reliability levels. To that end, we propose a personalized task recommender system for mobile crowdsensing, which recommends tasks to users based on a recommendation score that jointly takes each user's preference and reliability into consideration. We first present a simple but effective method to profile the users' preferences by exploiting the implicit feedback from their historical performance. Then, to profile the users' reliability levels, we formalize the problem as a semi-supervised learning model, and propose an efficient block coordinate descent algorithm to solve the problem. For some tasks that lack historical information, we further propose a matrix factorization method to infer the users' reliability on those tasks. We conduct extensive experiments to evaluate the performance of our system, and the evaluation results demonstrate that our system can achieve superior performance to our benchmarks in both user profiling and personalized task matching.

As more applications and businesses move to the cloud, pricing for inter-datacenter links has become an important problem. In this paper, we study revenue maximizing pricing from the perspective of a network provider in inter-datacenter networks. Designing a practical bandwidth pricing scheme requires us to jointly consider the requirements of envy-freeness and arbitrage-freeness, where envy-freeness guarantees the fairness of resource allocation and arbitrage-freeness induces users to truthfully reveal their data transfer requests. Considering the non-convexity of the revenue maximization problem and the lack of information about the users' utilities, we propose a framework for computationally efficient pricing to approximately maximize revenue in a range of environments. We first study the case of a single link accessed by many users, and design a (1 + E)-approximation pricing scheme with polynomial time complexity and information complexity. Based on dynamic programming, we then extend the pricing scheme for the tollbooth network, preserving the (1 + E) approximation ratio and the computational complexity. For the general network setting, we analyze the revenue generated by uniform pricing, which determines a single per unit price for all potential users. We show that when users have similar utilities, uniform pricing can achieve a good approximation ratio, which is independent of network topology and data transfer requests. The pricing framework can be extended to multiple time slots, enabling time-dependent pricing.

With the commoditization of personal privacy, pricing private data has become an intriguing problem. In this paper, we study noisy aggregate statistics trading from the perspective of a data broker in data markets. We thus propose ERATO, which enables aggrEgate statistics pRicing over privATe cOrrelated data. On one hand, ERATO guarantees arbitrage freeness against cunning data consumers. On the other hand, ERATO compensates data owners for their privacy losses using both bottom-up and top-down designs. We further apply ERATO to three practical aggregate statistics, namely weighted sum, probability distribution fitting, and degree distribution, and extensively evaluate their performances on MovieLens dataset, 2009 RECS dataset, and two SNAP large social network datasets, respectively. Our analysis and evaluation results reveal that ERATO well balances utility and privacy, achieves arbitrage freeness, and compensates data owners more fairly than differential privacy based approaches.

The recent proliferation of mobile devices embedded with capable sensors, provides an opportunity to the popular concept of mobile crowdsensing. By studying the correlation of crowd-sensed data in both spatial and temporal dimensions, we can get a clear understanding of the intrinsic pattern of data in mobile crowdsensing, which is the basic for further data analysis, such as data filtering, smoothing and prediction. However, the crowd-sensed data are normally noise and unreliable due to the diverse mobility patterns and selfish behaviours of mobile users, making the classical data models in wireless sensor networks fail in this new context. In this paper, we propose a robust and reliable time series data model based on Dynamic Bayesian Network to describe the characteristics of the crowd-sensed data. The proposed data model can figure out the spatial and temporal correlation of data in the environment, where the data has high noise levels and mobile users are untrustworthy. We conduct extensive evaluations based on both simulation and a real-world data set. Our evaluation results show that our method successfully modeled the crowd-sensed time series data with effectiveness, efficiency and trustworthiness.

Mobile crowdsensing has emerged as a promising paradigm for data collection due to increasingly pervasive and powerful mobile devices. There have been extensive research works that propose incentive mechanisms for crowdsensing, but they all make the assumption that mobile users will positively complete the allocated sensing tasks. In this paper, we consider a new and practical scenario of crowdsensing, where a user may fail to complete the task with a certain probability. It is an important and emerging issue for the incentive mechanisms to ensure fault tolerance for each sensing task under such unreliable scenarios. We design reverse auctions to model the strategic interaction between the platform and mobile users, in which users' probability of success and cost to perform the tasks are private information. Considering the task execution uncertainty, the goal of the auction mechanism is to minimize the social cost of user recruitment, while guaranteeing the tasks to be completed with high probability. We prove that minimizing the social cost is an NP-hard problem, and design computationally efficient mechanisms that achieve good approximation ratio and economic-robust properties, e.g., strategy-proofness. We conduct extensive simulations to evaluate the performance of our mechanisms based on a real data set. The evaluation results show that our mechanisms outperform the heuristic algorithm and approach to the optimal solution.

As a significant business paradigm, many online information platforms have emerged to satisfy society's needs for person-specific data, where a service provider collects raw data from data contributors, and then offers value-added data services to data consumers. However, in the data trading layer, the data consumers face a pressing problem, i.e., how to verify whether the service provider has truthfully collected and processed data? Furthermore, the data contributors are usually unwilling to reveal their sensitive personal data and real identities to the data consumers. In this paper, we propose TPDM, which efficiently integrates Truthfulness and Privacy preservation in Data Markets. TPDM is structured internally in an Encrypt-then-Sign fashion, using somewhat homomorphic encryption and identitybased signature. It simultaneously facilitates batch verification, data processing, and outcome verification, while maintaining identity preservation and data confidentiality. We also instantiate TPDM with a profile-matching service, and extensively evaluate its performance on Yahoo! Music ratings dataset. Our evaluation results show that TPDM achieves several desirable properties, while incurring low computation and communication overheads when supporting a large-scale data market.

With the rapid growth of smart devices, mobile crowdsensing is becoming an important paradigm to acquire information from physical environments. Considering that the sensing data collected by mobile users are normally noisy and imprecise, one of the pressing problems in mobile crowdsensing is to evaluate the data quality in real time and to steer users to acquire data with high quality. However, it is challenging to estimate the data quality without the availability of ground truth data. In this paper, we observe that sensing context has a significant impact on data quality, which motivates us to propose a context-aware data quality estimation scheme. With historical sensing data, we train a context-quality classifier, which captures the relation between context information and data quality, to estimate data quality in an online manner. We apply such a context-aware data quality estimation scheme to guide user recruitment in mobile crowdsensing. We model the process of user recruitment as a stochastic submodular maximization problem, and design a random adaptive greedy algorithm to guarantee a constant approximation ratio. We evaluate our algorithm on a real-world temperature data set. The evaluation results show that our algorithm outperforms other existing techniques, in terms of prediction accuracy.

Last decade has witnessed the explosion in the number of smart mobile phones and other smart devices equipped with powerful sensors. Therefore, various crowdsensing applications which recruit people to complete sensing tasks have sprung up. Designing incentive mechanism plays an indispensable role in crowdsensing network. However, most existing works about incentive mechanism base on the assumption that agents will complete the allocated sensing tasks without any problem. However, when we take the failures of agents into consideration, most existing incentive mechanisms become invalid. Considering a more practical scenario, we suppose that there is a crucial sensing task which needs to remain high enough probability of success completion for a certain period of time and each alternative agent has a certain probability to cover a certain period successfully. To ensure the fault tolerance of the crowdsensing system, we propose two novel incentive mechanisms, single slot coverage (SSC) mechanism and continuous coverage (CC) mechanism, for different problem models, respectively. In our mechanisms, agents' probabilities of success, costs of completing task, start time and end time are all private information. Our objective is to minimize the total costs of selected agents, while ensuring the task is fully covered with a high enough probability over a certain period. Our work presents detailed proofs of the computational efficiency, truthfulness and individual rationality. Besides, we implement extensive simulation to evaluate proposed mechanisms, which validates the properties of our mechanisms.

Although data has become an important kind of commercial goods, there are few appropriate online platforms to facilitate the trading of mobile crowd-sensed data so far. In this paper, we present the first architecture of mobile crowd-sensed data market, and conduct an in-depth study of the design problem of online data pricing. To build a practical mobile crowd-sensed data market, we have to consider three major design challenges: data uncertainty, economic-robustness (arbitrage-freeness in particular), revenue maximization. By jointly considering the design challenges, we propose a novel online query-bAsed cRowd-sensEd daTa pricing mEchanism, namely ARETE, to determine the trading price of crowd-sensed data. Our theoretical analysis shows that ARETE guarantees both arbitrage-freeness and a constant competitive ratio in terms of revenue maximization. We have evaluated ARETE on a real-world sensory data set collected by Intel Berkeley lab. Evaluation results show that ARETE outperforms the state-of-the-art pricing mechanisms, and achieves around 90% of the optimal revenue.

As a significant business paradigm, data trading has attracted increasing attention. However, the study of data acquisition in data markets is still in its infancy. Mobile crowdsensing has been recognized as an efficient and scalable way to acquire large-scale data. Designing a practical data acquisition scheme for crowd-sensed data markets has to consider three major challenges: crowd-sensed data trading format determination, profit maximization with polynomial computational complexity, and payment minimization in strategic environments. In this paper, we jointly consider these design challenges, and propose VENUS, which is the first profit-driVEN data acqUiSition framework for crowd-sensed data markets. Specifically, VENUS consists of two complementary mechanisms: VENUS-PRO for profit maximization and VENUS-PAY for payment minimization. Given the expected payment for each of the data acquisition points, VENUS-PRO greedily selects the most “cost-efficient” data acquisition points to achieve a sub-optimal profit. To determine the minimum payment for each data acquisition point, we further design VENUS-PAY, which is a data procurement auction in Bayesian setting. Our theoretical analysis shows that VENUS-PAY can achieve both strategy-proofness and optimal expected payment. We evaluate VENUS on a public sensory data set, collected by Intel Research, Berkeley Laboratory. Our evaluation results show that VENUS-PRO approaches the optimal profit, and VENUS-PAY outperforms the canonical second-price reverse auction, in terms of total payment.

Mobile crowdsensing is a novel paradigm to collect sensing data and extract useful information about regions of interest. It widely employs incentive mechanisms to recruit a number of mobile users to fulfill coverage requirement in the interested regions. In practice, sensing service providers face a pressing optimization problem: How to maximize the valuation of the covered interested regions under a limited budget? However, the relation between two important factors, i.e., Coverage Maximization and Budget Feasibility, has not been fully studied in existing incentive mechanisms for mobile crowdsensing. Furthermore, the existing approaches on coverage maximization in sensor networks can work, when mobile users are rational and selfish. In this paper, we present the first in-depth study on the coverage problem for incentive-compatible mobile crowdsensing, and propose BEACON, which is a Budget fEAsible and strategy-proof incentive mechanism for weighted COverage maximizatioN in mobile crowdsensing. BEACON employs a novel monotonic and computationally tractable approximation algorithm for sensing task allocation, and adopts a newly designed proportional share rule based compensation determination scheme to guarantee strategy-proofness and budget feasibility. Our theoretical analysis shows that BEACON can achieve strategy-proofness, budget feasibility, and a constant-factor approximation. We deploy a noise map crowdsensing system to capture the noise level in a selected campus, and evaluate the system performance of BEACON on the collected sensory data. Our evaluation results demonstrate the efficacy of BEACON.

Wearable devices with various sensors are useful instruments to monitor human health. Due to the limited size, these wearable devices, however, always encounter critical energy problem, which further hinders their widely application. Considering that wireless communication dominates the total energy consumption, we make an in-depth study on the problem of communication energy consumption in body sensor networks. We first observe that the communication signals from wearable devices have strong correlation with human movements. Based on this correlation, we propose a Movement-based Adaptive Prediction Mechanism (MAPM). Specifically, we exploit Gaussian process regression to precisely fit and predict the transmission power combined with the characteristics of human movements. This prediction enables transmitters to automatically control their transmission power without feedback. Through simulation, we demonstrate that MAPM can save more than 40% energy compared to the sate-of-the-art methods.

With the growing deployment of wireless communication technologies, radio spectrum is becoming a scarce resource. Auctions are believed to be among the most effective tools to solve or relieve the problem of radio spectrum shortage. However, designing a practical spectrum auction mechanism has to consider five major challenges: strategic behaviors of unknown users, channel heterogeneity, preference diversity, channel spatial reusability, and social welfare maximization. Unfortunately, none of the existing work fully considered these five challenges. In this paper, we model the problem of heterogeneous spectrum allocation as a combinatorial auction, and propose AEGIS, which is the first framework of unknown combinatorial Auction mEchanisms for heteroGeneous spectrum redIStribution. AEGIS contains two mechanisms, namely AEGIS-SG and AEGIS-MP. AEGIS-SG is a direct revelation combinatorial spectrum auction mechanism for unknown single-minded users, achieving strategy-proofness and approximately efficient social welfare. We further design an iterative ascending combinatorial auction, namely AEGIS-MP, to adapt to the scenario with unknown multi-minded users. AEGIS-MP is implemented in a set of undominated strategies and has a good approximation ratio. We evaluate AEGIS on two practical datasets: Google Spectrum Database and GoogleWiFi. Evaluation results show that AEGIS achieves much better performance than the state-of-the-art mechanisms.

Ad exchanges are kind of the most popular online advertising marketplaces for trading ad spaces over the Internet. Ad exchanges run auctions to sell the ad spaces on publishers' web-pages to advertisers, who want to display ads on the ad spaces. However, the parties in the auction cannot check whether the auction is carried out correctly or not. Furthermore, the advertisers are usually not willing to reveal their sensitive information when participating in the auction. In this paper, we jointly consider the auction verifiability and advertisers' privacy preservation, and propose ERA, which is an Efficient, pRivacy-preserving, and verifiAble online auction mechanism for ad exchanges. ERA exploits an Order Preserving Encryption Scheme (OPES) to guarantee privacy-preservation, and achieves verifiability by integrating a Certified Bulletin Board (CBB) and a protocol of Privacy-Preserving Integer Comparison (PPIC), which is based on the Paillier's Homomorphic Encryption Scheme (PHES). We extensively evaluate the performance of ERA, and our evaluation results show that ERA satisfies the properties of verifiability and privacy-preservation with low overhead, so ERA can be easily deployed in today's ad exchanges.

Bandwidth reservation has been recognized as a value-added service to the cloud provider in recent years. We consider an open market of cloud bandwidth reservation, in which cloud providers offer bandwidth reservation services to cloud tenants, especially online streaming service providers, who have strict requirements on the amount of bandwidth to guarantee their quality of services. In this paper, we model the open market as a double-sided auction, and propose the first family of STrategy-proof double Auctions for multi-cloud, multi-tenant bandwidth Reservation (STAR). STAR contains two auction mechanisms. The first one, STAR-Grouping, divides the tenants into groups by a bid-independent way, and carefully matches the cloud providers with the tenant groups to form good trades. The second one, STAR-Padding, greedily matches the cloud providers with the tenants, and fills the partially reserved cloud provider(s) with a novel virtual padding tenant who can be a component of the auctioneer. Our analysis shows that both of the two auction mechanisms achieve strategy-proofness and ex-post budget balance. Our evaluation results show that they achieve good performance in terms of social welfare, cloud bandwidth utilization, and tenant satisfaction ratio.

Auction is believed to be an effective way to solve or relieve the problem of radio spectrum shortage, by dynamically redistributing idle wireless channels of primary users to secondary users. However, to design a practical channel auction mechanism, we have to consider five challenges, including strategy-proofness, channel spatial reusability, channel heterogeneity, bid diversity, and social welfare maximization. Unfortunately, none of the existing works fully considered the five design challenges. In this paper, we present the first in-depth study on the problem of dynamic channel redistribution jointly considering the five design challenges, and present SMASHER, which is a family of Strategy-proof coMbinatorial Auction mechaniSms for HEterogeneous channel Redistribution. SMASHER contains two strategy-proof auction mechanisms, namely SMASHER-AP and SMASHER-GR. SMASHER-AP is a strategy-proof, approximately efficient combinatorial auction mechanism for indivisible channel redistribution. We further consider the case, in which channels can be shared by the users in a paradigm of time-division multiplexing and propose SMASHER-GR, which is a strategy-proof channel allocation and scheduling mechanism. We have extensively evaluated our designs. The evaluation results show that our designs achieve much better performance than existing works.

Online mechanism design has been widely applied to various practical applications. However, designing a strategy-proof online mechanism is much more challenging than that in a static scenario due to short of knowledge of future information. In this paper, we investigate online auctions with time discounting values, in contrast to the flat values studied in most of existing work. We present a strategy-proof 2-competitive online auction mechanism despite of time discounting values. We also implement our design and compare it with off-line optimal solution. Our numerical results show that our design achieves good performance in terms of social welfare, revenue, average winning delay, and average valuation loss.

With the growing deployment of wireless communication technologies, radio spectrum is becoming a scarce resource. Auctions are believed to be among the most effective tools to solve or relieve the problem of radio spectrum shortage. However, designing a practical spectrum auction mechanism has to consider five major challenges: strategic behaviors of unknown users, channel heterogeneity, preference diversity, channel spatial reusability, and social welfare maximization. Unfortunately, none of existing work fully considered these five challenges. In this paper, we model the problem of heterogeneous spectrum allocation as a combinatorial auction, and propose AEGIS, which is the first framework of unknown combinatorial auction mechanisms for heterogeneous spectrum redistribution. AEGIS contains two mechanisms, namely AEGIS-SG and AEGIS-MP. AEGIS-SG is a direct revelation combinatorial spectrum auction mechanism for unknown single-minded users, achieving strategy-proofness and approximately efficient social welfare. We further design an iterative ascending combinatorial auction, namely AEGIS-MP, to adapt to the scenario with unknown multi-minded users. AEGIS-MP is implemented in a set of undominated strategies and has a good approximation ratio. We evaluate AEGIS on two practical datasets: Google Spectrum Database and GoogleWiFi. Evaluation results show that AEGIS achieves much better performance than the state-of-the-art mechanisms.

Cooperative communication is a new fashion to alleviate the low channel utilization and signal fading problems in today's wireless network. The success of cooperative communication heavily depends on the efficient assignment of relay resource. Auction theory has been applied successfully to allocate limited resources in wireless network for decades. However, most of the existing auction mechanisms restricted buyers to use simple bidding language, which greatly lowers the social welfare and relay assignment efficiency. In this paper, we model the relay assignment as a combinatorial auction with flexible bidding language and propose SAIL, which is a Strategy-proof and Approximately effIcient combinatoriaL auction for relay assignment in cooperative communication. We show analytically that SAIL is strategy-proof and achieves approximate efficient social welfare. Furthermore, we present evaluation results to show that SAIL achieves a good system performance in terms of social welfare, buyer satisfaction and relay utilization.

Auction is believed to be an effective way to solve or relieve the problem of radio spectrum shortage, by dynamically redistributing idle wireless channels of primary users to secondary users. However, to design a practical channel auction mechanism, we have to consider five challenges, including strategy-proofness, channel spatial reusability, channel heterogeneity, bid diversity, and social welfare maximization. Unfortunately, none of the existing works fully considered the five design challenges. In this paper, we present the first in-depth study on the problem of dynamic channel redistribution by jointly considering the five design challenges, and present SMASHER, which is a Strategy-proof coMbinatorial Auction mechaniSm for HEterogeneous channel Redistribution. Our analyses show that SMASHER achieves both strategy-proofness and approximately efficient social welfare.