The long-term goal of research in my group is to create provable machine learning algorithms that facilitate efficient and accurate data analysis. In the “big data” era, despite the plethora of data in both public and private sectors, most datasets are incompletely observed. The target structure is often missing, and the salient structures are obscured by the raw feature representation. Although machine learning is evolving to tackle these challenges with increasingly delicate models, the training schemes have been relying on heuristics that provide no theoretical guarantees such as global optimality.

1. Convexify multi-layer neural networks by reformulating them in terms of the kernel matrices of the latent output, discovering salient data abstractions efficiently under various network architectures. This was first achieved for a single-hidden layer [27], later extended to multiple-hidden layers using normalized kernels [21], then to structured latent representations such as chains and graph matching [18], and finally to an inductive setting [13] that is scalable to tens of thousands of examples [T1].

2. Incorporate prior knowledge and structured correlations in data while retaining global optimality. A lot of domain specific priors such as invariance and robustness can be modeled effectively in the framework. We first achieved it in [11] and [T2] by warping the kernels with transformation invariance and directional smoothness, tapping into our original observation that many invariances can be compactly represented by a linear functional [25]. In [8], this was further extended to sublinear invariances such as logical relationships between multiple classes and mixup regularization, and the result is a novel semi-inner-product space where the representer of each example can be efficiently embedded into a Euclidean space. This is a transformative breakthrough that enables a variety of generalized invariances to be incorporated in convex representation learning, and we are applying it to unsupervised domain adaptation and adversarial training of graph neural networks.

3. Design efficient and provable optimization algorithms based on greedy approximation and parallel optimization, both exploiting the problem structure such as double separability. To optimize kernel matrices, we utilized low-rank approximation through the conditional gradient algorithm, establishing the first O(1/epsilon) rate of convergence in [2, 30] and [T1]. It was then accelerated to linear convergence on polytopes whose rates were tightened, for the first time, by using the sparsity of the solution [15]. We also discovered the first linear convergence for variance-reduced stochastic optimization with Bregman divergence on min-max problems [16], O(1/epsilon) rates for finding the minimal enclosing convex shapes [37], along with distributed optimization for huge datasets (228 GB) and models (358 GB) [10, 17].