The value and copyright of training data are crucial in the artificial intelligence industry. Service platforms should protect data providers' legitimate rights and fairly reward them for their contributions. Shapley value, a potent tool for evaluating contributions, outperforms other methods in theory, but its computational overhead escalates exponentially with the number of data providers. Recent studies on Shapley values have proposed various approximation algorithms to address the computational complexity issues inherent in exact calculations. However, they need to retrain for each test sample, leading to intolerable costs. We propose Fast-DataShapley, a one-pass training framework that leverages the weighted least squares characterization of the Shapley value to train a reusable explainer model with real-time reasoning speed. Given new test samples, no retraining is required to calculate the Shapley values of the training data. Additionally, we propose three methods with theoretical guarantees to reduce training overhead from two aspects: the approximate calculation of the utility function and the reduction of the sample space complexity. We analyze time complexity to show the efficiency of our methods. The experimental evaluations on various image datasets demonstrate superior performance and efficiency compared to baselines. Specifically, the performance is improved to more than 2×, and the explainer's training speed can be increased by two orders of magnitude.

Distributed Parameter-Efficient Fine-Tuning (PEFT) has emerged as a promising framework for personalizing Large Language Models (LLMs) by leveraging a collaboration between cloud servers and edge devices. However, this paradigm harbors a critical privacy vulnerability: the cloud can perform inversion attacks on the intermediate results (e.g., embeddings) sent from the edge to reconstruct the user's raw input prompt. Existing privacy-preserving techniques present a difficult trade-off: they are either too computationally expensive or they degrade model performance. To address this challenge, we introduce PrivSplit, a novel and lightweight protocol for prompt privacy in the Distributed PEFT framework. The core idea of PrivSplit is a ''Split and Compensate'' strategy: the edge device splits the input embedding into a public part sent to the cloud and a private part retained locally. The influence of this private part is then perfectly restored using a precise, lossless compensation mechanism during the interaction. We theoretically prove that PrivSplit is secure against both reconstruction and distinguishability attacks. Crucially, our method is perfectly lossless, ensuring that the model's performance is mathematically identical to the non-private baseline. This allows the security parameters to be arbitrarily strengthened without any impact on utility, breaking the conventional privacy-performance trade-off.

Large-scale data analysis services require efficient periodic model updates to adapt to the possibly changing data distributions. Manually labeling all available samples for task model updates is infeasible for a large sample scale. Active learning technique is proposed to iteratively select subsets of the most informative samples for labeling. From our experience of applying active learning in a real-world video analysis system, we identify a previously overlooked bottleneck of time cost: data selection. Existing active learning methods select data by estimating informativeness (e.g., output confidence) over all unlabeled samples in each iteration. This data selection process can take up to 42% of the time cost of end-to-end model updates in our system (totals include the time for manual labeling, data selection, and model updates.). To address the time cost bottleneck caused by data selection, we propose a new idea: proxy informativeness estimation. We start with modeling the time cost of data selection, from which we identify three key factors: unit estimation cost, the number of samples for estimation, and the number of iteration rounds. The influence of the first two factors increases cumulatively with the number of iteration rounds. Correspondingly, we design a proxy estimator and a sample pooling method, respectively. Our proxy estimator is a lightweight neural network for direct informativeness estimation to replace the role of the high-cost task model, thus reducing the unit cost. And, our sample pooling method leverages historical estimation results to narrow the scope of sample candidates. Based on the above design, we develop ProxySampler, which can be integrated with various active learning approaches as a plug-in. Experimental results show that integrating ProxySampler with state-of-the-art active learning methods can reduce the time cost by 53.6-83.3% (a 2.15-6.01x speedup) when achieving the same accuracy.

Federated learning (FL) has achieved favorable progress in addressing the data silo problem without compromising clients' data privacy. In real-world scenarios, there are numerous low-capacity clients, i.e., devices with limited resources like computational power, storage and bandwidth, holding unique and valuable data. Yet the conventional model-homogeneous paradigm is unsuitable due to its uniform model demands on all clients. To effectively utilize the data from clients of various capacities for learning a well-performing global model, researchers have proposed submodel extraction-based partial training methods allowing clients to locally train heterogeneous submodels of different sizes. However, existing partial training methods are inadequate in terms of parameter space coverage efficiency and convergence stability, which adversely affects convergence rate and the final performance. In this work, we introduce FedEcover, a model-heterogeneous framework to learn a fast and stable converging global model in challenging scenarios with dual heterogeneity of data and client capacity. Specifically, our framework incorporates an efficient submodel extraction scheme applying a random sampling without replacement strategy and a step-size decay mechanism in the global aggregation process, to enable the global model fully leveraging the heterogeneous data distributed across capacity-heterogeneous clients. Experimental results on multiple models and datasets demonstrate that our framework outperforms existing submodel extraction-based partial training methods and model-homogeneous FedAvg in both convergence rate and converged performance of the global model.

The hybrid-storage blockchain (HSB) facilitates flexible data sharing and search applications across decentralized clients. However, ensuring data privacy and result integrity, while enhancing query and result verification efficiency in HSB-based search applications over dynamic datasets, poses significant challenges. In this paper, we propose E3FS, the first efficient, secure, and verifiable search scheme over dynamically updatable datasets in HSB systems, supporting multi-keyword fuzzy search, an important search function. E3FS accelerates search and verification through an updatable hybrid index with an efficient on-chain process. This design integrates encrypted LSH-based Bloom filters for maintaining file keyword information and an inverted index linking each keyword to a novel authenticated index tree spanning multiple files. Lightweight digests of these trees are stored on-chain to assist with verification, achieving sublinear search and verification costs. Moreover, the framework guarantees forward privacy by securely updating and refreshing both on-chain and off-chain index with new secrets upon each data update. Experimental results demonstrate that our solution outperforms state-of-the-art methods, achieving at least$\mathbf{58.6}\times$faster search and$\mathbf{34.4}\times$faster verification while reducing communication overhead by approximately$\mathbf{60}\times$.

The need to safeguard data privacy and adhere to regulations such as GDPR creates data silos and has prompted the emergence and widespread adoption of techniques for distributed databases. To effectively explore the value of data across multiple organizations, techniques for data management, data analysis and data functionality from distributed databases have been proposed. Recently, Vertical Federated Learning (VFL) has become a solution with growing interests, which enables collaborative model training when data features are partitioned into multiple parts and are held by different parties. However, typical VFL methods heavily rely on private set intersection (PSI) to align data before training and only utilize aligned data for training. In this work, we provide a theoretical analysis to show that unaligned data actually contains valuable and rich features, and a thoughtful design that harnesses the potential of unaligned samples to significantly improve the performance of VFL models. Regrettably, many existing methods simply discard unaligned data, resulting in an irrecoverable loss of performance. To address this data sacrifice problem, we introduce the concept of data mixture, which enables the utilization of both aligned and unaligned data during training. Building upon the data mixture idea, we present FedMix, the first on-the-fly and distribution-agnostic framework designed to boost the performance of VFL models by leveraging unaligned data. A data seasoning approach is also designed to utilize auxiliary data lacking label information. Evaluations on diverse datasets under different settings demonstrate the effectiveness of the proposed FedMix compared with various SOTA approaches. FedMix achieves up to 15% model performance improvement and 30.5 hours time cost reduction.

Conversion rate (CVR) prediction is essential in recommender systems, facilitating precise matching between recommended items and users’ preferences. However, the sample selection bias (SSB) and data sparsity (DS) issues pose challenges to accurate prediction. Existing works have proposed the click-through and conversion rate (CTCVR) prediction task which models samples from exposure to ``click and conversion" in entire space and incorporates multi-task learning. This approach has shown efficacy in mitigating these challenges. Nevertheless, it intensifies the false negative sample (FNS) problem. To be more specific, the CTCVR task implicitly treats all the CVR labels of non-click samples as negative, overlooking the possibility that some samples might convert if clicked. This oversight can negatively impact CVR model performance, as empirical analysis has confirmed. To this end, we advocate for discarding the CTCVR task and proposing a Non-click samples Improved Semi-supErvised (NISE) method for conversion rate prediction, where the non-click samples are treated as unlabeled. Our approach aims to predict their probabilities of conversion if clicked, utilizing these predictions as pseudo-labels for further model training. This strategy can help alleviate the FNS problem, and direct modeling of the CVR task across the entire space also mitigates the SSB and DS challenges. Additionally, we conduct multi-task learning by introducing an auxiliary click-through rate prediction task, thereby enhancing embedding layer representations. Our approach is applicable to various multi-task architectures. Comprehensive experiments are conducted on both public and production datasets, demonstrating the superiority of our proposed method in mitigating the FNS challenge and improving the CVR estimation. The implementation code is available at https://github.com/Hjh233/NISE.

Deep ensemble learning has been widely adopted to boost accuracy through combing outputs from multiple deep models prepared for the same task. However, the extra computation and memory cost it entails could impose an unacceptably high deadline miss rate in latency-sensitive tasks. Conventional approaches, including ensemble selection, focus on accuracy while ignoring deadline constraints, and thus cannot smartly cope with bursty query traffic and queries with different hardness. This paper explores redundancy in deep ensemble model inference and presents Schemble, a query difficulty-dependent task scheduling framework. Schemble treats ensemble inference progress as multiple base model inference tasks and schedules tasks for queries based on their difficulty and queuing status. We evaluate Schemble on real-world datasets, considering intelligent Q&A system, video analysis and image retrieval as the running applications. Experimental results show that Schemble achieves a 5× lower deadline miss rate and improves the accuracy by 30.8% given deadline constraints.

Due to the difficulty of obtaining high-quality data in real-world scenarios, datasets inevitably contain noisy labeled data, leading to inefficient data usage and poor model performance. Thus, noisy label detection is an important research topic. Previous efforts mainly focus on noisy label detection on specific datasets that have been collected. Some works select clean samples based on relations between representations during the training process; some works utilize confidence outputs of a pre-trained model for noisy label detection. However, how to perform efficient and fine-grained noisy label detection on constantly arriving datasets in a data lake with a large amount of inventory data has not been explored. The rapidly growing volume and changing distribution of data make conventional methods either incur large computation overhead due to repeated training or become increasingly ineffective on newly arriving data. To address these challenges, in this work, we propose a novel approach ENLD to perform efficient and accurate noisy label detection on incremental datasets. Our extensive experiments demonstrate that ENLD outperforms the next best method in both efficiency and accuracy, which achieves 3.65 ×-4.97× detection speedup and higher average f1 scores with various noise rate settings.

The success of many web services relies on the large-scale domain-specific high-quality labeled dataset. Insufficient public datasets motivate us to reduce the cost of data labeling while maintaining high accuracy in support of intelligent web applications. The rule-based method and the learning-based method are common techniques for labeling. In this work, we study how to utilize the rule-based and learning-based methods for resource-effective text labeling. We propose CoTel, the first ontology-neural co-enhanced framework for text labeling. We propose critical ontology extraction in the rule-based module and ontology-enhanced loss prediction in the learning-based module. CoTel can integrate explicit labeling rules and implicit labeling models and make them help each other to improve resource efficiency in text labeling tasks. We evaluate CoTel on both public datasets and real applications with three different tasks. Compared with the baseline, CoTel can reduce the time cost by 64.75% (a 2.84× speedup) and the number of labeling by 62.07%.

Many data applications can be facilitated or even spawned by joint analysis on databases held by different owners, but privacy concerns are currently the biggest hindrance. Though a practical privacy-preserving collaborative database analytics system is strongly desired, existing approaches do not support efficient queries for several essential SQL operators such as the general join, especially on large databases. In this paper, we propose, analyze, and implement Scape, a Scalable Collaborative Analytics system on Private databasE with malicious security. In Scape, databases from different parties are secretly shared to three non-colluding computing parties. Users can perform various SQL queries (including fully functional Join, Group by, Aggregation, etc.) on shared databases, and all entities learn nothing beyond their priori knowledge during the whole execution even when they deviate from protocols. At the heart of Scape lies several asymptotically efficient SQL protocols. Particularly, our general join protocol has O (n log2n + m) communication/computation cost when joining two tables with o (n) rows to a table with 0 (m) rows, significantly outperforming the state-of-the-art approach with O(n2) cost. The benchmark results confirm the advantages of Scape, which is up to 25 x faster than the baseline.

Data annotation has been a key boost for the artificial intelligence. However, difficult tasks such as fine-grained classification need lots of labeled data to train a feasible model. On the one hand, using people who have expert knowledge on the datasets to annotate all data can be costly. On the other hand, amateurs are cheaper but not able to give precise labels. Related works like machine labeling need labeled data to start up. Crowd-Model labeling can hardly solve complex tasks like fine-grained classification. Lately, combining domain experts and cost-effective crowd to solve complex tasks has become an area of increasing interest in research and industry. However, most works rarely investigate the cost gap between experts and amateurs and see how it influences the final annotation cost. In this paper, we combine both experts and amateurs to build a cost-effective data annotation system called COCA. COCA annotates the target dataset from scratch and save costs by our annotation assignment strategy. Extensive evaluations show that when reaching the same precision, COCA can reach a lower cost than SOTA automatic labeling models when the ratio of expert price to amateur price is above a certain value.

Federated Learning (FL) enables multiple partici-pants to collaboratively train a model in a privacy-preserving way. The performance of the FL model heavily depends on the quality of participants' local data, which makes measuring the contributions of participants an essential task for various purposes, e.g., participant selection and reward allocation. The Shapley value is widely adopted by previous work for contribution assessment, which, however, requires repeatedly leave-one-out retraining and thus incurs the prohibitive cost for FL. In this paper, we propose a highly efficient approach, named DIG-FL, to estimate the Shapley value of each participant without any model retraining. It's worth noting that our approach is applicable to both vertical federated learning (VFL) and horizontal federated learning (HFL), and we provide concrete design for VFL and HFL. In addition, we propose a DIG-FL based reweight mechanism to improve the model training in terms of accuracy and convergence speed by dynamically adjusting the weights of participants according to their per-epoch contributions, and theoretically analyze the convergence speed. Our extensive evaluations on 14 public datasets show that the estimated Shapley value is very close to the actual Shapley value with Pearson's correlation coefficient up to 0.987, while the cost is orders of magnitude smaller than state-of-the-art methods. When there are more than 80% participants holding low-quality data, by dynamically adjusting the weights, DIG-FL can effectively accelerate the convergence and improve the model accuracy.

In online display advertising, guaranteed delivery (GD) ads and real-time bidding (RTB) are two main ways to sell impressions for a publisher. While RTB has gained increasing popularity, there is still a proportion of revenue generated from GD ads [1]. Existing mainstream impression allocation models deal with the two delivery ways separately, failing to achieve optimal allocation for multi-objective under multi-constraints, e.g., maximizing gross merchandise volume pre mille (GPM) and revenue per mille (RPM), thus limiting the overall revenue for both the publisher and advertisers. To solve the above problems, we propose a unified guaranteed impression allocation framework to optimally allocate impressions for both GD ads and RTB ads simultaneously. Specifically, we formulate the optimization problem as a non-convex quadratically constrained quadratic programming (QCQP) problem. Then we design an end-to-end unified impression allocation framework to approximately solve the QCQP problem. Furthermore, experiments on real data from Tencent News show that our design significantly increases the overall revenue of both the publisher and advertisers, while achieving much faster convergence than the current state-of-the-art methods.

Labeling data (e.g., labeling the people, objects, actions, and scene in images) comprehensively and efficiently is a widely needed but challenging task. Numerous models were proposed to label various data and many approaches were designed to enhance the ability of deep learning models or accelerate them. Unfortunately, a single machine-learning model is not powerful enough to extract various semantic information from data. Given certain applications, such as image retrieval platforms and photo album management apps, it is often required to execute a collection of models to obtain sufficient labels. With limited computing resources and stringent delay, given a data stream and a collection of applicable resource-hungry deep-learning models, we design a novel approach to adaptively schedule a subset of these models to execute on each data item, aiming to maximize the value of the model output (e.g., the number of high-confidence labels). Achieving this lofty goal is nontrivial since a model’s output on any data item is content-dependent and unknown until we execute it. To tackle this, we propose an Adaptive Model Scheduling framework, consisting of (1) a deep reinforcement learning-based approach to predict the value of unexecuted models by mining semantic relationship among diverse models, and (2) two heuristic algorithms to adaptively schedule the model execution order under a deadline or deadline-memory constraints, respectively. The proposed framework does not require any prior knowledge of the data, which works as a powerful complement to existing model optimization technologies. We conduct extensive evaluations on five diverse image datasets and 30 popular image labeling models to demonstrate the effectiveness of our design: our design could save around 53% execution time without loss of any valuable labels.

Federated learning (FL) enables large amounts of participants to construct a global learning model, while storing training data privately at each client device. A fundamental issue in this framework is the susceptibility to the erroneous training data. This problem is especially challenging due to the invisibility of clients' local training data and training process, as well as the resource constraints of a large number of mobile and edge devices. In this paper, we try to tackle this challenging issue by introducing the first FL debugging framework, FLDebugger, for mitigating test error caused by erroneous training data. The pro-posed solution traces the global model's bugs (test errors), jointly through the training log and the underlying learning algorithm, back to first identify the clients and subsequently their training samples that are most responsible for the errors. In addition, we devise an influence-based participant selection strategy to fix bugs as well as to accelerate the convergence of model retraining. The performance of the identification algorithm is evaluated via extensive experiments on a real AIoT system (50 clients, including 20 edge computers, 20 laptops and 10 desktops) and in larger-scale simulated environments. The evaluation results attest to that our framework achieves accurate and efficient identification of negatively influential clients and samples, and significantly improves the model performance by fixing bugs.

Labeling data comprehensively and efficiently is a widely needed but challenging task. With limited computing resources, given a data stream and a collection of deep-learning models, we propose to adaptively select and schedule a subset of these models to execute, aiming to maximize the value of the model output. Achieving this goal is nontrivial since a model's output on any data item is content-dependent and hard to predict. In this paper, we present an Adaptive Model Scheduling framework, consisting of 1) a deep reinforcement learning-based approach to predict the value of unexecuted models by mining semantic relationship among diverse models, and 2) two heuristic algorithms to adaptively schedule models under deadline or deadline-memory constraints. The proposed framework does not require any prior knowledge of the data, which works as a powerful complement to existing model optimization technologies. We conduct extensive evaluations on 30 popular image labeling models to demonstrate the effectiveness of our design.

The guaranteed delivery model is widely used in online advertising. The publisher sells impressions in advance by promising to serve each advertiser an agreed-upon number of target impressions that satisfy specific attribute requirements over a fixed time period. Previous efforts usually model the service as a crowd-level or user-level supply allocation problem and focus on searching optimal allocation for online serving, assuming that forecasts of supply are available and contracts are already signed. Existing techniques are not sufficient to meet the needs of today's industry trends: 1) advertisers pursue more precise targeting, which requires not only user-level attributes but also request-level attributes; 2) users prefer more friendly ad serving, which imposes more diverse serving constraints; 3) the bottleneck of the publisher's revenue growth lies in not only the ad serving, but also the forecast accuracy and sales strategy. These issues are non-trivial to address, since the scale of the request-level model is orders of magnitude larger than that of the crowd-level or user-level models. Facing the challenges, we present a holistic design of a request-level guaranteed delivery advertising planning system with careful optimization for all three critical components including impression forecasting, selling and serving. Our system has been deployed in the Tencent online guaranteed delivery advertising system serving billion level users for nearly one year. Evaluations on large-scale real data and the performance of the deployed system both demonstrate that our design can significantly increase the request-level impression forecast accuracy and delivery rate.

Understanding and forecasting user visits is of great importance for a variety of tasks, e.g., online advertising, which is one of the most profitable business models for Internet services. Publishers sell advertising spaces in advance with user visit volume and attributes guarantees. There are usually tens of thousands of attribute combinations in an online advertising system. The key problem is how to accurately forecast the number of user visits for each attribute combination. Many traditional work characterizing temporal trends of every single time series are quite inefficient for large-scale time series. Recently, a number of models based on deep learning or matrix factorization have been proposed for high-dimensional time series forecasting. However, most of them neglect correlations among attribute combinations, or are tailored for specific applications, resulting in poor adaptability for different business scenarios.Besides, sophisticated deep learning models usually cause high time and space complexity. There is still a lack of an efficient highly scalable and adaptable solution for accurate high-dimensional time series forecasting. To address this issue, in this work, we conduct a thorough analysis on large-scale user visits data and propose a novel deep spatial-temporal tensor factorization framework, which provides a general design for high-dimensional time series forecasting. We deployed the proposed framework in Tencent online guaranteed delivery advertising system, and extensively evaluated the effectiveness and efficiency of the framework in two different large-scale application scenarios. The results show that our framework outperforms existing methods in prediction accuracy. Meanwhile, it significantly reduces the parameter number and is resistant to incomplete data with up to 20% missing values.