(self, p_k, g_Ok, g_Sk=None, options={})
Performs a single optimization step.

        Inputs:
            p_k (tensor): 1-D tensor specifying search direction
            g_Ok (tensor): 1-D tensor of flattened gradient over overlap O_k used
                            for gradient differencing in curvature pair update
            g_Sk (tensor): 1-D tensor of flattened gradient over full sample S_k
                            used for curvature pair damping or rejection criterion,
                            if None, will use g_Ok (default: None)
            options (dict): contains options for performing line search

        Options for Armijo backtracking line search:
            'closure' (callable): reevaluates model and returns function value
            'current_loss' (tensor): objective value at current iterate (default: F(x_k))
            'gtd' (tensor): inner product g_Ok'd in line search (default: g_Ok'd)
            'eta' (tensor): factor for decreasing steplength > 0 (default: 2)
            'c1' (tensor): sufficient decrease constant in (0, 1) (default: 1e-4)
            'max_ls' (int): maximum number of line search steps permitted (default: 10)
            'interpolate' (bool): flag for using interpolation (default: True)
            'inplace' (bool): flag for inplace operations (default: True)
            'ls_debug' (bool): debugging mode for line search

        Options for Wolfe line search:
            'closure' (callable): reevaluates model and returns function value
            'current_loss' (tensor): objective value at current iterate (default: F(x_k))
            'gtd' (tensor): inner product g_Ok'd in line search (default: g_Ok'd)
            'eta' (float): factor for extrapolation (default: 2)
            'c1' (float): sufficient decrease constant in (0, 1) (default: 1e-4)
            'c2' (float): curvature condition constant in (0, 1) (default: 0.9)
            'max_ls' (int): maximum number of line search steps permitted (default: 10)
            'interpolate' (bool): flag for using interpolation (default: True)
            'inplace' (bool): flag for inplace operations (default: True)
            'ls_debug' (bool): debugging mode for line search

        Outputs (depends on line search):
          . No line search:
                t (float): steplength
          . Armijo backtracking line search:
                F_new (tensor): loss function at new iterate
                t (tensor): final steplength
                ls_step (int): number of backtracks
                closure_eval (int): number of closure evaluations
                desc_dir (bool): descent direction flag
                    True: p_k is descent direction with respect to the line search
                    function
                    False: p_k is not a descent direction with respect to the line
                    search function
                fail (bool): failure flag
                    True: line search reached maximum number of iterations, failed
                    False: line search succeeded
          . Wolfe line search:
                F_new (tensor): loss function at new iterate
                g_new (tensor): gradient at new iterate
                t (float): final steplength
                ls_step (int): number of backtracks
                closure_eval (int): number of closure evaluations
                grad_eval (int): number of gradient evaluations
                desc_dir (bool): descent direction flag
                    True: p_k is descent direction with respect to the line search
                    function
                    False: p_k is not a descent direction with respect to the line
                    search function
                fail (bool): failure flag
                    True: line search reached maximum number of iterations, failed
                    False: line search succeeded

        Notes:
          . If encountering line search failure in the deterministic setting, one
            should try increasing the maximum number of line search steps max_ls.
Performs a single optimization step.
Performs a single optimization step .
def _step(self, p_k, g_Ok, g_Sk=None, options={}):
        """
        Performs a single optimization step.

        Inputs:
            p_k (tensor): 1-D tensor specifying search direction
            g_Ok (tensor): 1-D tensor of flattened gradient over overlap O_k used
                            for gradient differencing in curvature pair update
            g_Sk (tensor): 1-D tensor of flattened gradient over full sample S_k
                            used for curvature pair damping or rejection criterion,
                            if None, will use g_Ok (default: None)
            options (dict): contains options for performing line search

        Options for Armijo backtracking line search:
            'closure' (callable): reevaluates model and returns function value
            'current_loss' (tensor): objective value at current iterate (default: F(x_k))
            'gtd' (tensor): inner product g_Ok'd in line search (default: g_Ok'd)
            'eta' (tensor): factor for decreasing steplength > 0 (default: 2)
            'c1' (tensor): sufficient decrease constant in (0, 1) (default: 1e-4)
            'max_ls' (int): maximum number of line search steps permitted (default: 10)
            'interpolate' (bool): flag for using interpolation (default: True)
            'inplace' (bool): flag for inplace operations (default: True)
            'ls_debug' (bool): debugging mode for line search

        Options for Wolfe line search:
            'closure' (callable): reevaluates model and returns function value
            'current_loss' (tensor): objective value at current iterate (default: F(x_k))
            'gtd' (tensor): inner product g_Ok'd in line search (default: g_Ok'd)
            'eta' (float): factor for extrapolation (default: 2)
            'c1' (float): sufficient decrease constant in (0, 1) (default: 1e-4)
            'c2' (float): curvature condition constant in (0, 1) (default: 0.9)
            'max_ls' (int): maximum number of line search steps permitted (default: 10)
            'interpolate' (bool): flag for using interpolation (default: True)
            'inplace' (bool): flag for inplace operations (default: True)
            'ls_debug' (bool): debugging mode for line search

        Outputs (depends on line search):
          . No line search:
                t (float): steplength
          . Armijo backtracking line search:
                F_new (tensor): loss function at new iterate
                t (tensor): final steplength
                ls_step (int): number of backtracks
                closure_eval (int): number of closure evaluations
                desc_dir (bool): descent direction flag
                    True: p_k is descent direction with respect to the line search
                    function
                    False: p_k is not a descent direction with respect to the line
                    search function
                fail (bool): failure flag
                    True: line search reached maximum number of iterations, failed
                    False: line search succeeded
          . Wolfe line search:
                F_new (tensor): loss function at new iterate
                g_new (tensor): gradient at new iterate
                t (float): final steplength
                ls_step (int): number of backtracks
                closure_eval (int): number of closure evaluations
                grad_eval (int): number of gradient evaluations
                desc_dir (bool): descent direction flag
                    True: p_k is descent direction with respect to the line search
                    function
                    False: p_k is not a descent direction with respect to the line
                    search function
                fail (bool): failure flag
                    True: line search reached maximum number of iterations, failed
                    False: line search succeeded

        Notes:
          . If encountering line search failure in the deterministic setting, one
            should try increasing the maximum number of line search steps max_ls.

        """

        assert len(self.param_groups) == 1

        # load parameter options
        group = self.param_groups[0]
        lr = group['lr']
        line_search = group['line_search']
        dtype = group['dtype']
        debug = group['debug']

        # variables cached in state (for tracing)
        state = self.state['global_state']
        d = state.get('d')
        t = state.get('t')
        prev_flat_grad = state.get('prev_flat_grad')
        Bs = state.get('Bs')

        # keep track of nb of iterations
        state['n_iter'] += 1

        # set search direction
        d = p_k

        # modify previous gradient
        if prev_flat_grad is None:
            prev_flat_grad = g_Ok.clone()
        else:
            prev_flat_grad.copy_(g_Ok)

        # set initial step size
        t = lr

        # closure evaluation counter
        closure_eval = 0

        if g_Sk is None:
            g_Sk = g_Ok.clone()

        # perform Armijo backtracking line search
        if(line_search == 'Armijo'):

            # load options
            if(options):
                if('closure' not in options.keys()):
                    raise(ValueError('closure option not specified.'))
                else:
                    closure = options['closure']

                if('gtd' not in options.keys()):
                    gtd = g_Ok.dot(d)
                else:
                    gtd = options['gtd']

                if('current_loss' not in options.keys()):
                    F_k = closure()
                    closure_eval += 1
                else:
                    F_k = options['current_loss']

                if('eta' not in options.keys()):
                    eta = 2
                elif(options['eta'] <= 0):
                    raise(ValueError('Invalid eta; must be positive.'))
                else:
                    eta = options['eta']

                if('c1' not in options.keys()):
                    c1 = 1e-4
                elif(options['c1'] >= 1 or options['c1'] <= 0):
                    raise(ValueError('Invalid c1; must be strictly between 0 and 1.'))
                else:
                    c1 = options['c1']

                if('max_ls' not in options.keys()):
                    max_ls = 10
                elif(options['max_ls'] <= 0):
                    raise(ValueError('Invalid max_ls; must be positive.'))
                else:
                    max_ls = options['max_ls']

                if('interpolate' not in options.keys()):
                    interpolate = True
                else:
                    interpolate = options['interpolate']

                if('inplace' not in options.keys()):
                    inplace = True
                else:
                    inplace = options['inplace']

                if('ls_debug' not in options.keys()):
                    ls_debug = False
                else:
                    ls_debug = options['ls_debug']

            else:
                raise(ValueError('Options are not specified; need closure evaluating function.'))

            # initialize values
            if(interpolate):
                if(torch.cuda.is_available()):
                    F_prev = torch.tensor(np.nan, dtype=dtype).cuda()
                else:
                    F_prev = torch.tensor(np.nan, dtype=dtype)

            ls_step = 0
            t_prev = 0 # old steplength
            fail = False # failure flag

            # begin print for debug mode
            if ls_debug:
                print('==================================== Begin Armijo line search ===================================')
                print('F(x): %.8e  g*d: %.8e' %(F_k, gtd))

            # check if search direction is descent direction
            if gtd >= 0:
                desc_dir = False
                if debug:
                    print('Not a descent direction!')
            else:
                desc_dir = True

            # store values if not in-place
            if not inplace:
                current_params = self._copy_params()

            # update and evaluate at new point
            self._add_update(t, d)
            F_new = closure()
            closure_eval += 1

            # print info if debugging
            if(ls_debug):
                print('LS Step: %d  t: %.8e  F(x+td): %.8e  F-c1*t*g*d: %.8e  F(x): %.8e'
                      %(ls_step, t, F_new, F_k + c1*t*gtd, F_k))

            # check Armijo condition
            while F_new > F_k + c1*t*gtd or not is_legal(F_new):

                # check if maximum number of iterations reached
                if(ls_step >= max_ls):
                    if inplace:
                        self._add_update(-t, d)
                    else:
                        self._load_params(current_params)

                    t = 0
                    F_new = closure()
                    closure_eval += 1
                    fail = True
                    break

                else:
                    # store current steplength
                    t_new = t

                    # compute new steplength

                    # if first step or not interpolating, then multiply by factor
                    if(ls_step == 0 or not interpolate or not is_legal(F_new)):
                        t = t/eta

                    # if second step, use function value at new point along with
                    # gradient and function at current iterate
                    elif(ls_step == 1 or not is_legal(F_prev)):
                        t = polyinterp(np.array([[0, F_k.item(), gtd.item()], [t_new, F_new.item(), np.nan]]))

                    # otherwise, use function values at new point, previous point,
                    # and gradient and function at current iterate
                    else:
                        t = polyinterp(np.array([[0, F_k.item(), gtd.item()], [t_new, F_new.item(), np.nan],
                                                [t_prev, F_prev.item(), np.nan]]))

                    # if values are too extreme, adjust t
                    if(interpolate):
                        if(t < 1e-3*t_new):
                            t = 1e-3*t_new
                        elif(t > 0.6*t_new):
                            t = 0.6*t_new

                        # store old point
                        F_prev = F_new
                        t_prev = t_new

                    # update iterate and reevaluate
                    if inplace:
                        self._add_update(t-t_new, d)
                    else:
                        self._load_params(current_params)
                        self._add_update(t, d)

                    F_new = closure()
                    closure_eval += 1
                    ls_step += 1 # iterate

                    # print info if debugging
                    if(ls_debug):
                        print('LS Step: %d  t: %.8e  F(x+td):   %.8e  F-c1*t*g*d: %.8e  F(x): %.8e'
                              %(ls_step, t, F_new, F_k + c1*t*gtd, F_k))

            # store Bs
            if Bs is None:
                Bs = (g_Sk.mul(-t)).clone()
            else:
                Bs.copy_(g_Sk.mul(-t))

            # print final steplength
            if ls_debug:
                print('Final Steplength:', t)
                print('===================================== End Armijo line search ====================================')

            state['d'] = d
            state['prev_flat_grad'] = prev_flat_grad
            state['t'] = t
            state['Bs'] = Bs
            state['fail'] = fail

            return F_new, t, ls_step, closure_eval, desc_dir, fail

        # perform weak Wolfe line search
        elif(line_search == 'Wolfe'):

            # load options
            if(options):
                if('closure' not in options.keys()):
                    raise(ValueError('closure option not specified.'))
                else:
                    closure = options['closure']

                if('current_loss' not in options.keys()):
                    F_k = closure()
                    closure_eval += 1
                else:
                    F_k = options['current_loss']

                if('gtd' not in options.keys()):
                    gtd = g_Ok.dot(d)
                else:
                    gtd = options['gtd']

                if('eta' not in options.keys()):
                    eta = 2
                elif(options['eta'] <= 1):
                    raise(ValueError('Invalid eta; must be greater than 1.'))
                else:
                    eta = options['eta']

                if('c1' not in options.keys()):
                    c1 = 1e-4
                elif(options['c1'] >= 1 or options['c1'] <= 0):
                    raise(ValueError('Invalid c1; must be strictly between 0 and 1.'))
                else:
                    c1 = options['c1']

                if('c2' not in options.keys()):
                    c2 = 0.9
                elif(options['c2'] >= 1 or options['c2'] <= 0):
                    raise(ValueError('Invalid c2; must be strictly between 0 and 1.'))
                elif(options['c2'] <= c1):
                    raise(ValueError('Invalid c2; must be strictly larger than c1.'))
                else:
                    c2 = options['c2']

                if('max_ls' not in options.keys()):
                    max_ls = 10
                elif(options['max_ls'] <= 0):
                    raise(ValueError('Invalid max_ls; must be positive.'))
                else:
                    max_ls = options['max_ls']

                if('interpolate' not in options.keys()):
                    interpolate = True
                else:
                    interpolate = options['interpolate']

                if('inplace' not in options.keys()):
                    inplace = True
                else:
                    inplace = options['inplace']

                if('ls_debug' not in options.keys()):
                    ls_debug = False
                else:
                    ls_debug = options['ls_debug']

            else:
                raise(ValueError('Options are not specified; need closure evaluating function.'))

            # initialize counters
            ls_step = 0
            grad_eval = 0 # tracks gradient evaluations
            t_prev = 0 # old steplength

            # initialize bracketing variables and flag
            alpha = 0
            beta = float('Inf')
            fail = False

            # initialize values for line search
            if(interpolate):
                F_a = F_k
                g_a = gtd

                if(torch.cuda.is_available()):
                    F_b = torch.tensor(np.nan, dtype=dtype).cuda()
                    g_b = torch.tensor(np.nan, dtype=dtype).cuda()
                else:
                    F_b = torch.tensor(np.nan, dtype=dtype)
                    g_b = torch.tensor(np.nan, dtype=dtype)

            # begin print for debug mode
            if ls_debug:
                print('==================================== Begin Wolfe line search ====================================')
                print('F(x): %.8e  g*d: %.8e' %(F_k, gtd))

            # check if search direction is descent direction
            if gtd >= 0:
                desc_dir = False
                if debug:
                    print('Not a descent direction!')
            else:
                desc_dir = True

            # store values if not in-place
            if not inplace:
                current_params = self._copy_params()

            # update and evaluate at new point
            self._add_update(t, d)
            F_new = closure()
            closure_eval += 1

            # main loop
            while True:

                # check if maximum number of line search steps have been reached
                if(ls_step >= max_ls):
                    if inplace:
                        self._add_update(-t, d)
                    else:
                        self._load_params(current_params)

                    t = 0
                    F_new = closure()
                    F_new.backward()
                    g_new = self._gather_flat_grad()
                    closure_eval += 1
                    grad_eval += 1
                    fail = True
                    break

                # print info if debugging
                if(ls_debug):
                    print('LS Step: %d  t: %.8e  alpha: %.8e  beta: %.8e'
                          %(ls_step, t, alpha, beta))
                    print('Armijo:  F(x+td): %.8e  F-c1*t*g*d: %.8e  F(x): %.8e'
                          %(F_new, F_k + c1*t*gtd, F_k))

                # check Armijo condition
                if(F_new > F_k + c1*t*gtd):

                    # set upper bound
                    beta = t
                    t_prev = t

                    # update interpolation quantities
                    if(interpolate):
                        F_b = F_new
                        if(torch.cuda.is_available()):
                            g_b = torch.tensor(np.nan, dtype=dtype).cuda()
                        else:
                            g_b = torch.tensor(np.nan, dtype=dtype)

                else:

                    # compute gradient
                    F_new.backward()
                    g_new = self._gather_flat_grad()
                    grad_eval += 1
                    gtd_new = g_new.dot(d)

                    # print info if debugging
                    if(ls_debug):
                        print('Wolfe: g(x+td)*d: %.8e  c2*g*d: %.8e  gtd: %.8e'
                              %(gtd_new, c2*gtd, gtd))

                    # check curvature condition
                    if(gtd_new < c2*gtd):

                        # set lower bound
                        alpha = t
                        t_prev = t

                        # update interpolation quantities
                        if(interpolate):
                            F_a = F_new
                            g_a = gtd_new

                    else:
                        break

                # compute new steplength

                # if first step or not interpolating, then bisect or multiply by factor
                if(not interpolate or not is_legal(F_b)):
                    if(beta == float('Inf')):
                        t = eta*t
                    else:
                        t = (alpha + beta)/2.0

                # otherwise interpolate between a and b
                else:
                    t = polyinterp(np.array([[alpha, F_a.item(), g_a.item()],[beta, F_b.item(), g_b.item()]]))

                    # if values are too extreme, adjust t
                    if(beta == float('Inf')):
                        if(t > 2*eta*t_prev):
                            t = 2*eta*t_prev
                        elif(t < eta*t_prev):
                            t = eta*t_prev
                    else:
                        if(t < alpha + 0.2*(beta - alpha)):
                            t = alpha + 0.2*(beta - alpha)
                        elif(t > (beta - alpha)/2.0):
                            t = (beta - alpha)/2.0

                    # if we obtain nonsensical value from interpolation
                    if(t <= 0):
                        t = (beta - alpha)/2.0

                # update parameters
                if inplace:
                    self._add_update(t - t_prev, d)
                else:
                    self._load_params(current_params)
                    self._add_update(t, d)

                # evaluate closure
                F_new = closure()
                closure_eval += 1
                ls_step += 1

            # store Bs
            if Bs is None:
                Bs = (g_Sk.mul(-t)).clone()
            else:
                Bs.copy_(g_Sk.mul(-t))

            # print final steplength
            if ls_debug:
                print('Final Steplength:', t)
                print('===================================== End Wolfe line search =====================================')

            state['d'] = d
            state['prev_flat_grad'] = prev_flat_grad
            state['t'] = t
            state['Bs'] = Bs
            state['fail'] = fail

            return F_new, g_new, t, ls_step, closure_eval, grad_eval, desc_dir, fail

        else:

            # perform update
            self._add_update(t, d)

            # store Bs
            if Bs is None:
                Bs = (g_Sk.mul(-t)).clone()
            else:
                Bs.copy_(g_Sk.mul(-t))

            state['d'] = d
            state['prev_flat_grad'] = prev_flat_grad
            state['t'] = t
            state['Bs'] = Bs
            state['fail'] = False

            return t
def _step ( self , p_k , g_Ok , g_Sk = None , options = { } ) : assert len ( self . param_groups ) == 1 # load parameter options group = self . param_groups [ 0 ] lr = group [ 'lr' ] line_search = group [ 'line_search' ] dtype = group [ 'dtype' ] debug = group [ 'debug' ] # variables cached in state (for tracing) state = self . state [ 'global_state' ] d = state . get ( 'd' ) t = state . get ( 't' ) prev_flat_grad = state . get ( 'prev_flat_grad' ) Bs = state . get ( 'Bs' ) # keep track of nb of iterations state [ 'n_iter' ] += 1 # set search direction d = p_k # modify previous gradient if prev_flat_grad is None : prev_flat_grad = g_Ok . clone ( ) else : prev_flat_grad . copy_ ( g_Ok ) # set initial step size t = lr # closure evaluation counter closure_eval = 0 if g_Sk is None : g_Sk = g_Ok . clone ( ) # perform Armijo backtracking line search if ( line_search == 'Armijo' ) : # load options if ( options ) : if ( 'closure' not in options . keys ( ) ) : raise ( ValueError ( 'closure option not specified.' ) ) else : closure = options [ 'closure' ] if ( 'gtd' not in options . keys ( ) ) : gtd = g_Ok . dot ( d ) else : gtd = options [ 'gtd' ] if ( 'current_loss' not in options . keys ( ) ) : F_k = closure ( ) closure_eval += 1 else : F_k = options [ 'current_loss' ] if ( 'eta' not in options . keys ( ) ) : eta = 2 elif ( options [ 'eta' ] <= 0 ) : raise ( ValueError ( 'Invalid eta; must be positive.' ) ) else : eta = options [ 'eta' ] if ( 'c1' not in options . keys ( ) ) : c1 = 1e-4 elif ( options [ 'c1' ] >= 1 or options [ 'c1' ] <= 0 ) : raise ( ValueError ( 'Invalid c1; must be strictly between 0 and 1.' ) ) else : c1 = options [ 'c1' ] if ( 'max_ls' not in options . keys ( ) ) : max_ls = 10 elif ( options [ 'max_ls' ] <= 0 ) : raise ( ValueError ( 'Invalid max_ls; must be positive.' ) ) else : max_ls = options [ 'max_ls' ] if ( 'interpolate' not in options . keys ( ) ) : interpolate = True else : interpolate = options [ 'interpolate' ] if ( 'inplace' not in options . keys ( ) ) : inplace = True else : inplace = options [ 'inplace' ] if ( 'ls_debug' not in options . keys ( ) ) : ls_debug = False else : ls_debug = options [ 'ls_debug' ] else : raise ( ValueError ( 'Options are not specified; need closure evaluating function.' ) ) # initialize values if ( interpolate ) : if ( torch . cuda . is_available ( ) ) : F_prev = torch . tensor ( np . nan , dtype = dtype ) . cuda ( ) else : F_prev = torch . tensor ( np . nan , dtype = dtype ) ls_step = 0 t_prev = 0 # old steplength fail = False # failure flag # begin print for debug mode if ls_debug : print ( '==================================== Begin Armijo line search ===================================' ) print ( 'F(x): %.8e  g*d: %.8e' % ( F_k , gtd ) ) # check if search direction is descent direction if gtd >= 0 : desc_dir = False if debug : print ( 'Not a descent direction!' ) else : desc_dir = True # store values if not in-place if not inplace : current_params = self . _copy_params ( ) # update and evaluate at new point self . _add_update ( t , d ) F_new = closure ( ) closure_eval += 1 # print info if debugging if ( ls_debug ) : print ( 'LS Step: %d  t: %.8e  F(x+td): %.8e  F-c1*t*g*d: %.8e  F(x): %.8e' % ( ls_step , t , F_new , F_k + c1 * t * gtd , F_k ) ) # check Armijo condition while F_new > F_k + c1 * t * gtd or not is_legal ( F_new ) : # check if maximum number of iterations reached if ( ls_step >= max_ls ) : if inplace : self . _add_update ( - t , d ) else : self . _load_params ( current_params ) t = 0 F_new = closure ( ) closure_eval += 1 fail = True break else : # store current steplength t_new = t # compute new steplength # if first step or not interpolating, then multiply by factor if ( ls_step == 0 or not interpolate or not is_legal ( F_new ) ) : t = t / eta # if second step, use function value at new point along with # gradient and function at current iterate elif ( ls_step == 1 or not is_legal ( F_prev ) ) : t = polyinterp ( np . array ( [ [ 0 , F_k . item ( ) , gtd . item ( ) ] , [ t_new , F_new . item ( ) , np . nan ] ] ) ) # otherwise, use function values at new point, previous point, # and gradient and function at current iterate else : t = polyinterp ( np . array ( [ [ 0 , F_k . item ( ) , gtd . item ( ) ] , [ t_new , F_new . item ( ) , np . nan ] , [ t_prev , F_prev . item ( ) , np . nan ] ] ) ) # if values are too extreme, adjust t if ( interpolate ) : if ( t < 1e-3 * t_new ) : t = 1e-3 * t_new elif ( t > 0.6 * t_new ) : t = 0.6 * t_new # store old point F_prev = F_new t_prev = t_new # update iterate and reevaluate if inplace : self . _add_update ( t - t_new , d ) else : self . _load_params ( current_params ) self . _add_update ( t , d ) F_new = closure ( ) closure_eval += 1 ls_step += 1 # iterate # print info if debugging if ( ls_debug ) : print ( 'LS Step: %d  t: %.8e  F(x+td):   %.8e  F-c1*t*g*d: %.8e  F(x): %.8e' % ( ls_step , t , F_new , F_k + c1 * t * gtd , F_k ) ) # store Bs if Bs is None : Bs = ( g_Sk . mul ( - t ) ) . clone ( ) else : Bs . copy_ ( g_Sk . mul ( - t ) ) # print final steplength if ls_debug : print ( 'Final Steplength:' , t ) print ( '===================================== End Armijo line search ====================================' ) state [ 'd' ] = d state [ 'prev_flat_grad' ] = prev_flat_grad state [ 't' ] = t state [ 'Bs' ] = Bs state [ 'fail' ] = fail return F_new , t , ls_step , closure_eval , desc_dir , fail # perform weak Wolfe line search elif ( line_search == 'Wolfe' ) : # load options if ( options ) : if ( 'closure' not in options . keys ( ) ) : raise ( ValueError ( 'closure option not specified.' ) ) else : closure = options [ 'closure' ] if ( 'current_loss' not in options . keys ( ) ) : F_k = closure ( ) closure_eval += 1 else : F_k = options [ 'current_loss' ] if ( 'gtd' not in options . keys ( ) ) : gtd = g_Ok . dot ( d ) else : gtd = options [ 'gtd' ] if ( 'eta' not in options . keys ( ) ) : eta = 2 elif ( options [ 'eta' ] <= 1 ) : raise ( ValueError ( 'Invalid eta; must be greater than 1.' ) ) else : eta = options [ 'eta' ] if ( 'c1' not in options . keys ( ) ) : c1 = 1e-4 elif ( options [ 'c1' ] >= 1 or options [ 'c1' ] <= 0 ) : raise ( ValueError ( 'Invalid c1; must be strictly between 0 and 1.' ) ) else : c1 = options [ 'c1' ] if ( 'c2' not in options . keys ( ) ) : c2 = 0.9 elif ( options [ 'c2' ] >= 1 or options [ 'c2' ] <= 0 ) : raise ( ValueError ( 'Invalid c2; must be strictly between 0 and 1.' ) ) elif ( options [ 'c2' ] <= c1 ) : raise ( ValueError ( 'Invalid c2; must be strictly larger than c1.' ) ) else : c2 = options [ 'c2' ] if ( 'max_ls' not in options . keys ( ) ) : max_ls = 10 elif ( options [ 'max_ls' ] <= 0 ) : raise ( ValueError ( 'Invalid max_ls; must be positive.' ) ) else : max_ls = options [ 'max_ls' ] if ( 'interpolate' not in options . keys ( ) ) : interpolate = True else : interpolate = options [ 'interpolate' ] if ( 'inplace' not in options . keys ( ) ) : inplace = True else : inplace = options [ 'inplace' ] if ( 'ls_debug' not in options . keys ( ) ) : ls_debug = False else : ls_debug = options [ 'ls_debug' ] else : raise ( ValueError ( 'Options are not specified; need closure evaluating function.' ) ) # initialize counters ls_step = 0 grad_eval = 0 # tracks gradient evaluations t_prev = 0 # old steplength # initialize bracketing variables and flag alpha = 0 beta = float ( 'Inf' ) fail = False # initialize values for line search if ( interpolate ) : F_a = F_k g_a = gtd if ( torch . cuda . is_available ( ) ) : F_b = torch . tensor ( np . nan , dtype = dtype ) . cuda ( ) g_b = torch . tensor ( np . nan , dtype = dtype ) . cuda ( ) else : F_b = torch . tensor ( np . nan , dtype = dtype ) g_b = torch . tensor ( np . nan , dtype = dtype ) # begin print for debug mode if ls_debug : print ( '==================================== Begin Wolfe line search ====================================' ) print ( 'F(x): %.8e  g*d: %.8e' % ( F_k , gtd ) ) # check if search direction is descent direction if gtd >= 0 : desc_dir = False if debug : print ( 'Not a descent direction!' ) else : desc_dir = True # store values if not in-place if not inplace : current_params = self . _copy_params ( ) # update and evaluate at new point self . _add_update ( t , d ) F_new = closure ( ) closure_eval += 1 # main loop while True : # check if maximum number of line search steps have been reached if ( ls_step >= max_ls ) : if inplace : self . _add_update ( - t , d ) else : self . _load_params ( current_params ) t = 0 F_new = closure ( ) F_new . backward ( ) g_new = self . _gather_flat_grad ( ) closure_eval += 1 grad_eval += 1 fail = True break # print info if debugging if ( ls_debug ) : print ( 'LS Step: %d  t: %.8e  alpha: %.8e  beta: %.8e' % ( ls_step , t , alpha , beta ) ) print ( 'Armijo:  F(x+td): %.8e  F-c1*t*g*d: %.8e  F(x): %.8e' % ( F_new , F_k + c1 * t * gtd , F_k ) ) # check Armijo condition if ( F_new > F_k + c1 * t * gtd ) : # set upper bound beta = t t_prev = t # update interpolation quantities if ( interpolate ) : F_b = F_new if ( torch . cuda . is_available ( ) ) : g_b = torch . tensor ( np . nan , dtype = dtype ) . cuda ( ) else : g_b = torch . tensor ( np . nan , dtype = dtype ) else : # compute gradient F_new . backward ( ) g_new = self . _gather_flat_grad ( ) grad_eval += 1 gtd_new = g_new . dot ( d ) # print info if debugging if ( ls_debug ) : print ( 'Wolfe: g(x+td)*d: %.8e  c2*g*d: %.8e  gtd: %.8e' % ( gtd_new , c2 * gtd , gtd ) ) # check curvature condition if ( gtd_new < c2 * gtd ) : # set lower bound alpha = t t_prev = t # update interpolation quantities if ( interpolate ) : F_a = F_new g_a = gtd_new else : break # compute new steplength # if first step or not interpolating, then bisect or multiply by factor if ( not interpolate or not is_legal ( F_b ) ) : if ( beta == float ( 'Inf' ) ) : t = eta * t else : t = ( alpha + beta ) / 2.0 # otherwise interpolate between a and b else : t = polyinterp ( np . array ( [ [ alpha , F_a . item ( ) , g_a . item ( ) ] , [ beta , F_b . item ( ) , g_b . item ( ) ] ] ) ) # if values are too extreme, adjust t if ( beta == float ( 'Inf' ) ) : if ( t > 2 * eta * t_prev ) : t = 2 * eta * t_prev elif ( t < eta * t_prev ) : t = eta * t_prev else : if ( t < alpha + 0.2 * ( beta - alpha ) ) : t = alpha + 0.2 * ( beta - alpha ) elif ( t > ( beta - alpha ) / 2.0 ) : t = ( beta - alpha ) / 2.0 # if we obtain nonsensical value from interpolation if ( t <= 0 ) : t = ( beta - alpha ) / 2.0 # update parameters if inplace : self . _add_update ( t - t_prev , d ) else : self . _load_params ( current_params ) self . _add_update ( t , d ) # evaluate closure F_new = closure ( ) closure_eval += 1 ls_step += 1 # store Bs if Bs is None : Bs = ( g_Sk . mul ( - t ) ) . clone ( ) else : Bs . copy_ ( g_Sk . mul ( - t ) ) # print final steplength if ls_debug : print ( 'Final Steplength:' , t ) print ( '===================================== End Wolfe line search =====================================' ) state [ 'd' ] = d state [ 'prev_flat_grad' ] = prev_flat_grad state [ 't' ] = t state [ 'Bs' ] = Bs state [ 'fail' ] = fail return F_new , g_new , t , ls_step , closure_eval , grad_eval , desc_dir , fail else : # perform update self . _add_update ( t , d ) # store Bs if Bs is None : Bs = ( g_Sk . mul ( - t ) ) . clone ( ) else : Bs . copy_ ( g_Sk . mul ( - t ) ) state [ 'd' ] = d state [ 'prev_flat_grad' ] = prev_flat_grad state [ 't' ] = t state [ 'Bs' ] = Bs state [ 'fail' ] = False return t