Search papers, labs, and topics across Lattice.
This paper introduces a conjugate learning theory framework based on convex conjugate duality to characterize practical learnability in finite sample settings for deep neural networks (DNNs). The framework demonstrates that mini-batch SGD achieves global optima by controlling extreme eigenvalues of a structure matrix and gradient energy, establishing a convergence theorem and elucidating the impact of batch size and model architecture on non-convex optimization. The work also derives model-agnostic lower bounds for empirical risk and deterministic/probabilistic generalization error bounds, quantifying the influence of information loss, maximum loss, and generalized conditional entropy.
Data fundamentally limits DNN trainability, regardless of model architecture, according to a new model-agnostic lower bound on achievable empirical risk.
In this work, we propose a notion of practical learnability grounded in finite sample settings, and develop a conjugate learning theoretical framework based on convex conjugate duality to characterize this learnability property. Building on this foundation, we demonstrate that training deep neural networks (DNNs) with mini-batch stochastic gradient descent (SGD) achieves global optima of empirical risk by jointly controlling the extreme eigenvalues of a structure matrix and the gradient energy, and we establish a corresponding convergence theorem. We further elucidate the impact of batch size and model architecture (including depth, parameter count, sparsity, skip connections, and other characteristics) on non-convex optimization. Additionally, we derive a model-agnostic lower bound for the achievable empirical risk, theoretically demonstrating that data determines the fundamental limit of trainability. On the generalization front, we derive deterministic and probabilistic bounds on generalization error based on generalized conditional entropy measures. The former explicitly delineates the range of generalization error, while the latter characterizes the distribution of generalization error relative to the deterministic bounds under independent and identically distributed (i.i.d.) sampling conditions. Furthermore, these bounds explicitly quantify the influence of three key factors: (i) information loss induced by irreversibility in the model, (ii) the maximum attainable loss value, and (iii) the generalized conditional entropy of features with respect to labels. Moreover, they offer a unified theoretical lens for understanding the roles of regularization, irreversible transformations, and network depth in shaping the generalization behavior of deep neural networks. Extensive experiments validate all theoretical predictions, confirming the framework's correctness and consistency.
