AdaGrad / RMSProp / Adam

Why AdaGrad / RMSProp / Adam Matters

A parameter vector can contain coordinates with very different gradient magnitudes and frequencies. A learning rate that works for one coordinate may move another too aggressively. AdaGrad, RMSProp, and Adam use a separate history-dependent denominator for each coordinate, rather than applying the same scalar multiplier to every gradient component.

The three methods remember different information. AdaGrad keeps all squared gradients accumulated so far. RMSProp replaces that unbounded sum with an exponential moving average. Adam combines a moving average of signed gradients with a moving average of squared gradients and corrects both for zero initialization.

These methods appear in numerical model fitting and machine learning, particularly when gradient scales or feature frequencies differ. Adaptation does not eliminate the learning rate, guarantee decreasing loss, or establish that the returned parameters are optimal. This lesson defines one exact convention for each method, follows all three on the same quadratic, and implements them in Python, C++, and Java. Full gradients keep the example deterministic; a mini-batch gradient can occupy the same update interface in a larger system.

Core Concepts and Terminology

Let $f:\mathbb R^d\to\mathbb R$ be a differentiable objective. Use a one-based update index $t=1,2,\ldots$: the incoming gradient is $\mathbf g_t=\nabla f(\mathbf x_{t-1})$, and the update produces $\mathbf x_t$. All vector squares, roots, divisions, and products in the optimizer formulas are coordinatewise.

Write $\eta\gt0$ for the base learning rate and $\epsilon\gt0$ for the additive denominator constant. We choose $\sqrt{s}+\epsilon$ throughout, with epsilon outside the square root. Other conventions exist; $\sqrt{s+\epsilon}$ is a different normalization.

AdaGrad. Initialize $\mathbf s_0=\mathbf0$, accumulate every squared gradient, and update using the new accumulator:

$$s_{t,j}=s_{t-1,j}+g_{t,j}^2,\qquad x_{t,j}=x_{t-1,j}-\eta\frac{g_{t,j}}{\sqrt{s_{t,j}}+\epsilon}.$$

The coefficient $\eta/(\sqrt{s_{t,j}}+\epsilon)$ cannot increase as $t$ grows in exact arithmetic. Coordinates with large accumulated squared gradients receive smaller multipliers. A rarely active coordinate can retain a relatively larger multiplier. This is the diagonal cumulative variant motivated by Duchi, Hazan, and Singer's AdaGrad paper.

Uncentered RMSProp without momentum or bias correction. Choose $0\leq\rho\lt1$ and initialize $\mathbf s_0=\mathbf0$:

$$s_{t,j}=\rho s_{t-1,j}+(1-\rho)g_{t,j}^2,\qquad x_{t,j}=x_{t-1,j}-\eta\frac{g_{t,j}}{\sqrt{s_{t,j}}+\epsilon}.$$

The reference programs use the input named beta2 for $\rho$. Old contributions decay, so the denominator can shrink as well as grow. This is a moving second moment, not a sum and not a centered variance. The original RMSProp lecture, slide 29 describes its squared-gradient moving average.

Adam. Initialize $\mathbf m_0=\mathbf s_0=\mathbf0$ and choose $0\leq\beta_1,\beta_2\lt1$:

$$m_{t,j}=\beta_1m_{t-1,j}+(1-\beta_1)g_{t,j},\qquad s_{t,j}=\beta_2s_{t-1,j}+(1-\beta_2)g_{t,j}^2.$$

Correct the zero-initialized moments before forming the update:

$$\widehat m_{t,j}=\frac{m_{t,j}}{1-\beta_1^t},\qquad \widehat s_{t,j}=\frac{s_{t,j}}{1-\beta_2^t},$$ $$x_{t,j}=x_{t-1,j}-\eta\frac{\widehat m_{t,j}}{\sqrt{\widehat s_{t,j}}+\epsilon}.$$

This is the explicit corrected-moment form of Kingma and Ba's Adam, Algorithm 1. The first moment retains direction; the second moment estimates squared magnitude. It is not a Hessian estimate. If gradient means and second moments are constant over time, division by the factors $1-\beta_1^t$ and $1-\beta_2^t$ removes the expectation bias caused by zero initialization. It does not make the ratio an unbiased gradient estimator, and it does not guarantee stationarity or convergence.

For a shared vocabulary, let $n_{t,j}$ denote the update numerator and $u_{t,j}$ the second statistic actually used: $(n,u)=(g,s)$ for AdaGrad and RMSProp, and $(n,u)=(\widehat m,\widehat s)$ for Adam. Define

$$D_{t,j}=\sqrt{u_{t,j}}+\epsilon,\qquad \delta_{t,j}=\eta\frac{n_{t,j}}{D_{t,j}},\qquad x_{t,j}=x_{t-1,j}-\delta_{t,j}.$$

The signed correction $\boldsymbol\delta_t$ is subtracted from the old point. Adam's numerator can retain a previous direction after the current gradient changes sign.

The teaching objective is $f(\mathbf x)=\tfrac12\sum_{j=1}^d a_j(x_j-c_j)^2$, with nonnegative curvatures $a_j$ and gradient $g_j=a_j(x_j-c_j)$. If all curvatures are positive, its unique minimizer is $\mathbf c$; zero-curvature coordinates are flat. The worked scalar case uses $a=1$, $c=0$, so $f(x)=x^2/2$ and $g=x$.

How AdaGrad / RMSProp / Adam Works, Step by Step

Inputs are the initial point, center and curvature vectors, base rate, two moment coefficients, epsilon, number of updates $K$, and one mode: ADAGRAD, RMSPROP, or ADAM. AdaGrad ignores both coefficients after validating them; RMSProp uses beta2 as $\rho$ and ignores beta1; Adam uses both.

1. Validate and initialize. Check shapes, finite values, ranges, integer update count, and mode. Copy inputs. Set the two raw moment vectors to zero and the two stored powers to $1$.
2. Record the starting loss. Evaluate $f(\mathbf x_0)$ once. The initial row has empty gradient, numerator, normalized-second-statistic, denominator, and correction fields because no update has occurred.
3. Check the cap. Return after exactly $K$ completed updates. A zero-update call still returns the initial point and its loss, with zero gradient evaluations.
4. Evaluate one gradient at the old point. Compute all coordinates before changing parameters. All three algorithms in this lesson use $\mathbf x_{t-1}$; there is no look-ahead probe.
5. Update raw history. AdaGrad adds $\mathbf g_t^2$ to the cumulative accumulator. RMSProp and Adam decay the old second moment and add the weighted new square. Adam also updates the raw signed first moment.
6. Advance Adam's powers and correct. On the first Adam update the powers become $\beta_1$ and $\beta_2$, not $1$. Form both corrected moments using $1-\beta_i^t$. The programs maintain powers by repeated multiplication in the same order in every language. Non-Adam modes keep dummy powers at $1$ and never use them in a bias division.
7. Normalize and construct a candidate. Use the newly updated statistics. For each coordinate, take the square root of the selected nonnegative second statistic, add epsilon, divide the numerator, multiply that quotient by the learning rate, then subtract the signed correction from the old parameter.
8. Commit, monitor, and record. Replace the whole parameter vector together, evaluate the new loss, and append copies of the state. The loss monitor does not accept, reject, or alter updates.

A row numbered $t\geq1$ records the committed $\mathbf x_t$ and its loss, together with the incoming $\mathbf g_t$ evaluated at $\mathbf x_{t-1}$. It also records raw first and second moments, numerator, the second statistic actually used, denominator, correction, and Adam's powers. The gradient field is not the residual at the new point.

There is no early exit on a zero gradient, a numerical no-op, or an increased objective. Adam can move with a zero current gradient because its first moment can remain nonzero. A production stopping test needs a stated residual and state policy; one zero sampled gradient is particularly weak evidence in stochastic training.

flowchart TD
    A["Validate mode, shapes, numbers, and controls"] --> B["Copy parameters; zero moments; powers = 1; record starting loss"]
    B --> C{"Completed K updates?"}
    C -->|Yes| Z["Return final state, counters, and history"]
    C -->|No| D["Evaluate one gradient at old parameters"]
    D --> E{"AdaGrad?"}
    E -->|Yes| F["Add squared gradient to accumulator"]
    E -->|No| G["Exponential-average the squared gradient"]
    F --> H{"Adam?"}
    G --> H
    H -->|Yes| I["Update signed first moment and powers; correct both moments"]
    H -->|No| J["Numerator = current gradient; use raw second statistic"]
    I --> L["Denominator = square root of second statistic plus epsilon"]
    J --> L
    L --> M["Divide numerator, multiply rate, subtract from old parameters"]
    M --> N["Commit candidate; evaluate loss; copy state; count update"]
    N --> C

Worked Example with a Full Trace

Use $f(x)=x^2/2$, $g=x$, start $x_0=2$, base rate $\eta=1$, epsilon $\epsilon=1$, $\beta_1=1/2$, $\beta_2=\rho=3/4$, and $K=3$. All raw moments start at zero. These deliberately simple coefficients and large teaching epsilon make the arithmetic visible; they are not recommended training settings. No random seed is needed because the gradients and starting point are deterministic.

Initially $f(2)=2$. Below, $s$ is the raw second statistic, $n$ the chosen numerator, $u$ the second statistic used for normalization, $D=\sqrt u+1$, and $\delta=n/D$ because $\eta=1$. The approximate values are rounded to ten decimal places. Exact fractions describe the real-arithmetic formulas; the programs apply the stated binary64 operation order and can differ in the last bits from exact fractions. Do not round the state between updates.

AdaGrad: keep the entire squared-gradient sum.

1. Gradient $g_1=2$. Accumulator $s_1=0+2^2=4$. Thus $n_1=2$, $u_1=4$, $D_1=3$, $\delta_1=2/3$, $x_1=2-2/3=4/3$, and $f(x_1)=8/9$.
2. Gradient $g_2=4/3$. Accumulator $s_2=4+16/9=52/9\approx5.7777777778$. Thus $n_2=4/3$, $u_2=s_2$, $D_2=1+2\sqrt{13}/3\approx3.4037008503$, and $\delta_2=4/(3+2\sqrt{13})\approx0.3917304699$. Therefore $x_2\approx0.9416028635$ and $f(x_2)\approx0.4433079763$.
3. Gradient $g_3\approx0.9416028635$. Its square is approximately $0.8866159525$, so $s_3=s_2+g_3^2\approx6.6643937303$. With $n_3=g_3$ and $u_3=s_3$, the denominator is $D_3\approx3.5815487077$, the correction is $\delta_3\approx0.2629038275$, the new parameter is $x_3\approx0.6786990360$, and the loss is approximately $0.2303161907$.

AdaGrad keeps a dummy first moment of zero. It has no bias correction here.

RMSProp: decay the old square history.

1. Gradient $g_1=2$. Second moment $s_1=(3/4)0+(1/4)4=1$. Thus $n_1=2$, $u_1=1$, $D_1=2$, $\delta_1=1$, $x_1=1$, and $f(x_1)=1/2$.
2. Gradient $g_2=1$. Second moment $s_2=(3/4)1+(1/4)1=1$. Thus $n_2=1$, $u_2=1$, $D_2=2$, $\delta_2=1/2$, $x_2=1/2$, and $f(x_2)=1/8$.
3. Gradient $g_3=1/2$. Its square is $1/4$, so $s_3=3/4+1/16=13/16=0.8125$. Thus $n_3=1/2$, $u_3=13/16$, $D_3=1+\sqrt{13}/4\approx1.9013878189$, and $\delta_3=2/(4+\sqrt{13})\approx0.2629658164$. The new parameter is $x_3\approx0.2370341836$, and the loss is approximately $0.0280926021$.

This uncentered RMSProp variant also keeps a dummy first moment of zero and applies no startup bias correction. Its second moment decreases on the third update.

Adam: combine and correct both moments.

1. Gradient $g_1=2$. Raw moments $m_1=(1/2)2=1$ and $s_1=(1/4)4=1$. Powers are $p_1=1/2$, $p_2=3/4$. Hence $n_1=\widehat m_1=1/(1/2)=2$ and $u_1=\widehat s_1=1/(1/4)=4$. Thus $D_1=3$, $\delta_1=2/3$, $x_1=4/3$, and $f(x_1)=8/9$.
2. Gradient $g_2=4/3$. Raw moments are $m_2=(1/2)1+(1/2)(4/3)=7/6$ and $s_2=(3/4)1+(1/4)(16/9)=43/36$. Powers are $p_1=1/4$ and $p_2=9/16$. Thus $n_2=(7/6)/(3/4)=14/9\approx1.5555555556$ and $u_2=(43/36)/(7/16)=172/63\approx2.7301587302$. The denominator is $D_2\approx2.6523191974$, the correction is $\delta_2\approx0.5864888197$, the new parameter is $x_2\approx0.7468445136$, and its loss is approximately $0.2788883638$.
3. Gradient $g_3\approx0.7468445136$, with square approximately $0.5577767275$. Raw moments are $m_3=(1/2)m_2+(1/2)g_3\approx0.9567555902$ and $s_3=(3/4)s_2+(1/4)g_3^2\approx1.0352775152$. Powers are $p_1=1/8$ and $p_2=27/64$. Correcting gives $n_3=m_3/(7/8)\approx1.0934349602$ and $u_3=s_3/(37/64)\approx1.7907502966$. Therefore $D_3\approx2.3381891857$, $\delta_3\approx0.4676417832$, $x_3\approx0.2792027305$, and $f(x_3)\approx0.0389770823$.

Each run uses exactly three full-gradient evaluations and four scalar objective evaluations. RMSProp has the smallest final loss for these particular inputs. AdaGrad and Adam agree on step $1$ because Adam's corrected first-step moments are $g_1$ and $g_1^2$; their different history rules separate them afterwards. The finite comparison establishes neither a general ranking nor convergence.

Implementation in Python, C++, and Java

Each panel is complete and independently runnable. The shared callable is adaptive(initial, center, weights, rate, beta1, beta2, epsilon, steps, mode). It returns the last point, raw moments, powers, objective, counters, and snapshots. The history field second_used stores $u_t$; it is an uncentered second statistic, not a centered variance. For AdaGrad and RMSProp, first remains zero and both dummy powers remain one; those modes never divide by the dummy bias factors.

The teaching API accepts $1\leq d\leq32$, an integer $0\leq K\leq2000$, finite coordinates and centers of magnitude at most $10^4$, curvatures in $[0,10^4]$, $0\lt\eta\leq1000$, $0\leq\beta_1,\beta_2\lt1$, and $10^{-12}\leq\epsilon\leq1000$. These bounds keep the demonstration within a controlled numeric range; they are not a stability theorem or universal optimizer restrictions. The routine validates coefficients even in a mode that ignores them. Python rejects boolean numeric controls and requires an actual integer update count; C++ and Java express the count type in their signatures.

There is no general callback, mini-batch sampler, projection, weight decay, gradient clipping, schedule, momentum option for RMSProp, AMSGrad maximum, or stopping tolerance in these programs. The loop always runs the requested number of updates, including zero-gradient and numerical no-op updates. Changing the objective requires replacing both its value and gradient and revisiting numeric assumptions.

Run Python 3 with python main.py. Compile C++17 with g++ -std=c++17 -ffp-contract=off main.cpp -o adaptive and run ./adaptive; avoid fast-math so the stated arithmetic order is retained. Save Java as Main.java, use Java 17 or later, compile with javac Main.java, and run java Main. Java's decimal helper only formats stored binary64 values with eight decimal places and half-even rounding; the optimizer itself uses double arithmetic.

The three programs print the same parameter vector and objective at each iteration. Their sample is the full trace above. Counters count full gradient and scalar value calls, not individual coordinates. Initial history has no gradient because computing the starting objective does not request one. All returned snapshots own their arrays.

from dataclasses import dataclass
import math


@dataclass
class State:
    iteration: int
    point: list
    gradient: list
    first: list
    second: list
    numerator: list
    second_used: list
    denominator: list
    correction: list
    value: float
    power1: float
    power2: float


@dataclass
class Result:
    point: list
    first: list
    second: list
    value: float
    steps: int
    gradient_evaluations: int
    value_evaluations: int
    power1: float
    power2: float
    history: list


def objective(point, center, weights):
    total = 0.0
    for x, c, a in zip(point, center, weights):
        delta = x - c
        square = delta * delta
        term = a * square
        total = total + term
    return 0.5 * total


def adaptive(initial, center, weights, rate, beta1, beta2, epsilon, steps, mode):
    if type(steps) is not int or not 0 <= steps <= 2000:
        raise ValueError("steps must be an integer in [0,2000]")
    if mode not in ("ADAGRAD", "RMSPROP", "ADAM"):
        raise ValueError("invalid optimizer mode")

    def number(x):
        return type(x) is int or (type(x) is float and math.isfinite(x))

    d = len(initial)
    if not 1 <= d <= 32 or len(center) != d or len(weights) != d:
        raise ValueError("invalid vector sizes")
    if any(not number(x) or abs(x) > 10000 for row in [initial, center] for x in row):
        raise ValueError("invalid point or center")
    if any(not number(a) or not 0 <= a <= 10000 for a in weights):
        raise ValueError("invalid curvature")
    if not number(rate) or not 0 < rate <= 1000:
        raise ValueError("invalid learning rate")
    if any(not number(b) or not 0 <= b < 1 for b in [beta1, beta2]):
        raise ValueError("invalid moment coefficient")
    if not number(epsilon) or not 1e-12 <= epsilon <= 1000:
        raise ValueError("invalid epsilon")
    point, origin, diagonal = [list(map(float, row)) for row in [initial, center, weights]]
    rate, beta1, beta2, epsilon = map(float, [rate, beta1, beta2, epsilon])
    one1, one2 = 1.0 - beta1, 1.0 - beta2
    first, second = [0.0] * d, [0.0] * d
    power1, power2 = 1.0, 1.0
    value = objective(point, origin, diagonal)
    history = [State(0, point[:], [], first[:], second[:], [], [], [], [],
                     value, power1, power2)]
    for k in range(1, steps + 1):
        gradient = []
        for x, c, a in zip(point, origin, diagonal):
            delta = x - c
            gradient.append(a * delta)
        if mode == "ADAM":
            power1 = power1 * beta1
            power2 = power2 * beta2
        next_first, next_second = [], []
        for m, s, g in zip(first, second, gradient):
            square = g * g
            if mode == "ADAGRAD":
                next_second.append(s + square)
            else:
                retained = beta2 * s
                innovation = one2 * square
                next_second.append(retained + innovation)
            if mode == "ADAM":
                retained = beta1 * m
                innovation = one1 * g
                next_first.append(retained + innovation)
            else:
                next_first.append(0.0)
        first, second = next_first, next_second
        numerator, second_used, denominator, correction, candidate = [], [], [], [], []
        for x, m, s, g in zip(point, first, second, gradient):
            n = m / (1.0 - power1) if mode == "ADAM" else g
            v = s / (1.0 - power2) if mode == "ADAM" else s
            den = math.sqrt(v) + epsilon
            scaled = n / den
            step = rate * scaled
            numerator.append(n)
            second_used.append(v)
            denominator.append(den)
            correction.append(step)
            candidate.append(x - step)
        point = candidate
        value = objective(point, origin, diagonal)
        history.append(State(k, point[:], gradient[:], first[:], second[:],
                             numerator[:], second_used[:], denominator[:], correction[:],
                             value, power1, power2))
    return Result(point[:], first[:], second[:], value, steps, steps, steps + 1,
                  power1, power2, history)


def vector(xs):
    return "(" + ",".join(f"{x:.8f}" for x in xs) + ")"


def main():
    for mode in ("ADAGRAD", "RMSPROP", "ADAM"):
        result = adaptive([2], [0], [1], 1.0, 0.5, 0.75, 1.0, 3, mode)
        print(mode)
        for s in result.history:
            print(f"k={s.iteration} x={vector(s.point)} f={s.value:.8f}")
        print(f"steps={result.steps} gradients={result.gradient_evaluations} "
              f"losses={result.value_evaluations}")


if __name__ == "__main__":
    main()

#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace std;

struct State {
    int iteration;
    vector<double> point, gradient, first, second, numerator, second_used, denominator, correction;
    double value, power1, power2;
};
struct Result {
    vector<double> point, first, second;
    double value;
    int steps, gradient_evaluations, value_evaluations;
    double power1, power2;
    vector<State> history;
};

double objective(const vector<double>& point, const vector<double>& center,
                 const vector<double>& weights) {
    double total = 0.0;
    for (size_t j = 0; j < point.size(); ++j) {
        double delta = point[j] - center[j];
        double square = delta * delta;
        double term = weights[j] * square;
        total = total + term;
    }
    return 0.5 * total;
}

Result adaptive(const vector<double>& initial, const vector<double>& center,
                const vector<double>& weights, double rate, double beta1, double beta2,
                double epsilon, int steps, const string& mode) {
    if (steps < 0 || steps > 2000 ||
        (mode != "ADAGRAD" && mode != "RMSPROP" && mode != "ADAM"))
        throw invalid_argument("invalid steps or mode");
    size_t d = initial.size();
    if (d < 1 || d > 32 || center.size() != d || weights.size() != d)
        throw invalid_argument("invalid vector sizes");
    for (size_t j = 0; j < d; ++j) {
        if (!isfinite(initial[j]) || abs(initial[j]) > 10000 ||
            !isfinite(center[j]) || abs(center[j]) > 10000 ||
            !isfinite(weights[j]) || weights[j] < 0 || weights[j] > 10000)
            throw invalid_argument("invalid coordinates or curvature");
    }
    if (!isfinite(rate) || rate <= 0 || rate > 1000 ||
        !isfinite(beta1) || beta1 < 0 || beta1 >= 1 ||
        !isfinite(beta2) || beta2 < 0 || beta2 >= 1 ||
        !isfinite(epsilon) || epsilon < 1e-12 || epsilon > 1000)
        throw invalid_argument("invalid optimizer controls");
    vector<double> point = initial, first(d, 0.0), second(d, 0.0);
    double one1 = 1.0 - beta1, one2 = 1.0 - beta2;
    double power1 = 1.0, power2 = 1.0;
    double value = objective(point, center, weights);
    vector<State> history;
    history.push_back(State{0, point, {}, first, second, {}, {}, {}, {}, value, power1, power2});
    for (int k = 1; k <= steps; ++k) {
        vector<double> gradient(d), next_first(d), next_second(d);
        for (size_t j = 0; j < d; ++j) {
            double delta = point[j] - center[j];
            gradient[j] = weights[j] * delta;
        }
        if (mode == "ADAM") {
            power1 = power1 * beta1;
            power2 = power2 * beta2;
        }
        for (size_t j = 0; j < d; ++j) {
            double square = gradient[j] * gradient[j];
            if (mode == "ADAGRAD") next_second[j] = second[j] + square;
            else {
                double retained = beta2 * second[j];
                double innovation = one2 * square;
                next_second[j] = retained + innovation;
            }
            if (mode == "ADAM") {
                double retained = beta1 * first[j];
                double innovation = one1 * gradient[j];
                next_first[j] = retained + innovation;
            } else next_first[j] = 0.0;
        }
        first = next_first;
        second = next_second;
        vector<double> numerator(d), second_used(d), denominator(d), correction(d), candidate(d);
        for (size_t j = 0; j < d; ++j) {
            numerator[j] = mode == "ADAM" ? first[j] / (1.0 - power1) : gradient[j];
            second_used[j] = mode == "ADAM" ? second[j] / (1.0 - power2) : second[j];
            denominator[j] = sqrt(second_used[j]) + epsilon;
            double scaled = numerator[j] / denominator[j];
            correction[j] = rate * scaled;
            candidate[j] = point[j] - correction[j];
        }
        point = candidate;
        value = objective(point, center, weights);
        history.push_back(State{k, point, gradient, first, second, numerator, second_used,
                                denominator, correction, value, power1, power2});
    }
    return Result{point, first, second, value, steps, steps, steps + 1, power1, power2, history};
}

string vector_text(const vector<double>& xs) {
    ostringstream out;
    out << fixed << setprecision(8) << '(';
    for (size_t j = 0; j < xs.size(); ++j) {
        if (j) out << ',';
        out << xs[j];
    }
    out << ')';
    return out.str();
}

int main() {
    for (const string& mode : {string("ADAGRAD"), string("RMSPROP"), string("ADAM")}) {
        Result r = adaptive({2}, {0}, {1}, 1.0, 0.5, 0.75, 1.0, 3, mode);
        cout << mode << '\n' << fixed << setprecision(8);
        for (const auto& s : r.history)
            cout << "k=" << s.iteration << " x=" << vector_text(s.point) << " f=" << s.value << '\n';
        cout << "steps=" << r.steps << " gradients=" << r.gradient_evaluations
             << " losses=" << r.value_evaluations << '\n';
    }
    return 0;
}

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static class State {
        int iteration;
        double[] point, gradient, first, second, numerator, second_used, denominator, correction;
        double value, power1, power2;
        State(int k, double[] x, double[] g, double[] m, double[] s, double[] n, double[] v,
              double[] den, double[] step, double f, double p1, double p2) {
            iteration = k; point = x.clone(); gradient = g.clone(); first = m.clone();
            second = s.clone(); numerator = n.clone(); second_used = v.clone();
            denominator = den.clone(); correction = step.clone();
            value = f; power1 = p1; power2 = p2;
        }
    }
    static class Result {
        double[] point, first, second;
        double value;
        int steps, gradient_evaluations, value_evaluations;
        double power1, power2;
        List<State> history;
        Result(double[] x, double[] m, double[] s, double f, int k, double p1, double p2,
               List<State> rows) {
            point = x.clone(); first = m.clone(); second = s.clone(); value = f;
            steps = k; gradient_evaluations = k; value_evaluations = k + 1;
            power1 = p1; power2 = p2; history = rows;
        }
    }

    static double objective(double[] point, double[] center, double[] weights) {
        double total = 0.0;
        for (int j = 0; j < point.length; ++j) {
            double delta = point[j] - center[j];
            double square = delta * delta;
            double term = weights[j] * square;
            total = total + term;
        }
        return 0.5 * total;
    }

    static Result adaptive(double[] initial, double[] center, double[] weights,
                           double rate, double beta1, double beta2, double epsilon,
                           int steps, String mode) {
        if (steps < 0 || steps > 2000 ||
            (!"ADAGRAD".equals(mode) && !"RMSPROP".equals(mode) && !"ADAM".equals(mode)))
            throw new IllegalArgumentException("invalid steps or mode");
        int d = initial.length;
        if (d < 1 || d > 32 || center.length != d || weights.length != d)
            throw new IllegalArgumentException("invalid vector sizes");
        for (int j = 0; j < d; ++j) {
            if (!Double.isFinite(initial[j]) || Math.abs(initial[j]) > 10000 ||
                !Double.isFinite(center[j]) || Math.abs(center[j]) > 10000 ||
                !Double.isFinite(weights[j]) || weights[j] < 0 || weights[j] > 10000)
                throw new IllegalArgumentException("invalid coordinates or curvature");
        }
        if (!Double.isFinite(rate) || rate <= 0 || rate > 1000 ||
            !Double.isFinite(beta1) || beta1 < 0 || beta1 >= 1 ||
            !Double.isFinite(beta2) || beta2 < 0 || beta2 >= 1 ||
            !Double.isFinite(epsilon) || epsilon < 1e-12 || epsilon > 1000)
            throw new IllegalArgumentException("invalid optimizer controls");
        double[] point = initial.clone(), first = new double[d], second = new double[d];
        double one1 = 1.0 - beta1, one2 = 1.0 - beta2, power1 = 1.0, power2 = 1.0;
        double value = objective(point, center, weights);
        List<State> history = new ArrayList<>();
        history.add(new State(0, point, new double[0], first, second, new double[0],
            new double[0], new double[0], new double[0], value, power1, power2));
        for (int k = 1; k <= steps; ++k) {
            double[] gradient = new double[d], nextFirst = new double[d], nextSecond = new double[d];
            for (int j = 0; j < d; ++j) {
                double delta = point[j] - center[j];
                gradient[j] = weights[j] * delta;
            }
            if (mode.equals("ADAM")) {
                power1 = power1 * beta1;
                power2 = power2 * beta2;
            }
            for (int j = 0; j < d; ++j) {
                double square = gradient[j] * gradient[j];
                if (mode.equals("ADAGRAD")) nextSecond[j] = second[j] + square;
                else {
                    double retained = beta2 * second[j];
                    double innovation = one2 * square;
                    nextSecond[j] = retained + innovation;
                }
                if (mode.equals("ADAM")) {
                    double retained = beta1 * first[j];
                    double innovation = one1 * gradient[j];
                    nextFirst[j] = retained + innovation;
                } else nextFirst[j] = 0.0;
            }
            first = nextFirst; second = nextSecond;
            double[] numerator = new double[d], second_used = new double[d], denominator = new double[d];
            double[] correction = new double[d], candidate = new double[d];
            for (int j = 0; j < d; ++j) {
                numerator[j] = mode.equals("ADAM") ? first[j] / (1.0 - power1) : gradient[j];
                second_used[j] = mode.equals("ADAM") ? second[j] / (1.0 - power2) : second[j];
                denominator[j] = Math.sqrt(second_used[j]) + epsilon;
                double scaled = numerator[j] / denominator[j];
                correction[j] = rate * scaled;
                candidate[j] = point[j] - correction[j];
            }
            point = candidate;
            value = objective(point, center, weights);
            history.add(new State(k, point, gradient, first, second, numerator, second_used,
                denominator, correction, value, power1, power2));
        }
        return new Result(point, first, second, value, steps, power1, power2, history);
    }

    static String fixed8(double x) {
        String s = new BigDecimal(x).setScale(8, RoundingMode.HALF_EVEN).toPlainString();
        return Double.doubleToRawLongBits(x) < 0 && s.charAt(0) != '-' ? "-" + s : s;
    }
    static String vector(double[] xs) {
        StringBuilder s = new StringBuilder("(");
        for (int j = 0; j < xs.length; ++j) {
            if (j > 0) s.append(',');
            s.append(fixed8(xs[j]));
        }
        return s.append(')').toString();
    }
    public static void main(String[] args) {
        for (String mode : new String[]{"ADAGRAD", "RMSPROP", "ADAM"}) {
            Result r = adaptive(new double[]{2}, new double[]{0}, new double[]{1},
                1.0, 0.5, 0.75, 1.0, 3, mode);
            System.out.println(mode);
            for (State s : r.history)
                System.out.println("k=" + s.iteration + " x=" + vector(s.point) + " f=" + fixed8(s.value));
            System.out.println("steps=" + r.steps + " gradients=" + r.gradient_evaluations +
                " losses=" + r.value_evaluations);
        }
    }
}

Expected standard output, identical in all three languages:

• ADAGRAD
• k=0 x=(2.00000000) f=2.00000000
• k=1 x=(1.33333333) f=0.88888889
• k=2 x=(0.94160286) f=0.44330798
• k=3 x=(0.67869904) f=0.23031619
• steps=3 gradients=3 losses=4
• RMSPROP
• k=0 x=(2.00000000) f=2.00000000
• k=1 x=(1.00000000) f=0.50000000
• k=2 x=(0.50000000) f=0.12500000
• k=3 x=(0.23703418) f=0.02809260
• steps=3 gradients=3 losses=4
• ADAM
• k=0 x=(2.00000000) f=2.00000000
• k=1 x=(1.33333333) f=0.88888889
• k=2 x=(0.74684451) f=0.27888836
• k=3 x=(0.27920273) f=0.03897708
• steps=3 gradients=3 losses=4

Complexity, Correctness, and Invariants

Let $d$ be the dimension and $K$ the requested number of updates. Each iteration evaluates one gradient, updates $O(d)$ optimizer state, performs $O(d)$ normalization and parameter work, evaluates one scalar objective for monitoring, and copies $O(d)$ data into history. For the diagonal quadratic, gradients and objective each cost $O(d)$.

There is no early exit, so best, average, and worst time are all $\Theta((K+1)d)$ for fixed valid $K,d$. The actual counts are $K$ gradient calls, $K+1$ value calls, and $K+1$ snapshots. A zero-step call still costs $O(d)$ to validate, copy, and evaluate the start. Optimizer state and temporary vectors need $O(d)$ working memory; retaining the full returned trace raises total storage to $\Theta((K+1)d)$. Streaming states instead of storing them reduces memory but not the work needed to produce them. The demonstration keeps a dummy first vector for non-Adam modes; a minimal implementation could omit it.

For another objective with gradient cost $C_g(d)$ and value cost $C_f(d)$, total time is $O(d+C_f(d)+K(C_g(d)+C_f(d)+d))$. Full-loss monitoring may cost a dataset pass even when training uses a small mini-batch, so it should be budgeted separately.

State invariant. After $t$ completed updates, the parameters equal the chosen recurrence's $\mathbf x_t$, and raw history summarizes the gradients already consumed. In exact arithmetic,

$$s_{t,j}=\sum_{i=1}^t g_{i,j}^2\quad\text{for AdaGrad},$$ $$s_{t,j}=(1-\rho)\sum_{i=1}^t\rho^{t-i}g_{i,j}^2\quad\text{for RMSProp},$$ $$m_{t,j}=(1-\beta_1)\sum_{i=1}^t\beta_1^{t-i}g_{i,j},\qquad s_{t,j}=(1-\beta_2)\sum_{i=1}^t\beta_2^{t-i}g_{i,j}^2\quad\text{for Adam}.$$

For Adam, the stored powers are $p_{1,t}=\beta_1^t$ and $p_{2,t}=\beta_2^t$. Expanding one recurrence step proves these sums by induction, with the empty sums zero initially. The powers begin at one; multiplying once per update produces the one-based correction factors. When a coefficient is zero, its update keeps only the new observation; interpret an exponent of zero as $1$ in the finite-sum expression, including when the coefficient itself is zero.

Implementation correctness. Assume the invariant before an update. The program evaluates the gradient using the old parameters, updates moments from that gradient once, and then selects exactly the defined raw or corrected statistics. Nonnegative square history and positive epsilon make every denominator positive in the mathematical recurrence. Subtracting the normalized correction from the frozen old point produces the next parameters. Committing the candidate, copying history, and incrementing counters preserves the invariant. In binary64 the invariant is the explicitly rounded sequence of operations; the exact weighted sums describe the corresponding real-arithmetic algorithm, not a promise that floating accumulation is exact.

Descent requires more than positive denominators. For AdaGrad or RMSProp on one quadratic coordinate with error $e_{t-1}=x_{t-1}-c$ and curvature $a\gt0$, define $\lambda_t=\eta/D_t$. Their current-gradient update gives

$$e_t=(1-a\lambda_t)e_{t-1}.$$

If $0\lt a\lambda_t\lt2$, this coordinate's squared error strictly decreases whenever its old error is nonzero. At $a\lambda_t=2$ its magnitude is unchanged; a larger value can increase the loss. This conditional calculation does not ensure that the chosen rate and evolving denominator satisfy the condition at every step. Positive normalization alone cannot guarantee finite-step descent. Adam uses $\widehat m_t$ in place of $g_t$, so the same scalar gradient-descent argument does not apply to it; the experiment card shows an update away from a minimizer.

AdaGrad's online convex regret guarantees require their stated loss, domain, and update assumptions. They should not be transferred automatically to this unconstrained fixed-horizon example. RMSProp and Adam also need suitable assumptions and parameter choices for convergence results. In particular, Reddi, Kale, and Kumar exhibit convex settings in which Adam fails to converge and introduce AMSGrad. An optimizer can implement the intended recurrence perfectly while failing to reach an optimum on a given problem.

Variants, Pitfalls, and Optimizations

Epsilon placement and square roots. The normalizer here is $\sqrt u+\epsilon$, not $u+\epsilon$ and not $\sqrt{u+\epsilon}$. On the first AdaGrad step, $u=4$ and $\epsilon=1$ give denominator $3$; placing epsilon inside the root instead gives $\sqrt5$. Both produce plausible decreasing losses on this example, so a loss-decrease smoke check would not catch the formula mismatch. With positive epsilon, exact gradient-scale invariance is also lost: rescaling a gradient and its square history leaves an additive epsilon term with a different relative size.

Correct both Adam moments at the correct time. Update index $1$ belongs to the first update. Using $t=0$ creates zero bias denominators. Correcting only the first moment, only the second, or neither defines a different rule. Retain raw moments in storage; do not feed corrected moments back into the raw recurrences. The denominator must use the newly updated second statistic, not yesterday's value. Repeated multiplication of the powers gives a specified floating-point convention; exponentiation or rearranged fused arithmetic can differ in the last bits.

Cumulative memory versus exponential forgetting. AdaGrad's squared sum never decreases, which can make later updates very small after a long history of nonzero gradients. RMSProp can recover larger multipliers as old large gradients fade. A coefficient close to one has a long effective memory, approximately $1/(1-\rho)$ updates for a second-moment average, and slow startup. The uncentered RMSProp variant here intentionally retains its zero-initialization effect; adding bias correction changes it. Centered RMSProp subtracts a squared moving mean from its second moment to estimate variance and requires an additional state convention and care with roundoff.

Sparse gradients and missing gradients. An explicit zero gradient still decays RMSProp and Adam moments; Adam's first moment can continue moving the parameter. Omitting the whole parameter update, as some systems do for a missing gradient, has different clock and state semantics. A dense implementation does not become $O(\operatorname{nnz}(\mathbf g))$ merely because many gradient entries are zero. Truly sparse or lazy implementations need to reproduce the intervening decay and parameter dynamics under their own specified semantics.

AMSGrad and other variants. AMSGrad adds a coordinatewise running maximum of second-moment estimates to retain longer memory in the denominator. A conventional raw-statistic definition is $\widetilde s_{t,j}=\max(\widetilde s_{t-1,j},s_{t,j})$; specify any bias-correction convention as well when comparing implementations. AdaMax uses a different norm-based scale. These are different optimizers, not flags silently enabled in this lesson.

Regularization and engineering. Coupled $L_2$ regularization adds its derivative to the gradient before the optimizer statistics are updated, so it also changes those statistics. Decoupled weight decay, as in AdamW, applies a separate parameter shrinkage and is not generally equivalent under adaptive normalization. Gradient clipping before the moment updates changes the statistics; clipping the final correction changes something else. State which operation you implement.

Save raw moments and the update counter or powers with model parameters for exact continuation. Resetting moments while retaining trained parameters restarts adaptation. In lower precision, squaring can overflow or underflow, epsilon can round away, and near-one coefficients can round to one. Maintain optimizer statistics in a suitable precision and check finite values in a general implementation. Fused kernels and reordered vector reductions can preserve the mathematical algorithm while changing bitwise reproducibility.

The reference programs make no automatic optimizer recommendation. Compare learning-rate schedules, gradient work, monitoring work, final and best losses, residuals, and held-out metrics under a stated experimental protocol. Feature scaling or preconditioning can still improve conditioning before applying any adaptive optimizer.

Practice Problems and Real-World Use

Start by reproducing the trace, then change one convention at a time. For model training, compare optimizers under the same data order and gradient-work budget, tune their base rates fairly, and account for full-loss monitoring separately. A three-step result on one quadratic is an arithmetic example, not evidence of a generally superior optimizer.

Use deterministic gradients to test the update logic before adding mini-batch sampling or automatic differentiation. When comparing a framework implementation, match epsilon placement, accumulator initialization, bias correction, schedules, missing-gradient behavior, and decay conventions before expecting matching trajectories.