We provide a novel – and to the best of our knowledge, the first – algorithm for high dimensional sparse regression with constant fraction of corruptions in explanatory and/or response variables. Our algorithm recovers the true sparse parameters with sub-linear sample complexity,in the presence of a constant fraction of arbitrary corruptions. Our main contribution is a robust variant of Iterative Hard Thresholding. Using this, we provide accurate estimators:when the covariance matrix in sparse regression is identity, our error guarantee is near information-theoretically optimal. We then deal with robust sparse regression with unknown structured covariance matrix. We propose a filtering algorithm whichconsists of a novel randomized outlier removal technique for robust sparse mean estimation that may be of interest in its own right: the filtering algorithm is flexible enough to deal with unknown covariance.Also, it is orderwise more efficient computationally than the ellipsoid algorithm.Using sub-linear sample complexity, our algorithm achieves the best known (and first) error guarantee. We demonstrate the effectiveness on large-scale sparse regression problems with arbitrary corruptions.

Extreme multi-label classification (XMC) is the problem of finding the relevant labels for an input, from a very large universe of possible labels. We consider XMC in the setting where labels are available only for groups of samples - but not for individual ones. Current XMC approaches are not built for such multi-instance multi-label (MIML) training data, and MIML approaches do not scale to XMC sizes. We develop a new and scalable algorithm to impute individual-sample labels from the group labels; this can be paired with any existing XMC method to solve the aggregated label problem. We characterize the statistical properties of our algorithm under mild assumptions, and provide a new end-to-end framework for MIML as an extension. Experiments on both aggregated label XMC and MIML tasks show the advantages over existing approaches.

In this paper, we study a simple and generic framework to tackle the problem of learning model parameters when a fraction of the training samples are corrupted. Our approach is motivated by a simple observation: in a variety of such settings, the evolution of training accuracy (as a function of training epochs) is different for clean samples and bad samples. We propose to iteratively minimize the trimmed loss, by alternating between (a) selecting samples with lowest current loss, and (b) retraining a model on only these samples. Analytically, we characterize the statistical performance and convergence rate of the algorithm for simple and natural linear and non-linear models. Experimentally, we demonstrate its effectiveness in three settings: (a) deep image classifiers with errors only in labels, (b) generative adversarial networks with bad training images, and (c) deep image classifiers with adversarial (image, label) pairs (i.e., backdoor attacks). For the well-studied setting of random label noise, our algorithm achieves state-of-the-art performance without having access to any a-priori guaranteed clean samples.

Given a linear regression setting, Iterative Least Trimmed Squares (ILTS) involves alternating between (a) selecting the subset of samples with lowest current loss, and (b) re-fitting the linear model only on that subset. Both steps are very fast and simple. In this paper, we analyze ILTS in the setting of mixed linear regression with corruptions (MLR-C). We first establish deterministic conditions (on the features etc.) under which the ILTS iterate converges linearly to the closest mixture component. We also provide a global algorithm that uses ILTS as a subroutine, to fully solve mixed linear regressions with corruptions. We then evaluate it for the widely studied setting of isotropic Gaussian features, and establish that we match or better existing results in terms of sample complexity. Finally, we provide an ODE analysis for a gradient-descent variant of ILTS that has optimal time complexity. Our results provide initial theoretical evidence that iteratively fitting to the best subset of samples -- a potentially widely applicable idea -- can provably provide state of the art performance in bad training data settings.

Quadratic regression involves modeling the response as a (generalized) linear function of not only the features $x^{j_1}$ but also of quadratic terms $x^{j_1}x^{j_2}$. The inclusion of such higher-order “interaction terms" in regression often provides an easy way to increase accuracy in already-high-dimensional problems. However, this explodes the problem dimension from linear $O(p)$ to quadratic $O(p^2)$, and it is common to look for sparse interactions (typically via heuristics). In this paper, we provide a new algorithm – Interaction Hard Thresholding (IntHT) which is the first one to provably accurately solve this problem in sub-quadratic time and space. It is a variant of Iterative Hard Thresholding; one that uses the special quadratic structure to devise a new way to (approx.) extract the top elements of a $p^2$ size gradient in sub-$p^2$ time and space. Our main result is to theoretically prove that, in spite of the many speedup-related approximations, IntHT linearly converges to a consistent estimate under standard high-dimensional sparse recovery assumptions. We also demonstrate its value via synthetic experiments. Moreover, we numerically show that IntHT can be extended to higher-order regression problems, and also theoretically analyze an SVRG variant of IntHT.

Yanyao Shen, Xu Tan, Di He, Tao Qin, Tie-Yan Liu. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers). 2018.

The algorithmic advancement of synchronizing maps is important in order to solve a wide range of practice problems with possible large-scale dataset. In this paper, we provide theoretical justifications for spectral techniques for the map synchronization problem, i.e., it takes as input a collection of objects and noisy maps estimated between pairs of objects, and outputs clean maps between all pairs of objects. We show that a simple normalized spectral method that projects the blocks of the top eigenvectors of a data matrix to the map space leads to surprisingly good results. As the noise is modelled naturally as random permutation matrix, this algorithm NormSpecSync leads to competing theoretical guarantees as state-of-the-art convex optimization techniques, yet it is much more efficient. We demonstrate the usefulness of our algorithm in a couple of applications, where it is optimal in both complexity and exactness among existing methods.

Cellular network is widely used and device-to-device (D2D)-assisted approaches have been proposed for improving performance on spectrum efficiency, overall throughput and energy efficiency. However, few of them have considered the downlink transmission for multiple concurrent devices from an energy efficiency perspective. In this paper, we focus on a D2D-assisted cellular communication in video stream sharing scenario. Two energy saving solutions for downlink transmission are proposed with constraint on D2D cluster's energy consumption. We take peak signal-to-noise ratio (PSNR) as the measurement for video quality and consider both the downlink transmission energy and reception energy. In particular, we propose the D2D cluster formation approach and the D2D caching performance both for the purpose of energy saving, with distributed merge-and-split algorithm adopted from the perspective of coalition game theory and a relaxation factor defined to give constraints on total energy consumption for each cluster. Both D2D cluster and D2D caching approaches are effective for energy saving for the BS combined with all user devices; however, D2D cluster brings an unfairness problem between the cluster head and other cluster nodes. Therefore, we compare the two approaches on energy saving performance as well as fairness measurement. Moreover, a centralized algorithm for D2D cluster is also proposed as a benchmark for the distributed D2D cluster algorithm. Simulation result shows considerable amount of energy saving in the proposed D2D cluster and caching assisted cellular network for video stream sharing problem.

The energy consumption of a base station (BS) has attracted much attention in the study of wireless communication. Device-to-device communication, which can be utilized to offload the traffic from the BS, provides an effective way to increase network energy efficiency. How to optimally coordinate users to redistribute the traffic so as to minimize the energy consumption is an important issue. In this paper, we study two problems that are critical to this issue. First, considering that relaying data to others incurs costs to the users and different users have different costs, we propose a contract theoretical approach to design the mechanism for pricing the contributions of users. The second problem is to make a proper matching between users who demand data and users who are willing to relay data. Matching theory is exploited to deal with this problem. Specifically, we consider both interference-free and interference scenarios and develop matching algorithms, which can achieve stable matching and weak stable matching, respectively. Simulation results demonstrate the effectiveness of the proposed algorithms.

The issue of data pricing is becoming more important than before in order to build an internet ecosystem. In this paper, we consider a data redistribution market where users with extra data quota are able to sell data to users that have used up their data quota. We consider this market problem with multiple users on both sides, and analyze on two possible market environment to achieve market equilibrium: the exogenous pricing scenario and endogenous pricing scenario. The stable matching algorithm and message-passing algorithm are used respectively. Simulation results show that while exogenous pricing market achieves equilibrium at a certain market price, the endogenous pricing market achieves equilibrium for each pair with better overall performance although without stability.