Chenhao Wang

Hau Chan, Jianan Lin, Chenhao Wang

We study the mechanism design problem of facility location on a metric space in the learning-augmented framework, where mechanisms have access to imperfect predictions of the optimal facility locations. Our objective is to design strategyproof (SP) mechanisms that truthfully elicit agents' preferences over facility locations and, using the given prediction, select a facility location that approximately minimizes the maximum cost among all agents. In particular, we seek SP mechanisms whose approximation guarantees depend on the prediction error: they should achieve improved performance when the prediction is accurate (the property of \emph{consistency}) while still ensuring strong worst-case guarantees when the prediction is arbitrarily inaccurate (the property of \emph{robustness}). On the real line, we characterize all deterministic SP mechanisms with consistency strictly better than 2 and bounded robustness for the maximum cost. We show that any such mechanism must coincide with the MinMaxP mechanism, which returns the prediction if it lies between the two extreme agent locations and otherwise returns the agent location closest to the prediction. For any prediction error $η\ge 0$, we prove that MinMaxP achieves a $(1+\min(1, η))$-approximation and that no deterministic SP mechanism can obtain a better approximation ratio. In addition, for two-dimensional spaces with the $\ell_p$ distance, we analyze the approximation guarantees of a deterministic mechanism that applies MinMaxP independently on each coordinate, as well as a randomized mechanism that selects between two deterministic mechanisms with carefully chosen probabilities. We further extend these results to the $L_p$-norm social cost objective on the line metric and the maximum cost objective on the tree metric. Finally, we examine the group strategyproofness of the mechanisms.

Chenhao Wang, Qianxin Yi, Xiuwu Liao et al.

Frequent Directions, as a deterministic matrix sketching technique, has been proposed for tackling low-rank approximation problems. This method has a high degree of accuracy and practicality, but experiences a lot of computational cost for large-scale data. Several recent works on the randomized version of Frequent Directions greatly improve the computational efficiency, but unfortunately sacrifice some precision. To remedy such issue, this paper aims to find a more accurate projection subspace to further improve the efficiency and effectiveness of the existing Frequent Directions techniques. Specifically, by utilizing the power of Block Krylov Iteration and random projection technique, this paper presents a fast and accurate Frequent Directions algorithm named as r-BKIFD. The rigorous theoretical analysis shows that the proposed r-BKIFD has a comparable error bound with original Frequent Directions, and the approximation error can be arbitrarily small when the number of iterations is chosen appropriately. Extensive experimental results on both synthetic and real data further demonstrate the superiority of r-BKIFD over several popular Frequent Directions algorithms, both in terms of computational efficiency and accuracy.

Qianxin Yi, Chenhao Wang, Kaidong Wang et al.

Low-tubal-rank tensor approximation has been proposed to analyze large-scale and multi-dimensional data. However, finding such an accurate approximation is challenging in the streaming setting, due to the limited computational resources. To alleviate this issue, this paper extends a popular matrix sketching technique, namely Frequent Directions, for constructing an efficient and accurate low-tubal-rank tensor approximation from streaming data based on the tensor Singular Value Decomposition (t-SVD). Specifically, the new algorithm allows the tensor data to be observed slice by slice, but only needs to maintain and incrementally update a much smaller sketch which could capture the principal information of the original tensor. The rigorous theoretical analysis shows that the approximation error of the new algorithm can be arbitrarily small when the sketch size grows linearly. Extensive experimental results on both synthetic and real multi-dimensional data further reveal the superiority of the proposed algorithm compared with other sketching algorithms for getting low-tubal-rank approximation, in terms of both efficiency and accuracy.