Levin Tree Search with Context Models
1 Line search for convex minimization
convex-line-search
quasi-exact-line-search
pt
ptg
8.12

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.