Pith Number

pith:LBCTHNMW

pith:2026:LBCTHNMWBXB5VJYAICKRKRCW7X

not attested not anchored not stored refs pending

High-Probability Guarantees for Random Zeroth-Order (Stochastic) Gradient Descent

Haishan Ye

Random zeroth-order gradient descent reaches ε-suboptimality with probability 1-δ using O((dL/μ)log(1/ε) + log(1/δ)) queries for smooth strongly convex functions.

arxiv:2604.23613 v2 · 2026-04-26 · math.OC

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{LBCTHNMWBXB5VJYAICKRKRCW7X}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

For deterministic L-smooth and μ-strongly convex objectives of d-dimension, the classical two-query random zeroth-order method finds an ε-suboptimal solution with probability at least 1-δ using O((dL/μ)log(1/ε) + log(1/δ)) function queries. For stochastic objectives under bounded-noise, random zeroth-order SGD achieves the same with O(d log(1/ε)(log(1/ε)+log(1/δ))/ε) queries.

C2weakest assumption

The objective is L-smooth and μ-strongly convex (deterministic case) or has bounded noise without uniformly bounded stochastic gradients (stochastic case); these are invoked to derive the stated query complexities but their necessity for the high-probability result is not relaxed in the abstract.

C3one line summary

Random zeroth-order gradient descent reaches ε-suboptimal solutions with probability 1-δ using O((dL/μ)log(1/ε) + log(1/δ)) queries deterministically and O(d log(1/ε)(log(1/ε)+log(1/δ))/ε) queries under bounded stochastic noise.

Receipt and verification

First computed	2026-06-23T01:12:07.537231Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

584533b5960dc3daa7004095154456fdd6a3beb511caaae809365cd3ba2cc06e

Aliases

arxiv: 2604.23613 · arxiv_version: 2604.23613v2 · doi: 10.48550/arxiv.2604.23613 · pith_short_12: LBCTHNMWBXB5 · pith_short_16: LBCTHNMWBXB5VJYA · pith_short_8: LBCTHNMW

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/LBCTHNMWBXB5VJYAICKRKRCW7X \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 584533b5960dc3daa7004095154456fdd6a3beb511caaae809365cd3ba2cc06e

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "5ad99d955f16be0532727a4cadd9afc4650979d555d149230f3e91e7b9c8e0d0",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "math.OC",
    "submitted_at": "2026-04-26T09:02:05Z",
    "title_canon_sha256": "fb12827e561a73ae399edcf4385c842f39c37504b26d324ca326e193033a4e26"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2604.23613",
    "kind": "arxiv",
    "version": 2
  }
}