Hong Kong Workshop on Information Theory, Coding and Learning

Abstract

I will briefly describe early and recent connections between Shannon's information theory and Yao’s communication complexity. The talk is based on a chapter in an upcoming third edition of Cover and Thomas’s Element of Information Theory.

Abstract

I will present an information-theoretic framework that casts learning as universal prediction under log loss, with performance characterized by regret bounds. At the heart of this framework is a principled notion of architecture-dependent model complexity, defined in terms of the probability mass or volume of models near the data-generating process. This volume can be related to spectral properties of the Hessian or Fisher Information Matrix, enabling practical approximations. I will argue that successful learning architectures exhibit a broad range of effective complexities, which allows them to adaptively fit a wide class of functions—even in highly over-parameterized settings. This perspective offers new insights into the role of inductive biases, the effectiveness of stochastic gradient descent, and phenomena such as flat minima. The framework unifies online and batch learning, supervised and generative modeling, and applies across the stochastic realizable, agnostic, and even individual sequence settings. It also sheds light on why modern architectures—such as deep neural networks and transformers—are so successful, suggesting that their layered structure naturally leads to a broad, adaptive complexity profile. These insights point toward the possibility of designing new architectures with comparable or superior performance. Joint work with Meir Feder and Yaniv Fogel and with the help of Ido Atlas, all Tel Aviv University.

Abstract

Let K and K' be two conditional mutual independencies of discrete random variables. In this work, we give complete characterizations of:

1. K is equivalent to K';
2. K implies K'.

Abstract

While modern LLMs exhibit impressive language understanding and generation capabilities, their reasoning abilities—particularly for complex, multi-step problems—remain a critical challenge. In this talk, we explore a suite of advanced techniques to systematically improve LLM reasoning performance. First, we discuss tool augmentation, where LLMs leverage external resources (e.g., Python interpreters) to improve the reasoning abilities. Next, we examine fine-tuning strategies, including supervised learning on interpolated reasoning datasets (e.g., via MATH or GSM8K). We highlight trade-offs between task-specific specialization and generalizability. We then present multi-agent frameworks, where multiple LLMs collaborate or debate to refine outputs. Techniques like self-consistency voting, iterative refinement, and role-specialized agents (e.g., "verifier" or "critic" models) mitigate individual model biases and errors. Our last focus is explicit reasoning traceability: structuring outputs as step-by-step chain-of-thoughts (CoT), where we introduce a learning from correctness way to trace the reasoning steps and correct possible wrong paths in the reasoning. Our results show promising solutions towards future LLMs with better reasoning abilities.

Abstract

Iterative minimization algorithms appear in various areas including machine learning, neural networks, and information theory. The em algorithm is one of the famous iterative minimization algorithms in the area of machine learning, and the Arimoto– Blahut algorithm is a typical iterative algorithm in the area of information theory. However, these two topics had been separately studied for a long time. In this talk, we propose a generalized framework that was recently proposed in the context of the Arimoto–Blahut algorithm. Then, we show various convergence theorems, one of which covers the case when each iterative step is done approximately. Also, we apply this algorithm to the target problem of the em algorithm, and propose its improvement. In addition, we apply it to other various problems in information theory.

This talk will cover the contents of:

• M. Hayashi, "Bregman-divergence-based Arimoto-Blahut algorithm," IEEE Transactions on Information Theory, vol. 71, no. 10, pp. 7788-7801, Oct. (2025).
• M. Hayashi, "Iterative minimization algorithm on a mixture family," Information Geometry, 2024 _Special Issue: Half a Century of Information Geometry, Part 2 (2004). https://doi.org/10.1007/s41884-024-00140-5
• M. Hayashi, "Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory," IEEE Transactions on Information Theory, vol. 69, 3460 -- 3492 (2023).

Abstract

Continuous-time Gaussian channels have traditionally been formulated and investigated using functional analysis. Although this approach is intuitively appealing, it presents several challenges. This talk will focus on the stochastic calculus approach, which, despite being less widely known, can effectively address many of the issues associated with the classical functional analysis method. It turns out that with some recent enhancement, the stochastic calculus approach can recover numerous existing results on continuous-time Gaussian channels, quantitatively strengthen some well-established findings in the literature and further rigorously derive new results.

Abstract

In this talk, I will discuss recent advancements in the auxiliary receiver approach. This approach serves as a mathematical tool for deriving outer bounds in network information theory. It has proven to be highly effective, providing state-of-the-art outer bounds for a variety of settings in network information theory, including relay channels, interference channels, broadcast channels, key agreement, distributed hypothesis testing, and more.