Home / Curated / Algorithms / AdGD (Adaptive Gradient Descent without Descent)

AdGD (Adaptive Gradient Descent without Descent)

Algorithms AIMech:AdGDAdaptiveGradientDescentWithoutDescent DRAFT

Aliases: AdGD Optimizer, Adaptive Gradient Descent without Line Search, Malitsky-Mishchenko Adaptive Gradient Descent

A line-search-free, function-value-free adaptive gradient descent algorithm (Algorithm 1) that updates iterates via x^{k+1} = x^k - lambda_k nabla f(x^k) using a step size governed by two rules — bounded growth lambda_k <= sqrt(1 + theta_{k-1}) lambda_{k-1} (or sqrt(1 + theta_{k-1}/2) lambda_{k-1}) where theta_k = lambda_k / lambda_{k-1}, and inverse local curvature bounding lambda_k <= ||x^k - x^{k-1}|| / (2 ||nabla f(x^k) - nabla f(x^{k-1})||) — guaranteeing global convergence on any convex function with locally Lipschitz gradients without enforcing monotonic decrease of f(x^k).

Identity Notes & Concept Scope Distinct from backtracking line search (Armijo/Goldstein) in that AdGD never evaluates f(x) or backtracks with extra gradient evaluations per step. Distinct from Polyak's step size in that it requires no knowledge or estimate of f_*. Distinct from the Barzilai-Borwein method in that AdGD caps step-size growth by sqrt(1 + theta_{k-1}) lambda_{k-1} and uses the l2 ratio ||x^k - x^{k-1}|| / (2 ||nabla f(x^k) - nabla f(x^{k-1})||), providing provable convergence for arbitrary locally smooth convex functions where Barzilai-Borwein can diverge.

Claims & Grounded Evidence

4 Claims

Mechanism #c-r595-two-step-lyapunov-without-descent-and-local-lipschitz-rate

Without requiring global smoothness L < infinity or monotonic objective descent f(x^{k+1}) <= f(x^k), AdGD (Algorithm 1) decreases the two-step Lyapunov energy ||x^{k+1} - x^*||^2 + (1/2)||x^{k+1} - x^k||^2 + 2 lambda_k (1 + theta_k)(f(x^k) - f_*) at every iteration (Lemma 1, Eq. 5), ensuring bounded iterates, convergence x^k -> x^*, and an ergodic rate f(x_hat^k) - f_* <= D / (2 S_k) = O(1/k) depending only on the local Lipschitz constant L over conv{x^*, x^0, x^1, ...} (Theorem 1).

supports Source: Adaptive Gradient Descent without Descent · Locator: Section 2.2, Lemma 1, Eq. (5) & Theorem 1, Eq. (11), pp. 4-6; Appendix Section 6, pp. 15-16

Mechanism #c-r595-locally-strongly-convex-linear-rate-and-extensions

When f is locally strongly convex and locally smooth on conv{x^*, x^0, x^1, ...} with local condition number kappa = L / mu, replacing sqrt(1 + theta_{k-1}) by sqrt(1 + theta_{k-1}/2) yields linear energy contraction Psi^{k+1} <= (1 - 1/(4 kappa)) Psi^k and O(kappa log(1/epsilon)) iteration complexity (Theorem 2, Eq. 16), while dual-space curvature estimation Lambda_k = min{sqrt(1 + Theta_{k-1}/2) Lambda_{k-1}, ||nabla f(x^k) - nabla f(x^{k-1})|| / (2 ||x^k - x^{k-1}||)} yields the Nesterov-accelerated heuristic AdGD-accel (Algorithm 2).

supports Source: Adaptive Gradient Descent without Descent · Locator: Section 2.3, Theorem 2 & Algorithm 2, pp. 7-8; Appendix Section 6, Eq. (16), p. 16

Application #c-r595-stochastic-adsgd-and-empirical-performance

In the stochastic setting (Algorithm 3, AdSGD), estimating L_k = ||nabla f_{xi^k}(x^k) - nabla f_{xi^k}(x^{k-1})|| / ||x^k - x^{k-1}|| achieves O((kappa^2 / epsilon) log(kappa / epsilon)) complexity with an independent curvature sample and O(kappa^2 log(1/epsilon)) on overparameterized models (Theorem 3, Theorems 6-7), outperforming GD, Nesterov AGD, Armijo line search, and Barzilai-Borwein on logistic regression, cubic regularization, and matrix factorization, and exceeding tuned SGD test accuracy on CIFAR-10 ResNet-18 and DenseNet-121.

supports Source: Adaptive Gradient Descent without Descent · Locator: Section 3.2, Theorem 3 & Algorithm 3, pp. 8-9; Section 4, Figures 1-6, pp. 9-12; Appendix Section 8, Theorems 6-7, pp. 20-22

Limitation #c-r595-nonconvex-composite-and-kappa2-stochastic-limitations

AdGD's two-step Lyapunov proof does not directly extend to general nonconvex objectives or proximal composite minimization, and its stochastic complexity bound incurs an extra factor of kappa (O(kappa^2) vs O(kappa)), while neural network training exhibits noisy early-stage progress during the first 75 epochs and plummeting step sizes once training loss becomes small.

supports Source: Adaptive Gradient Descent without Descent · Locator: Section 3.2, p. 9; Section 4-5, Perspectives 1, 3, & 4, pp. 11-12

⚠️ Curated Limitations & Negative Results

Theoretical convergence guarantees rely on convexity and do not directly extend to general nonconvex objectives or proximal composite splitting (Section 5, Perspectives 1 & 3).
The accelerated heuristic AdGD-accel (Algorithm 2) lacks a formal convergence proof, and stochastic AdSGD (Theorem 3) incurs an extra condition-number factor kappa in its worst-case complexity bound.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:ArtificialNeuralNetwork` Artificial Neural Network	related_match	AdGD and its stochastic variant AdSGD (Algorithm 3) are parameter-free local-curvature-adaptive gradient methods applied to convex optimization, matrix factorization, and deep neural network training.

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r595-primary-pdf`	Adaptive Gradient Descent without Descent Yura Malitsky, Konstantin Mishchenko	primary paper full_text	ID: https://dblp.org/rec/conf/icml/MalitskyM20 sha256:d55bd236a501…
`r595-arxiv-abs`	Adaptive Gradient Descent without Descent (arXiv abstract) Yura Malitsky, Konstantin Mishchenko	primary paper abstract_only	ID: https://arxiv.org/abs/1910.09529 sha256:a73d27bdcf04…
`r595-metadata-cr`	Adaptive Gradient Descent without Descent (Crossref metadata) Yura Malitsky, Konstantin Mishchenko	primary paper abstract_only	ID: https://dblp.org/rec/conf/icml/MalitskyM20 sha256:c029d8f2c5bf…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T11:18:00Z

Updated: 2026-10-19T11:18:00Z

Source File: data/curated/AdGDAdaptiveGradientDescentWithoutDescent.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