Abstract
Infinite-Layer Networks (ILN) have recently been proposed as an architecture that mimics neural networks while enjoying some of the advantages of kernel methods. ILN are networks that integrate over infinitely many nodes within a single hidden layer. It has been demonstrated by several authors that the problem of learning ILN can be reduced to the kernel trick, implying that whenever a certain integral can be computed analytically they are efficiently learnable. In this work we give an online algorithm for ILN, which avoids the kernel trick assumption. More generally and of independent interest, we show that kernel methods in general can be exploited even when the kernel cannot be efficiently computed but can only be estimated via sampling. We provide a regret analysis for our algorithm, showing that it matches the sample complexity of methods which have access to kernel values. Thus, our method is the first to demonstrate that the kernel trick is not necessary as such, and random features suffice to obtain comparable performance.
Introduction
Infinite Layer Networks (ILNs) represent a powerful class of models that bridge the gap between deep neural networks and kernel methods. By integrating over an infinite number of hidden nodes, ILNs can capture complex feature spaces. Traditionally, training these networks has relied on the "kernel trick," which requires the infinite integral over nodes to be analytically solvable into a closed-form kernel function.
However, in many practical scenarios—such as multi-layer convolutional structures or complex priors—this closed-form solution is intractable. This paper addresses a fundamental question: Can we efficiently learn ILNs when the kernel can only be estimated via random sampling? The authors introduce the Shrinking Gradient algorithm, demonstrating that the kernel trick is not a strict requirement for achieving optimal theoretical performance.
The Shrinking Gradient Algorithm
The proposed approach moves beyond the exact kernel trick by utilizing random feature sampling within an online learning framework. The core of the method is a modified version of Online Gradient Descent (OGD). Since the exact kernel is unavailable, the algorithm employs a two-step sampling procedure to generate unbiased stochastic estimates of the gradient.
A significant challenge in this setting is managing the variance of the stochastic gradient. In standard OGD, the variance of such estimators can grow with the $L_1$ norm of the learned weights, potentially hindering convergence. To mitigate this, the authors introduce a novel "shrinkage" mechanism. When the estimated scalar product exceeds a specific threshold—indicating the hypothesis is moving outside the optimal bounded region—the algorithm divides the weights by a factor of 4. This lightweight regularization keeps weights bounded and controls gradient variance without requiring the exact kernel for norm projections.
Empirical Performance
The algorithm was evaluated using a synthetic high-dimensional dataset where input dimensions $D$ ranged from 550 to 800. The performance of the Shrinking Gradient (Shrink-Grad) algorithm was compared against two baselines: Fixed-Random and Doubly-Stochastic Gradient Descent.
As shown in the figure above, Shrink-Grad consistently achieves a lower loss than the baseline methods across all tested input dimensions. This demonstrates that the shrinkage mechanism effectively manages the noise inherent in random feature sampling, leading to superior empirical efficiency under a fixed budget of random feature evaluations.
Key Insights and Theoretical Results
The research yields several critical insights:
- Kernel Trick Independence: Optimal sample complexity can be achieved through random sampling, matching the theoretical performance of exact kernel methods.
- Computational Parity: To reach an error rate of $O(1/\sqrt{T})$, the algorithm requires $\tilde{O}(T^2)$ scalar product estimations, which is computationally comparable to constructing a standard kernel matrix.
- Regret Bounds: The algorithm achieves a regret bound of $O(B\sqrt{T})$ in the online setting and an expected loss convergence rate of $O(1/\sqrt{T})$ in the batch setting, where $B$ is the norm bound of the target function.
Conclusion and Future Directions
While the Shrinking Gradient algorithm proves that the kernel trick is optional for ILNs, some limitations remain. The current theoretical guarantees are specific to squared loss, and the complexity dependence on the norm bound $B$ could be improved. Future work may extend this framework to handle missing or corrupted data entries in kernel matrices and explore applications beyond the squared loss function.
Summary updated