Home / Curated / Algorithms / ANITA Optimal Loopless Accelerated Variance-Reduced Gradient Method

ANITA Optimal Loopless Accelerated Variance-Reduced Gradient Method

Algorithms AIMech:AnitaOptimalLooplessAcceleratedVarianceReducedGradientMethod DRAFT

Aliases: ANITA, AN optImal loopless acceleraTed vAriance-reduced gradient method, Loopless Accelerated Variance-Reduced Gradient Method with Dynamic Snapshot Probability

A loopless (single-loop) accelerated variance-reduced gradient method introduced by Li (2021) for solving general convex (mu = 0) and mu-strongly convex (mu > 0) finite-sum optimization problems min_{x in R^d} f(x) = (1/n) sum_{i=1}^n f_i(x). At each iteration t, ANITA computes the first momentum interpolation x_under_t = theta_t x_t + (1 - theta_t) w_t, samples i in [n] uniformly at random to form the SVRG gradient estimator nabla_tilde_t = nabla f_i(x_under_t) - nabla f_i(w_t) + nabla f(w_t), updates x_{t+1} = (1 / (1 + mu eta_t))(x_t + mu eta_t x_under_t) - (eta_t / alpha_t) nabla_tilde_t and the second interpolation x_bar_{t+1} = theta_t x_{t+1} + (1 - theta_t) w_t, and probabilistically refreshes the snapshot point w_{t+1} = x_bar_{t+1} with probability p_t (or retains w_{t+1} = w_t with probability 1 - p_t) using a dynamic multi-stage probability schedule {p_t}.

Identity Notes & Concept Scope Distinct from double-loop accelerated variance-reduced methods such as Katyusha (Allen-Zhu 2017) and Varag (Lan et al. 2019), and distinct from fixed-probability loopless Katyusha (L-Katyusha, Kovalev et al. 2020, which only handles strongly convex objectives mu > 0 with constant p_t = p): ANITA uses a single-loop structure with a dynamic three-stage snapshot probability schedule {p_t} in the general convex regime (mu = 0), achieving the first optimal O(n) stochastic gradient complexity matching the Woodworth-Srebro Omega(n) lower bound when n >= 1/epsilon^2.

Claims & Grounded Evidence

4 Claims

Mechanism #anita-dynamic-three-stage-loopless-general-convex-convergence

For L-smooth general convex finite-sum objectives (mu = 0), Theorem 1 sets a three-stage target-error-free schedule: Stage 1 (0 <= t <= t_1, where t_1 ~ Geom(1/(n+1)) is the first snapshot update) uses p_t = 1/(n+1), theta_t = 1 - 1/(2 sqrt(n)), eta_t <= 1/(L(1 + 1/(1 - theta_t))), alpha_t = theta_t; Stages 2 and 3 (t > t_1) set p_t = max{4/(t - t_1 + 3 sqrt(n)), 4/(n + 3)}, theta_t = 2/(p_t(t - t_1 + 3 sqrt(n))), eta_t <= 1/(3L), and alpha_t = theta_t, satisfying the recursion (1 - p_t theta_t) eta_t / (p_t theta_t^2) <= eta_{t-1} / (p_{t-1} theta_{t-1}^2) (Eq. 40) and guaranteeing last-iterate convergence E[f(w_t) - f(x*)] <= 32 ||x_0 - x*||^2 / (eta_{t-1} p_{t-1} (t - t_1 + 3 sqrt(n))^2).

supports Source: ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method · Locator: Section 4.1, Theorem 1, Corollary 1 & Remark, pp. 7-8; Appendix A.1, Lemmas 5-7 & Equations (40)-(47), pp. 17-21

Mechanism #anita-optimal-general-convex-and-large-scale-gradient-complexity

By Corollary 1 and Table 2, ANITA finds an epsilon-approximate solution E[f(w_T) - f(x*)] <= epsilon in O(n min{1 + log(1/(epsilon sqrt(n))), log sqrt(n)} + sqrt(n L / epsilon)) stochastic gradient computations without requiring epsilon in advance, achieving the exact optimal O(n + sqrt(n L / epsilon)) complexity matching the Woodworth-Srebro lower bound Omega(n + sqrt(n L / epsilon)) for both large-scale problems (n >= 1/epsilon^2, where complexity is O(n)) and small-error regimes (epsilon <= L / (n log^2 sqrt(n))).

supports Source: ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method · Locator: Section 2, Tables 1-2, pp. 3-5; Section 4.1, Corollary 1, pp. 7-8; Appendix A.1.2, Equations (48)-(54), pp. 21-22

Scope #anita-strongly-convex-constant-parameter-optimal-linear-rate

For L-smooth mu-strongly convex finite-sum objectives (mu > 0), Theorem 2 uses constant parameters p_t = p = 1/n, theta_t = theta = (1/2) min{1, sqrt(mu / (p L))}, eta_t = eta <= 1 / (L theta (1 + 1/(1 - theta))), and alpha_t = 1 + mu eta, proving that the Lyapunov function Phi_t := f(w_t) - f(x*) + ((1 + mu eta) p theta / (2 eta)) ||x_t - x*||^2 contracts as E[Phi_t] <= (1 - 4 p theta / 5)^t Phi_0 and achieves optimal O(max{n, sqrt(n L / mu)} log(1/epsilon)) stochastic gradient complexity (Corollary 2).

supports Source: ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method · Locator: Section 4.2, Theorem 2 & Corollary 2, pp. 8-9; Appendix A.2, Lemma 8 & Equations (55)-(59), pp. 22-23

Limitation #anita-intermediate-error-logarithmic-gap-and-full-snapshot-limitation

In the intermediate error regime 1/sqrt(n) > epsilon > L / (n log^2 sqrt(n)), ANITA's general convex complexity O(n min{1 + log(1/(epsilon sqrt(n))), log sqrt(n)}) retains a logarithmic factor up to log sqrt(n) above the Omega(n + sqrt(n L / epsilon)) lower bound (Table 2), and every probabilistic snapshot update w_{t+1} = x_bar_{t+1} requires a full gradient evaluation nabla f(w_{t+1}) over all n components.

supports Source: ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method · Locator: Section 2, Table 2 & Section 2.1, pp. 4-6

⚠️ Curated Limitations & Negative Results

In the intermediate regime 1/sqrt(n) > epsilon > L / (n log^2 sqrt(n)), the general convex gradient complexity includes a logarithmic factor min{1 + log(1/(epsilon sqrt(n))), log sqrt(n)}.
Requires a full gradient computation nabla f(w_t) of cost n whenever the Bernoulli coin flip of probability p_t updates the snapshot w_{t+1} = x_bar_{t+1}.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:LogisticRegression` Logistic Regression	related_match	ANITA is designed for empirical risk minimization finite-sum problems and benchmarked on convex finite-sum logistic regression (Section 5, Eq. 6).

Evidence Sources & Primary Literature

3 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`r570-primary-pdf`	ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method Zhize Li	primary paper full_text	ID: https://api.openalex.org/works/W3137382134 sha256:ba0754683d80…
`r570-arxiv-abs`	ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method (arXiv abstract) Zhize Li	primary paper abstract_only	ID: https://arxiv.org/abs/2103.11333 sha256:0c5f75809218…
`r570-metadata-cr`	ANITA: An Optimal Loopless Accelerated Variance-Reduced Gradient Method (Crossref metadata) Zhize Li	primary paper abstract_only	ID: https://api.openalex.org/works/W3137382134 sha256:2e712bb52836…

Ontology & Grounding Topology

Open in interactive network graph →

Curation Provenance

Curator: Antigravity

Method: ai_assisted

Model: Gemini

Created: 2026-10-19T10:53:00Z

Updated: 2026-10-19T10:53:00Z

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