This paper proposes a new approach to accelerate spectral norm estimation for a kernel matrix of n data points. Our key intuition is that, by applying the seminal random feature technique, we can well estimate the norm without computing or operating on the n-by-n kernel matrix but only an n-by-q random feature matrix with q ≪ n features, thereby significantly reducing the estimation time from O(n2) to O(nq).Technically, our analysis suggests the spectral norm of a kernel matrix can be approximated by that of its corresponding random feature matrix with an $\tilde O\left( {\ln n/\sqrt q } \right)$ relative norm approximation error. This is comparable to the relative norm estimation error of power iteration (PI), a popular efficient norm estimation method, and suggests our method can be integrated with PI to further accelerate norm estimation without deteriorating the estimation accuracy. Based on these insights, we design a random feature-based power iteration (RFPI) estimator for the kernel matrix spectral norm. Experimental results on two real-world datat sets show RFPI has significantly less estimation time than PI while maintaining competitive estimation accuracy.

In machine learning, the relatedness across multiple tasks is usually complex and entangled. Due to dataset bias, the relatedness among tasks might be distorted and mislead the training of the models with solid learning ability, such as the multi-task neural networks. In this paper, we propose the idea of Relatedness Refinement Multi-Task Learning (RRMTDL) by introducing adversarial learning in the multi-task deep neural network to tackle the problem. The RRMTDL deep learning model restrains the misleading relatedness task by adversarial training and extracts information sharing across tasks with valuable relatedness. With RRMTDL, multi-task deep learning can enhance the task-specific representation for the major tasks by excluding the misleading relatedness. We design tests with various combinations of task-relatedness to validate the proposed model. Experimental results show that the RRMTDL model can effectively refine the task relatedness and prominently outperform other multi-task deep learning models in datasets with entangled task labels.

We propose a model-agnostic randomized learning framework based on Random Hypothesis Subspace Sampling (RHSS). Given any hypothesis class, it randomly samples $k$ hypotheses and learns a near-optimal model from their span by simply solving a linear least square problem in $O(n k^2)$ time, where $n$ is the number of training instances. On the theory side, we derive the performance guarantee of RHSS from a generic subspace approximation perspective, leveraging properties of metric entropy and random matrices. On the practical side, we apply the RHSS framework to learn kernel, network and tree based models. Experimental results show they converge efficiently as $k$ increases and outperform their model-specific counterparts including random Fourier feature, random vector functional link and extra tree on real-world data sets.

Active learning (AL) aims to actively label training data for supervised learners to efficiently improve accuracy of the trained models. However, traditional AL techniques ignore model fairness, which is an important social norm in modern machine learning applications. In this paper, we propose the first fairness-aware active learning technique for decoupled model called D-FA2L. It labels data that receive disagreed predictions from the decoupled models, and we hypothesize it can simultaneously improve model fairness and model accuracy. We present theoretical justification of D-FA2L, proving it can reduce model unfairness under proper conditions. In experiments, we show D-FA2L can reduce model unfairness effectively, and the reduction is more efficient than both classic and state-of-the-art AL techniques on three data sets. In the meantime, D-FA2L is able to maintain similar improvement rate on model accuracy.

Existing studies on individual fairness focus on the passive setting and typically require $O(\frac{1}{\varepsilon^2})$ labeled instances to achieve an $\varepsilon$ bias budget. In this paper, we build on the elegant Approximately Metric-Fair (AMF) learning framework and propose an active AMF learner that can provably achieve the same budget with only $O(\log \frac{1}{\varepsilon})$ labeled instances. To our knowledge, this is a first and substantial improvement of the existing sample complexity for achieving individual fairness. Through experiments on three data sets, we show the proposed active AMF learner improves fairness on linear and non-linear models more efficiently than its passive counterpart as well as state-of-the-art active learners, while maintaining a comparable accuracy. To facilitate algorithm design and analysis, we also design a provably equivalent form of the approximate metric fairness based on uniform continuity instead of the existing almost Lipschitz continuity.