Large language models (LLMs) such as GPT-4 sometimes appeared to be creative, solving novel tasks with a few demonstrations in the prompt. These tasks require the pre-trained models to generalize on distributions different from those from training data—which is known as out-of-distribution generalization. For example, in “symbolized language reasoning” where names/labels are replaced by arbitrary symbols, yet the model can infer the names/labels without any finetuning.

In this talk, I will focus on a pervasive structure within LLMs known as induction heads. By experimenting on a variety of LLMs, I will empirically demonstrate that compositional structure is crucial for Transformers to learn the rules behind training instances and generalize on OOD data. Further, I propose the “common bridge representation hypothesis” where a key intermediate subspace in the embedding space connects components of early layers and those of later layers as a mechanism of composition.

In solving a nonconvex stochastic optimization (SO) problem, in general, the most existing bounds on the sample complexity of stochastic first-order methods depend linearly on the problem dimensionality $d$, exhibiting a rate of complexity $ \mathcal{O} (d / \epsilon^4 ) $. This linear growth rate is increasingly undesirable for modern large-scale SO problems. In this work, we propose dimension-insensitive stochastic first-order methods (DISFOMs) to address nonconvex SO problems via introducing non-smooth and non-Euclidean proximal terms.  Under mild assumptions, we show that DISFOM exhibits a complexity of $ \mathcal{O} ( (\log d) / \epsilon^4 ) $ to obtain an $\epsilon$-stationary point. Furthermore, we prove that DISFOM employing variance reduction can sharpen this bound to $\mathcal{O}( (\log d)^2/\epsilon^3 )$, which perhaps leads to the best-known sample complexity result in terms of $d$. We provide two choices of the non-smooth distance functions, both of which allow for closed-form solutions to the proximal step in the unconstrained case. When the SO problem is subject to polyhedral constraints, the proposed non-smooth distance functions allow efficient resolution of the proximal projection step via a linear convergent ADMM. Numerical experiments are conducted to illustrate the dimension insensitive property of the proposed frameworks.