Research map / Optimization / Nonconvex and smooth optimization
Active Learning of Deep Neural Networks via Gradient-Free Cutting Planes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a gradient-free cutting-plane method that trains ReLU networks of arbitrary depth by reformulating training as a linear program over activation patterns, and uses it for active learning with a center-of-gravity convergence guarantee.
Problem
Gradient-based neural network training is sensitive to hyperparameters and slow; prior cutting-plane active learning was limited to linear binary classifiers requiring linear separability. The paper seeks a gradient-free, convergent training and active learning scheme for deep ReLU networks.
Approach
Reframe ReLU network training for binary classification as a linear program over enumerated activation patterns, so cutting-plane centers (analytic center) and cuts can be applied per queried data point, yielding a volume-shrinkage convergence guarantee for active learning.
Key results
- On the synthetic spiral task with a 20-query budget, cutting-plane AL reached perfect train and test accuracy, outperforming all deep AL baselines; 3-layer version reached 0.71/0.60 train/test accuracy with 57 and 34 neurons per layer.
- On quadratic regression, the method achieved train/test RMSE of 0.01/0.01, reducing errors by over 80%/75% versus the next best baseline.
- The center-of-gravity cut guarantees volume shrinkage to less than (1-1/e) of the previous volume per cut, giving the first convergence guarantee for deep active learning as claimed by the authors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use cutting-plane active learning with a two-layer ReLU model instead of the strongest baseline | Quadratic regression · Quadratic regression | RMSE: 0.01/0.01; reducing errors by over 80%/75% compared to the next best baseline | Helped |
| Use cutting-plane active learning instead of deep active learning baselines | Two-layer ReLU · Synthetic spiral train and test | accuracy | Helped |
| Use a three-layer ReLU network instead of the two-layer version | Cutting-plane AL · Synthetic spiral train and test | accuracy: 0.71/0.60 | Mixed |
| Use a nonlinear two-layer ReLU model instead of a linear model | IMDB sentiment classification with Phi-2 embeddings · IMDB | accuracy | Helped |
| Use active sampling instead of random sampling | Two-layer ReLU classifier · IMDB | accuracy | Helped |
| Use cutting-plane training instead of SGD | Two-layer ReLU classifier · IMDB | accuracy | Helped |
| Use the linear cutting-plane AL method for nonlinear quadratic regression | Linear model · Quadratic regression | feasibility: 4 | Hurt |
Surprising findings
- The linear cutting-plane AL becomes infeasible after four queries on the quadratic regression task, as expected from linear model capacity.
Limitations
- Activation pattern subsampling is not exhaustive, hurting performance on high-dimensional data.
- Analytic center computation via CVXPY on CPU is inefficient for large-scale problems.
- Applied only to classification and regression, not LLM cross-entropy training.
Experimental setup
Datasets: synthetic two-spiral dataset synthetic quadratic regression data (y = x^2) IMDB movie reviews
Benchmarks: synthetic spiral classification quadratic regression IMDB sentiment classification
Metrics: accuracy RMSE
Baselines: scikit-activeml deep AL baselines DeepAL baselines linear cutting-plane AL random sampling SGD
Builds on: cutting-plane active learning with linear models convex reformulation of two-layer ReLU networks Grünbaum's inequality
Closest papers by meaning
- Low-Budget Active Learning via Wasserstein Distance: An Integer Programming Approach (ICLR 2022 · similarity 0.86)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.84)
- Transductive Active Learning: Theory and Applications (NeurIPS 2024 · similarity 0.84)
- Neural Active Learning Beyond Bandits (ICLR 2024 · similarity 0.84)
- Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes (NeurIPS 2024 · similarity 0.83)
- Sharper Guarantees for Learning Neural Network Classifiers with Gradient Methods (ICLR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.