Research map / Optimization / Optimizers
Newton Losses: Using Curvature Information for Learning with Differentiable Algorithms
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 Newton Losses, which replace a hard-to-optimize algorithmic loss with a locally convex quadratic Newton-step loss (via Hessian or empirical Fisher curvature) while training the network with plain gradient descent, and evaluates on MNIST multi-digit sorting and Warcraft shortest-path benchmarks.
Problem
Training neural networks with non-convex, non-differentiable-turned-relaxed algorithmic losses (ranking, shortest-path) suffers from vanishing/exploding gradients, making the loss itself the optimization bottleneck.
Approach
Apply a Newton step on the loss w.r.t. its outputs (using the Hessian or empirical Fisher as curvature, with Tikhonov regularization) and convert it into a convex quadratic surrogate loss whose gradient equals that Newton step, so the network itself is still trained with first-order gradient descent.
Key results
- On n=10 MNIST sorting, NeuralSort full-ranking accuracy rises from 24.26% baseline to 84.83% with Hessian Newton Loss.
- Logistic DSN on n=10 improves from 12.31% to 75.35% (Hessian) full-ranking accuracy.
- Perturbed optimizers with Fenchel-Young loss on Warcraft improve perfect-match accuracy by more than 2% with the Hessian variant (e.g., 80.64% to 83.09% at 3 samples).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply Hessian-based Newton Loss to NeuralSort | NeuralSort · MNIST sorting n=5 | ranking accuracy: 71.33 -> 83.31 | Helped |
| Apply empirical Fisher-based Newton Loss to NeuralSort | NeuralSort · MNIST sorting n=10 | ranking accuracy: 24.26 -> 39.23 | Helped |
| Apply Hessian-based Newton Loss to SoftSort | SoftSort · MNIST sorting n=10 | ranking accuracy: 27.46 -> 55.07 | Helped |
| Apply empirical Fisher-based Newton Loss to SoftSort | SoftSort · MNIST sorting n=5 | ranking accuracy: 70.70 -> 84.03 | Helped |
| Apply Hessian-based Newton Loss to Logistic DSN | Logistic DSN · MNIST sorting n=10 | ranking accuracy: 12.31 -> 42.14 | Helped |
| Apply empirical Fisher-based Newton Loss to Logistic DSN | Logistic DSN · MNIST sorting n=10 | ranking accuracy: 12.31 -> 25.72 | Mixed |
| Apply Hessian-based Newton Loss to Cauchy DSN | Cauchy DSN · MNIST sorting n=10 | ranking accuracy: 55.29 -> 56.49 | Helped |
| Apply empirical Fisher-based Newton Loss to Cauchy DSN | Cauchy DSN · MNIST sorting n=5 | ranking accuracy: 85.09 -> 84.95 | Hurt |
| Apply Hessian-based Newton Loss to stochastic smoothing of the loss with 3 samples | Stochastic smoothing of loss · Warcraft shortest-path, 3 samples | perfect matches: 62.83 -> 62.40 | Hurt |
| Apply Newton Loss with 10 samples to stochastic smoothing of the loss | Stochastic smoothing of loss · Warcraft shortest-path, 10 samples | perfect matches: 77.01 -> 78.82; 77.01 -> 78.74 | Helped |
| Apply Hessian-based Newton Loss to perturbed optimizers with Fenchel-Young loss | Perturbed optimizer · Warcraft shortest-path, 3 samples | perfect matches: 80.64 -> 83.09 | Helped |
| Apply empirical Fisher-based Newton Loss to perturbed optimizers with Fenchel-Young loss | Perturbed optimizer · Warcraft shortest-path, 3 samples | perfect matches: 80.64 -> 80.70 | No clear effect |
Surprising findings
- The empirical Fisher variant gives no meaningful gain for Fenchel-Young perturbed optimizers, since the loss is defined via its derivative.
- Newton Losses applied to an MSE loss collapse to the original MSE loss, so non-trivial losses are required.
Limitations
- Hessian variant is expensive or unavailable for some differentiable algorithms (e.g., AlgoVision Bellman-Ford, SS of algorithm), forcing the weaker Fisher variant.
- Gains are small for already well-optimized losses such as Cauchy DSN and AlgoVision.
- Requires tuning the Tikhonov regularization strength lambda, which depends on loss gradient magnitude.
Experimental setup
Datasets: Multi-digit MNIST sorting benchmark Warcraft shortest-path benchmark
Benchmarks: Multi-digit MNIST sorting (n=5, 10, 15) Warcraft 12x12 shortest-path
Metrics: percentage of rankings correctly identified element-wise rank accuracy percentage of perfect shortest-path matches
Baselines: NeuralSort SoftSort Logistic DSN Cauchy DSN Relaxed Bellman-Ford (AlgoVision) Stochastic smoothing Perturbed optimizers with Fenchel-Young loss
Builds on: NeuralSort SoftSort Differentiable Sorting Networks Perturbed Optimizers with Fenchel-Young losses AlgoVision
Closest papers by meaning
- Global curvature for second-order optimization of neural networks (ICML 2025 · similarity 0.87)
- Are All Losses Created Equal: A Neural Collapse Perspective (NeurIPS 2022 · similarity 0.87)
- Fast Convergence of Natural Gradient Descent for Over-Parameterized Neural Networks (NeurIPS 2019 · similarity 0.86)
- Deeper or Wider: A Perspective from Optimal Generalization Error with Sobolev Loss (ICML 2024 · similarity 0.86)
- On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Features (ICML 2022 · similarity 0.86)
- Large Stepsize Gradient Descent for Non-Homogeneous Two-Layer Networks: Margin Improvement and Fast Optimization (NeurIPS 2024 · 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.