Finding linear functions that maximize AUC scores is important in ranking research. A typical approach to the ranking problem is to reduce it to a binary classification problem over a new instance space, consisting of all pairs of positive and negative instances. Specifically, this approach is formulated as hard or soft margin optimization problems over pn pairs of p positive and n negative instances. Solving the optimization problems directly is impractical since we have to deal with a sample of size pn, which is quadratically larger than the original sample size p+n. In this paper, we reformulate the ranking problem as variants of hard and soft margin optimization problems over p+n instances. The resulting classifiers of our methods are guaranteed to have a certain amount of AUC scores.

We consider Monte Carlo tree search problem, a variant of Min-Max tree search problem where the score of each leaf is the expectation of some Bernoulli variables and not explicitly given but can be estimated through (random) playouts. The goal of this problem is, given a game tree and an oracle that returns an outcome of a playout, to find a child node of the root which attains an approximate min-max score. This problem arises in two player games such as computer Go. We propose a simple and efficient algorithm for Monte Carlo tree search problem.

We consider online linear optimization over symmetric positive semi-definite matrices, which has various applications including the online collaborative filtering. The problem is formulated as a repeated game between the algorithm and the adversary, where in each round t the algorithm and the adversary choose matrices Xt and Lt, respectively, and then the algorithm suffers a loss given by the Frobenius inner product of Xt and Lt. The goal of the algorithm is to minimize the cumulative loss. We can employ a standard framework called Follow the Regularized Leader (FTRL) for designing algorithms, where we need to choose an appropriate regularization function to obtain a good performance guarantee. We show that the log-determinant regularization works better than other popular regularization functions in the case where the loss matrices Lt are all sparse. Using this property, we show that our algorithm achieves an optimal performance guarantee for the online collaborative filtering. The technical contribution of the paper is to develop a new technique of deriving performance bounds by exploiting the property of strong convexity of the log-determinant with respect to the loss matrices, while in the previous analysis the strong convexity is defined with respect to a norm. Intuitively, skipping the norm analysis results in the improved bound. Moreover, we apply our method to online linear optimization over vectors and show that the FTRL with the Burg entropy regularizer, which is the analogue of the log-determinant regularizer in the vector case, works well.

We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.

We propose online prediction algorithms for data streams whose characteristics might change over time. Our algorithms are applications of online learning with experts. In particular, our algorithms combine base predictors over sliding windows with different length as experts. As a result, our algorithms are guaranteed to be competitive with the base predictor with the best fixed-length sliding window in hindsight.

We prove generalization error bounds of classes of low-rank matrices with some norm constraints for collaborative filtering tasks. Our bounds are tighter, compared to known bounds using rank or the related quantity only, by taking the additional L1 and L∞ constraints into account. Also, we show that our bounds on the Rademacher complexity of the classes are optimal.

We introduce the Hexagonal Convolutional Neural Network (HCNN), a modified version of CNN that is robust against rotation. HCNN utilizes a hexagonal kernel and a multi-block structure that enjoys more degrees of rotation information sharing than standard convolution layers. Our structure is easy to use and does not affect the original tissue structure of the network. We achieve the complete rotational invariance on the recognition task of simple pattern images and demonstrate better performance on the recognition task of the rotated MNIST images, synthetic biomarker images and microscopic cell images than past methods, where the robustness to rotation matters.

In this paper, we investigate an online job scheduling problem with n jobs and k servers, where the accessibilities between the jobs and the servers are given as a bipartite graph. The scheduler is tasked with minimizing the regret, defined as the difference between the total flow time of the scheduler over T rounds and that of the best-fixed scheduling in hindsight. We propose an algorithm whose regret bounds are $O(n^2 sqrt{Tln (nk)})$ for general bipartite graphs, $O((n^2/k^{1/2}) sqrt{Tln (nk)})$ for the complete bipartite graphs, and $O((n^2/k) sqrt{T ln (nk)}$ for the disjoint star graphs, respectively. We also give a lower regret bound of $Omega((n^2/k) sqrt{T})$ for the disjoint star graphs, implying that our regret bounds are almost optimal.

Following the formulation of Support Vector Regression (SVR), we consider a regression analogue of soft margin optimization over the feature space indexed by a hypothesis class H. More specifically, the problem is to find a linear model w ∈ ℝH that minimizes the sum of ρ-insensitive losses over all training data for as small ρ as posssible, where the ρ-insensitive loss for a single data (xi, yi) is defined as max{|yi - ∑h whh(xi)| - ρ, 0}. Intuitively, the parameter ρ and the ρ-insensitive loss are defined analogously to the target margin and the hinge loss in soft margin optimization, respectively. The difference of our formulation from SVR is two-fold: (1) we consider L1-norm regularization instead of L2-norm regularization, and (2) the feature space is implicitly defined by a hypothesis class instead of a kernel. We propose a boosting-type algorithm for solving the problem with a theoretically guaranteed convergence rate under a natural assumption on the weak learnability.