Black-box attacks have emerged as a significant threat to deep neural networks. This challenge is particularly difficult in discrete sequential data compared to continuous data. Recently, the Blockwise Bayesian Attack (BBA) leveraging discrete Bayesian optimization with an adapted RBF kernel has gained prominence as a cutting-edge solution. However, it relies solely on alignment information (i.e., positional differences) within the RBF kernel, which may not fully capture the information (such as statistical, structural, and semantic information) inherent in discrete sequential data and potentially lacks the desired inductive bias necessary to approximate the target function accurately. To overcome this limitation, this paper proposes a novel bilevel Bayesian optimization approach to adaptively learn a hybrid space that better captures the similarity between discrete sequences. Specifically, we introduce a multi-kernel mechanism that incorporates multiple types of information, creating a more comprehensive similarity measure. Moreover, we develop a bilevel Bayesian optimization algorithm, where the outer-level objective determines the optimal weights of the multiple kernels, while the inner-level objective identifies the optimal adversarial sequence. Extensive experiments conducted on discrete sequential data demonstrate that our approach ensures secure multi-kernel selection and achieves a higher attack success rate with only a few additional queries, compared to BBA and other traditional optimization strategies.

Vertical Federated Learning (VFL) has garnered significant attention due to its applicability in multi-party collaborative learning and the increasing demand for privacy-preserving measures. Most existing VFL algorithms primarily focus on accuracy as the training model metric. However, the data we access is often imbalanced in the real world, making it difficult for models based on accuracy to correctly classify minority samples. The Area Under the Curve (AUC) serves as an effective metric to evaluate the performance of a model on imbalanced data. Therefore, optimizing AUC can enhance the model's ability to handle imbalanced data. Besides, computational resources within VFL systems are also imbalanced, which makes synchronous VFL algorithms are difficult to apply in the real world. To address the double imbalance issue, we propose Asynchronous Vertical Federated Kernelized AUC Maximization (AVFKAM). Specifically, AVFKAM asynchronously updates a kernel model based on triply stochastic gradients with respect to (w.r.t.) the pairwise loss and random feature approximation. To facilitate theoretical analysis, we transfer the asynchrony of model coefficients to the functional gradient through a dual relationship between coefficients and objective function. Furthermore, we demonstrate that AVFKAM converges to the optimal solution at a rate of O(1/t), where t represents the global iteration number, and discuss the security of the model. If t is denoted as the global iteration number, we provide that it converges to the optimal solution with the rate of O(1/t). Finally, experimental results on various benchmark datasets demonstrate that AVFKAM maintains high AUC performance and efficiency.

In this paper, we introduce a novel framework for black-box prompt tuning with a subspace learning and selection strategy, leveraging derivative-free optimization algorithms. This approach is crucial for scenarios where user interaction with language models is restricted to API usage, without direct access to their internal structures or gradients, a situation typical in Language-Model-as-a-Service (LMaaS). Our framework focuses on exploring the low-dimensional subspace of continuous prompts. Previous work on black-box prompt tuning necessitates a substantial number of API calls due to the random choice of the subspace. To tackle this problem, we propose to use a simple zeroth-order optimization algorithm to tackle nonconvex optimization challenges with nonsmooth nonconvex regularizers: the Zeroth-Order Mini-Batch Stochastic Proximal Gradient method (ZO-MB-SPG). A key innovation is the incorporation of nonsmooth nonconvex regularizers, including the indicator function of the l0 constraint, which enhances our ability to select optimal subspaces for prompt optimization. The experimental results show that our proposed black-box prompt tuning method on a few labeled samples can attain similar performance to the methods applicable to LMaaS with much fewer API calls.

Adversarial training has been shown to be the most popular and effective technique to protect models from imperceptible adversarial samples. Despite its success, it also accompanies the significant performance degeneration to clean data. To achieve a good performance on both clean and adversarial samples, the main effort is searching for an adaptive perturbation radius for each training sample. However, this method suffers from a conflict between exact searching and computational overhead. To address this conflict, in this paper, firstly we show the superiority of adaptive perturbation radii on the accuracy and robustness respectively. Then we propose our novel self-adaptive adjustment framework for perturbation radii without tedious searching. We also discuss this framework on both deep neural networks (DNNs) and kernel support vector machines (SVMs). Finally, extensive experimental results show that our framework can improve adversarial robustness without compromising the natural generalization. It is also competitive with existing searching strategies in terms of running time.

Area under the ROC curve (AUC) is an important and widely used metric in machine learning especially for imbalanced datasets. In current practical learning problems, not only adversarial samples but also noisy samples seriously threaten the performance of learning models. Nowadays, there have been a lot of research works proposed to defend the adversarial samples and noisy samples separately. Unfortunately, to the best of our knowledge, none of them with AUC optimization can secure against the two kinds of harmful samples simultaneously. To fill this gap and also address the challenge, in this paper, we propose a novel doubly robust dAUC optimization (DRAUC) algorithm. Specifically, we first exploit the deep integration of self-paced learning and adversarial training under the framework of AUC optimization, and provide a statistical upper bound to the AUC adversarial risk. Inspired by the statistical upper bound, we propose our optimization objective followed by an efficient alternatively stochastic descent algorithm, which can effectively improve the performance of learning models by guarding against adversarial samples and noisy samples. Experimental results on several standard datasets demonstrate that our DRAUC algorithm has better noise robustness and adversarial robustness than the state-of-the-art algorithms.

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.

Sparsity regularized loss minimization problems play an important role in various fields including machine learning, data mining, and modern statistics. Proximal gradient descent method and coordinate descent method are the most popular approaches to solving the minimization problem. Although existing methods can achieve implicit model identification, aka support set identification, in a finite number of iterations, these methods still suffer from huge computational costs and memory burdens in high-dimensional scenarios. The reason is that the support set identification in these methods is implicit and thus cannot explicitly identify the low-complexity structure in practice, namely, they cannot discard useless coefficients of the associated features to achieve algorithmic acceleration via dimension reduction. To address this challenge, we propose a novel accelerated doubly stochastic gradient descent (ADSGD) method for sparsity regularized loss minimization problems, which can reduce the number of block iterations by eliminating inactive coefficients during the optimization process and eventually achieve faster explicit model identification and improve the algorithm efficiency. Theoretically, we first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity. More importantly, we prove that ADSGD can achieve a linear rate of explicit model identification. Numerically, experimental results on benchmark datasets confirm the efficiency of our proposed method.

Semi-Supervised Support Vector Machine (S3VM) is one of the most popular methods for semi-supervised learning, which can make full use of plentiful, easily accessible unlabeled data. Balancing constraint is normally enforced in S3VM (denoted as BCS3VM) to avoid the harmful solution which assigns all or most of the unlabeled examples to one same label. Traditionally, non-linear BCS3VM is solved by sequential minimal optimization algorithm. Recently, a novel incremental learning algorithm (IL-BCS3VM) was proposed to scale up BCS3VM further. However, IL-BCS3VM needs to calculate the inverse of the linear system related to the support matrix, making the algorithm not scalable enough. To make BCS3VM be more practical in large-scale problems, in this paper, we propose a new scalable BCS3VM with accelerated triply stochastic gradients (denoted as TSG-BCS3VM). Specifically, to make the balancing constraint handle different proportions of positive and negative samples among labeled and unlabeled data, we propose a soft balancing constraint for S3VM. To make the algorithm scalable, we generate triply stochastic gradients by sampling labeled and unlabeled samples as well as the random features to update the solutions, where Quasi-Monte Carlo (QMC) sampling is utilized on random features to accelerate TSG-BCS3VM further. Our theoretical analysis shows that the convergence rate is O(1/√T) for both diminishing and constant learning rates where T is the number of iterations, which is much better than previous results thanks to the QMC method. Empirical results on a variety of benchmark datasets show that our algorithm not only has a good generalization performance but also enjoys better scalability than existing BCS3VM algorithms.

Adversarial training has been proved to be the most effective defensive strategy to protect models from adversarial attacks. In the practical application scenario of adversarial training, besides labeled data, we also face an enormous amount of unlabeled data. However, existing adversarial training methods are naturally targeting supervised learning problems. To adapt to semi-supervised learning problems, they need to estimate labels for unlabeled data in advance, which inevitably degenerates the performance of the learned model due to the bias on the estimation of labels for unlabeled data. To mitigate this issue, in this paper, we propose a new semi-supervised adversarial training framework via maximizing AUCs which is also a minimax problem but treats the unlabeled samples as both positive and negative ones, which allows us to avoid guessing labels for unlabeled data. Quite naturally, the minimax problem can be solved via a traditional adversarial training algorithm by extending singly stochastic gradients to triply stochastic gradients, to adapt to the three (i.e. positive, negative, and unlabeled) data sources. To further accelerate the training procedure, we transform the minimax adversarial training problem into an equivalent minimization one based on the kernel perspective. For the minimization problem, we discuss scalable and efficient algorithms not only for deep neural networks but also for kernel support vector machines. Extensive experimental results show that our algorithms not only achieve better generalization performance against various adversarial attacks, but also enjoy efficiency and scalability when considered from the kernel perspective.

Convolutional kernel networks (CKN) have been proposed to solve image classification tasks, and have shown competitive performance over classical neural networks while being easy to train and robust to overfitting. In real-world ordinal regression problems, we usually have plenty of unlabeled data but a limited number of labeled ordered data. Although recent research works have shown that directly optimizing AUC can impose a better ranking on the data than optimizing traditional error rate, it is still an open question to design an efficient semi-supervised ordinal regression AUC maximization algorithm based on CKN with convergence guarantee. To address this question, in this paper, we propose a new semi-supervised ordinal regression CKN algorithm (S^2 CKNOR) with end-to-end AUC maximization. Specifically, we decompose the ordinal regression into a series of binary classification subproblems and propose an unbiased non-convex objective function to optimize AUC, such that both labeled and unlabeled data can be used to enhance the model performance. Further, we propose a nested alternating minimization algorithm to solve the non-convex objective, where each (convex) subproblem is solved by a quadruply stochastic gradient algorithm, and the non-convex one is solved by the stochastic projected gradient method. Importantly, we prove that our S^2 CKNOR algorithm can finally converge to a critical point of the non-convex objective. Extensive experimental results demonstrate that our S^2 CKNOR achieves the best AUC results on various real-world datasets.

Vertical federated learning (VFL) attracts increasing attention due to the emerging demands of multi-party collaborative modeling and concerns of privacy leakage. A complete list of metrics to evaluate VFL algorithms should include model applicability, privacy security, communication cost, and computation efficiency, where privacy security is especially important to VFL. However, to the best of our knowledge, there does not exist a VFL algorithm satisfying all these criteria very well. To address this challenging problem, in this paper, we reveal that zeroth-order optimization (ZOO) is a desirable companion for VFL. Specifically, ZOO can 1) improve the model applicability of VFL framework, 2) prevent VFL framework from privacy leakage under curious, colluding, and malicious threat models, 3) support inexpensive communication and efficient computation. Based on that, we propose a novel and practical VFL framework with black-box models, which is inseparably interconnected to the promising properties of ZOO. We believe that it takes one stride towards designing a practical VFL framework matching all the criteria. Under this framework, we raise two novel asynchronous zeroth-order algorithms for vertical federated learning (AsyREVEL) with different smoothing techniques. We theoretically drive the convergence rates of AsyREVEL algorithms under nonconvex condition. More importantly, we prove the privacy security of our proposed framework under existing VFL attacks on different levels. Extensive experiments on benchmark datasets demonstrate the favorable model applicability, satisfied privacy security, inexpensive communication, efficient computation, scalability and losslessness of our framework.

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.

Vertical federated learning (VFL) is an effective paradigm of training the emerging cross-organizational (e.g., different corporations, companies and organizations) collaborative learning with privacy preserving. Stochastic gradient descent (SGD) methods are the popular choices for training VFL models because of the low per-iteration computation. However, existing SGD-based VFL algorithms are communication-expensive due to a large number of communication rounds. Meanwhile, most existing VFL algorithms use synchronous computation which seriously hamper the computation resource utilization in real-world applications. To address the challenges of communication and computation resource utilization, we propose an asynchronous stochastic quasi-Newton (AsySQN) framework for VFL, under which three algorithms, i.e. AsySQN-SGD, -SVRG and -SAGA, are proposed. The proposed AsySQN-type algorithms making descent steps scaled by approximate (without calculating the inverse Hessian matrix explicitly) Hessian information convergence much faster than SGD-based methods in practice and thus can dramatically reduce the number of communication rounds. Moreover, the adopted asynchronous computation can make better use of the computation resource. We theoretically prove the convergence rates of our proposed algorithms for strongly convex problems. Extensive numerical experiments on real-word datasets demonstrate the lower communication costs and better computation resource utilization of our algorithms compared with state-of-the-art VFL algorithms.

In a lot of real-world data mining and machine learning applications, data are provided by multiple providers and each maintains private records of different feature sets about common entities. It is challenging to train these vertically partitioned data effectively and efficiently while keeping data privacy for traditional data mining and machine learning algorithms. In this paper, we focus on nonlinear learning with kernels,and propose a federated doubly stochastic kernel learning (FDSKL) algorithm for vertically partitioned data. Specifically, we use random features to approximate the kernel mapping function and use doubly stochastic gradients to update the solutions, which are all computed federatedly without the disclosure of data. Importantly, we prove that FDSKL has a sublinear convergence rate, and can guarantee the data security under the semi-honest assumption. Extensive experimental results on a variety of benchmark datasets show that FDSKL is significantly faster than state-of-the-art federated learning methods when dealing with kernels, while retaining the similar generalization performance.

Multi-label classification (MLC) is pervasive in real-world applications. Conventional MLC algorithms assume that enough ground truth labels are available for training a classifier. While in reality, obtaining ground truth labels is expensive and time-consuming. In the field of data mining, it is more efficient to use crowdsourcing for label collection. In this setting, an MLC algorithm needs to deal with the noisiness of the crowdsourced labels as well as the remaining massive unlabeled data. In this paper, we propose a deep generative model to describe the label generation process for this semi-supervised multi-label learning problem. Although deep generative models are widely used for MLC problems, no previous work could address the noisy crowdsourced multi-labels and unlabeled data simultaneously. To address this challenging problem, our novel generative model incorporates latent variables to describe the labeled/unlabeled data as well as the labeling process of crowdsourcing. We introduce an efficient sequential inference model to approximate the model posterior and infer the ground truth labels. Our experimental results on various scales of datasets demonstrate the effectiveness of our proposed model. It performs favorably against four state-of-the-art deep generative models.

Variable selection is a challenging problem in high-dimensional linear regression problems with a large number of predictors. Thus, sparsity-inducing and clustering-inducing regularization methods are widely used to identify highly correlated covariates. Ordered Weight L1(OWL) family of regularizers for linear regression perform well to identify precise clusters of correlated covariates and interpret the effect of each variable. Solution path algorithms are helpful to select hyperparameters to tune the OWL model. Due to over-complex representation of the penalty, so far the OWL model has no solution path algorithms for hyperparameter selection. To address this challenge, in this paper, we propose an efficient approximate solution path algorithm (OWLAGPath) to solve the OWL model with accuracy guarantee. For a given accuracy bound ε, OWLAGPath can find the corresponding solutions for the OWL model with numerous hyperparameters while keeping the sparsity and precise features grouping properties. Theoretically, we prove that all the solutions produced by OWLAGPath can strictly satisfy the given accuracy bound ε. The experimental results on three benchmark datasets not only confirm the effectiveness and efficiency of our OWLAGPath algorithm, but also show the advantages of OWLAGPath for model selection than the existing algorithms.

Semi-Supervised Support Vector Machine (S3VM) is one of the most popular methods for semi-supervised learning. To avoid the trivial solution of classifying all the unlabeled examples to a same class, balancing constraint is often used with S3VM (denoted as BCS3VM). Recently, a novel incremental learning algorithm (IL-S3VM) based on the path following technique was proposed to significantly scale up S3VM. However, the dynamic relationship of balancing constraint with previous labeled and unlabeled samples impede their incremental method for handling BCS3VM. To fill this gap, in this paper, we propose a new incremental S3VM algorithm (IL-BCS3VM) based on IL-S3VM which can effectively handle the balancing constraint and directly update the solution of BCS3VM. Specifically, to handle the dynamic relationship of balancing constraint with previous labeled and unlabeled samples, we design two unique procedures which can respectively eliminate and add the balancing constraint into S3VM. More importantly, we provide the finite convergence analysis for our IL-BCS3VM algorithm. Experimental results on a variety of benchmark datasets not only confirm the finite convergence of IL-BCS3VM, but also show a huge reduction of computational time compared with existing batch and incremental learning algorithms, while retaining the similar generalization performance.

With the crowdsourcing of small tasks becoming easier, it is possible to obtain non-expert/imperfect labels at low cost. With low-cost imperfect labeling, it is straightforward to collect multiple labels for the same data items. This paper proposes strategies of utilizing these multiple labels for supervised learning, based on two basic ideas: majority voting and pairing. We show several interesting results based on our experiments. (i) The strategies based on the majority voting idea work well under the situation where the certainty level is high. (ii) On the contrary, the pairing strategies are more preferable under the situation where the certainty level is low. (iii) Among the majority voting strategies, soft majority voting can reduce the bias and roughness, and perform better than majority voting. (iv) Pairing can completely avoid the bias by having both sides (potentially correct and incorrect/noisy information) considered. Beta estimation is applied to reduce the impact of the noise in pairing. Our experimental results show that pairing with Beta estimation always performs well under different certainty levels. (v) All strategies investigated are labeling quality agnostic strategies for real-world applications, and some of them perform better than or at least very close to the gnostic strategies.

Semi-supervised learning is especially important in data mining applications because it can make use of plentiful unlabeled data to train the high-quality learning models. Semi-Supervised Support Vector Machine (S3VM) is a powerful semi-supervised learning model. However, the high computational cost and non-convexity severely impede the S3VM method in large-scale applications. Although several learning algorithms were proposed for S3VM, scaling up S3VM is still an open problem. To address this challenging problem, in this paper, we propose a new incremental learning algorithm to scale up S3VM (IL-S3VM) based on the path following technique in the framework of Difference of Convex (DC) programming. The traditional DC programming based algorithms need multiple outer loops and are not suitable for incremental learning, and traditional path following algorithms are limited to convex problems. Our new IL-S3VM algorithm based on the path-following technique can directly update the solution of S3VM to converge to a local minimum within one outer loop so that the efficient incremental learning can be achieved. More importantly, we provide the finite convergence analysis for our new algorithm. To the best of our knowledge, our new IL-S3VM algorithm is the first efficient path following algorithm for a non-convex problem (i.e., S3VM) with local minimum convergence guarantee. Experimental results on a variety of benchmark datasets not only confirm the finite convergence of IL-S3VM, but also show a huge reduction of computational time compared with existing batch and incremental learning algorithms, while retaining the similar generalization performance.

Feature selection is one of the most important data mining research topics with many applications. In practical problems, features often have group structure to effect the outcomes. Thus, it is crucial to automatically identify homogenous groups of features for high-dimensional data analysis. Octagonal shrinkage and clustering algorithm for regression (OSCAR) is an important sparse regression approach with automatic feature grouping and selection by ℓ1 norm and pairwise ℓ∞ norm. However, due to over-complex representation of the penalty (especially the pairwise ℓ∞ norm), so far OSCAR has no solution path algorithm which is mostly useful for tuning the model. To address this challenge, in this paper, we propose a groups-keeping solution path algorithm to solve the OSCAR model (OscarGKPath). Given a set of homogenous groups of features and an accuracy bound ε, OscarGKPath can fit the solutions in an interval of regularization parameters while keeping the feature groups. The entire solution path can be obtained by combining multiple such intervals. We prove that all solutions in the solution path produced by OscarGKPath can strictly satisfy the given accuracy bound ε. The experimental results on benchmark datasets not only confirm the effectiveness of our OscarGKPath algorithm, but also show the superiority of our OscarGKPath in cross validation compared with the existing batch algorithm.