Wojciech Szpankowski

A cornerstone of Shannon’s famous information theory is the idea of decoupling the meaning of a message from its efficient transmission. In this article, we propose an extension of Shannon’s communication model where the sender and receiver are assumed to have reasoning capabilities. In such a setting, we gain insights by coupling the fields of information theory and mathematical logic. Under the assumption that a message is coming from a stochastic source, Shannon’s theory establishes that the fundamental compression limit is the entropy of the source. Imagine, however, that we were not interested in the message itself, but rather, we were focused on the logical conclusions that one could derive from it. In this work, we obtain a closed-form expression for a fundamental compression limit in the presence of reasoning capabilities. Our expression is valid under various assumptions about what the sender and receiver know, providing initial answers to key questions such as how much the fundamental limit varies as one narrows or widens the amount of knowledge that is being transferred from sender to receiver, or how, surprisingly, such a fundamental limit remains the same even if the sender is unaware of what it is that a receiver already knows. We also offer practical algorithms that are empirically demonstrated to be significantly more efficient than alternatives that do not account for the existence of reasoning capabilities.

In online learning, a learner receives data in rounds and, at each round, predicts a label that is then compared to the true label, incurring a loss. The total loss over T rounds, when compared to the loss of the best expert from a class of experts or forecasters, is called the regret. In this paper, we focus on logarithmic loss for logistic-like experts with unbounded d-dimensional weights, a scenario that has been largely unexplored. To address the irregularities introduced by the unbounded weight norm, we introduce a regularized version of the average (fixed design) minimax regret by imposing a soft constraint on the weight norm. We demonstrate that the regularized minimax regret is fully characterized by a complexity measure we term the regularized Shtarkov sum. We also show how the behavior of the standard regret can be inferred from the regularized regret. Our main results provide a precise characterization of the regularized Shtarkov sum and, consequently, the regularized regret with unbounded weights up to second-order asymptotics. Notably, unlike the d/2 log T regret growth known for bounded weights, our results imply that the regularized regret grows as (1/2+α/4)d log T when the regularization parameter is of order Θ(T^−α) for α ≤ 1/2. We achieve this using tools from analytic combinatorics, including multidimensional Fourier analysis, the saddle point method, and the Mellin transform.

We study sequential probability assignment in the context of online learning under logarithmic loss and obtain tight lower and upper bounds for sequential minimax regret. Sequential minimax regret is defined as the minimum excess loss over data horizon T that a predictor incurs over the best expert in a class, when the samples are presented sequentially and adversarially . Our upper bounds are established by applying Bayesian averaging over a novel "smooth truncated covering" of the expert class. This allows us to obtain tight (minimax) upper bounds that subsume the best known non-constructive bounds in an algorithmic fashion. For lower bounds, we reduce the problem to analyzing the fixed design regret via a novel application of Shtarkov sum adapted to online learning. We demonstrate the effectiveness of our approach by establishing tight regret bounds for a wide range of expert classes. In particular, we fully characterize the regret of generalized linear function with worst Lipschitz transform functions when the parameters are restricted to a unit norm ℓ _s ( s ≥ 2) ball of dimension d . We show that the regret grows as Θ( d log T ) when d ≤ O ( T ^s/(s+1)-ϵ ) for all ϵ > 0 (with precise constant 1 when d ≤ e ^{o(log T)} ) and Õ( T ^s/(s+1) ) when d ≥ Ω( T ^s/(s+1) ). Finally, we show that the Bayesian approach may not always be optimal if the support of the prior is included in the reference class itself.

Many conventional learning algorithms rely on loss functions other than the natural 0-1 loss for computational efficiency and theoretical tractability. Among them are approaches based on absolute loss (L1 regression) and square loss (L2 regression). The first is proved to be an \textit{agnostic} PAC learner for various important concept classes such as \textit{juntas}, and \textit{half-spaces}. On the other hand, the second is preferable because of its computational efficiency, which is linear in the sample size. However, PAC learnability is still unknown as guarantees have been proved only under distributional restrictions. The question of whether L2 regression is an agnostic PAC learner for 0-1 loss has been open since 1993 and yet has to be answered. This paper resolves this problem for the junta class on the Boolean cube -- proving agnostic PAC learning of k-juntas using L2 polynomial regression. Moreover, we present a new PAC learning algorithm based on the Boolean Fourier expansion with lower computational complexity. Fourier-based algorithms, such as Linial et al. (1993), have been used under distributional restrictions, such as uniform distribution. We show that with an appropriate change, one can apply those algorithms in agnostic settings without any distributional assumption. We prove our results by connecting the PAC learning with 0-1 loss to the minimum mean square estimation (MMSE) problem. We derive an elegant upper bound on the 0-1 loss in terms of the MMSE error and show that the sign of the MMSE is a PAC learner for any concept class containing it.

Many current applications in data science need rich model classes to adequately represent the statistics that may be driving the observations. But rich model classes may be too complex to admit estimators that converge to the truth with convergence rates that can be uniformly bounded over the entire collection of probability distributions comprising the model class, i.e. it may be impossible to guarantee uniform consistency of such estimators as the sample size increases. In such cases, it is conventional to settle for estimators with guarantees on convergence rate where the performance can be bounded in a model-dependent way, i.e. pointwise consistent estimators. But this viewpoint has the serious drawback that estimator performance is a function of the unknown model within the model class that is being estimated, and is therefore unknown. Even if an estimator is consistent, how well it is doing at any given time may not be clear, no matter what the sample size of the observations. Departing from the classical uniform/pointwise consistency dichotomy that leads to this impasse, a new analysis framework is explored by studying rich model classes that may only admit pointwise consistency guarantees, yet all the information about the unknown model driving the observations that is needed to gauge estimator accuracy can be inferred from the sample at hand. We expect that this data-derived estimation framework will be broadly applicable to a wide range of estimation problems by providing a methodology to deal with much richer model classes. In this paper we analyze the lossless compression problem in detail in this novel data-derived framework.

A fundamental challenge in learning is the presence of nonlinear redundancies and dependencies in the data. To address this, we propose a Fourier-based approach to characterize feature redundancies, in unsupervised learning, and feature-label dependencies, in the supervised variant of the problem. We first develop a novel Fourier expansion for functions (more generally stochastic mappings) of correlated binary random variables. This is a generalization of the standard Fourier expansion on the Boolean cube beyond product probability spaces. As an important application of this analysis, we investigate learning with feature subset selection. In the unsupervised variant of this problem, we characterize feature redundancies via the Shannon entropy and group the features into sufficiently informative and redundant. Then, we make a connection to the proposed Fourier expansion and derive an upper bound on the joint entropy. Based on that, we propose a measure to quantify feature redundancies and present an unsupervised learning algorithm. We test our method on various real-world and synthetic datasets and demonstrate improvements on conventional unsupervised feature selection techniques. Then, we investigate the supervised feature subset selection and reformulate it in the Fourier domain. Bridging the Bayesian error rate with the Fourier coefficients, we demonstrate that the Fourier expansion provides a powerful tool to characterize nonlinear feature-label dependencies. Further, we introduce a computationally efficient measure for selecting relevant features. Via a theoretical analysis, we show that our proposed measure finds provably asymptotically optimal feature subsets. Lastly, we present an algorithm based on this measure and via numerical experiments demonstrate its improvements on various supervised feature selection algorithms.