Topic: sample complexity

Maissam Barkeshli uses synthetic data of adjustable complexity to study how transformers learn. Sequences from graph, hypergraph and hierarchical random walks make it possible to investigate scaling laws, sample complexity and unexpected temperature effects in controlled settings. The presentation also considers how parameterisation changes hyperparameter scaling, including the importance of scaling the embedding-layer learning rate.

David Woodruff develops sampling bounds for estimating the spectrum of symmetric matrices with bounded entries. Principal-submatrix sampling achieves epsilon times n additive error using roughly 1/epsilon² samples, eliminating dependence on n and improving prior epsilon dependence up to logarithmic factors. Squared row-norm sampling gives epsilon times the Frobenius norm accuracy with roughly 1/epsilon² samples, improving a previous 1/epsilon⁸ bound. For bounded-entry positive-semidefinite matrices, O(1/epsilon) sampled columns permit nonadaptive approximation of the leading eigenvector with e