Matrix Factorization (MF) is essential to many estimation tasks. Most existing matrix factorization methods focus on least squares matrix factorization (LSMF), which aims to minimize a smooth L2 loss between observations and their dependent matrix measurement variables. In reality, however, L1 loss and check loss are widely used in regression to deal with outliers or observations contaminated by skewed or heavy-tailed noise. Although under certain conditions, linear convergence to the global optimality can be established for matrix factorization under the L2 loss, there is a lack of provably efficient algorithms for solving matrix factorization under non-smooth losses. In this paper, we investigate Quantile Matrix Factorization (QMF), the counterpart of Quantile Regression in matrix estimation, that adopts a tunable check loss and introduces robustness to matrix estimation for skewed and heavy- tailed observations, which are prevalent in reality. To deal with the non-smooth loss, we propose Nesterov- smoothed QMF (NsQMF), extending Nesterov's optimal smooth approximation technique to the matrix factorization setting. We then present an alternating minimization algorithm to solve the smooth NsQMF efficiently. We mathematically prove that solving the smoothed NsQMF is equivalent to solving the original non-smooth QMF problem and that our proposed algorithm achieves linear convergence to the global optimality of QMF. Numerical evaluations verify our theoretical findings and demonstrate that NsQMF significantly outperforms the commonly used LSMF and prior approximate smoothing heuristics for QMF under various noise distributions.

Matrix factorization is a popular approach to solving matrix estimation problems based on partial observations. Existing matrix factorization is based on least squares and aims to yield a low-rank matrix to interpret the conditional sample means given the observations. However, in many real applications with skewed and extreme data, least squares cannot explain their central tendency or tail distributions, yielding undesired estimates. In this paper, we propose expectile matrix factorization by introducing asymmetric least squares, a key concept in expectile regression analysis, into the matrix factorization framework. We propose an efficient algorithm to solve the new problem based on alternating minimization and quadratic programming. We prove that our algorithm converges to a global optimum and exactly recovers the true underlying low-rank matrices when noise is zero. For synthetic data with skewed noise and a real-world dataset containing web service response times, the proposed scheme achieves lower recovery errors than the existing matrix factorization method based on least squares in a wide range of settings.

We study the problem of personalized Quality of Service (QoS) estimation for web services. State-of-the-art methods use matrix factorization or collaborative prediction to estimate web service response times and throughput for each user based on partial measurements collected from past invocations. We point out that in reality, both the response times and through-put of web services follow highly skewed distributions. In this case, the conditional mean QoS estimates generated by traditional matrix completion approaches can be heavily biased toward a few outliers, leading to poor web service recommendation performance. In this paper, we propose the Quantile Matrix Factorization (QMF) technique for web service recommendation by introducing quantile regression into the matrix factorization framework. We propose a novel and efficient algorithm based on Iterative Reweighted Least Squares (IRLS) to solve the QMF problem involving a non-smooth objective function. We further extend the proposed QMF approach to take into account user and service side attributes. Extensive evaluation based on a large-scale QoS dataset has shown that our schemes significantly outperform various state-of-the-art web service QoS estimation schemes in terms of personalized recommendation performance.

Virtualized datacenter networks have been deployed in production platforms, e.g., Amazon VPC and VMware's NVP, to offer the flexibility of network management to enterprise-level clients. A common characteristic of these platforms is that they adopt software switches, such as Open vSwitch (OvS), instead of hardware switches to transfer data between VMs. Although group communication is common in enterprise applications, the unique characteristics of software switches have posed new challenges to the design of multicast protocols. How logical multicast can be optimally performed with software switches is still not well understood. In this paper, we observe that unlike hardware switches, the per-stream output rate in a software switch critically depends on the packet processing overhead of flow cloning. We study the optimal OvS multicast topology with or without the help of additional dedicated software switches called service nodes, and formulate the throughput maximization as a new class of degree-supervised combinatorial graph problems due to the presence of flow cloning costs. We propose a lineartime optimal solution that translates into simple forwarding rules installed at each software switch. Through emulation-based OvS profiling and extensive simulation results, we demonstrate that our proposed logical multicast solutions can significantly improve session throughput with the ability to handle load balancing and latency issues, as compared to the state-of-the-art in the literature.

Network latency prediction is important for server selection and quality-of-service estimation in real-time applications on the Internet. Traditional network latency prediction schemes attempt to estimate the latencies between all pairs of nodes in a network based on sampled round-trip times, through either Euclidean embedding or matrix factorization. However, these schemes become less effective in terms of estimating the latencies of personal devices, due to unstable and time-varying network conditions, triangle inequality violation and the unknown ranks of latency matrices. In this paper, we propose a matrix completion approach to network latency estimation. Specifically, we propose a new class of low-rank matrix completion algorithms, which predicts the missing entries in an extracted “network feature matrix” by iteratively minimizing a weighted Schatten-p norm to approximate the rank. Simulations on true low-rank matrices show that our new algorithm achieves better and more robust performance than multiple state-of-the-art matrix completion algorithms in the presence of noise. We further enhance latency estimation based on multiple “frames” of latency matrices measured in the past, and extend the proposed matrix completion scheme to the case of 3-D tensor completion. Extensive performance evaluations driven by real-world latency measurements collected from the Seattle platform show that our proposed approaches significantly outperform various state-of-the-art network latency estimation techniques, especially for networks that contain personal devices.