Skip to content

optora.solvers.saddle_point

Primal-dual saddle-point solver for the DRO minimax problem.

SaddlePointProblem dataclass

Minimax problem solved by SaddlePointSolver.

Represents \(\min_x \max_y \mathrm{objective}(x, y)\), the shape of the DRO minimax problem once a decision variable x and an ambiguity set over distributions y are both in play.

Attributes:

Name Type Description
objective Callable[[Tensor, Tensor], Tensor]

Differentiable scalar-valued function objective(primal_point, dual_point), minimized over its first argument and maximized over its second. It must depend on both arguments through autograd; the solver rejects an objective whose value is disconnected from either iterate rather than treating it as stationary in that variable.
primal_initial_point Tensor

Starting point for the primal (minimizing) variable.
dual_initial_point Tensor

Starting point for the dual (maximizing) variable.
dual_projection Callable[[Tensor], Tensor] | None

Callable applied to the dual iterate after every ascent step to keep it inside its feasible set, for example projection onto the probability simplex or onto a DRO ambiguity set. Defaults to the identity (unconstrained ascent) when None.

SaddlePointResult dataclass

Bases: ConvergenceDiagnostics

Outcome of a SaddlePointSolver solve.

Attributes:

Name Type Description
primal_point Tensor

Final primal (minimizing) iterate.
dual_point Tensor

Final dual (maximizing) iterate.
value Tensor

Objective value at (primal_point, dual_point).
status ConvergenceStatus

Convergence diagnostics of the solve, exposed on the host as converged and num_iterations by ConvergenceDiagnostics and read back from the device only when one of those is accessed. Convergence is the combined primal/dual gradient norm falling below tol before max_iter iterations are exhausted.

converged property

Whether the convergence criterion was met before the iteration budget.

num_iterations property

Number of iterations actually performed.

SaddlePointSolver

Bases: Solver[SaddlePointProblem, SaddlePointResult]

Primal-dual gradient ascent-descent for a minimax problem.

Solves \(\min_x \max_y \mathrm{objective}(x, y)\) by alternating, at every iteration, a gradient descent step on the primal variable \(x\) and a gradient ascent step on the dual variable \(y\):

\[ x \leftarrow x - \mathrm{primal\_step\_size} \cdot \nabla_x \mathrm{objective}(x, y) \]
\[ y \leftarrow \mathrm{dual\_projection}\big( y + \mathrm{dual\_step\_size} \cdot \nabla_y \mathrm{objective}(x, y) \big) \]

dual_projection keeps y feasible after each ascent step. This is the generic minimax solve optora.dro.minimax_solver uses to train a decision variable against a DRO ambiguity set: x is the decision variable, y ranges over distributions inside the ambiguity set, and dual_projection enforces that constraint (for example simplex projection or an AmbiguitySet-specific projection).

The gradient-norm test is evaluated on the iterates' device and read back to the host only every check_interval iterations; iterations taken after convergence are frozen, so the solution does not depend on that interval. Keep check_interval=1 when the objective is expensive, for example when each iteration costs an optora.dro inner dual solve. See optora.core.convergence.ConvergenceTracker. The returned diagnostics stay on the device as well (see optora.core.convergence.ConvergenceStatus), so a solve nobody inspects never synchronizes for them.

Attributes:

Name Type Description
primal_step_size

Positive learning rate for the descent step on the primal variable.
dual_step_size

Positive learning rate for the ascent step on the dual variable.
max_iter

Maximum number of ascent-descent iterations.
tol

Convergence tolerance on the combined primal/dual gradient norm.
check_interval

Number of iterations between host reads of the convergence flag.

__init__(primal_step_size=0.01, dual_step_size=0.01, max_iter=1000, tol=1e-06, check_interval=DEFAULT_CHECK_INTERVAL)

Initialize the saddle-point solver.

Parameters:

Name Type Description Default
primal_step_size float

Positive learning rate for the descent step on the primal variable.

 0.01
dual_step_size float

Positive learning rate for the ascent step on the dual variable.

 0.01
max_iter int

Maximum number of ascent-descent iterations.

 1000
tol float

Convergence tolerance on the combined primal/dual gradient norm.

 1e-06
check_interval int

Number of iterations between host reads of the convergence flag. Raise it to trade redundant frozen iterations for fewer device synchronizations, but only when an iteration is cheap relative to a synchronization.

 DEFAULT_CHECK_INTERVAL

Raises:

Type Description
ValueError

If primal_step_size, dual_step_size, max_iter, tol, or check_interval are not positive.

solve(problem)

Find a saddle point of problem.objective.

Parameters:

Name Type Description Default
problem SaddlePointProblem

Objective, initial primal/dual points, and optional dual feasibility projection to solve from.

 required

Returns:

Type Description
SaddlePointResult

A SaddlePointResult holding the final primal/dual iterates
SaddlePointResult

and convergence diagnostics.

Raises:

Type Description
ValueError

If problem.objective does not depend on both of its arguments through autograd.