Description
Computational Learning Theory Team(RIKEN) at RIKEN AIP
Speaker 1: Kohei Hatano (5 min.)
Title: Overview of Computational Learning TheoryTeam
Abstract: Computational Learning Theory Team investigates frontiers of intersections of learning theory (e.g., online learning), continuous/discrete optimization, and their applications. We briefly explain an overview of our team and some representative results.
Speaker 2: Sherief Hashima (35 min.)
Title: Bandit algorithms for 5G/6G wireless communication problems
Abstract: Building a smart and self-decision-making wireless communication systems is considered as one of the main objectives of future beyond 5G (B5G) and 6G. One of the targets is to overcome the high dynamicity and channel impairments of the millimeter wave (mmWave) communications. In this talk we will solve some of mmWave problems like mmWave device to device (D2D) neighbor discovery & selection (NDS), gateway unmanned arial vehicles (UAV) selection in disaster area, multiband selection, mmWave relay probing, etc. using energy aware multi armed bandits (MABs). A group of modified energy aware bandit algorithms (stochastic, adversarial, contextual, and sleeping bandits) are proposed that not only balance the exploration exploitation tradeoff but also consider the remaining energy of the devices during the game. Simulation results approved the efficiency of the proposed methods over traditional solutions with high energy efficiency and convergence rate.
Speaker 3: Daiki Suehiro (35 min.)
Title: Theory and Algorithms for Shapelet-based Multiple-Instance Learning
Abstract: We propose a new formulation of Multiple-Instance Learning (MIL), in which a unit of
data consists of a set of instances called a bag. The goal is to find a good classifier of bags based on the similarity with a “shapelet” (or pattern), where the similarity of a bag with a shapelet is the maximum similarity of instances in the bag. In previous work, some of the training instances are chosen as shapelets with no theoretical justification. In our formulation, we use all possible, and thus infinitely many shapelets, resulting in a richer class of classifiers. We show that the formulation is tractable, that is, it can be reduced through Linear Programming Boosting (LPBoost) to Difference of Convex (DC) programs of finite (actually polynomial) size. Our theoretical result also gives justification to the heuristics of some of the previous work. Our empirical study demonstrates that our algorithm uniformly works for Shapelet Learning tasks on time-series classification and various MIL tasks with comparable accuracy to the existing methods with reasonable computational time.
Speaker 4: Yaxiong Liu (25 min.)
Title: Improved algorithms for online load balancing
Abstract: We consider an online load balancing problem and its extensions in the framework of repeated games. On each round, the player chooses a distribution (task allocation) over K servers, and then the environment reveals the load of each server, which determines the computation time of each server for processing the task assigned. After all rounds, the cost of the player is measured by some norm of the cumulative computation-time vector. The cost is the makespan if the norm is L_infty-norm. The goal is to minimize the regret, i.e., minimizing the player’s cost relative to the cost of the best fixed distribution in hindsight. We propose algorithms for general norms and prove their regret bounds. In particular, for L_infty-norm, our regret bound matches the best known bound and the proposed algorithm runs in polynomial time per trial involving linear programming and second order programming, whereas no polynomial time algorithm was previously known to achieve the bound.
Discussion and Conclusion (10 min)
