Transfer learning enhances prediction accuracy on a target distribution by leveraging data from a source distribution, demonstrating significant benefits in various applications. This paper introduces a novel dissimilarity measure that utilizes vicinity information, i.e., the local structure of data points, to analyze the excess error in classification under covariate shift, a transfer learning setting where marginal feature distributions differ but conditional label distributions remain the same. We characterize the excess error using the proposed measure and demonstrate faster or competitive convergence rates compared to previous techniques. Notably, our approach is effective in the support non-containment assumption, which often appears in real-world applications, holds. Our theoretical analysis bridges the gap between current theoretical findings and empirical observations in transfer learning, particularly in scenarios with significant differences between source and target distributions.

We address the regression problem under the constraint of demographic parity, a commonly used fairness definition. Recent studies have revealed fair minimax optimal regression algorithms, the most accurate algorithms that adhere to the fairness constraint. However, these analyses are tightly coupled with specific data generation models. In this paper, we provide meta-theorems that can be applied to various situations to validate the fair minimax optimality of the corresponding regression algorithms. Furthermore, we demonstrate that fair minimax optimal regression can be achieved through post-processing methods, allowing researchers and practitioners to focus on improving conventional regression techniques, which can then be efficiently adapted for fair regression.

Evolution strategy (ES) is one of the promising classes of algorithms for black-box continuous optimization. Despite its broad successes in applications, theoretical analysis on the speed of its convergence is limited on convex quadratic functions and their monotonic transformation. In this study, an upper bound and a lower bound of the rate of linear convergence of the (1+1)-ES on locally$L$-strongly convex functions with$U$-Lipschitz continuous gradient are derived as$\exp (-\Omega _{d\to \infty }({L}/({d\cdot U})))$and$\exp (-1/d)$, respectively. Notably, any prior knowledge on the mathematical properties of the objective function, such as the Lipschitz constant, is not given to the algorithm, whereas the existing analyses of derivative-free optimization algorithms require it.

The Transformer is a deep learning architecture that processes sequence data. The Transformer attains the state-of-the-art in several tasks of sequence data analysis, and its variants, such as BERT and GPT-3, are used as a defacto-standard for solving general tasks in natural language processing (NLP). This work presents a 3-party multi-party computation (MPC) protocol for secure inference of the Transfomer in the honest majority setting. The attention layer is the most time-consuming part when implementing an MPC protocol for the Transformer with existing building blocks. The attention mechanism is a core component of the Transformer that captures and exploits complex dependencies among elements in the input sequences. The attention mechanism invokes the exponentiation function O(S2) times, which becomes a major bottleneck when implementing the Transformer with existing MPC primitives. To deal with this, we employ the Performer [11], a variant of the Transformer where the sigmoid function that invokes the exponentiation function is replaced with the ReLU function, a more MPC-friendly nonlinear function. Also, by introducing a kernel-based approximation of the attention matrix with random orthogonal matrices, we show that the attention layer can be processed with O(S) times calls of the ReLU function. We investigate the efficiency of the proposed method by an end-to-end implementation of the Transformer with 3-party MPC. Experimental evaluation shows that, for translating a sequence where the output sequence length is 64, the entire computation time takes about 19 minutes in the LAN environment.

A concept-based classifier can explain the decision process of a deep learning model by human understandable concepts in image classification problems. However, sometimes concept-based explanations may cause false positives, which misregards unrelated concepts as important for the prediction task. Our goal is to find the statistically significant concept for classification to prevent misinterpretation. In this study, we propose a method using a deep learning model to learn the image concept and then using the knockoff sample to select the important concepts for prediction by controlling the False Discovery Rate (FDR) under a certain value. We evaluate the proposed method in our experiments on both synthetic and real data. Also, it shows that our method can control the FDR properly while selecting highly interpretable concepts to improve the trustworthiness of the model.

We explore the minimax optimal error associated with a demographic parity-constrained regression problem within the context of a linear model. Our proposed model encompasses a broader range of discriminatory bias sources compared to the model presented by Chzhen and Schreuder. Our analysis reveals that the minimax optimal error for the demographic parity-constrained regression problem under our model is characterized by $\Theta(\frac{dM}{n})$, where $n$ denotes the sample size, $d$ represents the dimensionality, and $M$ signifies the number of demographic groups arising from sensitive attributes. Moreover, we demonstrate that the minimax error increases in conjunction with a larger bias present in the model.

This paper develops a certified defense for deep neural network (DNN) based content based image retrieval (CBIR) against adversarial examples (AXs). Previous works put their effort into certified defense for classification to improve certified robustness, which guarantees that no AX to cause misclassification exists around the sample. Such certified defense, however, could not be applied to CBIR directly because the goals of adversarial attack against classification and CBIR are completely different. To develop the certified defense for CBIR, we first define new certified robustness of CBIR, which guarantees that no AX that changes the ranking of CBIR exists around the query or candidate images. Then, we propose computationally tractable verification algorithms that verify whether the certified robustness of CBIR is achieved by utilizing upper and lower bounds of distances between feature representations of perturbed and non-perturbed images. Finally, we propose new objective functions for training feature extraction DNNs that increases the number of inputs that satisfy the certified robustness of CBIR by tightening the upper and lower bounds. Experimental results show that our objective functions significantly improve the certified robustness of CBIR than existing methods.

In this study, we consider a continuous min–max optimization problem minx∈ 𝕏maxy∈ 𝕐f(x, y) whose objective function is a black-box. We propose a novel approach to minimize the worst-case objective functionF(x) = maxy∈ 𝕐f(x, y) directly using a covariance matrix adaptation evolution strategy in which the rankings of solution candidates are approximated by our proposed worst-case ranking approximation mechanism. We develop two variants of worst-case ranking approximation combined with a covariance matrix adaptation evolution strategy and approximate gradient ascent as numerical solvers for the inner maximization problem. Numerical experiments show that our proposed approach outperforms several existing approaches when the objective function is a smooth strongly convex–concave function and the interaction betweenxandyis strong. We investigate the advantages of the proposed approach for problems where the objective function is not limited to smooth strongly convex–concave functions. The effectiveness of the proposed approach is demonstrated in the robust berthing control problem with uncertainty.

Statistically significant pattern mining (SSPM), which evaluates each pattern via a hypothesis test, is an essential and challenging data mining task for knowledge discovery. We introduce a preference relation between patterns and aim to discover the most preferred patterns under the constraint of statistical significance, which has never been considered in existing SSPM problems. We propose an iterative multiple testing procedure that can alternately reject a hypothesis and safely ignore the less useful hypotheses than the rejected one. By filtering out patterns with low utility, we can avoid the significance budget consumption of rejecting useless (uninteresting) patterns and focus the significance budget on more useful patterns, leading to more useful discoveries. We show that the proposed method can control the familywise error rate (FWER) under certain assumptions, which can be satisfied by a realistic problem class in SSPM. We also show that the proposed method always discovers equally or more useful patterns than Tarone-Bonferroni and Subfamily-wise Multiple Testing (SMT). Finally, we conducted several experiments with both synthetic and real-world data to evaluate the performance of our method. The proposed method discovered many more useful patterns in the experiments with real-world datasets than the existing method for all five conducted tasks.

We aim to explain a black-box classifier with the form: "data X is classified as class Y because X has A, B and does not have C" in which A, B, and C are high-level concepts. The challenge is that we have to discover in an unsupervised manner a set of concepts, i.e., A, B and C, that is useful for explaining the classifier. We first introduce a structural generative model that is suitable to express and discover such concepts. We then propose a learning process that simultaneously learns the data distribution and encourages certain concepts to have a large causal influence on the classifier output. Our method also allows easy integration of user's prior knowledge to induce high interpretability of concepts. Finally, using multiple datasets, we demonstrate that the proposed method can discover useful concepts for explanation in this form.

In this study, we investigate the problem of min-max continuous optimization in a black-box setting minx maxy f (x,y). A popular approach updates x and y simultaneously or alternatingly. However, two major limitations have been reported in existing approaches. (I) As the influence of the interaction term between x and y (e.g., xTBy) on the Lipschitz smooth and strongly convex-concave function f increases, the approaches converge to an optimal solution at a slower rate. (II) The approaches fail to converge if f is not Lipschitz smooth and strongly convex-concave around the optimal solution. To address these difficulties, we propose minimizing the worst-case objective function F(x) = maxy f (x, y) directly using the covariance matrix adaptation evolution strategy, in which the rankings of solution candidates are approximated by our proposed worst-case ranking approximation (WRA) mechanism. Compared with existing approaches, numerical experiments show two important findings regarding our proposed method. (1) The proposed approach is eficient in terms of f-calls on a Lipschitz smooth and strongly convex-concave function with a large interaction term. (2) The proposed approach can converge on functions that are not Lipschitz smooth and strongly convex-concave around the optimal solution, whereas existing approaches fail.

This paper focuses on the domain generalization task, which aims to learn a model that generalizes to unseen domains by utilizing multiple training domains. More specifically, we follow the idea of adversarial data augmentation, which aims to synthesize and augment training data with “hard” domains for improving the model's domain generalization ability. Previous works augment training data only with samples similar to the training data, resulting in limited generalization ability. We propose a novel adversarial data augmentation method, termed GADA (Generative Adversarial Domain Augmentation), which employs an image-to-image translation model to obtain a distribution of novel domains that are semantically different from the training domains, and, at the same time, hard to classify. Evaluation and further analysis suggest that adversarial data augmentation with semantically different samples leads to better domain generalization performance.

This study proposes a method that enables attribution of GAN-generated images to the GAN model that generated the images. Existing attribution methods (e.g., model watermark) require preprossessing on the model before model publication to attain high attribution performance. This study proposes a post-hoc attribution method that does not require preprocessing before model publication. Our attribution method is designed based on the fact that latent recovery can attain better image recovery if images to be attributed are generated by the source model. Our experimental evaluation shows that our post-hoc attribution method attains almost the same attribution performance as existing methods that require preprocessing if more than five images are available for attribution.

In real-world applications of multi-class classification models, misclassification in an important class (e.g., stop sign) can be significantly more harmful than in other classes (e.g., speed limit). In this paper, we propose a loss function that can improve the recall of an important class while maintaining the same level of accuracy as the case using cross-entropy loss. For our purpose, we need to make the separation of the important class better than the other classes. However, existing methods that give a class-sensitive penalty for cross-entropy loss do not improve the separation. On the other hand, the method that gives a margin to the angle between the feature vectors and the weight vectors of the last fully connected layer corresponding to each feature can improve the separation. Therefore, we propose a loss function that can improve the separation of the important class by setting the margin only for the important class, called Class-sensitive Additive Angular Margin Loss (CAMRI Loss). CAMRI loss is expected to reduce the variance of angles between features and weights of the important class relative to other classes due to the margin around the important class in the feature space by adding a penalty to the angle. In addition, concentrating the penalty only on the important classes hardly sacrifices the separation of the other classes. Experiments on CIFAR-10, GTSRB, and AwA2 showed that the proposed method could improve up to 9% recall improvement on cross-entropy loss without sacrificing accuracy.

We investigate policy transfer using image-to-semantics translation to mitigate learning difficulties in vision-based robotics control agents. This problem assumes two environments: a simulator environment with semantics, that is, low-dimensional and essential information, as the state space, and a real-world environment with images as the state space. By learning mapping from images to semantics, we can transfer a policy, pre-trained in the simulator, to the real world, thereby eliminating real-world on-policy agent interactions to learn, which are costly and risky. In addition, using image-to-semantics mapping is advantageous in terms of the computational efficiency to train the policy and the interpretability of the obtained policy over other types of sim-to-real transfer strategies. To tackle the main difficulty in learning image-to-semantics mapping, namely the human annotation cost for producing a training dataset, we propose two techniques: pair augmentation with the transition function in the simulator environment and active learning. We observed a reduction in the annotation cost without a decline in the performance of the transfer, and the proposed approach outperformed the existing approach without annotation.

In the field of reinforcement learning, because of the high cost and risk of policy training in the real world, policies are trained in a simulation environment and transferred to the corresponding real-world environment.However, the simulation environment does not perfectly mimic the real-world environment, lead to model misspecification. Multiple studies report significant deterioration of policy performance in a real-world environment.In this study, we focus on scenarios involving a simulation environment with uncertainty parameters and the set of their possible values, called the uncertainty parameter set. The aim is to optimize the worst-case performance on the uncertainty parameter set to guarantee the performance in the corresponding real-world environment.To obtain a policy for the optimization, we propose an off-policy actor-critic approach called the Max-Min Twin Delayed Deep Deterministic Policy Gradient algorithm (M2TD3), which solves a max-min optimization problem using a simultaneous gradient ascent descent approach.Experiments in multi-joint dynamics with contact (MuJoCo) environments show that the proposed method exhibited a worst-case performance superior to several baseline approaches.

We handle min-max black-box optimization problems in which the scenario variable to be maximized is discrete and the design variable to be minimized is a continuous vector. To reduce the number of objective function calls, which are assumed to be computationally expensive, we propose an approach that samples a subset of scenarios at each iteration to approximate the worst-case objective function and apply the covariance matrix adaptation evolution strategy to the approximated worst-case objective function. In addition, we develop an adaptation mechanism for the probability of sampling each scenario. Moreover, we introduce the notion of support scenarios to characterize min-max optimization problems with discrete scenario variables and design test problems with various characteristics of support scenarios. Empirical evaluations reveal that the proposed approach learns to sample the set of support scenarios, being more efficient than sampling all the scenarios, especially when the available scenarios outnumber the support scenarios.

The (1+1)-evolution strategy (ES) with success-based step-size adaptation is analyzed on a general convex quadratic function and its monotone transformation, that is, f(x) = g((x - x*)TH(x - x*)), where g: R → R is a strictly increasing function, H is a positive-definite symmetric matrix, and x* ∈ Rd is the optimal solution of f. The convergence rate, that is, the decrease rate of the distance from a search point mt to the optimal solution x*, is proven to be in O(exp(-L/Tr(H))), where L is the smallest eigenvalue of H and Tr(H) is the trace of H. This result generalizes the known rate of O(exp(-1/d)) for the case of H = Id (Id is the identity matrix of dimension d) and O(exp(-1/(d · ξ))) for the case of H = diag(ξ · Id/2, Id/2). To the best of our knowledge, this is the first study in which the convergence rate of the (1+1)-ES is derived explicitly and rigorously on a general convex quadratic function, which depicts the impact of the distribution of the eigenvalues in the Hessian H on the optimization and not only the impact of the condition number of H.

Video game level generation based on machine learning (ML), in particular, deep generative models, has attracted attention as a technique to automate level generation. However, applications of existing ML-based level generations are mostly limited to tile-based level representation. When ML techniques are applied to game domains with non-tile-based level representation, such as Angry Birds, where objects in a level are specified by real-valued parameters, ML often fails to generate playable levels. In this study, we develop a deep-generative-model-based level generation for the game domain of Angry Birds. To overcome these drawbacks, we propose a sequential encoding of a level and process it as text data, whereas existing approaches employ a tile-based encoding and process it as an image. Experiments show that the proposed level generator drastically improves the stability and diversity of generated levels compared with existing approaches. We apply latent variable evolution with the proposed generator to control the feature of a generated level computed through an AI agent's play, while keeping the level stable and natural.

Auditing fairness of decision-makers is now in high demand. To respond to this social demand, several fairness auditing tools have been developed. The focus of this study is to raise an awareness of the risk of malicious decision-makers who fake fairness by abusing the auditing tools and thereby deceiving the social communities. The question is whether such a fraud of the decision-maker is detectable so that the society can avoid the risk of fake fairness. In this study, we answer this question negatively. We specifically put our focus on a situation where the decision-maker publishes a benchmark dataset as the evidence of his/her fairness and attempts to deceive a person who uses an auditing tool that computes a fairness metric. To assess the (un)detectability of the fraud, we explicitly construct an algorithm, the stealthily biased sampling, that can deliberately construct an evil benchmark dataset via subsampling. We show that the fraud made by the stealthily based sampling is indeed difficult to detect both theoretically and empirically.

In this study, we consider black-box minimization problems with non-convex constraints, where the constraints are significantly cheaper to evaluate than the objective. Non-convex constraints generally make it difficult to solve problems using evolutionary approaches. In this paper, we revisit a conventional technique called decoder constraint handling, which transforms a feasible non-convex domain into an easy-to-control convex set. This approach is promising because it transforms a constrained problem into an almost unconstrained one. However, its application has been considerably limited, because designing or training such a nonlinear decoder requires domain knowledge or manually prepared training data. To fully automate the decoder design, we use deep generative models. We propose a novel scheme to train a deep generative model without using manually prepared training data. For this purpose, we first train feasible solution samplers, which are deep neural networks, using the constraint functions. Subsequently, we train another deep generative model using the data generated from the trained samplers as the training data. The proposed framework is applied to tasks inspired by topology optimization problems. The empirical study demonstrates that the proposed approach can locate better solutions with fewer objective function evaluations than the existing approach.

Statistically significant patterns mining (SSPM) is an essential and challenging data mining task in the field of knowledge discovery in databases (KDD), in which each pattern is evaluated via a hypothesis test. Our study aims to introduce a preference relation into patterns and to discover the most preferred patterns under the constraint of statistical significance, which has never been considered in existing SSPM problems. We propose an iterative multiple testing procedure that can alternately reject a hypothesis and safely ignore the hypotheses that are less useful than the rejected hypothesis. One advantage of filtering out patterns with low utility is that it avoids consumption of the significance budget by rejection of useless (that is, uninteresting) patterns. This allows the significance budget to be focused on useful patterns, leading to more useful discoveries. We show that the proposed method can control the familywise error rate (FWER) under certain assumptions, that can be satisfied by a realistic problem class in SSPM. We also show that the proposed method always discovers a set of patterns that is at least equally or more useful than those discovered using the standard Tarone-Bonferroni method SSPM. Finally, we conducted several experiments with both synthetic and real-world data to evaluate the performance of our method. As a result, in the experiments with real-world datasets, the proposed method discovered a larger number of more useful patterns than the existing method for all five conducted tasks.

This paper addresses a problem of estimating an additive functional given n i.i.d. samples drawn from a discrete distribution P=(p1, ...,pk) with alphabet size k. The additive functional is defined as θ(P;φ)=Σi=1kφ(pi) for a function φ, which covers the most of the entropy-like criteria. We revealed in the previous paper [1] that the minimax optimal rate of this problem is characterized by the divergence speed, whereas the characterization is valid only when α ∈ (0,1) where α denotes the parameter of the divergence speed. In this paper, we extend this characterization to a more general range of the divergence speed, including α ∈ (1,3/2) and α ∈ [3/2,2]. As a result, we show that the minimax rates for α ∈ (1,3/2) and α ∈ [3/2,2] are [1/n]+[(k2)/((nlnn)2α)] and [1/n], respectively.

This paper develops differentially private mechanisms for $\chi^2$ test of independence. While existing works put their effort into properly controlling the type-I error, in addition to that, we investigate the type-II error of differentially private mechanisms. Based on the analysis, we present unit circle mechanism: a novel differentially private mechanism based on the geometrical property of the test statistics. Compared to existing output perturbation mechanisms, our mechanism improves the dominated term of the type-II error from $O(1)$ to $O(\exp(-\sqrt{N}))$ where $N$ is the sample size. Furthermore, we introduce novel procedures for multiple $\chi^2$ tests by incorporating the unit circle mechanism into the sparse vector technique and the exponential mechanism. These procedures can control the family-wise error rate (FWER) properly, which has never been attained by existing mechanisms.

In this paper, we consider estimators for an additive functional of φ, which is defined as θ(P; φ) = Σki=1φ(pi), from n i.i.d. random samples drawn from a discrete distribution P = (p1,..., pk) with alphabet size k. We propose a minimax optimal estimator for the estimation problem of the additive functional. We reveal that the minimax optimal rate is characterized by the divergence speed of the fourth derivative of φ if the divergence speed is high. As a result, we show there is no consistent estimator if the divergence speed of the fourth derivative of φ is larger than p-4. Furthermore, if the divergence speed of the fourth derivative of φ is p4-αfor α ϵ (0,1), the minimax optimal rate is obtained within a universal multiplicative constant as k2/(n ln n)2α+ k2-2α/n.