Source-linked AI summary
AdaNet: Adaptive Structural Learning of Artificial Neural Networks
Corinna Cortes, Xavi Gonzalvo, Vitaly Kuznetsov, Mehryar Mohri, Scott Yang
TL;DR
Neural-network training requires difficult optimization and architecture selection, while fixed architectures can impose inappropriate complexity. AdaNet jointly learns network structure and weights using data-dependent generalization guarantees, and its algorithms solve strongly convex optimization problems; experiments report adaptive architectures with favorable performance across CIFAR-10 tasks.
Problem
Neural networks require specifying a large architecture and solving a difficult non-convex optimization problem, while fixed architectures can impose excessive complexity across tasks.
Method
AdaNet jointly learns architecture and parameters by adaptively adding penalized units and layers, guided by data-dependent generalization bounds.
Results
AdaNet outperformed other methods on each evaluated CIFAR-10 dataset, with architectures adapting in complexity to the problem.
Takeaways & Limitations
The framework provides adaptive neural-network architecture learning with theoretical guarantees and can extend to CNNs and RNNs.
Takeaways & Limitations
The presented learning scenario restricts the formal treatment to binary classification, although the authors state that extensions to multi-class classification are straightforward.
Abstract
from arXiv · showhide
We present new algorithms for adaptively learning artificial neural networks. Our algorithms (AdaNet) adaptively learn both the structure of the network and its weights. They are based on a solid theoretical analysis, including data-dependent generalization guarantees that we prove and discuss in detail. We report the results of large-scale experiments with one of our algorithms on several binary classification tasks extracted from the CIFAR-10 dataset. The results demonstrate that our algorithm can automatically learn network structures with very competitive performance accuracies when compared with those achieved for neural networks found by standard approaches.
1. Introduction
AdaNet addresses the difficulty of choosing neural-network architectures and optimizing their parameters by learning both simultaneously. Its theory guides adaptive algorithms whose optimization problems are strongly convex.
- Motivation: Pre-specified architectures impose fixed depth and complexity, even though tasks differ in the complexity they require.This can make complex models prone to overfitting when data are insufficient and makes architecture selection burdensome.
- Motivation: Architecture search is often treated as hyperparameter tuning, but the search space can become exorbitantly large.Practitioners may need substantial experience and domain knowledge to choose an appropriate architecture.
- Contribution: AdaNet provides generalization bounds for learning neural-network structure and parameters simultaneously, claimed as the first such generalization bounds.The guarantees guide the design of two algorithms for this setting.
- Method: Starting from a simple linear model, the algorithms add units and layers as needed while selecting and penalizing additions using estimates from statistical learning theory.This adaptively learns the model complexity rather than enforcing a fixed architecture.
- Result: Both algorithms solve strongly convex optimization problems with unique global solutions, unlike other neural-network training methodologies.The cited result contrasts their optimization properties with the non-convex optimization typically required for neural networks.
2. Network architecture
The paper considers feedforward networks with flexible skip connections and defines their function families through layer-wise units, norm-constrained weights, and convex-hull representations. Standard multilayer networks remain special cases of this broader architecture.
- Scope: The framework restricts attention to binary classification while stating that the architecture and guarantees extend straightforwardly to multi-class classification.The extension augments the number of output units and uses multi-class counterparts of ensemble margin bounds.
- Network architecture: The considered architectures allow units to connect to any lower layer, including direct connections from the output unit to arbitrary units.Standard multilayer feedforward networks are recovered by zeroing appropriate connections.
- Network architecture: Each intermediate layer has a specified maximum number of units, whose functions combine weighted outputs from lower-layer units through 1-Lipschitz activations.ReLU and sigmoid are given as allowable activation functions.
- Function families: The family F consists of functions whose connection-weight absolute values sum to one.This norm constraint defines the function family used in the architecture formalization.
- Function families: The function family F is represented as the convex hull of the union of layer-specific hypothesis families and their reflections.The paper also defines a related family F∗ whose architectures remain more general than standard feedforward networks.
3. Learning problem
The learning problem uses an i.i.d. labeled sample to choose a network function with low generalization error. Because accurate functions are expected to be sparse, solving this problem also learns an underlying architecture.
- Learning setup: Training and test examples are assumed to be drawn independently from the same distribution over inputs and binary labels.The training sample contains m labeled examples drawn from D^m.
- Learning objective: The objective is to use the training sample to determine a function with small generalization error.Generalization error is defined as the probability of incorrect classification under the data distribution.
- Architecture learning: An accurate predictor is expected to have many zero weights, fewer than the maximum number of units in each layer, and relatively few non-zero connections.This expected sparsity links function learning with learning the network architecture.
- Learning guarantees: The paper introduces data-dependent learning bounds in the following section to guide algorithm design for this learning problem.The bounds are based on complexity measures of the relevant hypothesis sets.
4. Generalization bounds
The paper develops data-dependent generalization bounds for neural-network hypothesis classes using Rademacher complexities and margin-based guarantees. These bounds distinguish layer-specific complexity and depend only logarithmically on depth, providing explicit guidance for structural learning and weight allocation.
- Data-dependent Rademacher complexities provide finer learning guarantees and can be estimated from data or replaced with convenient upper bounds.These alternatives support more informative or more easily used generalization bounds.
- The ensemble family F is analyzed as the convex hull of H using margin-based guarantees with explicit dependence on mixture weights w_k.This yields a learning guarantee for the ensemble function f.
- Theorem 1’s bound depends only logarithmically on network depth l and uses a ∥w_k∥1-weighted average of layer hypothesis-set complexities.The weighting is determined by the network’s own mixture weights.
- A deep network can retain a strong generalization guarantee when it has small empirical margin error and allocates more weight to lower-layer units.With sparse weights, this corresponds to relatively fewer units or connections at higher layers.
- The layer-family complexity results upper-bound the complexity of H_k using complexities of lower-layer families and provide explicit guarantees for feedforward networks.The bounds also discuss dependence on p, q, and the product N_k of units below layer k.
- The layer-specific bound is finer than earlier bounds because it differentiates weights across layers rather than treating all weights indiscriminately.The paper states that this prevents network complexity from needing to grow exponentially with depth and extends to additional architectures.
5. Algorithm
ADANET adaptively grows a neural network by optimizing a complexity-penalized objective over candidate subnetworks. It uses boosting-style coordinate descent, evaluates shallow and deeper extensions, and stops when further growth no longer improves the objective.
- Objective function: ADANET balances empirical risk minimization with model complexity while adaptively growing the neural-network structure.Its objective combines a convex surrogate loss with a weighted-l1 regularization term that includes both coefficient magnitude and subnetwork complexity.
- Objective function: The weighted-l1 penalty assigns each candidate a cost Γj = λrj + β based on its Rademacher complexity and regularization hyperparameters.This discriminates candidate functions according to complexity while retaining standard l1 regularization.
- Description: At each iteration, ADANET considers a same-depth subnetwork and a deeper subnetwork, selecting the option that produces the greatest objective reduction.The two extensions add B units per layer, with the deeper candidate increasing the network depth by one.
- Description: Previously learned units can feed later deeper subnetworks, allowing new components to use embeddings learned in earlier iterations.This permits incremental construction while reusing representations from the existing architecture.
- Description: ADANET terminates after T rounds or when no architecture extension improves the objective; candidate search may use heuristic δ-optimal coordinates.The main search can involve non-convex optimization, while the appendix variant restricts the search to a convex subproblem with a closed-form solution.
- Description: The algorithm applies block coordinate descent: it selects descent coordinates from H* and solves a convex optimization problem for their step sizes.Candidate subnetworks may be generated randomly or by optimizing the candidate-search objective, and the best candidate is then selected.
6. Experiments
The experiments evaluate AdaNet against standard neural networks and logistic regression on CIFAR-10 and Criteo tasks. AdaNet generally achieves competitive or better performance while selecting architectures adaptively, often using fewer layers or units.
- CIFAR-10: The CIFAR-10 comparison includes AdaNet, feedforward NN, logistic regression, and NN-GP, evaluated with 10-fold cross-validation.Average accuracy and standard deviations across test folds are reported in Table 1.
- Experimental setup: Neural-network hyperparameters are selected using grid search or Gaussian-process bandits, with models trained by mini-batch stochastic gradient methods.AdaNet uses the same mini-batch configuration to solve its optimization problem in the Criteo experiment.
- CIFAR-10: AdaNet outperforms other methods on each of five binary CIFAR-10 label-pair datasets.The label pairs are deer-truck, deer-horse, automobile-truck, cat-dog, and dog-horse.
- CIFAR-10: AdaNet typically selects one-layer architectures with fewer units than NN and NN-GP, but chooses two layers for the harder cat-dog task.The more complex cat-dog model results in better performance for that task.
- Criteo Click Rate Prediction: Criteo experiments use seven days of impression data with 13 count features and 26 categorical features, split into training, validation, and test sets.The training set contains 32,743,299 instances, while validation and test each contain 6,548,659 instances.
- Criteo Click Rate Prediction: On Criteo, AdaNet achieves better accuracy than NN with a single hidden layer of 512 nodes, whereas NN selects four hidden layers with 512 units each.The performance difference is reported as statistically significant on this challenging task.
7. Conclusion
The conclusion presents AdaNet as a framework for jointly learning neural-network structures and parameters. It connects the method to theoretical guarantees and favorable experiments, while noting that the test set in the linked Criteo data lacks ground-truth labels.
- Contributions: AdaNet simultaneously learns neural-network architecture and parameters by balancing model complexity against empirical risk minimization.The framework is supported by data-dependent generalization bounds.
- Empirical findings: The reported experiments show AdaNet learning architectures that perform better than those found through grid search.The authors describe the techniques as applicable to CNNs and RNNs.
- Data limitation: The linked Criteo test set has no ground-truth labels and cannot be used in the experiments.The experiments instead use the provided training data split into training, validation, and test sets.
A. Related work
Prior work studies neural-network objectives, optimization, and structure learning, including heuristic growth and pruning and search-based approaches. AdaNet is positioned as using different methods while learning structure from a single input layer.
- Theoretical understanding: Theoretical neural-network research has examined objective-function properties, black-box optimization algorithms, and related training questions.The cited lines include analyses of objective landscapes and optimization procedures.
- Structure learning: Earlier structure-learning methods grow and prune neural-network architectures using heuristics, while more recent work includes search-based approaches.These approaches form a major line of related research.
- Positioning: Compared with cited tensor-method work on two-layer networks, AdaNet uses different methods, applies to arbitrary networks, and learns structure from a single input layer.The passage explicitly contrasts the scope and structural-learning setup.
B. Proofs
The proofs establish generalization and complexity bounds for structural learning with ensembles of neural-network hypotheses. They use Rademacher-complexity arguments, norm-based steps, contraction, and extensions to multi-class classification.
- Generalization guarantees: The theoretical development begins with a structural-learning guarantee for ensembles of hypotheses.This guarantee supports the subsequent generalization analysis.
- Generalization guarantees: Theorem 1 provides a high-probability bound for ensemble predictors formed from hypothesis classes with structural decompositions.The theorem is derived from the cited DeepBoost generalization bound.
- Extensions: The generalization result extends straightforwardly to multi-class classification using existing multi-class ensemble-margin bounds.The network architecture is also extended by augmenting the number of output units.
- Complexity analysis: The proof bounds empirical Rademacher complexity recursively across network classes and uses sub-additivity, dual norms, and Talagrand’s contraction lemma.The cited proof steps connect the complexity of deeper classes to those of earlier classes.
- Complexity analysis: The analysis handles convex-hull and reflected hypothesis classes by relating their complexities and adjusting the relevant norm bounds.The proof combines these observations with the preceding lemma.
C. Alternative Algorithm
ADANET.CVX constructs candidate subnetworks for each existing layer plus one extension option, selecting the descent direction in closed form through Banach space duality. This yields efficient updates, but within a more restrictive search space than ADANET.
- Candidate construction: ADANET.CVX considers lt−1 + 1 candidate subnetworks: one for each existing layer and one for extending the model.Each candidate adds a single unit connected to the preceding layer.
- Candidate construction: The candidate subnetwork is selected from a restricted space H′ of subnetworks associated with the model’s layers.The algorithm compares candidates across layers and includes an additional extension candidate.
- Closed-form optimization: Banach space duality yields the optimal candidate subnetwork in closed form for the otherwise infinite-dimensional optimization problem.The construction uses connection weights that attain the Hölder-based upper bound.
- Closed-form optimization: For each layer s, the algorithm computes Λs,s−1∥ϵt,hs−1,t−1∥q and selects the descent coordinate producing the largest objective improvement.It then solves for the optimal step size in that direction to update the model weight.
- Algorithmic trade-off: ADANET.CVX designs the optimal candidate subnetwork within its searched space in closed form, enabling an extremely efficient update.The efficiency comes with a more restrictive search space than ADANET; its procedure is summarized in Figure 5.