2023/10/19 by Rustem Takhanov, Takhanov, Rustem, Maxat Tezekbayev +7 · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Mathematical Approximation and Integration #Statistical Methods and Inference
paper · pdf · doi:10.48550/arxiv.2310.12660
openalex publication_date 2023/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Classes of target functions containing a large number of approximately orthogonal elements are known to be hard to learn by the Statistical Query algorithms. Recently this classical fact re-emerged in a theory of gradient-based optimization of neural networks. In the novel framework, the hardness of a class is usually quantified by the variance of the gradient with respect to a random choice of a target function. A set of functions of the form x→ ax \bmod p, where a is taken from \mathbb Zp, has attracted some attention from deep learning theorists and cryptographers recently. This class can be understood as a subset of p-periodic functions on \mathbb Z and is tightly connected with a class of high-frequency periodic functions on the real line. We present a mathematical analysis of limitations and challenges associated with using gradient-based learning techniques to train a high-frequency periodic function or modular multiplication from examples. We highlight that the variance of the gradient is negligibly small in both cases when either a frequency or the prime base p is large. This in turn prevents such a learning algorithm from being successful.