use std::num::NonZeroU32;
use argmin::core::{
Error as ArgminError, IterState, KV, Problem, Solver, TerminationReason, TerminationStatus,
};
use argmin::solver::trustregion::{Steihaug, TrustRegion as ArgminTrustRegion};
use crate::error::GprError;
use crate::objective::TwiceDifferentiable;
use super::adapter::{
CachedProblem, EvalCache, RunEnd, WithHessian, best_value, consider_logit_run, run_argmin,
};
use super::logit::{log_theta_to_z, sample_log_uniform_z};
use super::{OptResult, Optimizer, Restarts};
#[derive(Clone, Debug, PartialEq)]
pub struct TrustRegion {
max_iterations: u64,
tolerance: f64,
initial_radius: f64,
max_radius: f64,
restarts: Option<Restarts>,
}
impl Default for TrustRegion {
fn default() -> Self {
Self {
max_iterations: 100,
tolerance: f64::EPSILON.sqrt(),
initial_radius: 1.0,
max_radius: 100.0,
restarts: None,
}
}
}
impl TrustRegion {
pub fn new() -> Self {
Self::default()
}
pub fn with_max_iterations(mut self, max_iterations: u64) -> Self {
self.max_iterations = max_iterations;
self
}
pub fn with_tolerance(mut self, tolerance: f64) -> Result<Self, GprError> {
if !tolerance.is_finite() || tolerance < 0.0 {
return Err(GprError::InvalidConfig {
reason: "trust-region gradient tolerance must be finite and >= 0".to_owned(),
});
}
self.tolerance = tolerance;
Ok(self)
}
pub fn with_radii(mut self, initial_radius: f64, max_radius: f64) -> Result<Self, GprError> {
let ok = initial_radius.is_finite()
&& max_radius.is_finite()
&& initial_radius > 0.0
&& initial_radius <= max_radius;
if !ok {
return Err(GprError::InvalidConfig {
reason: "trust radii must satisfy 0 < initial <= max, both finite".to_owned(),
});
}
self.initial_radius = initial_radius;
self.max_radius = max_radius;
Ok(self)
}
pub fn with_restarts(mut self, n: NonZeroU32, seed: u64) -> Self {
self.restarts = Some(Restarts { n, seed });
self
}
#[cfg(test)]
pub(crate) fn minimize_unconstrained<P: TwiceDifferentiable>(
&self,
objective: &mut P,
init: &[f64],
) -> Result<OptResult, GprError> {
run_trust_region(self, objective, init)
}
}
impl<P: TwiceDifferentiable> Optimizer<P> for TrustRegion {
fn minimize(&self, objective: &mut P, init: &[f64]) -> Result<OptResult, GprError> {
super::minimize_with_restarts(
objective,
init,
self.restarts,
log_theta_to_z,
sample_log_uniform_z,
|objective, intervals, z, _restart, best| {
consider_logit_run(objective, intervals, z, best, |mapped, z| {
run_trust_region(self, mapped, z)
})
},
)
}
}
fn run_trust_region<P: TwiceDifferentiable>(
optimizer: &TrustRegion,
objective: &mut P,
init: &[f64],
) -> Result<OptResult, GprError> {
let n = objective.num_params();
super::require_params(init, n)?;
let mut cache = EvalCache::<_, WithHessian>::new(objective, n);
cache.try_eval(init)?;
let subproblem = Steihaug::<Vec<f64>, f64>::new().with_max_iters(4 * n as u64 + 10);
let inner = ArgminTrustRegion::new(subproblem)
.with_radius(optimizer.initial_radius)
.and_then(|tr| tr.with_max_radius(optimizer.max_radius))
.map_err(|e| GprError::InvalidConfig {
reason: e.to_string(),
})?;
let solver = GradNormStop {
inner,
tolerance: optimizer.tolerance,
};
let RunEnd {
params,
cost,
iterations,
} = run_argmin(
CachedProblem::new(cache),
solver,
init,
optimizer.max_iterations,
)?;
let value = best_value(cost, iterations, || {
let mut grad = vec![0.0; n];
objective.value_and_gradient_into(¶ms, &mut grad)
})?;
Ok(OptResult {
params,
value,
iterations,
})
}
struct GradNormStop<S> {
inner: S,
tolerance: f64,
}
type TrState = IterState<Vec<f64>, Vec<f64>, (), Vec<Vec<f64>>, (), f64>;
impl<O, S> Solver<O, TrState> for GradNormStop<S>
where
S: Solver<O, TrState>,
{
fn name(&self) -> &str {
self.inner.name()
}
fn init(
&mut self,
problem: &mut Problem<O>,
state: TrState,
) -> Result<(TrState, Option<KV>), ArgminError> {
self.inner.init(problem, state)
}
fn next_iter(
&mut self,
problem: &mut Problem<O>,
state: TrState,
) -> Result<(TrState, Option<KV>), ArgminError> {
self.inner.next_iter(problem, state)
}
fn terminate(&mut self, state: &TrState) -> TerminationStatus {
if let Some(grad) = state.get_gradient() {
let norm = grad.iter().map(|g| g * g).sum::<f64>().sqrt();
if norm <= self.tolerance {
return TerminationStatus::Terminated(TerminationReason::SolverConverged);
}
}
self.inner.terminate(state)
}
}
#[cfg(test)]
mod tests {
use super::TrustRegion;
use crate::error::GprError;
use crate::gpr::Gpr;
use crate::kernel::{KernelSpec, RbfKernel};
use crate::likelihood::GaussianLikelihood;
use crate::objective::{Differentiable, Objective, TwiceDifferentiable};
use crate::optimizer::{Fixed, Optimizer};
const TOL: f64 = 1e-6;
use crate::test_check::assert_close;
struct Quadratic;
impl Objective for Quadratic {
fn num_params(&self) -> usize {
2
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
let mut dummy = [0.0; 2];
self.value_and_gradient_into(params, &mut dummy)
}
}
impl Differentiable for Quadratic {
fn gradient_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
self.value_and_gradient_into(params, out).map(|_| ())
}
fn value_and_gradient_into(
&mut self,
params: &[f64],
out: &mut [f64],
) -> Result<f64, GprError> {
if params.len() != 2 || out.len() != 2 {
return Err(GprError::ShapeMismatch {
reason: "quadratic is 2-D".to_owned(),
});
}
out[0] = params[0];
out[1] = params[1];
Ok(0.5 * (params[0] * params[0] + params[1] * params[1]))
}
}
impl TwiceDifferentiable for Quadratic {
fn hessian_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
if params.len() != 2 || out.len() != 4 {
return Err(GprError::ShapeMismatch {
reason: "quadratic Hessian is 2x2".to_owned(),
});
}
out[0] = 1.0;
out[1] = 0.0;
out[2] = 0.0;
out[3] = 1.0;
Ok(())
}
}
#[test]
fn trust_region_minimizes_quadratic_bowl() {
let mut obj = Quadratic;
let result = TrustRegion::new()
.with_max_iterations(50)
.minimize_unconstrained(&mut obj, &[1.0, -0.5])
.expect("bowl");
assert_close(result.params[0], 0.0, TOL);
assert_close(result.params[1], 0.0, TOL);
assert!(result.value < 1e-12);
}
#[test]
fn trust_region_lowers_gpr_nlml() {
let kernel = KernelSpec::from(RbfKernel::new(1.25).expect("valid"));
let likelihood = GaussianLikelihood::new(0.16).expect("valid");
let x = [0.0, 0.8, 1.7];
let y = [0.4, -0.2, 0.9];
let mut gpr = Gpr::new(kernel, likelihood)
.with_optimizer(Fixed)
.factor(&x, 3, 1, &y)
.unwrap_or_else(|(_, e)| panic!("{e}"));
let mut init = [0.0; 2];
gpr.get_params(&mut init).expect("len 2");
let start;
let result;
{
let mut obj = gpr.objective();
start = obj.value(&init).expect("spd");
result = TrustRegion::new()
.with_max_iterations(30)
.minimize(&mut obj, &init)
.expect("newton");
}
assert!(
result.value < start,
"start={start}, newton={}",
result.value
);
let fitted = Gpr::new(
KernelSpec::from(RbfKernel::new(1.25).expect("valid")),
GaussianLikelihood::new(0.16).expect("valid"),
)
.with_optimizer(TrustRegion::new().with_max_iterations(30))
.fit(&x, 3, 1, &y)
.unwrap_or_else(|(_, e)| panic!("{e}"));
assert!(fitted.neg_log_marginal_likelihood().expect("fitted") < start);
}
struct Sqrt1PlusSquare;
impl Objective for Sqrt1PlusSquare {
fn num_params(&self) -> usize {
1
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
let mut dummy = [0.0; 1];
self.value_and_gradient_into(params, &mut dummy)
}
}
impl Differentiable for Sqrt1PlusSquare {
fn gradient_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
self.value_and_gradient_into(params, out).map(|_| ())
}
fn value_and_gradient_into(
&mut self,
params: &[f64],
out: &mut [f64],
) -> Result<f64, GprError> {
let x = params[0];
if x.abs() > 50.0 {
return Err(GprError::NonFiniteKernelValue);
}
let root = (1.0 + x * x).sqrt();
out[0] = x / root;
Ok(root)
}
}
impl TwiceDifferentiable for Sqrt1PlusSquare {
fn hessian_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
let x = params[0];
out[0] = (1.0 + x * x).powf(-1.5);
Ok(())
}
}
#[test]
fn trust_region_converges_where_the_plain_newton_step_diverges() {
for start in [1.5, 2.0, 4.0, -3.0] {
let mut obj = Sqrt1PlusSquare;
let result = TrustRegion::new()
.with_max_iterations(200)
.minimize_unconstrained(&mut obj, &[start])
.expect("safeguarded newton");
assert_close(result.params[0], 0.0, 1e-6);
}
}
struct NegativeCurvature;
impl Objective for NegativeCurvature {
fn num_params(&self) -> usize {
1
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
Ok(-params[0].cos())
}
}
impl Differentiable for NegativeCurvature {
fn gradient_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
out[0] = params[0].sin();
Ok(())
}
fn value_and_gradient_into(
&mut self,
params: &[f64],
out: &mut [f64],
) -> Result<f64, GprError> {
out[0] = params[0].sin();
Ok(-params[0].cos())
}
}
impl TwiceDifferentiable for NegativeCurvature {
fn hessian_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
out[0] = params[0].cos();
Ok(())
}
}
#[test]
fn trust_region_descends_when_the_hessian_is_not_positive_definite() {
let mut obj = NegativeCurvature;
let result = TrustRegion::new()
.with_max_iterations(200)
.minimize_unconstrained(&mut obj, &[2.0])
.expect("falls back to steepest descent");
assert!(result.value < -0.999, "value {}", result.value);
}
#[test]
fn trust_region_rejects_bad_radii() {
assert!(TrustRegion::new().with_radii(0.0, 1.0).is_err());
assert!(TrustRegion::new().with_radii(2.0, 1.0).is_err());
assert!(TrustRegion::new().with_radii(1.0, f64::INFINITY).is_err());
}
#[derive(Default)]
struct CountingBowl {
separate_gradients: usize,
separate_hessians: usize,
joint: usize,
}
impl Objective for CountingBowl {
fn num_params(&self) -> usize {
2
}
fn value(&mut self, params: &[f64]) -> Result<f64, GprError> {
Ok((params[0] - 0.3).powi(2) + 2.0 * (params[1] + 0.2).powi(2))
}
}
impl Differentiable for CountingBowl {
fn gradient_into(&mut self, params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
self.separate_gradients += 1;
out[0] = 2.0 * (params[0] - 0.3);
out[1] = 4.0 * (params[1] + 0.2);
Ok(())
}
}
impl TwiceDifferentiable for CountingBowl {
fn hessian_into(&mut self, _params: &[f64], out: &mut [f64]) -> Result<(), GprError> {
self.separate_hessians += 1;
out.copy_from_slice(&[2.0, 0.0, 0.0, 4.0]);
Ok(())
}
fn value_gradient_hessian_into(
&mut self,
params: &[f64],
grad: &mut [f64],
hess: &mut [f64],
) -> Result<f64, GprError> {
self.joint += 1;
grad[0] = 2.0 * (params[0] - 0.3);
grad[1] = 4.0 * (params[1] + 0.2);
hess.copy_from_slice(&[2.0, 0.0, 0.0, 4.0]);
self.value(params)
}
}
#[test]
fn trust_region_evaluates_each_candidate_through_the_joint_entry_point() {
let mut bowl = CountingBowl::default();
let result = TrustRegion::new()
.minimize_unconstrained(&mut bowl, &[2.0, 1.0])
.expect("minimize");
assert_close(result.params[0], 0.3, TOL);
assert_close(result.params[1], -0.2, TOL);
assert!(bowl.joint > 0);
assert_eq!(
bowl.separate_hessians, 0,
"a candidate's Hessian is part of the joint call"
);
assert_eq!(
bowl.separate_gradients, 0,
"a candidate's gradient is part of the joint call"
);
}
}