scipy: BUG: #18481 made BFGS minimization less accurate

Describe your issue.

#18481 appears to have made BFGS minimization less accurate. We noticed this in the JAX upstream nightly tests, which began failing after #18481 was merged: https://github.com/google/jax/actions/workflows/upstream-nightly.yaml

I suspect the dtype changes in approx_derivative are to blame.

Reproducing Code Example

import numpy as np
import scipy

def func(p):
    x, y = p
    return (x ** 2 + y - 11.) ** 2 + (x + y ** 2 - 7.) ** 2

x0 = np.ones(2, dtype='float32')
result = scipy.optimize.minimize(func, x0, method='BFGS')

print(f"{scipy.__version__=}")
print(result)
np.testing.assert_allclose(result.x, [3, 2])

Error message

Output before #18481:

scipy.__version__='1.11.1'
  message: Optimization terminated successfully.
  success: True
   status: 0
      fun: 2.288511533827582e-15
        x: [ 3.000e+00  2.000e+00]
      nit: 8
      jac: [-1.907e-08  2.738e-08]
 hess_inv: [[ 1.612e-02 -9.549e-03]
            [-9.549e-03  3.517e-02]]
     nfev: 39
     njev: 13

Output after #18481:

scipy.__version__='1.12.0.dev0+1440.64be173'
  message: Desired error not necessarily achieved due to precision loss.
  success: False
   status: 2
      fun: 9.628441344453949e-06
        x: [ 3.000e+00  2.000e+00]
      nit: 6
      jac: [ 6.255e-04  2.977e-04]
 hess_inv: [[ 1.615e-02 -9.191e-03]
            [-9.191e-03  3.561e-02]]
     nfev: 291
     njev: 70
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-1-d421a22eaf1d> in <cell line: 13>()
     11 result = scipy.optimize.minimize(func, x0, method='BFGS')
     12 print(result)
---> 13 np.testing.assert_allclose(result.x, [3, 2])

/usr/lib/python3.10/contextlib.py in inner(*args, **kwds)
     77         def inner(*args, **kwds):
     78             with self._recreate_cm():
---> 79                 return func(*args, **kwds)
     80         return inner
     81 

/usr/local/lib/python3.10/dist-packages/numpy/testing/_private/utils.py in assert_array_compare(comparison, x, y, err_msg, verbose, header, precision, equal_nan, equal_inf, strict)
    795                                 verbose=verbose, header=header,
    796                                 names=('x', 'y'), precision=precision)
--> 797             raise AssertionError(msg)
    798     except ValueError:
    799         import traceback

AssertionError: 
Not equal to tolerance rtol=1e-07, atol=0

Mismatched elements: 2 / 2 (100%)
Max absolute difference: 0.00049761
Max relative difference: 0.00016587
 x: array([2.999502, 1.999956])
 y: array([3, 2])

SciPy/NumPy/Python version and system information

The error is seen on the nightly scipy version:

$ pip install -i https://pypi.anaconda.org/scientific-python-nightly-wheels/simple --pre -U scipy

About this issue

  • Original URL
  • State: closed
  • Created a year ago
  • Reactions: 1
  • Comments: 18 (18 by maintainers)

Most upvoted comments

I’m guessing that judicious improvement of amin, xtol in line_search_wolfe1 and scalar_search_wolfe1 might improve the situation somewhat.

It looks like the default amin is approximately np.sqrt(np.finfo(np.float64).eps) (1.49e-8), the value in the linesearch code is 1e-8.

xtol seems to be an order of magnitude larger than np.finfo(np.float64).resolution. The default value used in linesearch is 1e-14, but float64 resolution is 1e-15.

If my assumptions are correct it might be possible to adjust the line-search code to account for float precision. We need advice from someone who is familiar with linesearches though, this is not my area of expertise.

In addition, bfgs calls the linesearch code with an amin=1e-100, which is too small to be represented by float32 (smallest number is 1.175494e-38). I don’t know the rationale for choosing amin and amax to be very small and very large.

From what I can tell of the fortran code in minpack2 there’s nothing exploiting floating point precision in there. @ilayn, it looks like this minpack2 code should be relatively straightforward to port from Fortran to Python. There’s only one goto.

By judicious use of print debugging the logic flow the callstack is:

  • _optimize._minimize_bfgs -> _optimize._line_search_wolfe12 -> _linesearch.line_search_wolfe1, _linesearch.scalar_search_wolfe1. The last function calls out to minpack2.dcsrch.

When the overall optimisation first starts minpack2.dcsrch returns task values of b'CONVERGENCE', with finite values for stp. After several top level iterations minpack2.dcsrch returns a task of b'WARNING: ROUNDING ERRORS PREVENT PROGRESS'. At this point the linesearch is regarded to have failed, see here and here, with _optimize.line_search_wolfe12 returning None. BFGS tries to fallback to _linesearch.line_search_wolfe2, but this fails as well. At this point the optimisation halts, and you get the top level minimisation halting.

Thus, the rounding errors seem to prevent BFGS working properly.

There are a few possible solutions:

  • back out the changes made in #18481
  • intercept x0 in BFGS and make sure we use float64 internally in that minimize method
  • try and change the linesearch code to work more easily with float32

At the current time I think BFGS and CG are going to be susceptible to this issue.