Robust support vector machine (RSVM) using ramp loss provides a better generalization performance than traditional support vector machine (SVM) using hinge loss. However, the good performance of RSVM heavily depends on the proper values of regularization parameter and ramp parameter. Traditional model selection technique with gird search has extremely high computational cost especially for fine-grained search. To address this challenging problem, in this paper, we first propose solution paths of RSVM (SPRSVM) based on the concave-convex procedure (CCCP) which can track the solutions of the non-convex RSVM with respect to regularization parameter and ramp parameter respectively. Specifically, we use incremental and decremental learning algorithms to deal with the Karush-Khun-Tucker violating samples in the process of tracking the solutions. Based on the solution paths of RSVM and the piecewise linearity of model function, we can compute the error paths of RSVM and find the values of regularization parameter and ramp parameter, respectively, which corresponds to the minimum cross validation error. We prove the finite convergence of SPRSVM and analyze the computational complexity of SPRSVM. Experimental results on a variety of benchmark datasets not only verify that our SPRSVM can globally search the regularization and ramp parameters respectively, but also show a huge reduction of computational time compared with the grid search approach.

Semi-supervised support vector machine (S3VM) is important because it can use plentiful unlabeled data to improve the generalization accuracy of traditional SVMs. In order to achieve good performance, it is necessary for S3VM to take some effective measures to select hyperparameters. However, model selection for semi-supervised models is still a key open problem. Existing methods for semi-supervised models to search for the optimal parameter values are usually computationally demanding, especially those ones with grid search. To address this challenging problem, in this article, we first propose solution paths of S3VM (SPS3VM), which can track the solutions of the nonconvex S3VM with respect to the hyperparameters. Specifically, we apply incremental and decremental learning methods to update the solution and let it satisfy the Karush-Kuhn-Tucker (KKT) conditions. Based on the SPS3VM and the piecewise linearity of model function, we can find the model with the minimum cross-validation (CV) error for the entire range of candidate hyperparameters by computing the error path of S3VM. Our SPS3VM is the first solution path algorithm for nonconvex optimization problem of semi-supervised learning models. We also provide the finite convergence analysis and computational complexity of SPS3VM. Experimental results on a variety of benchmark datasets not only verify that our SPS3VM can globally search the hyperparameters (regularization and ramp loss parameters) but also show a huge reduction of computational time while retaining similar or slightly better generalization performance compared with the grid search approach.

Zeroth-order (ZO) methods, which use the finite difference of two function evaluations (also called ZO gradient) to approximate first-order gradient, have attracted much attention recently in machine learning because of their broad applications. The accuracy of the ZO gradient highly depends on how many finite differences are averaged, which are intrinsically determined by the number of perturbations randomly drawn from a distribution. Existing ZO methods try to learn a data-driven distribution for sampling the perturbations to improve the efficiency of ZO optimization (ZOO) algorithms. In this paper, we explore a new and parallel direction, \textit{i.e.}, learn an optimal sampling policy instead of using a totally random strategy to generate perturbations based on the techniques of reinforcement learning (RL), which makes it possible to approximate the gradient with only two function evaluations. Specifically, we first formulate the problem of learning a sampling policy as a Markov decision process. Then, we propose our ZO-RL algorithm, \textit{i.e.}, using deep deterministic policy gradient, an actor-critic RL algorithm to learn a sampling policy that can guide the generation of perturbed vectors in getting ZO gradients as accurately as possible. Importantly, the existing ZOO algorithms for learning a distribution can be plugged in to improve the exploration of ZO-RL. Experimental results with different ZO estimators show that our ZO-RL algorithm can effectively reduce the query complexity of ZOO algorithms and converge faster than existing ZOO algorithms, especially in the later stage of the optimization process.

Semisupervised support vector machine (S3VM) is a powerful semisupervised learning model that can use large amounts of unlabeled data to train high-quality classification models. The choice of kernel parameters in the kernel function determines the mapping between the input space and the feature space and is crucial to the performance of the S3VM. Kernel path algorithms have been widely recognized as one of the most efficient tools to trace the solutions with respect to a kernel parameter. However, existing kernel path algorithms are limited to convex problems, while S3VM is nonconvex problem. To address this challenging problem, in this article, we first propose a kernel path algorithm of S3VM (KPS3VM), which can track the solutions of the nonconvex S3VM with respect to a kernel parameter. Specifically, we estimate the position of the breakpoint by monitoring the change of the sample sets. In addition, we also use an incremental and decremental learning algorithm to deal with the Karush-Khun-Tucker violating samples in the process of tracking the solutions. More importantly, we prove the finite convergence of our KPS3VM algorithm. Experimental results on various benchmark datasets not only validate the effectiveness of our KPS3VM algorithm but also show the advantage of choosing the optimal kernel parameters.

Fair classification is an emerging and important research topic in machine learning community. Existing methods usually formulate the fairness metrics as additional inequality constraints, and then embed them into the original objective. This makes fair classification problems unable to be effectively tackled by some solvers specific to unconstrained optimization. Although many new tailored algorithms have been designed to attempt to overcome this limitation, they often increase additional computation burden and cannot cope with all types of fairness metrics. To address these challenging issues, in this paper, we propose a novel method for fair classification. Specifically, we theoretically demonstrate that all types of fairness with linear and non-linear covariance functions can be transferred to two virtual samples, which makes the existing state-of-the-art classification solvers be applicable to these cases. Meanwhile, we generalize the proposed method to multiple fairness constraints. We take SVM as an example to show the effectiveness of our new idea. Empirically, we test the proposed method on real-world datasets and all results confirm its excellent performance.

It is well known that the performance of a kernel method is highly dependent on the choice of kernel parameter. However, existing kernel path algorithms are limited to plain support vector machines (SVMs), which has one equality constraint. It is still an open question to provide a kernel path algorithm to ν -support vector classification ( ν -SVC) with more than one equality constraint. Compared with plain SVM, ν -SVC has the advantage of using a regularization parameter ν for controlling the number of support vectors and margin errors. To address this problem, in this article, we propose a kernel path algorithm (KP ν SVC) to trace the solutions of ν -SVC exactly with respect to the kernel parameter. Specifically, we first provide an equivalent formulation of ν -SVC with two equality constraints, which can avoid possible conflicts during tracing the solutions of ν -SVC. Based on this equivalent formulation of ν -SVC, we propose the KP ν SVC algorithm to trace the solutions with respect to the kernel parameter. However, KP ν SVC traces nonlinear solutions of kernel method rather than the errors of loss function, and it is still a challenge to provide the algorithm that guarantees to find the global optimal model. To address this challenging problem, we extend the classical error path algorithm to the nonlinear kernel solution paths and propose a new kernel error path (KEP) algorithm that ensures to find the global optimal kernel parameter by minimizing the cross validation error. We also provide the finite convergence analysis and computational complexity analysis to KP ν SVC and KEP. Extensive experimental results on a variety of benchmark datasets not only verify the effectiveness of KP ν SVC but also show the advantage of applying KEP to select the optimal kernel parameter.

Fair classification which enforces a fairness constraint on the original learning problem is an emerging topic in machine learning. Due to its non-convexity and non-discontinuity, the original (true) fairness constraint is normally relaxed to a convex and smooth surrogate which could lead to slightly deviated solutions and could violate the original fairness constraint. To re-calibrate with the original constraint, existing methods usually hand-tunes a hyper-parameter of the convex surrogate. Such a method is obviously time consuming, besides it cannot guarantee to find the fairer classifier (i.e., original fairness constraint is less than a smaller threshold). To address this challenging problem, we propose a novel true fairness score path algorithm which guarantees to find fairer classifiers efficiently. Specifically, we first give a new formulation of fair classification which treats the surrogate fairness constraint as an additional regularization term, with a fairness hyper-parameter controlling the degree of surrogate fairness. Then, we propose a solution path algorithm which tracks the solutions of fair classification regarding to the fairness hyper-parameter. Based on the solution path, we further propose a true fairness score path algorithm which derives the curve of fairness score with respect to the fairness hyper-parameter and allows us to find the fairer classifiers. Finally, extensive experimental results not only verify the effectiveness of our algorithm, but also show that we can find the fairer classifiers efficiently.

Self-paced learning (SPL) is an emerging research topic in recent machine learning research which is often formulated as a bi-convex problem. The choice of the age parameter in SPL can control the learning pace and is crucial to achieve optimal performance. Traditionally, the age parameter is programmed to increase in a fixed rate while solving the SPL problem using the alternative optimization strategy (AOS). However, this simple heuristic is likely to miss the optimal age parameter especially when efficiency is a major concern. To address this problem, we propose a solution path method, APSPL, which can track the optimal solutions of SPL with respect to the change of age parameter (age path). Specifically, we use the difference of convex (DC) formulation to replace the original biconvex problem, which enables us to derive the path-following algorithm. For better efficiency, our algorithm uses a decremental and incremental training strategy to avoid retraining several times at different age values. We theoretically prove that the solutions produced by APSPL are the same as those generated by traditional SPL solvers. We also provide the finite time convergence proof of APSPL. To demonstrate the applicability of APSPL, we provide an extension of APSPL for semi-supervised classification. To the best of our knowledge, APSPL is the first solution path algorithm for self-paced learning. Experimental results on a variety of benchmark datasets not only verify the effectiveness and efficiency of APSPL over traditional SPL, but also show the advantage of using the optimal age parameter.

Active learning is an important learning paradigm in machine learning and data mining, which aims to train effective classifiers with as few labeled samples as possible. Querying discriminative (informative) and representative samples are the state-of-the-art approach for active learning. Fully utilizing a large amount of unlabeled data provides a second chance to improve the performance of active learning. Although there have been several active learning methods proposed by combining with semisupervised learning, fast active learning with fully exploiting unlabeled data and querying discriminative and representative samples is still an open question. To overcome this challenging issue, in this article, we propose a new efficient batch mode active learning algorithm. Specifically, we first provide an active learning risk bound by fully considering the unlabeled samples in characterizing the informativeness and representativeness. Based on the risk bound, we derive a new objective function for batch mode active learning. After that, we propose a wrapper algorithm to solve the objective function, which essentially trains a semisupervised classifier and selects discriminative and representative samples alternately. Especially, to avoid retraining the semisupervised classifier from scratch after each query, we design two unique procedures based on the path-following technique, which can remove multiple queried samples from the unlabeled data set and add the queried samples into the labeled data set efficiently. Extensive experimental results on a variety of benchmark data sets not only show that our algorithm has a better generalization performance than the state-of-the-art active learning approaches but also show its significant efficiency.

Robust support vector machine (RSVM) has been shown to perform remarkably well to improve the generalization performance of support vector machine under the noisy environment. Unfortunately, in order to handle the non-convexity induced by ramp loss in RSVM, existing RSVM solvers often adopt the DC programming framework which is computationally inefficient for running multiple outer loops. This hinders the application of RSVM to large-scale problems. Safe sample screening that allows for the exclusion of training samples prior to or early in the training process is an effective method to greatly reduce computational time. However, existing safe sample screening algorithms are limited to convex optimization problems while RSVM is a non-convex problem. To address this challenge, in this paper, we propose two safe sample screening rules for RSVM based on the framework of concave-convex procedure (CCCP). Specifically, we provide screening rule for the inner solver of CCCP and another rule for propagating screened samples between two successive solvers of CCCP. To the best of our knowledge, this is the first work of safe sample screening to a non-convex optimization problem. More importantly, we provide the security guarantee to our sample screening rules to RSVM. Experimental results on a variety of benchmark datasets verify that our safe sample screening rules can significantly reduce the computational time.