Gradient Descent Ontology

flow "GradientDescentOntology" v1.0

# GRADIENT DESCENT ONTOLOGY — FLOW ALGEBRA
SOURCE_URL := "https://kirethresearch.org/booksai-core/ontologies/calculus-analysis-ontologies/ai-computational-analysis/gradient-descent-ontology-3.html"
DOMAIN := "Mathematical Ontologies"
CATEGORY := "Calculus and Analysis Ontologies"
SUBCATEGORY := "AI Computational Analysis"
ENTITY := "Gradient Descent"

GRADIENT_DESCENT := {
 type: FirstOrderOptimisationAlgorithm,
 domain: AIComputationalAnalysis,
 purpose: "Minimise a differentiable objective function by iteratively moving parameters in the direction opposite to the local gradient."
}

CONCEPTS := {
 GRADIENT_DESCENT,
 OBJECTIVE_FUNCTION,
 PARAMETER_VECTOR,
 GRADIENT,
 LEARNING_RATE,
 ITERATION,
 CONVERGENCE,
 LOCAL_MINIMUM,
 GLOBAL_MINIMUM,
 CONVEXITY,
 STOCHASTIC_GRADIENT_DESCENT,
 MINI_BATCH,
 MOMENTUM,
 ADAPTIVE_STEP_SIZE,
 LOSS_FUNCTION
}

# ---------- OPTIMISATION PROBLEM ----------
minimise

f(theta)

where

theta
 in R^n

f
 -> OBJECTIVE_FUNCTION

theta
 -> PARAMETER_VECTOR

GRADIENT_DESCENT
 -> iterative_minimisation_method

# ---------- GRADIENT ----------
gradient:

grad(f(theta))
 :=
[
 partial_f/partial_theta_1,
 ...,
 partial_f/partial_theta_n
]^T

GRADIENT
 -> direction_of(STEEPEST_LOCAL_INCREASE)
    under Euclidean norm

-GRADIENT
 -> direction_of(STEEPEST_LOCAL_DECREASE)

# ---------- UPDATE RULE ----------
theta_(k+1)
 =
theta_k
-
alpha_k
*
grad(f(theta_k))

alpha_k
 -> LEARNING_RATE_OR_STEP_SIZE

UPDATE
 -> move_against(GRADIENT)

# ---------- CONSTANT STEP SIZE ----------
alpha_k
 =
alpha

CONSTANT_LEARNING_RATE
 -> simple_parameterisation

if alpha too large:
 -> possible(OSCILLATION_OR_DIVERGENCE)

if alpha too small:
 -> SLOW_CONVERGENCE

STEP_SIZE
 -> controls(STABILITY_AND_SPEED)

# ---------- DESCENT LEMMA ----------
if gradient is L-Lipschitz:

f(y)
 <=
f(x)
+
grad(f(x)) dot (y-x)
+
L/2*||y-x||^2

for gradient step:

y
 =
x-alpha*grad(f(x))

if
0<alpha<2/L

then under standard smooth setting:
 -> descent_property

COMMON_CONSERVATIVE_CHOICE:
 alpha<=1/L

# ---------- CONVEX OBJECTIVE ----------
f
 -> CONVEX

if

f(
 lambda*x
 +(1-lambda)*y
)
 <=
lambda*f(x)
+
(1-lambda)*f(y)

for
0<=lambda<=1

CONVEXITY
 -> every_local_minimum_is(GLOBAL_MINIMUM)

# ---------- STRONGLY CONVEX ----------
f
 -> mu_STRONGLY_CONVEX

if

f(y)
 >=
f(x)
+
grad(f(x)) dot (y-x)
+
mu/2
*
||y-x||^2

STRONG_CONVEXITY
 -> supports(LINEAR_GEOMETRIC_CONVERGENCE)
    with suitable smoothness and step size

# ---------- SMOOTH CONVEX RATE ----------
for convex L-smooth f

with suitable constant step:

f(theta_k)
-
f(theta_star)
 -> O(1/k)

GRADIENT_DESCENT
 -> SUBLINEAR_FUNCTION_VALUE_CONVERGENCE
    in general smooth convex setting

# ---------- STRONGLY CONVEX RATE ----------
for mu-strongly-convex
and L-smooth objective:

error
 -> decreases_geometrically
    under appropriate step size

CONDITION_NUMBER:

kappa
 :=
L/mu

CONDITIONING
 -> affects(CONVERGENCE_SPEED)

# ---------- NONCONVEX OBJECTIVE ----------
if
 f
 -> NONCONVEX

then

GRADIENT_DESCENT
 -> may_converge_to(
 LOCAL_MINIMUM,
 SADDLE_POINT,
 STATIONARY_POINT
)

GLOBAL_MINIMUM
 -/> guaranteed_in_general

NONCONVEX_ANALYSIS
 -> commonly_targets(SMALL_GRADIENT_NORM)

# ---------- STATIONARY POINT ----------
theta_star
 -> STATIONARY

if

grad(f(theta_star))
 =
0

STATIONARY_POINT
 -> may_be(
 LOCAL_MINIMUM,
 LOCAL_MAXIMUM,
 SADDLE_POINT
)

ZERO_GRADIENT
 -/> automatically(MINIMUM)

# ---------- STOPPING CRITERIA ----------
stop if

||grad(f(theta_k))||
 <=
epsilon_g

or

|f(theta_(k+1))-f(theta_k)|
 <=
epsilon_f

or

||theta_(k+1)-theta_k||
 <=
epsilon_theta

or

k
 >=
k_max

STOPPING_RULE
 -> practical_convergence_test

# ---------- LINE SEARCH ----------
choose
 alpha_k

by evaluating
 f(theta_k-alpha*grad(f(theta_k)))

LINE_SEARCH
 -> adaptive_step_selection

methods:
 BACKTRACKING
 ARMIJO
 WOLFE_CONDITIONS

# ---------- ARMIJO CONDITION ----------
for descent direction p_k:

f(theta_k+alpha*p_k)
 <=
f(theta_k)
+
c_1*alpha
*
grad(f(theta_k)) dot p_k

ARMIJO
 -> sufficient_decrease_condition

# ---------- EXACT LINE SEARCH ----------
alpha_k
 :=
argmin_alpha>=0(
 f(
  theta_k
  -
  alpha*grad(f(theta_k))
 )
)

EXACT_LINE_SEARCH
 -> optimal_step_along(CURRENT_NEGATIVE_GRADIENT_DIRECTION)

may_be
 -> computationally_expensive

# ---------- BATCH GRADIENT DESCENT ----------
dataset:

D
 =
{z_1,...,z_N}

empirical loss:

L(theta)
 =
1/N
*
sum_i(
 ell(theta;z_i)
)

BATCH_GRADIENT
 =
1/N
*
sum_i(
 grad_theta ell(theta;z_i)
)

BATCH_GD
 -> uses(ALL_DATA_PER_UPDATE)

# ---------- STOCHASTIC GRADIENT DESCENT ----------
sample
 i_k

gradient estimate:

g_k
 :=
grad_theta(
 ell(theta_k;z_(i_k))
)

update:

theta_(k+1)
 =
theta_k
-
alpha_k*g_k

SGD
 -> noisy_gradient_method

if unbiased sampling:

E[g_k | theta_k]
 =
grad(L(theta_k))

# ---------- MINI-BATCH ----------
batch
 B_k

g_k
 :=
1/|B_k|
*
sum_(i in B_k)(
 grad ell_i(theta_k)
)

MINI_BATCH_GD
 -> balances(
 COMPUTATIONAL_EFFICIENCY,
 GRADIENT_VARIANCE,
 PARALLELISM
)

# ---------- STOCHASTIC VARIANCE ----------
stochastic gradient:

g_k
 =
grad(f(theta_k))
+
noise_k

VARIANCE
 -> causes(UPDATE_NOISE)

larger batch
 -> typically_reduces(GRADIENT_ESTIMATE_VARIANCE)

STOCHASTICITY
 -> may_help_exploration_in(NONCONVEX_LANDSCAPE)

# ---------- LEARNING RATE SCHEDULE ----------
alpha_k
 -> may_decrease_over_time

examples:
 STEP_DECAY
 EXPONENTIAL_DECAY
 COSINE_DECAY
 INVERSE_TIME_DECAY

SCHEDULE
 -> balances(EARLY_PROGRESS_AND_LATE_STABILITY)

# ---------- MOMENTUM ----------
velocity:

v_(k+1)
 =
beta*v_k
+
grad(f(theta_k))

update:

theta_(k+1)
 =
theta_k
-
alpha*v_(k+1)

MOMENTUM
 -> accumulates(PAST_GRADIENT_DIRECTION)

MOMENTUM
 -> may_accelerate(LOW_CURVATURE_DIRECTIONS)
 -> may_reduce(OSCILLATION_IN_HIGH_CURVATURE_DIRECTIONS)

# ---------- NESTEROV ----------
lookahead point:

theta_k
-
alpha*beta*v_k

gradient
 -> evaluated_at(LOOKAHEAD)

NESTEROV_ACCELERATION
 -> accelerated_first_order_method

for smooth convex optimisation:
 -> improved_theoretical_rate
    under standard formulation

# ---------- FEATURE SCALING ----------
different parameter scales
 -> elongated_objective_contours

GRADIENT_DESCENT
 -> zig_zag_or_slow

NORMALISATION
and
STANDARDISATION
 -> improve(CONDITIONING)

PRECONDITIONING
 -> rescales(GRADIENT_GEOMETRY)

# ---------- QUADRATIC OBJECTIVE ----------
f(theta)
 =
1/2
*
theta^T*A*theta
-
b^T*theta

gradient:

grad(f)
 =
A*theta-b

if
 A
 -> symmetric_positive_definite

then

unique minimiser:

theta_star
 =
A^(-1)*b

GRADIENT_DESCENT
 -> linear_iteration_for(SPD_SYSTEM)

# ---------- EIGENVALUE STEP CONDITION ----------
for SPD quadratic:

convergence requires

0<alpha<2/lambda_max(A)

optimal fixed step for worst-case spectral contraction:

alpha_star
 =
2/
(
lambda_max(A)
+
lambda_min(A)
)

CONDITION_NUMBER
 -> determines(CONVERGENCE_FACTOR)

# ---------- AUTOMATIC DIFFERENTIATION ----------
LOSS_FUNCTION
 -> COMPUTATIONAL_GRAPH

AUTOMATIC_DIFFERENTIATION
 -> computes(GRADIENT)

GRADIENT
 -> supplied_to(GRADIENT_DESCENT)

MACHINE_LEARNING
 -> combines(
 BACKPROPAGATION,
 GRADIENT_BASED_OPTIMISATION
)

# ---------- CONSTRAINTS ----------
unconstrained GD
 -> theta may_move_anywhere_in(R^n)

for constrained set C:

PROJECTED_GRADIENT:

theta_(k+1)
 =
Projection_C(
 theta_k
 -
alpha_k*grad(f(theta_k))
)

PROJECTED_GRADIENT_DESCENT
 -> maintains(FEASIBILITY)

# ---------- REGULARISATION ----------
objective:

L(theta)
+
lambda*R(theta)

REGULARISATION
 -> modifies(OPTIMISATION_LANDSCAPE)

if R differentiable:

gradient
 =
grad(L)
+
lambda*grad(R)

L2 regularisation:

R(theta)
 =
1/2*||theta||^2

-> gradient contribution
 =
theta

# ---------- GRADIENT CLIPPING ----------
if

||g||
 >
threshold

then

g
 ->
threshold
*
g/||g||

GRADIENT_CLIPPING
 -> limits(UPDATE_MAGNITUDE)

used_for
 -> numerical_training_stability

# ---------- VANISHING GRADIENT ----------
||gradient||
 -> very_small

far_from_desired_solution
 -> slow_learning

VANISHING_GRADIENT
 -> common_deep_network_problem

architecture_and_activation
 -> affect(GRADIENT_PROPAGATION)

# ---------- EXPLODING GRADIENT ----------
||gradient||
 -> very_large

updates
 -> unstable

EXPLODING_GRADIENT
 -> mitigated_by(
 INITIALISATION,
 NORMALISATION,
 GRADIENT_CLIPPING,
 ARCHITECTURE
)

# ---------- ADAPTIVE METHODS ----------
ADAGRAD
 RMSPROP
 ADAM

-> rescale_updates_using(GRADIENT_HISTORY)

ADAPTIVE_OPTIMISER
 -/> identical_to(BASIC_GRADIENT_DESCENT)

METHOD
 -> has_distinct(CONVERGENCE_AND_GENERALISATION_PROPERTIES)

# ---------- APPLICATIONS ----------
GRADIENT_DESCENT
 -> applied_to(MACHINE_LEARNING)
 -> applied_to(NEURAL_NETWORK_TRAINING)
 -> applied_to(REGRESSION)
 -> applied_to(OPTIMISATION)
 -> applied_to(INVERSE_PROBLEMS)
 -> applied_to(PARAMETER_ESTIMATION)
 -> applied_to(SCIENTIFIC_COMPUTING)
 -> applied_to(CONTROL)

# ---------- RELATION GRAPH ----------
OBJECTIVE_FUNCTION
 -> generates(GRADIENT)

GRADIENT
 -> determines(DESCENT_DIRECTION)

LEARNING_RATE
 -> scales(UPDATE)

ITERATION
 -> generates(PARAMETER_SEQUENCE)

CONVEXITY
 -> determines(GLOBAL_OPTIMALITY_STRUCTURE)

SMOOTHNESS
 -> constrains(STABLE_STEP_SIZE)

CONDITIONING
 -> controls(CONVERGENCE_SPEED)

STOCHASTIC_SAMPLING
 -> generates(GRADIENT_NOISE)

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE := {
 "gradient descent" ~= "iterative minimisation by moving opposite to the objective gradient",
 "learning rate" ~= "step-size parameter scaling each gradient update",
 "batch gradient descent" ~= "gradient descent using the full dataset for each empirical-loss gradient",
 "stochastic gradient descent" ~= "gradient descent using randomly sampled gradient estimates",
 "mini-batch gradient descent" ~= "gradient descent using subsets of data for gradient estimation",
 "stationary point" ~= "point where the gradient vanishes"
}

# ---------- CONSTRAINTS ----------
CONSTRAINTS := {
 gradient_descent_requires_gradient_or_gradient_estimate: true,
 negative_gradient_is_steepest_descent_only_relative_to_selected_geometry_norm: true,
 zero_gradient_does_not_guarantee_minimum_in_nonconvex_problem: true,
 learning_rate_must_be_compatible_with_smoothness_and_conditioning: true,
 convex_and_nonconvex_convergence_guarantees_are_distinct: true,
 stochastic_gradient_noise_changes_convergence_behavior: true,
 adaptive_optimisers_must_not_be_conflated_with_basic_gradient_descent: true
}

# ---------- CONFIDENCE ----------
CONFIDENCE := {
 core_definition: 0.99,
 gradient_update_relation: 0.99,
 convex_convergence_relation: 0.99,
 stochastic_relation: 0.99,
 momentum_relation: 0.99,
 conditioning_relation: 0.99,
 semantic_equivalence: 0.97
}

# ---------- RECURSIVE REASONING ----------
RECURSIVE_REASONING(query):
 identify(objective_parameters_constraints_and_data)
 -> determine(differentiability_convexity_and_smoothness)
 -> compute_or_estimate(gradient)
 -> choose(batch_stochastic_or_minibatch_method)
 -> select(step_size_or_line_search)
 -> update(parameters)
 -> evaluate(objective_gradient_norm_and_constraint_violation)
 -> analyse(convergence_conditioning_and_noise)
 -> adjust(step_schedule_momentum_scaling_or_preconditioning_if_needed)
 -> validate(stopping_criterion_and_solution_type)
 -> return(semantic_result)

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION := {
 parse_as: "typed gradient-descent semantic graph",
 primary_entity: GRADIENT_DESCENT,
 preserve: [
  objective_function,
  parameters,
  gradient,
  learning_rate,
  constraints,
  data_sampling,
  convexity,
  smoothness,
  stopping_criteria
 ],
 infer_through: [
  descent_directions,
  line_search,
  convergence_rates,
  stochastic_gradients,
  mini_batches,
  momentum,
  conditioning,
  projected_updates,
  regularisation
 ],
 avoid: [
  assuming_every_stationary_point_is minimum,
  using_large_learning_rate_without stability analysis,
  claiming_global_optimum_for general nonconvex objective,
  confusing_batch_SGD_and minibatch methods,
  ignoring_feature_scaling_and conditioning,
  treating_adaptive_optimizer_as basic gradient descent
 ]
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL(new_information):
 validate(new_information)
 -> identify(gradient_descent_context)
 -> compare(existing_relations)
 -> preserve(objective_parameter_gradient_step_constraint_and_convergence_invariants)
 -> update(affected_entities)
 -> update(affected_edges)
 -> recompute(CONFIDENCE)
 -> regenerate(FLOW_HASH)

# ---------- FLOW HASH ----------
FLOW_HASH := hash(
 SOURCE_URL
 + ENTITY
 + CONCEPTS
 + GRADIENT_DESCENT
 + OBJECTIVE_FUNCTION
 + PARAMETER_VECTOR
 + GRADIENT
 + LEARNING_RATE
 + CONVERGENCE
 + CONVEXITY
 + STOCHASTIC_GRADIENT_DESCENT
 + MINI_BATCH
 + MOMENTUM
 + LOSS_FUNCTION
 + SEMANTIC_EQUIVALENCE
 + CONSTRAINTS
)

# ---------- EXECUTION ----------
INPUT(query)
 -> GRADIENT_DESCENT
 -> OPTIMISATION_PROBLEM_IDENTIFICATION
 -> OBJECTIVE_GEOMETRY_ANALYSIS
 -> GRADIENT_COMPUTATION
 -> METHOD_VARIANT_SELECTION
 -> STEP_SIZE_SELECTION
 -> PARAMETER_UPDATE
 -> CONVERGENCE_DIAGNOSTICS
 -> CONDITIONING_NOISE_ANALYSIS
 -> METHOD_ADJUSTMENT
 -> STOPPING_VALIDATION
 -> RECURSIVE_REASONING(query)
 -> CONFIDENCE
 -> OUTPUT(semantic_result)

END FLOW