An AI agent might surprisingly find she has reached an unknown state which she has never been aware of -- an unknown unknown. We mathematically ground this scenario in reinforcement learning: an agent, after taking an action calculated from value functions $Q$ and $V$ defined on the {\it {aware domain}}, reaches a state out of the domain. To enable the agent to handle this scenario, we propose an {\it episodic Markov decision {process} with growing awareness} (EMDP-GA) model, taking a new {\it noninformative value expansion} (NIVE) approach to expand value functions to newly aware areas: when an agent arrives at an unknown unknown, value functions $Q$ and $V$ whereon are initialised by noninformative beliefs -- the averaged values on the aware domain. This design is out of respect for the complete absence of knowledge in the newly discovered state. The upper confidence bound momentum Q-learning is then adapted to the growing awareness for training the EMDP-GA model. We prove that (1) the regret of our approach is asymptotically consistent with the state of the art (SOTA) without exposure to unknown unknowns in an extremely uncertain environment, and (2) our computational complexity and space complexity are comparable with the SOTA -- these collectively suggest that though an unknown unknown is surprising, it will be asymptotically properly discovered with decent speed and an affordable cost.

Graph neural networks (GNNs) have gained popularity for various graph-related tasks. However, similar to deep neural networks, GNNs are also vulnerable to adversarial attacks. Empirical studies have shown that adversarially robust generalization has a pivotal role in establishing effective defense algorithms against adversarial attacks. In this paper, we contribute by providing adversarially robust generalization bounds for two kinds of popular GNNs, graph convolutional network (GCN) and message passing graph neural network, using the PAC-Bayesian framework. Our result reveals that spectral norm of the diffusion matrix on the graph and spectral norm of the weights as well as the perturbation factor govern the robust generalization bounds of both models. Our bounds are nontrivial generalizations of the results developed in (Liao et al., 2020) from the standard setting to adversarial setting while avoiding exponential dependence of the maximum node degree. As corollaries, we derive better PAC-Bayesian robust generalization bounds for GCN in the standard setting, which improve the bounds in (Liao et al., 2020) by avoiding exponential dependence on the maximum node degree.

Logarithms turn a product of numbers into a sum of numbers: log(xy) log(x) log(y). Hyperlogarithms generalize the concept as follows: Hlog(XY) Hlog(X) Hlog(y), where X and Y are any kind of objects, and the product and sum are replaced by operators in some arbitrary space. Here we focus exclusively on operations on sets: XY becomes the intersection of the sets X and Y, and X Y the union of X and Y. The question is: which functions satisfy Hlog(XY) Hlog(X) Hlog(y). We assume here that the argument for Hlog is a set X, and the returned value Hlog(X) Y is another set Y from the same set of sets. Let E {X, Y, ... } be the sets of all potential arguments for Hlog.

Logarithms turn a product of numbers into a sum of numbers: log(xy) log(x) log(y). Hyperlogarithms generalize the concept as follows: Hlog(XY) Hlog(X) Hlog(y), where X and Y are any kind of objects, and the product and sum are replaced by operators in some arbitrary space. Here we focus exclusively on operations on sets: XY becomes the intersection of the sets X and Y, and X Y the union of X and Y. The question is: which functions satisfy Hlog(XY) Hlog(X) Hlog(y). We assume here that the argument for Hlog is a set X, and the returned value Hlog(X) Y is another set Y from the same set of sets. Let E {X, Y, ... } be the sets of all potential arguments for Hlog.

Logarithms turn a product of numbers into a sum of numbers: log(xy) log(x) log(y). Hyperlogarithms generalize the concept as follows: Hlog(XY) Hlog(X) Hlog(y), where X and Y are any kind of objects, and the product and sum are replaced by operators in some arbitrary space. Here we focus exclusively on operations on sets: XY becomes the intersection of the sets X and Y, and X Y the union of X and Y. The question is: which functions satisfy Hlog(XY) Hlog(X) Hlog(y). We assume here that the argument for Hlog is a set X, and the returned value Hlog(X) Y is another set Y from the same set of sets. Let E {X, Y, ... } be the sets of all potential arguments for Hlog.