tf.contrib.constrained_optimization.AdditiveExternalRegretOptimizer

Class AdditiveExternalRegretOptimizer

Defined in tensorflow/contrib/constrained_optimization/python/external_regret_optimizer.py.

A ConstrainedOptimizer based on external-regret minimization.

This ConstrainedOptimizer uses the given tf.train.Optimizers to jointly minimize over the model parameters, and maximize over Lagrange multipliers, with the latter maximization using additive updates and an algorithm that minimizes external regret.

For more specifics, please refer to:

Cotter, Jiang and Sridharan. "Two-Player Games for Efficient Non-Convex Constrained Optimization". https://arxiv.org/abs/1804.06500

The formulation used by this optimizer--which is simply the usual Lagrangian formulation--can be found in Definition 1, and is discussed in Section 3. It is most similar to Algorithm 3 in Appendix C.3, with the two differences being that it uses proxy constraints (if they're provided) in the update of the model parameters, and uses tf.train.Optimizers, instead of SGD, for the "inner" updates.

Properties

constraint_optimizer

Returns the tf.train.Optimizer used for the Lagrange multipliers.

optimizer

Returns the tf.train.Optimizer used for optimization.

Methods

__init__

__init__(
    optimizer,
    constraint_optimizer=None,
    maximum_multiplier_radius=None
)

Constructs a new AdditiveExternalRegretOptimizer.

Args:

  • optimizer: tf.train.Optimizer, used to optimize the objective and proxy_constraints portion of ConstrainedMinimizationProblem. If constraint_optimizer is not provided, this will also be used to optimize the Lagrange multipliers.
  • constraint_optimizer: optional tf.train.Optimizer, used to optimize the Lagrange multipliers.
  • maximum_multiplier_radius: float, an optional upper bound to impose on the sum of the Lagrange multipliers.

Returns:

A new AdditiveExternalRegretOptimizer.

Raises:

  • ValueError: If the maximum_multiplier_radius parameter is nonpositive.

minimize

minimize(
    minimization_problem,
    unconstrained_steps=None,
    global_step=None,
    var_list=None,
    gate_gradients=train_optimizer.Optimizer.GATE_OP,
    aggregation_method=None,
    colocate_gradients_with_ops=False,
    name=None,
    grad_loss=None
)

Returns an Op for minimizing the constrained problem.

This method combines the functionality of minimize_unconstrained and minimize_constrained. If global_step < unconstrained_steps, it will perform an unconstrained update, and if global_step >= unconstrained_steps, it will perform a constrained update.

The reason for this functionality is that it may be best to initialize the constrained optimizer with an approximate optimum of the unconstrained problem.

Args:

  • minimization_problem: ConstrainedMinimizationProblem, the problem to optimize.
  • unconstrained_steps: int, number of steps for which we should perform unconstrained updates, before transitioning to constrained updates.
  • global_step: as in tf.train.Optimizer's minimize method.
  • var_list: as in tf.train.Optimizer's minimize method.
  • gate_gradients: as in tf.train.Optimizer's minimize method.
  • aggregation_method: as in tf.train.Optimizer's minimize method.
  • colocate_gradients_with_ops: as in tf.train.Optimizer's minimize method.
  • name: as in tf.train.Optimizer's minimize method.
  • grad_loss: as in tf.train.Optimizer's minimize method.

Returns:

TensorFlow Op.

Raises:

  • ValueError: If unconstrained_steps is provided, but global_step is not.

minimize_constrained

minimize_constrained(
    minimization_problem,
    global_step=None,
    var_list=None,
    gate_gradients=train_optimizer.Optimizer.GATE_OP,
    aggregation_method=None,
    colocate_gradients_with_ops=False,
    name=None,
    grad_loss=None
)

Returns an Op for minimizing the constrained problem.

The optimizer constructor parameter will be used to update the model parameters, while the Lagrange multipliers will be updated using constrained_optimizer (if provided) or optimizer (if not).

Args:

Returns:

TensorFlow Op.

minimize_unconstrained

minimize_unconstrained(
    minimization_problem,
    global_step=None,
    var_list=None,
    gate_gradients=train_optimizer.Optimizer.GATE_OP,
    aggregation_method=None,
    colocate_gradients_with_ops=False,
    name=None,
    grad_loss=None
)

Returns an Op for minimizing the unconstrained problem.

Unlike minimize_constrained, this function ignores the constraints (and proxy_constraints) portion of the minimization problem entirely, and only minimizes objective.

Args:

Returns:

TensorFlow Op.