Is it another name for continuation?

It is an optimization form of that general strategy, using a sequence of related problems.

Must smoothing use a Gaussian distribution?

No. The worked example uses a uniform perturbation, and other constructions are possible.

Does it always reach a global minimum?

No. Guarantees require additional assumptions; continuation can fail or follow an unsuitable path.

AI Glossary / Mathematics and optimization / Advanced

Graduated optimization

Definition

Graduated optimization tackles a difficult objective through a sequence of simpler approximations. It first optimizes a heavily simplified or smoothed version, then gradually reduces the simplification, using each stage's result to initialize the next stage until the original objective is approached.

What it means

A complicated objective may contain many local valleys that attract a local optimizer. Smoothing can suppress some small-scale structure and reveal a broader landscape. The hope is that a useful solution of the easier problem can guide optimization as the difficult details return.

This is a continuation strategy, not a universal global-optimization guarantee. A desirable starting solution can split into several branches, become unstable or lead toward a poor solution of the original problem.

How it works

Choose a family of objectives f_delta, indexed by a simplification parameter delta. One construction averages f over nearby perturbed inputs. Larger neighborhoods provide more smoothing; shrinking delta brings the approximation closer to the original objective under suitable assumptions.

Optimize the first stage, reduce delta, and start the next optimization from the previous result. Specify the smoothing schedule, inner optimizer, stopping accuracy and handling of constraints. Final evaluation must use the original objective, not just a convenient smoothed surrogate.

Computing an exact average can be expensive. Some methods estimate smoothed gradients or values through sampling. Theoretical guarantees apply only under stated structural and sampling assumptions; they do not follow merely from running progressively less smoothing.

Three practical examples

1. Image alignment: an optimization workflow can begin with simplified image structure before introducing finer detail. Whether this helps depends on the objective and on how solutions transfer between stages.

2. Nonconvex model fitting: smooth a difficult fitting objective, solve a sequence of progressively closer approximations and compare the final fit with direct optimization from several starting points.

3. Algorithm research: construct a family of test objectives whose smoothed minima can be derived analytically. This reveals when a continuation path is stable and when additional decisions or perturbations are needed.

Think of it this way

Imagine studying a landscape first through a blurred map and then through increasingly detailed maps. The blurred view may help locate a broad valley, but the detailed map can reveal branches or obstacles.

Worked example

Consider a one-dimensional objective f(x) = (x squared − 1) squared. It has two global minima, at −1 and +1, with value zero. At x = 0 its value is one, and zero is a local maximum.

Smooth the function by adding a uniformly distributed perturbation U between −delta and +delta and averaging f(x + U). The relevant moments are E[U] = E[U cubed] = 0, E[U squared] = delta squared / 3, and E[U to the fourth] = delta to the fourth / 5.

Expanding and averaging gives f_delta(x) = x to the fourth + (2 delta squared − 2)x squared + delta to the fourth / 5 − 2 delta squared / 3 + 1. The final three terms are constant in x, so they change objective values but not the locations of minima.

At delta = 1.5, the coefficient of x squared is 2.5. The smoothed problem has a unique minimum at zero. At delta = 1, the variable part becomes x to the fourth, still minimized at zero.

At delta = 0.8, the coefficient becomes −0.72 and the minima split to x = plus or minus 0.6. At delta = 0.4, they lie at plus or minus the square root of 0.84, approximately 0.916515. At delta = 0, the original minima at plus or minus one are recovered.

Following the positive minimizing branch would reduce the original objective from 1 at zero to 0.4096 at 0.6, then 0.0256 at approximately 0.916515, and finally zero at one.

There is a catch: every smoothed objective has derivative zero at x = 0. A plain gradient iteration initialized exactly there remains there even after zero becomes a local maximum. A branch choice, perturbation or other suitable mechanism is needed to move away. These are analytically derived stage minima, not a claim that an unspecified numerical optimizer automatically follows them.

Illustrative case study

In a fictional visual-inspection project, engineers compare direct optimization with a sequence of smoothed alignment objectives. Early stages produce stable coarse matches, but some repeated patterns generate competing alignments when details return.

The team records the solution at each stage, tests different smoothing schedules and scores every final candidate on the original objective. It also checks the resulting alignments against independently labeled examples rather than accepting a low surrogate loss as sufficient evidence.

The experiment shows where continuation helps and where ambiguity remains.

Common misconceptions and mistakes

Graduated optimization is not just reducing the learning rate. It changes the objective or its representation across stages, while a learning-rate schedule can leave the objective unchanged.

Smoothing does not necessarily make every stage convex or preserve every important minimum. Even an initially convex approximation can develop multiple branches as smoothing decreases.

A good value on a smoothed objective is not automatically a good value on the original one. The worked example's initial smoothed minimizer is a maximum of the original objective.

Do not extend a theorem for a specially defined function class to arbitrary neural-network training or arbitrary nonconvex problems. The example here is illustrative and is not asserted to satisfy any particular global-convergence theorem.

Business use

The approach can be worth evaluating when direct optimization repeatedly settles on poor solutions and a meaningful family of simpler objectives is available. Its cost includes solving multiple stages and constructing or estimating the approximations.

Compare methods using total computation, final original-objective quality and task-level performance. Record sensitivity to schedules and initial conditions.

Check your understanding

Where is the heavily smoothed example minimized at delta = 1.5?

Answer: At zero.

Where are the minima when delta = 0.8?

Answer: At −0.6 and +0.6.

Why can gradient descent remain at zero?

Answer: Its derivative is zero there at every stage, even when zero is no longer a minimum.

Related terms

Smoothing
Continuation method
homotopy
nonconvex optimization
local minimum
warm start
graduated nonconvexity

Learn next

Differentiate the smoothed quartic and classify its stationary points as delta changes. Then compare a deterministic gradient iteration started exactly at zero with one started slightly away from zero, evaluating both on the original objective.

Sources

Elad Hazan, Kfir Yehuda Levy and Shai Shalev-Shwartz, On Graduated Optimization for Stochastic Non-Convex Problems, ICML 2016, introduction and smoothing framework: https://proceedings.mlr.press/v48/hazanb16.pdf

The quartic calculations and visual-inspection case are original illustrations.

Previous: Gradient temporal-difference learning Next: Grafting (decision trees)