# Line Search

Choosing how far to move along a chosen descent direction, either exactly or by accepting the first step that improves the objective sufficiently.

**Rests on:** Gradient Descent

*Mathematical Foundations · Optimization*


## Why learn this

This concept solves the practical problem of deciding how big a step to take when you are trying to improve a situation mathematically. Imagine you are adjusting the volume on a stereo system to get the clearest sound. You know which direction turns the knob toward better sound, but if you turn it too far, you overshoot and the sound gets worse again. Line search is the method for choosing exactly how much to turn that knob. Without it, algorithms either crawl forward at a snail’s pace or jump wildly out of control. By understanding this step, you gain immediate control over whether a calculation settles into a good answer or crashes. It is the critical bridge between knowing which way to go and actually getting there efficiently.


## The intuition

Imagine standing on a foggy hillside where you need to reach the lowest point in the valley. You can feel the slope under your feet, which tells you the direction of steepest downhill. This steepness is the gradient. But the slope’s direction alone does not tell you how far to walk. If you take a tiny step, you will be walking all day with little progress. If you take a huge step, you might stride past the valley floor and end up on the opposite hillside, higher than where you started. This is what happens when the loss (a number measuring how wrong your current answer is) increases instead of decreases. Line search answers the question: 'How far along this downhill path should I go?' One extreme is to calculate the exact spot that is lowest in this direction—this is called exact line search. The more practical approach is backtracking line search. Here, you take a tentative step, check if the loss has decreased sufficiently using a rule called the Armijo condition, and if it hasn’t dropped enough, you shrink your step and try again. You keep shrinking the step until the drop in loss meets the requirement. This 'try, check, shrink' cycle ensures you make steady progress without wasting time or overshooting.


## An analogy

Think of adjusting a thermostat to find the perfect room temperature. You know whether the room is too hot or too cold, so you know which way to turn the dial. However, turning it fully to one side might make the room much worse before it gets better. You turn the dial a small amount, then wait to see if the temperature is improving. If it is close enough to your target, you stop and leave it there. If not, you turn it a bit more in the same direction or shrink the adjustment and check again. This mirrors backtracking line search: you propose an adjustment size, measure the result against a sufficient improvement threshold, and reduce the size if needed. The analogy breaks down because a room has only one temperature setting, whereas optimizing a complex model involves millions of variables simultaneously, making the 'dial' impossible to scan completely; thus, you must rely on these local checks rather than a full search.


## Definition

Line search is a method for determining the appropriate step size in an optimization algorithm by evaluating progress along a chosen direction and adjusting the distance until a sufficient decrease in error is achieved.


## How it connects

This concept works hand-in-hand with Gradient Descent, which is the technique of moving in the direction opposite to the gradient (the steepest slope) to minimize error. While Gradient Descent identifies the path, line search determines how many units of distance to cover on that path. It also relates directly to Hyperparameter Tuning, as the maximum initial step size used in this process is a key setting you often adjust manually to ensure stability.


## The mathematics

Line search is a step in optimization algorithms used to find the minimum of a function. Optimization means finding the input values that make a function as small as possible. In machine learning, this function is often called the loss or objective function.

Imagine you are standing on a hill and want to get to the bottom. You look around and decide which way is downhill; this direction is called the descent direction, denoted by d. Now you need to decide how far to walk in that direction. This distance is called the step size, denoted by t.

The goal of line search is to find a positive number t such that moving from your current position x by t times the direction d results in a lower function value. Mathematically, we want:
f(x + t * d) < f(x)

There are two main ways to choose t:

1. Exact Line Search: This tries to find the single best t that makes f(x + t * d) as small as possible along the entire line. This is often too difficult or slow to calculate for complex functions.

2. Backtracking Line Search (Armijo Condition): This is a practical, faster method. It starts with a guess for t (usually t = 1) and checks if the decrease in the function is "good enough." If not, it shrinks t and tries again.

The condition for "good enough" decrease is called the Armijo condition. It compares the actual drop in the function value to what we would expect if the function were a straight line sloping down at the current gradient. The formula is:
f(x + t * d) ≤ f(x) + c * t * (gradient at x dotted with d)

Here is what each part means:
- f(x): The value of the function at your starting point.
- f(x + t * d): The value of the function after taking the step.
- gradient at x: A vector that points in the direction of steepest ascent (uphill). Its dot product with d tells us how steep the slope is in the direction we are walking. Since d is a descent direction, this dot product will be negative.
- c: A small constant, typically 0.1 or 0.01. It ensures we don't accept steps that are too shallow.
- t * (gradient at x dotted with d): This term represents the predicted decrease if the function were perfectly linear. Because the gradient dot d is negative, this whole term is negative, representing a drop.

The backtracking algorithm works like this:
1. Start with an initial step size, usually t = 1.
2. Calculate the new point: x_new = x + t * d.
3. Evaluate the function at the new point: f(x_new).
4. Check the Armijo condition: Is f(x_new) less than or equal to f(x) plus c times t times (gradient dot d)?
5. If yes, accept this t and move to x_new.
6. If no, shrink t by multiplying it by a factor rho (typically 0.5), so t becomes t / 2. Go back to step 2.

This process repeats until the condition is met. It guarantees that each step reduces the function value sufficiently without requiring expensive calculations.


## A worked example

Let us walk through a concrete example using backtracking line search.

The Setup:
- Objective function: f(x) = (x - 3)^2. This is a simple parabola with its minimum at x = 3, where the value is 0.
- Current point: x = 5.
- Gradient (slope): The derivative of f(x) is 2 * (x - 3). At x = 5, the gradient is 2 * (5 - 3) = 4. This positive number means the function is increasing as x increases, so to go downhill, we must move left.
- Descent direction: d = -gradient = -4. This points in the negative x-direction.
- Parameters for backtracking:
  - Initial step size t = 1.
  - Shrink factor rho = 0.5 (we will halve t if the step is not good enough).
  - Armijo constant c = 0.1.

Step-by-Step Execution:

Iteration 1:
1. Current values: x = 5, t = 1.
2. Calculate the new point candidate: x_new = x + t * d = 5 + 1 * (-4) = 1.
3. Evaluate the function at the new point: f(x_new) = f(1) = (1 - 3)^2 = (-2)^2 = 4.
4. Check the Armijo condition:
   - Left side: f(x_new) = 4.
   - Right side: f(x) + c * t * (gradient * d)
     - f(x) = f(5) = (5 - 3)^2 = 4.
     - gradient * d = 4 * (-4) = -16. This is the rate of change in the direction d.
     - c * t * (gradient * d) = 0.1 * 1 * (-16) = -1.6.
     - Right side total = 4 + (-1.6) = 2.4.
   - Condition check: Is f(x_new) ≤ Right side? Is 4 ≤ 2.4?
   - Answer: No. 4 is not less than or equal to 2.4. The step was too large; the function did not decrease enough compared to the linear prediction.
5. Shrink t: New t = t * rho = 1 * 0.5 = 0.5.

Iteration 2:
1. Current values: x = 5, t = 0.5.
2. Calculate the new point candidate: x_new = x + t * d = 5 + 0.5 * (-4) = 5 - 2 = 3.
3. Evaluate the function at the new point: f(x_new) = f(3) = (3 - 3)^2 = 0.
4. Check the Armijo condition:
   - Left side: f(x_new) = 0.
   - Right side: f(x) + c * t * (gradient * d)
     - f(x) = 4 (unchanged).
     - gradient * d = -16 (unchanged, as it depends only on the starting point x=5).
     - c * t * (gradient * d) = 0.1 * 0.5 * (-16) = 0.05 * (-16) = -0.8.
     - Right side total = 4 + (-0.8) = 3.2.
   - Condition check: Is f(x_new) ≤ Right side? Is 0 ≤ 3.2?
   - Answer: Yes. 0 is less than or equal to 3.2.
5. Accept the step. The algorithm stops.

Result:
We accepted t = 0.5 and moved from x = 5 to x_new = 3. At x = 3, the function value is 0, which is the global minimum for this simple quadratic function. In more complex problems, backtracking line search ensures we make progress downhill without overshooting, even if it does not find the exact bottom of the valley in one step.


## From scratch, in Python

```python
# Backtracking line search in plain Python.
# We'll minimize f(x) = (x - 3)^2, starting at x = 5.

# Step 1: Define the objective function. 
# This is a function: it takes a number x and returns (x-3)^2.
def objective(x):
    return (x - 3) ** 2

# Step 2: Define the gradient (slope) of the objective.
# For this simple function, the derivative is 2 * (x - 3).
# In general, you'd compute this separately, but here it's a simple expression.
def gradient(x):
    return 2 * (x - 3)

# Step 3: Set parameters.
c = 0.1    # Armijo constant (typical value)
rho = 0.5  # shrink factor (typical value)
max_iter = 100  # safety limit to avoid infinite loops

# Step 4: Starting point.
x = 5.0

# Step 5: Compute the descent direction (negative gradient).
d = -gradient(x)

# Step 6: Initial step size.
t = 1.0

# Step 7: Evaluate the objective at the current point.
f_current = objective(x)

# Step 8: Loop: try steps, shrink until Armijo is satisfied.
for _ in range(max_iter):
    # Candidate new point
    x_new = x + t * d
    f_new = objective(x_new)
    
    # Armijo condition: f_new <= f_current + c * t * (gradient dot d)
    # Here, gradient(x) and d are just numbers, so the dot product is multiplication.
    if f_new <= f_current + c * t * gradient(x) * d:
        break  # accept this step
    else:
        t = t * rho  # shrink the step size

# After the loop, t is the accepted step size, and x_new is the new point.
print("Accepted step size:", t)
print("New point:", x_new)
print("New objective:", f_new)
```


## What the code does

The code starts by defining the objective function (a simple quadratic) and its gradient (the slope). We set the Armijo constant c=0.1 and shrink factor rho=0.5. We start at x=5 and compute the descent direction d = -gradient(x) = -4. We set the initial step t=1. In each iteration of the loop, we compute the candidate x_new = x + t*d and evaluate f_new. We check the Armijo condition: f_new must be no greater than f_current plus a small fraction of the expected linear decrease (c * t * gradient(x) * d). If it passes, we break and accept the step. If it fails, we multiply t by rho (0.5) to shrink it and try again. The loop has a safety limit of 100 iterations to avoid an infinite loop. At the end, we print the accepted step size and the new point. For this example, the loop shrinks t from 1 to 0.5, then accepts, and x_new becomes 3.


## Common misconceptions

**Line search always finds the optimal step size** — Line search will find the exact best step to take.

Exact line search is often infeasible for complex functions; in practice, backtracking accepts the first step that meets a sufficient decrease condition, which is not necessarily optimal. In fact: Backtracking line search is a heuristic that guarantees some progress, not the best possible progress. It is designed to be cheap and reliable, not perfect.

**Step size is just a fixed learning rate** — The step size is just the learning rate you set at the start, and it stays constant.

Line search adapts the step size at each iteration based on the current objective. A fixed learning rate is a special case that ignores the local landscape. In fact: Line search chooses a step size dynamically. When you set a constant learning rate, you skip that adaptation and risk divergence or slow convergence.

**Line search only works for convex problems** — Line search requires the function to be convex (having one minimum).

It works for any smooth function, including the nonconvex loss surfaces of deep networks. The Armijo condition only checks local decrease, not global structure. In fact: Line search is general: it only requires that the objective is smooth enough for the gradient to exist. It does not require convexity.

**Any downhill step is fine, so I can just pick a small random one** — Since any step that goes downhill is better than going uphill, I can just pick a small random step size.

Without a sufficient decrease condition, you might make negligible progress each iteration, slowing training to a crawl. Or you might accidentally take a step that goes uphill because of curvature. In fact: The Armijo condition ensures each step reduces the objective by a meaningful amount, balancing progress and stability.

**Line search is obsolete in deep learning** — Modern deep learning never uses line search, so I can ignore it.

Adaptive optimisers like Adam implicitly perform a line-search-like adjustment per parameter, and learning rate schedules are a form of line search across training. In fact: While not called 'line search' daily, the concept of adjusting step size to ensure progress remains central. Understanding line search helps you diagnose divergence and tune schedules.


## In short

Line search decides how far to move along a descent direction. The cheap, standard method is backtracking with the Armijo condition: try a step, check if the objective decreases sufficiently, shrink if not, accept when it does. It separates direction (from gradient descent) from step size (the learning rate). In deep learning, you'll mostly see schedules and adaptive optimisers doing this implicitly, but the principle explains why too-large steps diverge and too-small steps crawl.


## Where this is used

Line search is rarely written by hand in modern deep learning, but its principle shows up everywhere. In large language models (LLMs) like GPT, the training loop uses a learning rate schedule — the step size starts at a certain value and decreases over time (e.g., linear warm-up then cosine decay). This is essentially a pre-determined line search: instead of computing the optimal step each iteration (which would be too expensive for billions of parameters), the schedule pre-commits to a shrinking step size. The Armijo condition is not checked every step, but the schedule is designed to keep the loss decreasing without diverging — the same goal. In small models running on devices (TinyML), such as keyword spotters on a phone, the same idea applies but with even tighter constraints: they typically use a fixed learning rate with momentum, skipping line search entirely for speed and simplicity. But the step size still matters enormously — a bad one makes the model never converge or diverge. In retrieval-augmented generation (RAG), line search appears conceptually in the retrieval step: you have a query and you want to retrieve relevant documents. The 'direction' is embedding similarity, and the 'step size' might be how many documents to retrieve — you try a few numbers and take the first that gives a good retrieval score. In agentic systems that plan and call tools, an agent often uses a form of line search when deciding how many reasoning steps to take: it tries a few, checks if progress is being made, and stops when improvement stalls. In everyday applied machine learning (e.g., training a logistic regression with scikit-learn), line search is used inside solvers like L-BFGS and Newton-CG. A developer might write `from scipy.optimize import line_search; alpha, _ = line_search(f, grad, x, -grad)` — behind the scenes it does exactly the backtracking you coded above, finding a step size that satisfies the Armijo condition. When line search is done badly — say, a fixed step size too large — training diverges, and the loss becomes NaN. When it's too small, training crawls and never finishes. That's why adaptive optimisers like Adam, which adjust the step size per parameter, have become standard: they encapsulate the 'how far' decision inside the update rule, making explicit line search less critical but still visible in the 'learning rate' hyperparameter.


---

Read this on the web: https://basavapurushottam.com/learn-ai/line-search
