Christos Thrampoulidis

Language models trained with next-token prediction acquire internal representations that encode rich semantic structure, including syntactic regularities, linear semantic analogies, and a coarse-to-fine progression in learned concepts. While these phenomena are well documented, their origin remains conceptually opaque: how does predicting next-token distributions produce such structure?This thesis tackles this question from first principles. We frame next-token prediction as a soft-label classification problem, where each context is paired with a sparse target distribution over next tokens. Variation in support across contexts creates a structured pattern of label sparsity, captured by a data co-occurrence matrix.To formalize this, we adopt the Unconstrained Features Model (UFM), a minimal setting where logits are parameterized as a product of word and context embeddings and trained with cross-entropy loss plus ridge regularization. We prove that gradient descent drives directional convergence: context embeddings with identical support sets collapse to a shared direction, partitioning the embedding space by support pattern. This process uncovers latent structure in the data, even without explicit semantic supervision.We further show that the singular vectors of the co-occurrence matrix align with interpretable semantic directions in embedding space. Each vector induces a partition over words or contexts based on alignment with a latent concept. These directions emerge sequentially during training, with dominant concepts learned first—yielding a spectral explanation for the progression from coarse to fine-grained structure.Experiments on synthetic and real data confirm these predictions. Trained transformers exhibit the same alignment between embeddings and the singular directions of the co-occurrence matrix. Semantic structure appears in both synthetic tasks and pretrained models. Tracking learning in text data and step-imbalanced MNIST shows coarse distinctions—such as part-of-speech or majority class—emerging early, followed by finer categories, consistent with spectral ordering.Finally, we extend the analysis to settings with class imbalance, showing that reweighting the loss flattens the singular spectrum of the co-occurrence matrix, thereby accelerating the acquisition of underrepresented features. These results demonstrate that semantic structure in next-token prediction arises predictably from the interaction between label structure—particularly its spectral properties—and the implicit bias of optimization.

View record

Deep learning has increasingly shifted towards using Transformers across various applications, including computer vision and natural language processing, with large language models leading this success. However, the optimization and generalization dynamics of Transformer models remain poorly understood. In this thesis, we take steps towards establishing a foundational theory. Specifically, we focus on self-attention models, the core mechanism of the Transformer. We first study multi-head attention models in a binary classification setting, developing optimization and generalization bounds that elucidate the finite-time behavior of these models when trained with gradient descent. The non-linear and non-convex nature of the softmax function makes this analysis particularly challenging. To establish bounds in this complex regime, our theory leverages the smoothness of the softmax function and pertinent second-order information through the Hessian. The latter gives the loss landscape a weakly-convex nature on sufficient overparameterization. We further leverage the algorithmic stability framework to derive generalization bounds, using on-average model stability. Our bounds have the potential for extension to more complex architectures, and draw connections to the existing theory of overparameterized multilayer perceptrons. While finite-time optimization and generalization guarantees address part of the puzzle, a complete understanding of training dynamics requires studying the time evolution of training parameters. One approach is to study where the training parameters converge as training time blows up—specifically, whether GD training exhibits any implicit preference among the possible minimizers of the training loss. This preference is known as the implicit bias of the optimizer, and we explore this for self-attention models. We demonstrate that in non-trivial data settings, when training the combined key-query matrix, it globally converges (regardless of initial direction) to the solution of a hard-margin SVM problem. Further, our theory characterizes the complete training dynamics in this setup, explaining the time evolution of the loss function, the growth of parameters, and the evolution of the attention map. Finally, we explore benefits of using adaptive step rules for Transformer optimization. Our findings reinforce the implicit bias perspective of self-attention and strengthen its connections to implicit bias in linear logistic regression, despite the intricate non-convex nature of the former.

View record

Class imbalance in machine learning has long been a significant research challenge. As models grow, reaching interpolation capacity (where models fully fit the training data), traditional methods like loss reweighting or data resampling become less effective. While new methods address imbalanced learning in the over-parameterized regime, their impact on deep learning is unclear. Recent studies reveal the Neural Collapse (NC) phenomenon in over-parameterized networks, where features from penultimate layers collapse into class-representative vectors. These vectors align with last layer classifiers, forming symmetric geometry with maximal class separation. Initially observed experimentally, NC has been analyzed theoretically using the Unconstrained Feature Model (UFM), focusing on the last layer and assuming networks produce optimized outputs, mainly on balanced datasets. In this thesis, we extend the UFM framework to analyze Cross-Entropy (CE) and Supervised Contrastive Loss (SCL) in imbalanced data. We introduce the SELI framework to characterize classifier/feature geometry under CE loss, explaining symmetric geometry on balanced datasets and predicting geometry in imbalanced cases. This leads to our identification of the Minority Collapse phenomenon, where minority class classifiers collapse, reducing margins and classification performance. We explore logit-adjusted CE loss variations that improve accuracy by favoring minority margins. We study resulting geometries and propose optimal hyperparameters for achieving symmetric geometries, enhancing minority margins. For SCL loss, adding a non-negative activation function like ReLU restores symmetry in geometry regardless of imbalance. Our analysis reveals batching's importance in contrasting features, leading to minimum requirements for NC feature collapse. We suggest batching strategies aiding SCL convergence to symmetric geometry and propose using prototype vectors to fine-tune geometry in SCL models without non-negativity constraints. Our findings are supported by extensive experiments on standardized vision datasets.

View record

Deep neural networks have achieved transformative success in numerous fields such as computer vision, natural language processing, and robotics, largely due to their ability to capture complex patterns from large datasets. Among the innovations driving this success, the transformers mechanism has played a pivotal role by overcoming the limitations of earlier models, like recurrent neural networks. Despite the empirical success, our theoretical understanding of transformers and their core, self-attention mechanism remains incomplete, especially with regard to their optimization and generalization behaviors.Previous research has predominantly focused on single-head attention, thereby limiting insights into the impact of overparameterization in more complex models. Motivated by the demonstrated benefits of overparameterization in training fully-connected networks, we explore the potential optimization and generalization advantages of employing multiple attention heads. Specifically, we derive convergence and generalization guarantees for gradient descent training of a single-layer multi-head self-attention model, under a suitable realizability condition on the data. Additionally, we identify initialization conditions that ensure the realizability assumption is met and verify that these conditions hold in a simple but practical data model. Our findings offer insights that could be extended to various data models and architectural settings. Building upon these insights, we also examine the influence of other architectural components on training dynamics, focusing specifically on normalization. To this end, we study batch normalization, a widely-used technique that has proven to accelerate training and improve generalization in deep neural networks. Despite its popularity, our understanding of its underlying mechanisms remains limited, and we believe that uncovering its impact could further help extend our results to the other normalization variants across different neural network architectures. We investigate the impact of batch normalization on a simple two-layer neural network and show that when training with gradient descent on a simple data model, the network parameters converge to a solution with uniform margin directions. Furthermore, we derive finite-time rates for the evolution of both the loss and the weights during the training process.

View record

In this thesis, we investigate the ability of neural networks, particularly Transformers, to reason and memorize. First, we focus on graph neural networks and Transformers, and analyze their performance on algorithmic reasoning tasks. We show that while models can achieve high accuracy on data from the same distribution as their training data, their performance drops significantly when faced with new, out-of-distribution data. We further show that even high performance on benchmark numbers may be misleading and true reasoning capability of these models remains limited. We identify several challenges involved in achieving true reasoning abilities and generalization to new data. We propose solutions to some of these challenges, including fixing input representation issues, hybrid models, and enlarging the training dataset. We also examine the expressivity of Transformers, providing a theoretical analysis of their ability to memorize data points. The results show a linear relationship between a Transformer's memory capacity and both the number of its attention heads as well as the input's context size.

View record

Machine learning has trended toward training overparameterized networks that can exactly fit the training set. In this regime, when the training data is class-imbalanced, traditional methods for mitigating imbalances are not effective and yield poor performance on minorities. Tailored to the over-parameterized setting, one successful technique to combat imbalances involves adjusting the logits during training by introducing several hyper-parameters in the cross-entropy loss. The idea behind these adjustments is rooted in the implicit bias analysis which, for linear models, explains why they successfully induce bias on the optimization path towards solutions that favor minorities. However, the impact of these adjustments is not well-understood for deep, non-linear models that simultaneously learn features from the data and fit classifiers on them. In this work, we take a step towards formalizing the impact of data imbalances and the choice of loss function when learning in over-parameterized setups.At the core of our analysis is the unconstrained features model (UFM), which recently provided partial theoretical justification for the empirical finding known as Neural-collapse. Limited to the balanced setting, Neural-collapse suggests that over-parameterized models learn features and classifiers that are arranged in a perfectly symmetric and maximally-separated geometry. Leveraging the UFM in our analysis, we analytically characterize the changes in the learned geometry as data becomes imbalanced or the loss function is modified. Our analysis characterizes the properties of the learned features and classifiers, justifying previously observed empirical findings on imbalanced training. To verify the accuracy of our theoretical predictions, we conduct experiments on benchmark networks and vision datasets. Additionally, we adopt the UFM to conduct a preliminary study on supervised contrastive loss, a recently proposed alternative to the cross-entropy. We observe that these two losses, under UFM, exhibit certain similarities. Furthermore, with a slight modification to the model, we discover that we can make the training geometry invariant to imbalances in this case. Overall, despite its simplicity, UFM uncovers certain biases of over-parameterized models at the training stage. Indeed, this simplification is not without its own limitations, which will become clear throughout our analysis.

View record

In many machine learning problems, an objective is required to be optimizedwith respect to some constraints. In many cases, these constraints are unknownto us but we can search and take measurements within an exploration radius. Inthe machine learning community, we call this safe optimization. One importantpoint in safe optimization algorithms is how fast we can converge to optima andget in a neighborhood of the optimal solution. In this thesis, we introduce a novelsafe optimization algorithm that is fast. The experiments are performed througha software package we developed called ASFW which is available for download.On the application side, we demonstrate how safe optimization techniques can beapplied to a real-world problem and make an attempt to employ safe optimizationapproaches to solve a real-world problem and propose a frame work that may beapplied in various industrial settings.

View record