Metadata-Version: 2.4
Name: gaussianzeroorder
Version: 0.1.0
Summary: Two-point Gaussian zeroth-order stochastic optimization with high-probability last-iterate certificates under conditional sub-Gaussian noise.
Author-email: Your Name <you@example.com>
Maintainer-email: Your Name <you@example.com>
License: MIT
Project-URL: Homepage, https://github.com/USER/REPO
Project-URL: Repository, https://github.com/USER/REPO
Project-URL: Documentation, https://github.com/USER/REPO#readme
Project-URL: Issues, https://github.com/USER/REPO/issues
Keywords: zeroth-order-optimization,derivative-free-optimization,stochastic-optimization,gaussian,high-probability,certification,black-box-optimization
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24
Provides-Extra: test
Requires-Dist: pytest>=7.0; extra == "test"
Requires-Dist: hypothesis>=6.0; extra == "test"
Requires-Dist: pytest-asyncio>=0.21; extra == "test"
Provides-Extra: dev
Requires-Dist: gaussianzeroorder[test]; extra == "dev"
Requires-Dist: build>=1.0; extra == "dev"
Requires-Dist: twine>=4.0; extra == "dev"
Dynamic: license-file

# gaussianzeroorder

[![PyPI version](https://img.shields.io/pypi/v/gaussianzeroorder.svg)](https://pypi.org/project/gaussianzeroorder/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)

**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

| Module | Key components |
|---|---|
| `optimizer` | `TwoPointGaussianOptimizer`, `StepSizeSchedule`, `GaussianDirectionSampler` |
| `oracle` | `StochasticOracle` (protocol), `ProblemConfig`, `NoiseModel` |
| `certification` | `ConfidenceFactor`, `ComplexityEstimator`, `PostHocBound`, `DimensionCheck` |
| `diagnostics` | `OptimizationLogger`, `ProductWeightTracker`, `WeightedScanMonitor` |
| `utils` | `SphereGaussianProjection`, `ReproducibilityManager`, `CallbackSystem`, `AsyncOracleWrapper` |

## Installation

From PyPI:

```bash
pip install gaussianzeroorder
```

From source (editable, with test dependencies):

```bash
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.

```python
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`:

```python
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](https://arxiv.org/abs/2606.20446)). See that paper for the full analysis and
the definition of the stitched confidence factor `Gamma_T(delta)`.

## Development

```bash
pip install -e .[test]
pytest
```

## License

Released under the [MIT License](LICENSE).
