Levin Tree Search with Context Models

8.16.0.1

Levin Tree Search with Context Models🔗ℹ

lorseau

(require lts-cm)

package: levintreesearch_cm

See the README for introductory examples for the LTS+CM algorithm on several domains such as Rubik’s cube and Sokooban.

1 Line search for convex minimization🔗ℹ

(require lts-cm/delta-secant)

package: levintreesearch_cm

This module implements the Δ-Secant line search algorithm for the paper “Line Search for Convex Minimization”.

The function convex-line-search returns the lowest point found of a given convex function between two initial points when a stopping criterion is satisfied.

The function quasi-exact-line-search build upon convex-line-search to ensure sufficient progress is made, and is intended to be used within an optimization algorithm such as gradient descent or Frank-Wolfe.

procedure
(convex-line-search f
xleft
xright
[ #:yleft yleft
#:xq xq
#:yq yq
#:y-tolerance real?
#:stop-when stop-when
#:callback callback]) → dict?
  f : (-> real? real?)
  xleft : real?
  xright : real?
  yleft : real? = (f xleft)
  xq : real? = (* 0.5 (+ xleft xright))
  yq : real? = (f xq)
  real? : y-tolerance = 1e-10
   stop-when : (-> dict? any/c)
= (λ (dic) (<= (dict-ref dic 'ygap) y-tolerance))
  callback : (-> dict? any/c) = (λ (dic) (void))

The function f is assumed convex between xleft and xright, and the behaviour is undefined otherwise. Assume that y* = f(x*) = min_x f(x) is the minimum of f on the interval [xleft, xright].

This function returns a dictionary of values with the following keys:

'iter: Number of iterations performed.
'xlow and 'ylow: lowest point found — usually these are the quantities of interest.
'xgap and 'ygap: upper bounds on |xlow - x*| and |ylow - x*|.
'x- and 'x+: x-interval containing x*.
'ya and 'yb: The minimum of these two values is a lower bound on y*.
'pts: The 5 points around x*. See paper.

The arguments yleft and yq MUST be equal to (f xleft) and (f xq).

The argument xq is the first point within [xleft, xright] to be queried.

The argument stop-when controls when the algorithm should terminate. By default, it terminates when the y-distance to the minimum ('ygap) is provably less than y-tolerance.

The argument callback can be used to monitor the progress of the line search.

Examples:

> (convex-line-search (λ (x) (sqr (- x 1))) -2 5)
(list
'(iter . 23)
(list
  'pts
  (pt 0.9999892887337545 1.1473122458246348e-10)
  (pt 0.9999966814872121 1.1012527123440112e-11)
  (pt 1.0000016825306512 2.8309093923890705e-12)
  (pt 1.0000135688568499 1.8411387621275733e-10)
  (pt 1.000055351641258 3.063804189957421e-9))
'(x- . 0.9999972646480525)
'(x+ . 1.0000109385368174)
'(xgap . 1.3673888764942355e-5)
'(ya . -2.9452989812498634e-11)
'(yb . -1.1960640832144743e-11)
'(ygap . 3.2283899204887706e-11)
'(xlow . 1.0000016825306512)
'(ylow . 2.8309093923890705e-12))
> (define (keep-keys dic keys) (filter (λ (l) (memq (car l) keys)) dic))
> (keep-keys (convex-line-search (λ (x) (sqr (- x 1))) -2 5 #:y-tolerance 0.01)
             '(iter xlow ylow y-gap))
'((iter . 7) (xlow . 1.0095288532116586) (ylow . 9.079904352933715e-5))
> (keep-keys
   (convex-line-search (λ (x) (max (sqr (- x 1)) (sqr (+ x 1)))) -2 5)
   '(iter xlow ylow xgap ygap))
'((iter . 15)
  (xgap . 1.5371377058688084e-11)
  (ygap . 9.722889160457271e-12)
  (xlow . -2.796517824676535e-12)
  (ylow . 1.0000000000055929))

procedure
(quasi-exact-line-search f
[ xleft
xright
#:yleft yleft
#:xq xq
#:yq yq
#:jac^2 jac^2
#:c c
#:callback callback]) → dict?
  f : (-> real? real?)
  xleft : real? = 0.0
  xright : real? = 1.0
  yleft : real? = (f xleft)
  xq : real? = (* 0.5 (+ xleft xright))
  yq : real? = (f xq)
  jac^2 : (or/c #f positive-real?) = #f
  c : positive-real? = 1.0
  callback : (-> dict? any/c) = (λ (dic) (void))

Like convex-line-search but the argument c controls how close to the minimum the returned value ylow (within the returned dictionary) should be compared to the initial value yleft; more precisely, we have ylow - y* ≤ c(yleft - ylow).

Moreover, by contrast to convex-line-search, if the minimum is found to be at xright, the range [xleft, xright] is quadrupled to the right and the line search continues, and so on. This means that for example the call (quasi-exact-line-search / 1 2) loops forever. To prevent this quadrupling behaviour, one can force the function f to be increasing at xright, for eaxmple with (λ (x) (if (< x 2) (/ x) +inf.0)) instead of /.

The argument jac^2, if provided, should be the squared 2-norm of the jacobian (aka the gradient or derivative) at xleft. This information may be used to speed up the search.

See convex-line-search for the description of the returned dictionary, and of the other arguments.

Example:

> (for/list ([c '(1 10 100)])
    (keep-keys
     (quasi-exact-line-search (λ (x) (sqr (- x 1))) -2 5 #:c c)
     '(iter xlow ylow)))
'(((iter . 2) (xlow . 1.47265625) (ylow . 0.2234039306640625))
  ((iter . 4) (xlow . 0.7788681457319648) (ylow . 0.04889929697201954))
  ((iter . 6) (xlow . 1.0095288532116586) (ylow . 9.079904352933715e-5)))

struct
(struct pt (x y))
  x : real?
  y : real?
struct
(struct ptg pt (g))
  g : real?

Points without and with gradient. May be used in the 'pts entry of the return dictionaries of convex-line-search and quasi-exact-line-search.