Parabolic Approximation Line Search
Algorithms AIMech:ParabolicApproximationLineSearch DRAFT
Aliases: PAL, PAL Optimizer, Parabolic Approximation Line Search for DNNs
A stochastic line-search optimization algorithm for deep neural networks that at each step t defines a one-dimensional loss cross-section l_t(s) = L(x_t; theta_t + s d_t / ||d_t||_2) along a unit-normalized search direction d_t / ||d_t||_2 (where d_t = -grad_{theta_t} L(x_t; theta_t) + beta d_{t-1} with beta in [0, 1]), evaluates the current mini-batch loss l_t(0), directional derivative b = l'_t(0) = grad_{theta_t} L(x_t; theta_t)^T d_t / ||d_t||_2, and one additional forward pass l_t(mu) at measuring step distance mu > 0 on the same mini-batch (reusing any stochastic dropout masks), fits the exact interpolating 1D parabola l_hat_t(s) = a s^2 + b s + c with a = (l_t(mu) - l_t(0) - b mu) / mu^2 and c = l_t(0), and updates parameters by theta_{t+1} = theta_t + min(alpha s_upd, s_max) d_t / ||d_t||_2 where s_upd = -b / (2a) when a > 0 and b < 0, s_upd = mu when a <= 0 and b < 0, and s_upd = 0 otherwise.
Identity Notes & Concept Scope
Distinct from backtracking Armijo Stochastic Line Search (SLS, which requires the interpolation condition and checks sufficient decrease via variable numbers of forward passes), from linear loss-approximation step-size schemes (L4, ALIG), and from Gaussian-process Probabilistic Line Search (PLS): PAL uses a deterministic 2-forward-pass, 1-backward-pass 1D parabolic fit along unit-normalized negative-gradient or conjugate-like directions.
Claims & Grounded Evidence
4 Claims
Mechanism
#c-r624-parabolic-vertex-update-and-quadratic-exactness
Given l_t(0), b = l'_t(0) = grad L(x_t; theta_t)^T d_t / ||d_t||_2, and l_t(mu) at measuring distance mu > 0 along unit direction u_t = d_t / ||d_t||_2, the quadratic coefficient a = (l_t(mu) - l_t(0) - b mu) / mu^2 satisfies 2a = l_hat''_t(0), which equals the exact directional curvature u_t^T H u_t whenever L is quadratic, and for a > 0, b < 0 the vertex update s_upd = -b / (2a) = -l'_t(0) mu^2 / (2 (l_t(mu) - l_t(0) - l'_t(0) mu)) places theta_{t+1} at the exact 1D minimum where the new gradient is orthogonal (90 degrees) to u_t.
Mechanism
#c-r624-case-discrimination-and-conjugate-direction-adaptation
To handle non-convex cross-sections and ill-conditioned curvature, PAL discriminates three curvature regimes — Case 1 (a > 0, b < 0: parabolic minimum s_upd = -b / (2a)), Case 2 (a <= 0, b < 0: concave or negatively sloped cross-section where l_t(mu) < l_t(0), setting s_upd = mu), and Case 3 (b = 0: stationary point s_upd = 0) — while combining conjugate-like momentum direction adaptation d_t = -grad L(x_t; theta_t) + beta d_{t-1} (Eq. 3-4), step scaling alpha >= 1, and step capping s_max.
Application
#c-r624-inexact-batch-line-search-and-non-interpolating-robustness
Empirical evaluation across over 4,500 trained networks on CIFAR-10/100 (DenseNet-40, EfficientNet-B0, ResNet-32, MobileNetV2), ImageNet (DenseNet-121, ResNet-50), and non-interpolating kernel/factorization benchmarks shows that PAL outperforms SLS, ALIG, SGD-HD, and COCOB without hand-tuned learning-rate schedules, and that slightly narrow inexact parabolic steps outperform 20-evaluation exact binary line search on mini-batch losses because the mini-batch line minimum overshoots the full empirical loss minimum.
Limitation
#c-r624-second-forward-pass-and-random-state-reuse-limitation
PAL requires two forward passes and one backward pass per parameter update step (evaluating both l_t(0) and l_t(mu)), increasing per-step wall-clock time relative to standard first-order optimizers, and requires reusing identical random number generator states (such as dropout masks) across both forward passes to preserve continuity of l_t(s).
⚠️ Curated Limitations & Negative Results
- Incurs the computational cost of a second forward pass per iteration to evaluate l_t(mu) at measuring step distance mu.
- Stochastic layers such as Dropout must reuse the exact same random draws during both forward evaluations l_t(0) and l_t(mu) within a step, otherwise stochastic noise corrupts the finite-difference curvature estimate a = (l_t(mu) - l_t(0) - b mu) / mu^2.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ArtificialNeuralNetwork
Artificial Neural Network
|
related_match | PAL is a line-search optimization algorithm specifically designed for automatic step-size selection in deep neural networks. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
r624-primary-pdf
|
Maximus Mutschler, Andreas Zell
|
primary paper
full_text
|
ID: https://dblp.org/rec/conf/nips/MutschlerZ20
sha256:d022f6c34a8b…
|
r624-arxiv-abs
|
Maximus Mutschler, Andreas Zell
|
primary paper
abstract_only
|
ID: https://proceedings.neurips.cc/paper/2020/hash/3a30be93eb45566a90f4e95ee72a089a-Abstract.html
sha256:05a3d3f4bb32…
|
r624-metadata-cr
|
Maximus Mutschler, Andreas Zell
|
primary paper
abstract_only
|
ID: https://dblp.org/rec/conf/nips/MutschlerZ20
sha256:51894c8be41f…
|
Ontology & Grounding Topology
Open in interactive network graph →Curation Provenance
Curator: Antigravity
Method: ai_assisted
Model: Gemini
Created: 2026-10-19T11:47:00Z
Updated: 2026-10-19T11:47:00Z
Source File:
data/curated/ParabolicApproximationLineSearch.yaml
· Schema:
curated_concept.yaml
Explore across X-Mech
Related computational & biological Mechs:
Embedding Map
Network Graph
ProteinTraitsMech (ESM-2 pLM)
DUFMech (Domain pLM)
TraitMech
CultureMech
All 14 X-Mech Repositories