We address the optimization problem of simultaneously minimizing multiple objective functionals over a family of probability distributions. This type of Multi-Objective Distributional Optimization commonly arises in machine learning and statistics, with applications in areas such as multiple target sampling, multi-task learning, and multi-objective generative modeling. To solve this problem, we propose an iterative particle-based algorithm, which we call Muliple Wasserstein Gradient Descent (MWGraD), which constructs a flow of intermediate empirical distributions, each being represented by a set of particles, which gradually minimize the multiple objective functionals simultaneously. Specifically, MWGraD consists of two key steps at each iteration. First, it estimates the Wasserstein gradient for each objective functional based on the current particles. Then, it aggregates these gradients into a single Wasserstein gradient using dynamically adjusted weights and updates the particles accordingly. In addition, we provide theoretical analysis and present experimental results on both synthetic and real-world datasets, demonstrating the effectiveness of MWGraD.

Automatic portfolio optimization (APO) is the process of automatically optimizing the allocation of assets in an investment portfolio through algorithms and models. Empirical evidence suggests that stock prices are likely to follow the mean reversion theory. Although existing mean reversion strategies for APO have been shown to achieve good empirical performance across many real-world datasets, they tend to construct single-stock portfolios, which results in high risk. In this paper, we propose a risk diversification version of Online Moving Average Reversion (OLMAR) [16], one of the major mean reversion strategies. The parameter k of our proposed method OLMAR-k controls the search space for optimization to guarantee the existence of solutions and prevent from solutions close to uniform. According to experimental results in resent datasets, OLMAR-k outperforms other state-of-the-art APO methods in terms of popular metrics for return and risk.

A budget-constrained combinatorial optimal facility investment problem is a problem that optimally locates multiple facilities on the vertices of a given undirected graph and allocates many different types of equipment to each facility under a budget constraint. The objective function is not given explicitly, and we can know the evaluation of our investment through a given noisy blackbox function. We propose a search method using Monte Carlo tree search (MCTS) for this problem with a noisy blackbox function. In our search through MCTS, we make use of the lattice structure of subspaces defined using a hierarchical range partition for each variable and reinforce to select good order of variable range partitions preferentially using the upper confidence bound score, into which rapid action value estimation method is incorporated, for selection operations. The effectiveness of our proposed method is demonstrated through the experiments for the layout optimization problem of distributed small power grids (nanogrids) using a public simulator and data that are based on real-world maps, population, and weather as a noisy blackbox function and another setting including an undirected graph, respectively.

Classification bandits are multi-armed bandit problems whose task is to classify a given set of arms into either positive or negative class depending on whether the rate of the arms with the expected reward of at least h is not less than w for given thresholds h and w. We study a special classification bandit problem in which arms correspond to points x in d-dimensional real space with expected rewards f(x) which are generated according to a Gaussian process prior. We develop a framework algorithm for the problem using various arm selection policies and propose policies called FCB (Farthest Confidence Bound) and FTSV (Farthest Thompson Sampling Value). We show a smaller sample complexity upper bound for FCB than that for the existing algorithm of the level set estimation, in which whether f(x) is at least h or not must be decided for every arm’s x. Arm selection policies depending on an estimated rate of arms with mean rewards of at least h are also proposed and shown to improve empirical sample complexity. According to our experimental results, the rate-estimation versions of FCB and FTSV, together with that of the popular active learning policy which selects the point with the maximum variance, outperform other policies for synthetic functions, and the rate-estimation version of FTSV is also the best performer for our real-world dataset.

The classification bandit problem aims to determine whether a set of given $K$ arms contains at least $L$ good arms or not. Here, an arm is said to be good if its expected reward is no less than a specified threshold. To solve this problem, we introduce an asymptotically optimal algorithm, named P-tracking, based on posterior sampling. Unlike previous asymptotically optimal algorithms that require solving a linear programming problem with an exponentially large number of constraints, P-tracking solves an equivalent optimization problem that can be computed in time linear in $K$. Additionally, unlike existing algorithms, P-tracking does not require forced exploration steps. Empirical results show that P-tracking outperforms existing algorithms in sample efficiency.

Although differentially private streaming data release has been studied extensively, how to strike a good balance between privacy and utility on correlated data is still an open problem. Many existing works focus on enhancing privacy when applying differential privacy to correlated data. They show that differential privacy may suffer extra privacy leakage under correlations, and it is inevitable to resort to a small privacy budget to prevent such privacy leakage. However, there is no attempt to solve the consequential utility problem. In this work, for the first time, we propose a post-processing framework to boost the utility of differential privacy data release under temporal correlations. Specifically, we model the problem as a maximum posterior estimation given the released differentially private data and correlation model. We finally transform this problem into a nonlinear constrained programming. Our experiments demonstrate the effectiveness of the proposed approach where the utility and accuracy of differentially private data are significantly improved by nearly ten times in terms of mean square error when a strict privacy budget is given.

We propose a method of converting a real-weighted voting classifier to a compact integer-weighted voting classifier. Real-weighted voting classifiers like those trained using boosting are very popular and widely used due to their high prediction performance. Real numbers, however, are space-consuming and its floating-point arithmetic is slow compared to integer arithmetic, so compact integer weights are preferable for implementation on devices with small computational resources. Our conversion makes use of given feature vectors and solves an integer linear programming problem that minimizes the sum of integer weights under the constraint of keeping the classification result for the vectors unchanged. According to our experimental results using datasets of UCI Machine Learning Repository, the bit representation sizes are reduced to $5.2$-$33.4$% within $3.7$% test accuracy degrade in 7 of 8 datasets for the weighted voting classifiers of decision stumps learned using AdaBoost-SAMME.

Monte Carlo tree search (MCTS) has received considerable interest due to its spectacular success in the difficult problem of computer Go and also proved beneficial in a range of other domains. A major issue that has received little attention in the MCTS literature is the fact that, in most games, different actions can lead to the same state, that may lead to a high degree of redundancy in tree representation and unnecessary additional computational cost. We extend MCTS to single rooted directed acyclic graph (SR-DAG), and consider the Best Arm Identification (BAI) and the Best Leaf Identification (BLI) problem of an expanding SR-DAG of arbitrary depth. We propose algorithms that are (∊, σ)-correct in the fixed confidence setting, and prove an asymptotic upper bounds of sample complexity for our BAI algorithm. As a major application for our BLI algorithm, a novel approach for Feature Selection is proposed by representing the feature set space as a SR-DAG and repeatedly evaluating feature subsets until a candidate for the best leaf is returned, a proof of concept is shown on benchmark data sets.

Abstract We consider a novel stochastic multi-armed bandit problem called good arm identification (GAI), where a good arm is defined as an arm with expected reward greater than or equal to a given threshold. GAI is a pure-exploration problem in which a single agent repeats a process of outputting an arm as soon as it is identified as a good one before confirming the other arms are actually not good. The objective of GAI is to minimize the number of samples for each process. We find that GAI faces a new kind of dilemma, the exploration-exploitation dilemma of confidence, which is different from the best arm identification. As a result, an efficient design of algorithms for GAI is quite different from that for the best arm identification. We derive a lower bound on the sample complexity of GAI that is tight up to the logarithmic factor $$\mathrm {O}(\log \frac{1}{\delta })$$ O ( log 1 δ ) for acceptance error rate $$\delta $$ δ . We also develop an algorithm whose sample complexity almost matches the lower bound. We also confirm experimentally that our proposed algorithm outperforms naive algorithms in synthetic settings based on a conventional bandit problem and clinical trial researches for rheumatoid arthritis.

We study the problem of enumerating concepts in a Sperner family concept class using subconcept queries, which is a general problem including maximal frequent itemset mining as its instance. Though even the theoretically best known algorithm needs quasi-polynomial time to solve this problem in the worst case, there exist practically fast algorithms for this problem. This is because many instances of this problem in real world have low complexity in some measures. In this paper, we characterize the complexity of Sperner family concept class by the VC dimension of its intersection closure and its characteristic dimension, and analyze the worst case time complexity on the enumeration problem of its concepts in terms of the VC dimension. We also showed that the VC dimension of real data used in data mining is actually small by calculating the VC dimension of some real datasets using a new algorithm closely related to the introduced two measures, which does not only solve the problem but also let us know the VC dimension of the intersection closure of the target concept class.

A set of convex bodies including samples of a single class only is used for classification. The convex body is defined by some facets (hyper-planes) that separate the class from the other classes. This paper describes an algorithm to find a set of such convex bodies efficiently and examine the performance of a classifier using them. The relationship to the support vector machines is also discussed.

Associative classifiers that utilize association rules have been widely studied. It has been shown that associative classifiers often outperform traditional classifiers. Associative classifiers usually find only rules with high support values, because reducing the minimum support to be satisfied increases computational cost. However, rules with low support but high confidence may contribute to classification. We have proposed an approach to build a classifier composed of almost all consistent (100% confident) rules. The proposed classifier was extended by introducing item reduction and bagging in order to relax the constraint of consistency, which resulted in slightly increased performance for 26 datasets from the UCI machine learning repository.

We introduce a stricter Web community definition to overcome boundary ambiguity of a Web community defined by Flake, Lawrence and Giles [2], and consider the problem of finding communities that satisfy our definition. We discuss how to find such communities and hardness of this problem.We also propose Web page partitioning by equivalence relation defined using the class of communities of our definition. Though the problem of efficiently finding all communities of our definition is NP-complete, we propose an efficient method of finding a subclass of communities among the sets partitioned by each of n-1 cuts represented by a Gomory-Hu tree [10], and partitioning a Web graph by equivalence relation defined using the subclass.According to our preliminary experiments, partitioning by our method divided the pages retrieved by keyword search into several different categories to some extent.

Bayesian networks have become one of the major models used for statistical inference. We study the question whether the decisions computed by a Bayesian network can be represented within a low-dimensional inner product space. We focus on two-label classification tasks over the Boolean domain. As main results we establish upper and lower bounds on the dimension of the inner product space for Bayesian networks with an explicitly given (full or reduced) parameter collection. In particular, these bounds are tight up to a factor of 2. For some nontrivial cases of Bayesian networks we even determine the exact values of this dimension. We further consider logistic autoregressive Bayesian networks and show that every sufficiently expressive inner product space must have dimension at least Ω(n2), where n is the number of network nodes. We also derive the bound 2Ω(n) for an artificial variant of this network, thereby demonstrating the limits of our approach and raising an interesting open question. As a major technical contribution, this work reveals combinatorial and algebraic structures within Bayesian networks such that known methods for the derivation of lower bounds on the dimension of inner product spaces can be brought into play.

We addressed two issues concerning the practical aspects of optimally scheduling web advertising proposed by Langheinrich et al. [5], which scheduling maximizes the total number of click-throughs for all banner advertisements. One is the problem of multi-impressions in which two or more banner ads are impressed at the same time. The other is inventory management, which is important in order to prevent over-selling and maximize revenue. We propose efficient methods which deal with these two issues.

We propose and evaluate the performance of a number of methods for automatic recording of TV programs for digital video servers, which estimate the user's preference over TV programs based on her/his past viewing behavior and automatically record a selected number of TV programs believed to be of interest to the user. Our methods combine the so-called content-based filtering and social (or collaborative) filtering methods and are based on a certain class of on-line learning algorithms known as the `specialist' algorithms, recently developed in the field of computational learning theory. We empirically evaluated the performance of content-based part of the proposed methods using preference data on TV programs consisting of scores given by people on actual TV programs. The results are largely encouraging and indicate in particular that our methods are practical in terms of both the precision in predicting the user's preference and computational complexity.

Article Free Access Share on Learning specialist decision lists Author: Atsuyoshi Nakamura Theory NEC Laboratory, Real World Computing Partnership(RWCP), c/o C & C Media Research Laboratories, NEC Corporation, 4-1-1 Miyazaki Miyamae-ku, Kawasaki 216-8555, Japan Theory NEC Laboratory, Real World Computing Partnership(RWCP), c/o C & C Media Research Laboratories, NEC Corporation, 4-1-1 Miyazaki Miyamae-ku, Kawasaki 216-8555, JapanView Profile Authors Info & Claims COLT '99: Proceedings of the twelfth annual conference on Computational learning theoryJuly 1999 Pages 215–225https://doi.org/10.1145/307400.307442Published:06 July 1999Publication History 1citation235DownloadsMetricsTotal Citations1Total Downloads235Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We consider the on-line learning problem for