Algorithms

Algorithms

Algorithm

Base class for algorithms optimizing group weights.

Stores common bookkeeping (objective trace, timings, iterates) and a reference to an :class:~badr.oracles.Oracle.

Parameters:

• name (str) –

  Display name for the algorithm.

Attributes:

• oracle (Oracle or None) –

  Oracle providing fun/grad (and possibly stochastic primitives).

• n_groups (int) –

  Number of groups (set from the oracle).

• group_weights (ndarray) –

  Latest group-weight iterate (typically on the simplex).

• history_f (list[float]) –

  Traced objective values (when enabled by the algorithm / trace flag).

• history_time (list[float]) –

  Elapsed time trace (seconds).

• history_lambda (list[ndarray]) –

  Traced group-weight iterates (when enabled).

run(max_iter: int = 1, verbose: int = 1, trace: bool = False)

Run the algorithm.

Parameters:

• max_iter (int, default: 1 ) –

  Maximum number of iterations.

• verbose (int, default: 1 ) –

  Verbosity level (interpretation is algorithm-specific).

• trace (bool, default: False ) –

  If True, record per-iteration history (objective/iterates/times).

Raises:

• NotImplementedError –

  If not implemented by a subclass.

BADRSGD

Bases: Algorithm

Stochastic BADR updates over (w, v, lambda) with simplex projection.

Uses a :class:~badr.oracles.StochasticOracle-style interface: draws a minibatch, forms a group-weighted inner gradient for w, updates an auxiliary vector v using Hessian-vector products, and updates lambda via a clipped step followed by projection onto the simplex.

Parameters:

• w0 (ndarray) –

  Initial parameter vector for the lower-level variable w.

• batch_size (int, default: 1 ) –

  Total minibatch size across groups.

• step_w (float, default: 1e-1 ) –

  Step size for w and v updates (used as step_1).

• step_v (float, default: 1e-1 ) –

  Stored step size for v (currently not used in the shown code).

• step_lambda (float, default: 1.0 ) –

  Step size for lambda update (used as step_2).

• clip_value (float, default: 1.0 ) –

  L2-norm clipping threshold applied to the lambda gradient estimate.

Attributes:

• primal_solution (ndarray or None) –

  Final w iterate.

• aux_solution (ndarray or None) –

  Final v iterate.

• message (str or None) –

  Status message after :meth:run.

• history_w, history_v, history_lambda (list[ndarray]) –

  Iterates recorded during :meth:run.

• history_inner_loss_batch (list[float]) –

  f_hat(w, lambda; batch) over iterations.

• history_outer_metric (list[float]) –

  Metric value on the full split at current w.

• history_norm_grad_w, history_norm_v, history_norm_jt_v, history_norm_grad_H_w (list[float]) –

  Diagnostic norms recorded per iteration.

• history_lambda_entropy (list[float]) –

  Entropy -sum(lambda log lambda) per iteration.

• history_clip_fraction (list[float]) –

  Running fraction of iterations where lambda-gradient clipping activated.

Notes

• Simplex projection uses sorting-based Euclidean projection.
• Clipping is detected by comparing the pre/post L2 norms of the gradient.

run(max_iter: int = 1000, verbose: int = 1, trace: bool = False)

Run stochastic BADR iterations.

Parameters:

• max_iter (int, default: 1000 ) –

  Number of iterations.

• verbose (int, default: 1 ) –

  If > 0, prints a completion message.

• trace (bool, default: False ) –

  If True, also appends the outer metric to history_f each iteration.

Returns:

• ndarray –

  Final group weights lambda.

Raises:

• ValueError –

  If no oracle has been set.

FrankWolfe

Bases: Algorithm

Frank--Wolfe on the simplex using a linear minimization oracle.

Uses the oracle gradient g = oracle.grad(x) and the simplex LMO that returns the vertex at argmin_i g_i. The update uses a diminishing step size given in :meth:_step. Convergence is checked with the FW gap g_t = -g^T (x - x_prev).

Parameters:

• starting_point (ndarray or None, default: None ) –

  Initial point on the simplex. If None, uses the uniform distribution.

• eps (float, default: 1e-6 ) –

  Stopping threshold on the FW gap.

Attributes:

• iterates (list[ndarray]) –

  Stored iterates (always filled).

• success (bool) –

  True if the stopping condition was reached.

• message (str or None) –

  Status message after :meth:run.

postprocess()

Populate history_f from the stored history_x.

Raises:

• ValueError –

  If no oracle has been set.

run(max_iter: int = 300, verbose: int = 1, trace: bool = False)

Run Frank--Wolfe iterations.

Parameters:

• max_iter (int, default: 300 ) –

  Maximum number of iterations.

• verbose (int, default: 1 ) –

  If > 0, prints success and message.

• trace (bool, default: False ) –

  If True, records iterates and elapsed time.

Returns:

• ndarray –

  Final group weights.

Raises:

• ValueError –

  If no oracle has been set.

SLSQP

Bases: Algorithm

SLSQP wrapper for simplex-constrained optimization of group weights.

Solves min_x oracle.fun(x) subject to sum(x) = 1 + eps and box bounds x_i in [eps, 1+eps] using SciPy's SLSQP with user-supplied gradient.

Parameters:

• starting_point (ndarray or None, default: None ) –

  Initial point. If None, uses the uniform distribution.

• tol (float, default: 1e-10 ) –

  Function tolerance passed as ftol to SciPy.

Attributes:

• success (bool) –

  Whether SciPy reported success.

• message (str or None) –

  Solver message or exception text.

run(max_iter: int = 500, verbose: int = 1, trace: bool = False)

Run SLSQP.

Parameters:

• max_iter (int, default: 500 ) –

  Maximum iterations passed to SciPy.

• verbose (int, default: 1 ) –

  If > 0, prints success and message (or interruption notice).

• trace (bool, default: False ) –

  If True, records iterates, times, and objective values via a callback.

Returns:

• None –

  This method sets self.group_weights in-place.

Raises:

• Exception –

  Re-raises exceptions from SciPy after storing the latest trace iterate (when available).

TrustConstr

Bases: Algorithm

SciPy trust-constr wrapper for simplex-constrained optimization.

Solves min_x oracle.fun(x) with equality constraint sum(x) = 1 + eps and box bounds using SciPy's trust-constr method and BFGS Hessian approximation.

Parameters:

• starting_point (ndarray or None, default: None ) –

  Initial point. If None, uses the uniform distribution.

Attributes:

• success (bool or None) –

  Whether SciPy reported success.

• message (str or None) –

  Solver message.

run(max_iter: int = 500, verbose: int = 1, trace: bool = False)

Run trust-constr.

Parameters:

• max_iter (int, default: 500 ) –

  Maximum iterations passed to SciPy.

• verbose (int, default: 1 ) –

  If > 0, prints success and message.

• trace (bool, default: False ) –

  If True, records elapsed time and objective values via a callback.

Returns:

• None –

  This method sets self.group_weights in-place.