Despite the success of deep learning, from a theoretical standpoint, it remains absurdly unclear why deep learning is better than shallow learning. The main difficulty comes from that we do not actually know how the network features at intermediate layers are learned hierarchically. Why does the first layer learn edges, the second layer learn textures, the third layer learn patterns? Or, do they? (Spoiler alert, not really.)

We present a theory towards explaining how hierarchical feature learning is done, by breaking the learning process into three principles: forward feature learning, backward feature correction, and feature purification. They together show how network features evolve during the training process, and elegantly match what happen in real world deep learning tasks.

On the technical side, we give (1) the first theory showing that deep learning can be time efficient on certain learning tasks, where NO KNOWN shallow learning algorithms are efficient; and (2) the first theory showing how adversarial training of a neural network can lead to provably robust models, when low-complexity models such as linear models MUST be vulnerable to adversarial attacks even with infinite training data.

Packing and covering linear programs (PC-LPs) form an important class of LPs across computer science, operations research, and optimization. In 1993, Luby and Nisan constructed an iterative algorithm for approximately solving PC-LPs in nearly linear time, where the time complexity scales nearly linearly in N, the number of nonzero entries of the matrix, and polynomially in e, the (multiplicative) approximation error.

Unfortunately, existing nearly linear-time algorithms [4, 10, 23, 31, 35, 36] for solving PC-LP s require time at least proportional to 1/e^2. In this paper, we break this longstanding barrier by designing a solver that runs in time O(N/e).

Joint work with Lorenzo Orecchia

The experimental design problem concerns the selection of \(k\) points from a potentially very large design pool of \(p\)-dimensional vectors, so as to maximize the statistical efficiency regressed on the selected \(k\) design points.

We achieve \(1+\varepsilon\) approximations to all popular optimality criteria for this problem, including A-optimality, D-optimality, T-optimality, E-optimality, V-optimality and G-optimality, with only \(k = O(p/\varepsilon^2)\) design points.

In contrast, to the best of our knowledge, previously (1) no polynomial-time algorithm exists for achieving any \(1+\varepsilon\) approximations for D/T/E/G-optimality, and (2) the algorithm achieving \(1+\varepsilon\) approximation for A/V-optimality require \(k \geq \Omega(p^2/\varepsilon)\).

Joint work with Yuanzhi Li, Aarti Singh, and Yining Wang.

In this tutorial, we will provide an accessible and extensive overview on recent advances to optimization methods based on stochastic gradient descent (SGD), for both convex and non-convex tasks.

In particular, this tutorial shall try to answer the following questions with theoretical support. How can we properly use momentum to speed up SGD? What is the maximum parallel speedup can we achieve for SGD? When should we use dual or primal-dual approach to replace SGD? What is the difference between coordinate descent (e.g. SDCA) and SGD? How is variance reduction affecting the performance of SGD? Why does the second-order information help us improve the convergence of SGD?

In STOC 2015, we developed a regret minimization framework for matrix games, and applied it to give faster algorithms for "finding graph linear-sized spectral sparsifiers."

In this talk, I will review and upgrade this framework to obtain nearly optimal algorithms for (1) online eigenvector and for (2) experiment design, two famous problems in learning theory and statistics respectively.

Many machine learning tasks can be solved via generic optimization methods such as gradient descent and stochastic gradient descent. In this talk, I will argue that this path of algorithm design may be restrictive and less efficient,

I will show instead how to develop novel optimization tools to enrich the dimension of algorithm design. In particular, I will present a "linear-coupling" framework, and apply it to obtain faster first-order algorithms for stochastic convex optimization (e.g., SVM, Lasso regression) and for stochastic non-convex optimization (e.g., deep learning).

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient method, the Chebyshev approximation theory, and raise several open questions at the end. No prior knowledge is required on first-order methods.

[1] Even Faster Accelerated Coordinate Descent Using Non-Uniform Sampling.
[2] The First Direct Acceleration of Stochastic Gradient Methods.
[3] Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent.

Regret minimization over the PSD cone is a key component in many fast spectral algorithms, and yields nearly-linear time algorithms for many versions of graph partitioning problems. All applications of this idea rely on the matrix version of the classical multiplicative weight update method (MWU).

In this talk, I explain how Matrix MWU naturally arises as an instance of the Follow-the-Regularized-Leader method with the entropy regularizer. I will then generalize this approach to a larger class of regularizers. As an application, I will provide an alternative construction of the linear-sized spectral sparsifiers of Batson, Spielman and Srivastava, and show how to construct these sparsifiers in almost quadratic time.

Fast iterative methods from Convex Optimization play a crucial role in a number of recent breakthroughs in the design of nearly-linear-time algorithms for fundamental graph problems, such as maximum flow and graph partitioning. Multiplicative Weight Updates, Euclidean and Non-Euclidean Gradient Descent, and Nesterov's Method have become a mainstay in the construction and analysis of fast algorithms.

However, until recently, the relation between these different methods and the reason for their success have been somewhat murky. What is the exact relation between Multiplicative Weight Updates and Gradient Descent? Why do Multiplicative Weight Updates show up in so many settings? What is the intuition behind Nesterov's iterative algorithm that achieves the asymptotically optimal iteration count for smooth convex functions (hint: it isn't just an algebraic trick)? The answer to these questions was not clear.

In this survey, we will provide answers by presenting a unified framework that reveals the power and limitations of each method and provides much needed geometric intuition. Among other insights, we will explain how Multiplicative Weight Updates are a particular instance of a dual iterative method, known as Mirror Descent, and how Nesterov's algorithm can be naturally derived as a combination of Mirror and Gradient Descent.

This talk is based on joint work and also co-lectured with Lorenzo Orecchia.

Motivated by applications of large-scale graph clustering, we study random-walk-based local algorithms whose running times depend only on the size of the output cluster, rather than the entire graph. All previously known such algorithms guarantee an output conductance of \(\tilde{O}(\sqrt{\phi(A)})\) when the target set A has conductance \(\phi(A)\in[0,1]\). In this paper, we improve it to \[\tilde{O}\bigg( \min\Big\{\sqrt{\phi(A)}, \frac{\phi(A)}{\sqrt{\mathsf{Conn}(A)}} \Big\} \bigg)\enspace, \] where the internal connectivity parameter \(\mathsf{Conn}(A)\in[0,1]\) is defined as the reciprocal of the mixing time of the random walk over the induced subgraph on A.

For instance, using \(\mathsf{Conn}(A)=\Omega(\lambda(A)/\log n)\) where \(\lambda\) is the second eigenvalue of the Laplacian of the induced subgraph on A, our conductance guarantee can be as good as \(\tilde{O}(\phi(A)/\sqrt{\lambda(A)})\). This builds an interesting connection to the recent advance of the so-called improved Cheeger's Inequality [KKL+13], which says that global spectral algorithms can provide a conductance guarantee of \(O(\phi_{\mathsf{opt}}/\sqrt{\lambda_3})\) instead of \(O(\sqrt{\phi_{\mathsf{opt}}})\).

In addition, we provide theoretical guarantee on the clustering accuracy (in terms of precision and recall) of the output set. We also prove that our analysis is tight, and perform empirical evaluation to support our theory on both synthetic and real data.

It is worth noting that, our analysis outperforms prior work when the cluster is well-connected. In fact, the better it is well-connected inside, the more significant improvement (both in terms of conductance and accuracy) we can obtain. Our results shed light on why in practice some random-walk-based algorithms perform better than its previous theory, and help guide future research about local clustering.

This is joint work with Silvio Lattanzi and Vahab Mirrokni.