Kyoto Information and Society Seminar (KISS)

This seminar series invites speakers from a variety of research fields, including from informatics to mathmatical sciences, and humanities, as well as from the fields of social application and implementation of information technology. The seminar will be held in English and will be scheduled to be held once or twice a month. If you are interested in attending or giving a presentation, please contact takeuchi@i.kyoto-u.ac.jp. [Japanese page] Current schedule:
  • [KISS-004]
    • Title: A tutorial on metaheuristics for combinatorial optimization problems
    • Presenter: Shunji Umetani (Senior Researcher Advanced Technology Lab., Recruit Co., Ltd.) [web]
    • Date：12/17 13:30-15:00
    • Location：Lecture room 3, Research Bldg. No. 7 (104, 1st floor)
    • Abstract:
      We often encounter computationally hard (a.k.a. NP-hard) combinatorial optimization problems in a wide range of industrial applications. A standard approach is formulating the real-world problem as a mixed integer programming (MIP) problem and then solve it by one of the state-of-the-art MIP solvers. Continuous development of the MIP technology has much improved the performance of MIP solvers and this has been accompanied by advances in computing machinery. However, many real-world problems still remains unsolved due to a large gap between the lower and upper bounds of the optimal values. We often consider an alternative approach based on heuristic algorithms that give us (not optimal) but practically good feasible solutions for such hard problems.
      Metaheuristics can be considered as the collection of ideas on designing heuristic algorithm for combinatorial optimization problems. The ideas of metaheuristics give us a systematic view by incorporating them into the basic strategies such as greedy and local search algorithms. In this tutorial, we first introduce how to design efficient local search algorithms along with their ingredients. We then introduce their expansions called “metaheuristics” along with types of strategies such as iterated local search (ILS), simulated annealing (SA), genetic algorithm (GA), guided local search (GLS) and so on.

Past schedule:

  • [KISS-003]
    • Title: How Transformers Learn Causal Structure with Gradient Descent
    • Presenter: Jason D. Lee (Associate Professor, Princeton University) [web]
    • Date：12/5 13:30-15:00
    • Location：Lecture room 2, Research Bldg. No. 7 (101, 1st floor)
    • Abstract:
      The incredible success of transformers on sequence modeling tasks can be largely attributed to the self-attention mechanism, which allows information to be transferred between different parts of a sequence. Self-attention allows transformers to encode causal structure which makes them particularly suitable for sequence modeling. However, the process by which transformers learn such causal structure via gradient-based training algorithms remains poorly understood. To better understand this process, we introduce an in-context learning task that requires learning latent causal structure. We prove that gradient descent on a simplified two-layer transformer learns to solve this task by encoding the latent causal graph in the first attention layer. The key insight of our proof is that the gradient of the attention matrix encodes the mutual information between tokens. As a consequence of the data processing inequality, the largest entries of this gradient correspond to edges in the latent causal graph. As a special case, when the sequences are generated from in-context Markov chains, we prove that transformers learn an induction head (Olsson et al., 2022). We confirm our theoretical findings by showing that transformers trained on our in-context learning task are able to recover a wide variety of causal structures
  • [KISS-002]
    • Title: Best Arm Identification: Fixed Confidence and Fixed Budget Settings
    • Presenter: Jumpei Komiyama (Assistant Professor, NYU) [web]
    • Date：10/29 13:30-15:00
    • Location：Lecture room 3, Research Bldg. No. 7 (104, 1st floor)
    • Abstract:
      We consider the best arm identification problem, where the goal is to find the arm with the largest mean. In this problem, there are two popular settings: the fixed-confidence setting, where the desired confidence level is given, and the fixed-budget setting, where the sample size is predetermined. We introduce the basic ideas of this problem and discuss how differences in the problem setting affect algorithmic design. If time permits, I will also introduce other recent works by the speaker.
  • [KISS-001]
    • Title: Outlier-Robust Neural Network Training: Efficient Optimization of Transformed Trimmed Loss with Variation Regularization
    • Presenter: Akihumi Okuno (Assistant Professor, ISM) [web]
    • Date：10/8 13:30-15:00
    • Location：Lecture room 3, Research Bldg. No. 7 (104, 1st floor)
    • Abstract:
      In this study, we consider outlier-robust predictive modeling using highly-expressive neural networks. To this end, we employ (1) a transformed trimmed loss (TTL), which is a computationally feasible variant of the classical trimmed loss, and (2) a higher-order variation regularization (HOVR) of the prediction model. Note that using only TTL to train the neural network may possess outlier vulnerability, as its high expressive power causes it to overfit even the outliers perfectly. However, simultaneously introducing HOVR constrains the effective degrees of freedom, thereby avoiding fitting outliers. We newly provide an efficient stochastic gradient supergradient descent (SGSD) algorithm for optimization and its theoretical convergence guarantee. (This work is a joint work with Shotaro Yagishita (ISM))