Abstract: The way the basis path set works in neural network remains mysterious, and the generalization of newly appeared G-SGD algorithm to more practical network is hindered. The Basis Path Set Searching problem is formulated from the perspective of graph theory, to find the basis path set in a regular complicated neural network. Our paper aims to discover the underlying cause of path dependency between two independent substructures. Algorithm DEAH is designed to solve the Basis Path Set Searching problem by eliminating such path dependency. The path subdivision chain is proposed to effectively eliminate the path dependency inside the chain and between chains. The theoretical proofs and analysis of polynomial time complexity are presented. The paper therefore provides one methodology to find the basis path set in a more general neural network, which offers theoretical and algorithmic support for the application of G-SGD algorithm in more practical scenarios.
Introduction: The Path Space Optimization Challenge
Training deep neural networks with ReLU activation functions is complex due to their "positive scale-invariant" nature. Standard Stochastic Gradient Descent (SGD) does not account for this property, which can lead to inefficient training. A promising alternative, $\mathcal{G}$-SGD, optimizes in "path space" rather than "weight space." However, the practical application of $\mathcal{G}$-SGD is bottlenecked by the need to identify a Basis Path Set—a minimal, independent set of paths from input to output that can represent the entire network. While finding this set is trivial for simple architectures, modern networks like ResNets and DenseNets introduce complex path dependencies that were previously intractable.
The DEAH Algorithm
To address this, we introduce the Dependency Eliminating Algorithm based on Hierarchical idea (DEAH). The algorithm operates in three main stages:
- Upper-Level Decomposition: Decomposing the network into maximally independent substructures using linear algebra (specifically the rank of adjacency matrices).
- Lower-Level Basis Search: Identifying local basis path sets for each individual substructure.
- Dependency Elimination: Pruning redundant paths that emerge when substructures are combined.
Path Subdivision: A Tool for Dependency
The core innovation of DEAH lies in its handling of path dependency through Path Subdivision Chains. Path dependency is typically caused by "shared edges" between substructures, allowing paths to "swap" segments and become linear combinations of one another. By viewing complex paths as subdivisions of simpler ones—where nodes are inserted into existing edges—we establish a hierarchy that makes these dependencies explicit.
Eliminating Redundancy
Once paths are organized into subdivision chains, the algorithm can systematically prune redundant paths. This process effectively eliminates dependencies both within individual chains and between different chains. This hierarchical approach avoids the exponential complexity of checking every possible path pair, which is a common pitfall in deep networks where path counts grow exponentially with depth.
Complexity and Generalization
We provide a rigorous theoretical proof that DEAH successfully identifies the maximal independent path set for regular fully connected networks with skip connections. Crucially, we demonstrate that DEAH operates in polynomial time, with a derived complexity of $O(RL^2 W_{max}^2) + O(\max(R, T^2)(L + B_{max}^3))$. This ensures that the algorithm remains practical for large-scale, modern architectures like ResNet, which previous methods could not support.
Conclusion
By bridging graph theory and neural network optimization, this work provides the necessary theoretical and algorithmic framework to apply $\mathcal{G}$-SGD to practical, complex architectures. The DEAH algorithm effectively solves the Basis Path Set Searching problem, offering a robust methodology for future advancements in path-space optimization.
Summary updated