gaussianzeroorder

Two-point Gaussian zeroth-order stochastic optimization with high-probability last-iterate certificates.

gaussianzeroorder implements the same-sample, two-point Gaussian zeroth-order stochastic gradient descent method of Ye (2026). It provides rigorous, finite-sample, high-confidence certificates for the last iterate under conditional sub-Gaussian noise — not just expectation bounds or guarantees on averaged iterates.

Features

• High-probability last-iterate guarantee. With probability at least 1 - delta, the final iterate x_T is within a controlled distance of the optimum. The confidence cost depends only logarithmically / double-logarithmically on delta, avoiding the polynomial 1/delta blow-up of nave union-bound analyses.
• Same-sample variance reduction. Both function evaluations within a single finite-difference step use the same stochastic sample (common random numbers), canceling the independent differencing noise that would otherwise dominate.
• Theoretically principled step size. A dimension- and problem-aware schedule eta_t = 4d / (mu * (t + T0) * ||u_t||^2) with T0 = 32 d L / mu is used directly — no learning-rate tuning required.
• Explicit dimension & confidence scaling. The theoretical parameters (d, T, delta, mu, L, sigma^2) are first-class inputs, so you can compute a priori how many oracle calls are needed for a target precision at a target confidence.
• Certification & diagnostics layer. Compute the stitched confidence factor Gamma_T(delta), estimate complexity, and derive a post-hoc numerical bound on f(x_T) - f(x*) that holds with probability >= 1 - delta. Per-iteration diagnostics (logger, product-weight tracker, weighted scan monitor) are included.
• Reproducible & production-friendly. Reproducibility manager, callback hooks, and an async oracle wrapper for batched / concurrent evaluations.

Module overview

Installation

From PyPI:

pip install gaussianzeroorder

From source (editable, with test dependencies):

git clone https://github.com/USER/REPO.git
cd REPO
python -m venv .venv && source .venv/bin/activate   # Windows: .venv\Scripts\activate
pip install -e .[test]

Runtime requirement: Python >=3.10 and NumPy >=1.24.

Usage

The optimizer drives a user-supplied StochasticOracle, whose evaluate(x, seed) method must return a scalar and use seed to enforce common random numbers.

import numpy as np

from gaussianzeroorder.oracle.base import StochasticOracle
from gaussianzeroorder.oracle.config import ProblemConfig
from gaussianzeroorder.optimizer.core import TwoPointGaussianOptimizer
from gaussianzeroorder.optimizer.step_size import StepSizeSchedule
from gaussianzeroorder.optimizer.direction import GaussianDirectionSampler


class QuadraticStochasticOracle(StochasticOracle):
    """Strongly convex quadratic f(x) = (mu/2)||x||^2 with additive linear noise."""

    def __init__(self, d: int, mu: float, sigma: float) -> None:
        self.d, self.mu, self.sigma = d, mu, sigma

    def evaluate(self, x: np.ndarray, seed: int) -> float:
        rng = np.random.default_rng(seed)
        xi = rng.normal(0.0, self.sigma, size=self.d)
        return float(0.5 * self.mu * np.sum(x**2) + np.dot(xi, x))


# Problem parameters
d, mu, L, sigma = 50, 2.0, 2.0, 0.5
T = 2000
delta = 0.05

# Configuration (positional: d, L, mu, sigma^2, Delta_0, delta)
config = ProblemConfig(d, L, mu, (sigma**2) * d, 0.0, delta)

# Components
schedule = StepSizeSchedule(d, L, mu)
sampler = GaussianDirectionSampler(d, seed=42)
oracle = QuadraticStochasticOracle(d, mu, sigma)

optimizer = TwoPointGaussianOptimizer(oracle, config, schedule, sampler)

x0 = np.random.default_rng(0).standard_normal(d)
x_final = optimizer.optimize(x0, total_iteration_horizon_T=T)

print(f"Final iterate norm: {np.linalg.norm(x_final):.6e}")

Certification

After optimization, compute a rigorous bound on suboptimality that holds with probability at least 1 - delta:

from gaussianzeroorder.certification.confidence import ConfidenceFactor
from gaussianzeroorder.certification.bounds import PostHocBound

T0 = 32.0 * d * L / mu
gamma_T = ConfidenceFactor().compute_gamma_T(T, T0, delta)

trajectory = [None] * (T + 1)  # replace with the real recorded trajectory
cert_bound = PostHocBound().compute_bound(trajectory, gamma_T, config)
print(f"Theoretical 1-delta certificate bound: {cert_bound:.6e}")

Theory

The method targets smooth, strongly convex objectives f with sub-Gaussian stochastic oracle noise. Under the high-dimensional compatibility condition d >= 16 log(6T/delta) it attains the convergence rate O~(d/T) for the last iterate with probability >= 1 - delta. The analysis is based on the paper "High-Probability Last-Iterate Guarantees for Two-Point Gaussian Zeroth-Order Stochastic Gradient Descent" by Haishan Ye (arXiv:2606.20446). See that paper for the full analysis and the definition of the stitched confidence factor Gamma_T(delta).

Development

pip install -e .[test]
pytest

License

Released under the MIT License.