Learning High-Degree Parities: The Crucial Role of the Initialization

Emmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, Donald Kougang-Yombi · 2024

Read Learning High-Degree Parities: The Crucial Role of the Initialization by Emmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, Donald Kougang-Yombi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04910.txt.

Introduction

Parity functions, where the answer is the product of a chosen subset of bits, are the litmus test of machine learning theory. Gradient-trained networks learn low-degree parities easily and fail as the degree nears the full input size. Emmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, and Donald Kougang-Yombi show the borderline case hinges on how the weights start.

Begin from a discrete Rademacher pattern and almost-full parities become learnable; blur that start with enough Gaussian noise and learning fails, for one fixed function, not just on average. A gradient-alignment measure explains the split. Starting points, usually an afterthought, here decide what is learnable at all.

Catalog record

CREATOREmmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, Donald Kougang-Yombi
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE142 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-04910

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning High-Degree Parities: The Crucial Role of the Initialization Emmanuel Abbe, Elisabetta Cornacchia, Jan Hązła, Donald Kougang-Yombi Abstract Parities have become a standard benchmark for evaluating learning algorithms. Recent works show that regular neural networks trained by gradient descent can efficiently learn degree k k parities on uniform inputs for constant k k , but fail to do so when k k and d − k d-k grow with d d (here d d is the ambient dimension). However, the case where k = d − O d ​ ( 1 ) k=d-O_{d}(1) , including the degree d d parity (the full parity ), has remained unsettled. This paper shows that for gradient descent on regular neural networks, learnability depends on the initial weight distribution. On one hand, the discrete Rademacher initialization enables efficient learning of full parities, while on the other hand, its Gaussian perturbation with large enough constant standard deviation σ \sigma prevents it. The positive result for full parity is shown to hold up to σ = O ⁡ ( d − 1 ) \sigma=O(d^{-1}) , pointing to questions about a sharper threshold phenomenon. Unlike statistical query (SQ) learning, where a singleton function class like the full parity is trivially learnable, our negative result applies to a fixed function and relies on an initial gradient alignment measure of potential broader relevance to neural networks learning. 1 Introduction Initialization plays a crucial role in the performance of neural network training algorithms. It has been shown that a proper initialization can help avoiding issues such as vanishing or exploding gradients, or set the foundation for efficient convergence and improved generalization ( [ HZRS15 , GB10 , SMDH13 , Kum17 ] ). In this work, we show that the choice of initialization can be critical when learning complex functions, such as high-degree parities. Parity functions are a well-known class of challenging problems for differentiable learning models, where the task is to determine the parity of bits belonging to an unknown subset of input coordinates. Due to their inherent non-linearity and extreme sensitivity to small input changes, parity functions often serve as a challenging benchmark for evaluating and comparing learning algorithms, including gradient descent on neural networks ( [ AS20 , DM20 ] ). For instance, they have been used for showing the advantages of using convolutional architectures over fully connected ones ( [ MSS20 ] ), the superiority of differentiable models compared to kernel methods ( [ AKM+21 ] ), and the efficacy of curriculum learning in contrast to standard training ( [ ACL24 , CM23 ] ). Previous research has mainly focused on the family of sparse parities, also known as k -parities, where the size of the support of the target parity, k , is bounded, i.e., it does not grow with input dimension d . It has been shown that on uniform inputs, k -parities can be learned by gradient descent algorithms (GD/SGD) on standard architectures, such as 2 -layer fully connected ( [ BEG+22 , ABA22 , Gla23 , KCGK24 ] ), with a sample complexity of \tilde{O}(d^{k-1}) 1 1 1 Where \tilde{O}(d^{c})=O(d^{c}\poly\log(d)) , for c\in\mathbb{R} . ( [ KCGK24 ] ). In contrast, for dense parities, where the support of the target parity is unbounded ( k=\omega_{d}(1) ), the picture is less clear. It has been shown that when both k and d-k are unbounded, stochastic gradient descent (SGD) with large batch size and limited gradient precision on fully connected architectures cannot learn dense parities with any initialization 2 2 2 Assuming the initialization is invariant to permutation of the input neurons. ( [ AS20 ] ). The difficulty in learning parities stems from their orthogonality on uniform inputs, leading to a low cross-predictability (CP) ( [ AS20 ] ). However, this only occurs if a given class of k -parities is sufficiently large. Since the cardinality of this class is \binom{d}{k}=\binom{d}{d-k} , this hardness result does not extend to almost-full parities, where k=d-O_{d}(1) , including the special case of the single d -parity (the full parity ). In fact, it is known that the full parity, as a symmetric function, is learnable by gradient descent methods with specific initialization ( [ NY20 ] ), such as setting all first layer weights to 1 . For random and symmetric initializations, [ ABA22 ] showed that almost-full parities are weakly-learnable 3 3 3 i.e., an inverse polynomial edge over the trivial estimator is achieved with constant probability. by gradient descent on a two-layer fully connected network with discrete Rademacher initialization. In this paper, we focus on almost-full parity functions and provide a deeper understanding of how the initialization impacts their learning. First, we show that SGD on a two-layer fully connected \ReLU network with Rademacher initialization can achieve perfect accuracy for k=d-O_{d}(1) , thus going beyond weak learning. Next, we investigate the robustness of this positive result and argue that it is a special case. In particular, we prove that with Gaussian initialization GD with limited gradient precision with the correlation loss cannot learn high degree parities on two layer ReLU networks. We then introduce an intermediate case of perturbed -Rademacher initialization, where the weights are initialized from a mixture of two Gaussian distributions with means +1 and -1 and a standard deviation of \sigma . In the case of full parity we prove that when \sigma=O(d^{-1}) , the positive result still holds, while if \sigma is a large enough constant, learning does not occur. We leave the analysis for the remaining range of \sigma and the investigation of a potential threshold to future work. While our theoretical analysis focuses on Gaussian perturbations, our experiments also explore other perturbations, both discrete and continuous, supporting our claim that the success of the Rademacher initialization is a special case. In our experiments, we also explore other settings beyond our theoretical analysis in order to justify the robustness of our findings. Crucially, the proof technique for our negative result does not rely on constructing an orbit class or using measures for function classes (as in the cross-predictability case). Instead, it introduces a new approach centered on a novel measure, the initial gradient alignment , which may be relevant for evaluating the suitability of an initialization for a target distribution beyond the specific parity setting discussed in this paper. 2 Related Work Learning Parities. Learning parities on uniform inputs is easy with specialized techniques like Gaussian elimination over two-element fields or through emulation networks trained with Stochastic Gradient Descent (SGD) using small batch sizes ( [ AS20 ] ). However, in the statistical query (SQ) setting ( [ Kea98 ] ) and with gradient descent methods that have limited gradient precision ( [ AS20 ] ), learning parities presents computational barriers. Recent works have focused on sparse parities, or k -parities (where k=O_{d}(1) ), as a classical benchmark for evaluating learning algorithms ( [ SWON24 , EGK+23 , BEG+22 , DM20 , MKAS21 , ABA22 , MSS20 , ACL24 , CM23 , WLLM19 , JT19 ] ). In particular, in the special case of k=2 (i.e. the XOR problem), [ Gla23 ] proved a sample complexity upper bound of \tilde{O}(d) on a 2-layer network of logarithmic width, while for general

Read the complete text