Research map / Learning theory and algorithms / Sample complexity
Second-Order Complexity Theory for Neural Networks
Yoshihiro Maruyama
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's abstract only. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies neural-network training primitives as represented-real operators within Kawamura and Cook's second-order complexity framework to formalize continuous-data complexity of gradient-based training.
Problem
Gradient-based neural network training is usually analyzed via finite-dimensional arithmetic operation counts, not formal complexity over continuous real-valued data.
Approach
Recasts neural-network training primitives as represented-real operators in the second-order complexity framework of Kawamura and Cook, defining second-order polynomial time for computing real-valued operators on represented reals.
Experimental setup
Builds on: Kawamura and Cook second-order complexity
Closest papers by meaning
- Second-Order Complexity of Neural ODE Inference (NeurIPS 2026 · similarity 0.87)
- On the Parameterization of Second-Order Optimization Effective towards the Infinite Width (ICLR 2024 · similarity 0.87)
- On the Hardness of Training Deep Neural Networks Discretely (AAAI 2025 · similarity 0.86)
- Exact, Tractable Gauss-Newton Optimization in Deep Reversible Architectures Reveal Poor Generalization (NeurIPS 2024 · similarity 0.85)
- Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function (NeurIPS 2025 · similarity 0.85)
- Towards Learning High-Precision Least Squares Algorithms with Sequence Models (ICLR 2025 · similarity 0.85)
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.
