Tutorials

General Abstract:  In practice, signals and data are not unstructured. Their samples usually lie around low-dimensional manifolds and have high correlation among them. Such characteristics can be effectively described by low rankness. As an extension to the sparsity of first order signals, such as voices, low rankness is also an effective measure for the sparsity of second order signals, such as images. In this tutorial, based on our own work, we review the theories, algorithms and applications of the low rank subspace recovery models in signal and data processing.

Part I (by John Wright): Low-Rank Subspace Recovery – Theories

Abstract of Part I:  We present the popular low rank models, including Robust PCA, Robust PCA with Outlier Pursuit, Low-Rank Representation, Latent Low-Rank Representation, and their exact recovery guarantees and closed-form solutions.

Part II (by Zhouchen Lin): Low-Rank Subspace Recovery – Algorithms

Abstract of Part II:  We present efficient algorithms to solve the low rank models. The convex ones include: Accelerated Proximal Gradient, Alternating Direction Method, and Linearized Alternating Direction Method. Nonconvex ones include: Iterative Reweighted Least Squares, Generalized Singular Value Thresholding, and Factorization Method.

Part III (by Zhouchen Lin): Low-Rank Subspace Recovery – Applications

Abstract of Part III:  We present representative applications of low rank models in signal/image/text processing and computer vision.

Part I (by Zongpeng Li): Virtual Machine Auctions in Cloud Computing

Abstract of Part I:  Cloud computing has emerged as a cost-effective solution to elastic computing. Computing, storage and communication resources in data centers are virtualized and packed into various types of virtual machines (VMs) to serve cloud users. The cloud market is a large and complex one, with VM transactions happen mainly in two fashions: long-term contracts and short term auctions. We will review a series of recent work on the design of short-term VM auctions between the cloud provider and the cloud users, including both one-round auctions and online auctions that span multiple rounds. The desired properties pursued in these VM auction design include truthful bidding, computational efficiency and economic efficiency. The main techniques applied include approximation algorithm design, primal-dual optimization, online algorithm design, and randomized auction design.

Part II (by Hong Xu): Load balancing in data center networks

Abstract of Part II:  Modern data center networks often use Clos topologies such as fat tree or leaf-spine that provide many equal-cost paths between hosts. Load balancing among these paths is thus crucial to the latency performance of millions of mice flows in a large-scale network. This tutorial covers two parts. In the first, I will introduce necessary background about Clos topologies, the de factor load balancing protocol used in commodity switches—ECMP, and the latency problem they cause. In the second I will talk about two new distributed data plane load balancing protocols that improve upon ECMP significantly. The first, RepNet, is an application layer mechanism that replicates each mice flow to distinct paths, and exploits the path diversity of congestion to improve latency. It can be deployed today without modifying hosts or switches. The second, Expeditus, is a distributed congestion-aware load balancing protocol. It monitors congestion information from ordinary data packets, and dynamically chooses the least congested path for each mice flow to improve latency. We present our design and preliminary evaluation of Expeditus that overcomes the fundamental challenge of scalability in a large-scale data center network.

Part I (by Wotao Yin): Operator Splitting for Parallel and Distributed Optimization

Abstract of Part I:  Operator splitting breaks a complicated and possible nonsmooth optimization problem into simple steps, which can be easily parallelized or distributed. The resulting algorithms are often very short and easy to implement and exhibit (nearly) state-of-the-art performance for large-scale optimization problems. Operator splitting has led to a large number of recent algorithms in machine learning, compressed sensing, medical imaging, geophysics, and bioengineering. The importance of operator splitting, a technique that dates back to the 1950, has significantly increased in the past decade.

This tutorial will overview the pipeline operator splitting, from identifying simple parts in the original problem, to applying operator-splitting schemes, and to developing parallel and distributed algorithms. We will cover a number of existing algorithms such as von Neumann’s alternating projection, iterative soft-thresholding algorithm, ADMM, various primal-dual algorithms, as well as new algorithms for more complicated problems. The convergence results are presented. Through examples, we also demonstrate that they lead to high-performance low-cost methods for large-scale optimization problems.

This talk includes joint work with Damek Davis, Zhimin Peng, Yangyang Xu, and Ming Yan.

Part II (by Tong Zhang): Stochastic Optimization Techniques for Big Data Machine Learning

Abstract of Part II:  Many modern big-data machine learning problems encountered in the internet industry involve optimization problems so large that traditional methods are difficult to handle. The complex issues in these large scale applications have stimulated fast development of novel optimization techniques in recent years.

I will present an overview of progresses made by the machine learning community to handle these large scale optimization problems, as well as challenges and directions.

Part I: Introduction to Deep Learning

Deep learning has become a major breakthrough in artificial intelligence and achieved amazing success on solving grand challenges in many fields including computer vision. Its success benefits from big training data and super parallel computational power emerging in recent years, as well as advanced model design and training strategies. In this part of tutorial, Xiaogang will try to introduce deep learning and explain the magic behind it with layman terms. Through concrete examples of computer vision applications, Xiaogang will focus on four key points about deep learning. (1) Different than traditional pattern recognition systems, which heavily rely on manually designed features, deep learning automatically learns hierarchical feature representations from data and disentangles hidden factors of input data through multi-level nonlinear mappings. (2) Different than existing pattern recognition systems which sequentially design or training their key components, deep learning is able to jointly optimize all the components and crate synergy through close interactions among them. (3) While most machine learning tools can be approximated with neural networks with shallow structures, for some tasks, the expressive power of deep models increases exponentially as their architectures go deep. (4) Benefitting the large learning capacity of deep models, we also recast some classical computer vision challenges as high-dimensional data transform problems and solve them from new perspectives.

Part II: Deep Learning for Face Recognition

In this part of tutorial, Xiaogang will introduce their recent works on deep learning for face recognition. With a novel deep model and a moderate training set with 400,000 face images, 99.47% accuracy has been achieved on LFW, the most challenging and extensively studied face recognition dataset. Deep learning provides a powerful tool to separate intra-personal and inter-personal variations, whose distributions are complex and highly nonlinear, through hierarchical feature transforms. It is essential to learn effective face representations by using two supervisory signals simultaneously, i.e. the face identification and verification signals. Some people understand the success of deep learning as using a complex model with many parameters to fit a dataset. Instead of treating it as a black box, Xiaogang and his team further investigate face recognition process in deep nets, what information is encoded in neurons, and how robust they are to data corruptions. We discovered several interesting properties of deep nets, including sparseness, selectiveness and robustness.

In Multi-View Perception, a hybrid deep model is proposed to simultaneously accomplish the tasks of face recognition, pose estimation, and face reconstruction. It employs deterministic and random neurons to encode identity and pose information respectively. Given a face image taken in an arbitrary view, it can untangle the identity and view features, and in the meanwhile the full spectrum of multi-view images of the same identity can be reconstructed. It is also capable to interpolate and predict images under viewpoints that are unobserved in the training data.

Next, Shiguang Shan will introduce their recent practices on deep learning for face analysis and recognition. One of his team’s works is CNN-based feature learning for face recognition and expression recognition, which helps them win both the PaSC video-based face recognition challenge organized by the IEEE International Conference on Face and Gesture Recognition 2015 (FG’15) and the EmotioW2014 challenge organized by ACM ICMI 2014. Shiguang will introduce how their systems achieved the best results in both challenges.

Most DL models work well only with large-scale training data. Shiguang will then discuss how to learn deep models, even in case only “small” data are available. The basic idea is to approximate the high degree non-linearity by “dividing and conquering” or “piece-wise non-linearity”. Two example practices will be introduced. One is the Coarse-to-Fine Auto-encoder Networks (CFAN) for face alignment, which cascades several deep models. In the other work, titled Stacked Progressive Auto-Encoder (SPAE), the targets of the middle layers are imposed to satisfy the progressive prior of the pose changes. Both works imply that deep models elaborately designed can also work well in case of “small” data.