decent_bench.centralized_algorithms#

decent_bench.centralized_algorithms.solve(cost: Cost, max_iter: int = 100, stop_tol: float | None = None, max_tol: float | None = None, show_progress: bool = True) → Array[source]#

Minimize a cost function using a suitable solver.

Applies solve() to quadratic costs, accelerated gradient descent to smooth and (strongly) convex costs, (sub)gradient descent to any other cost.

Parameters:

  • cost – cost function to minimize.

  • max_iter – maximum number of iterations to run. Defaults to 100.

  • stop_tol – optional early stopping tolerance; stops if ||x_new - x_old||^2 drops below this value.

  • max_tol – optional final tolerance; RuntimeError is raised if ||x_new - x_old||^2 exceeds this value after max_iter iterations.

  • show_progress – whether to display a progress bar during iterative solves. Defaults to True.

Returns:

Approximate minimizer or stationary point.

Raises:

ValueError – when the cost has m_smooth = 0.

class decent_bench.centralized_algorithms.Solver(cost: Cost, x0: Array | None = None)[source]#

Bases: ABC

Base class for centralized solvers.

Initializes iterate (x) and previous iterate (x_old), validates domain shape, and stores hyperparameters. Subclasses must implement the step method to define one iteration of their algorithm.

abstractmethod step(iteration: int) → None[source]#

Perform one iteration of the solver.

Subclasses must update self.x exactly once per step. Use the iteration counter for algorithms with iteration-dependent parameters (e.g., step schedules).

Parameters:

iteration – current iteration number.

final run(max_iter: int = 100, stop_tol: float | None = None, max_tol: float | None = None, check_frequency: float = 0.01, show_progress: bool = True) → Array[source]#

Run the solver.

Executes step() for up to max_iter iterations. Stops early if the squared norm of the iterate change drops below stop_tol. After completion, verifies that the final iterate change is at most max_tol.

Parameters:

  • max_iter – maximum number of iterations; must be positive. Defaults to 100.

  • stop_tol – optional early stopping tolerance; stops if ||x_new - x_old||^2 <= stop_tol. Must be positive if provided.

  • max_tol – optional final tolerance; raises RuntimeError if ||x_new - x_old||^2 > max_tol after max_iter iterations. Must be positive if provided.

  • check_frequency – float in (0, 1] defining how often the early stopping condition should be checked. A smaller value means that the stopping condition is checked more often. This applies only if stop_tol is not None.

  • show_progress – whether to display a progress bar during iteration. Defaults to True.

Returns:

Final iterate x as an Array.

Raises:

  • ValueError – if max_iter < 1, or if stop_tol or max_tol are provided and non-positive.

  • RuntimeError – if max_tol is provided and the final iterate change exceeds max_tol.

Warning

Do not override this method. Instead, override step() to define solver behavior.

class decent_bench.centralized_algorithms.GradientDescent(cost: Cost, step_size: float | Callable[[int], float] | None = None, x0: Array | None = None)[source]#

Bases: Solver

Gradient descent solver.

If step_size is not provided, defaults to: - Non-smooth or non-convex: \(1/\sqrt{k+1}\) - Strongly convex: \(2/(L+mu)\) - Convex: step_size = 1/m_smooth

step(iteration: int) → None[source]#

Perform one iteration of the solver.

class decent_bench.centralized_algorithms.AcceleratedGradientDescent(cost: Cost, step_size: float | None = None, momentum: float | Callable[[int], float] | None = None, x0: Array | None = None)[source]#

Bases: Solver

Accelerated gradient descent (Nesterov momentum) solver.

If step_size is not provided, defaults to: \(1/L\).

If momentum is not provided, defaults to: - Strongly convex: \((\sqrt(L)-\sqrt(mu)) / (\sqrt(L)+\sqrt(mu))\) - Otherwise: \(k / (k+3)\)

step(iteration: int) → None[source]#

Perform one iteration of the solver.

decent_bench.centralized_algorithms.proximal_solver(cost: Cost, y: Array, penalty: float, max_iter: int = 100) → Array[source]#

Approximate the cost’s proximal at y using accelerated gradient descent.

This is an approximate solution to the proximal operator defined as:

\[\operatorname{prox}_{\rho f}(\mathbf{x}) = \arg\min_{\mathbf{y}} \left\{ f(\mathbf{y}) + \frac{1}{2\rho} \| \mathbf{y} - \mathbf{x} \|^2 \right\}\]

where \(\rho > 0\) is the penalty and \(f\) the cost function.

The cost must be differentiable, L-smooth, and convex.

Parameters:

  • cost – cost function to compute the proximal of.

  • y – point at which to evaluate the proximal.

  • penalty – penalty parameter.

  • max_iter – maximum number of iterations of the solver.

Returns:

Approximate proximal at y.

Raises:

  • ValueError – if cost’s domain and y do not have the same shape, or if penalty is not positive.

  • NotImplementedError – if the cost is not differentiable, L-smooth, and convex.