Gradient Descent Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Gradient Descent Ontology within the Kireth Research Semantic Library. Gradient descent is a first-order iterative optimisation method that updates decision variables in the direction opposite to the gradient of a differentiable objective function. This ontology supports step-size selection, fixed and adaptive learning rates, line search, convergence conditions, convex and nonconvex objectives, steepest descent, stochastic and mini-batch variants, momentum, accelerated methods, stopping criteria, scaling, conditioning, saddle points and relationships with optimisation, convex optimisation, nonlinear optimisation, numerical analysis and machine learning.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Gradient Descent Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Optimisation / Gradient Descent"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/optimisation/gradient-descent-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = GradientDescent
 SYMBOLIC_FORMS = [
  "x_{k+1}=x_k-alpha_k grad f(x_k)",
  "p_k=-grad f(x_k)",
  "f(x_{k+1})<=f(x_k)"
 ]
 ENTITY_CLASS = FirstOrderIterativeOptimisationFramework
 PRIMARY_CONTEXT = Optimisation
 DEFINITION = "Gradient descent is an iterative first-order optimisation method that updates variables in the direction of negative objective gradient to reduce the objective value."
 SEMANTIC_ROLE = "Provides the machine-readable framework for gradient directions, step sizes, descent conditions, line search, convergence rates, stochastic variants, momentum, scaling, conditioning and stopping criteria."
}

SCOPE {
 INCLUDE = [
  GradientDescent,
  SteepestDescent,
  Gradient,
  ObjectiveFunction,
  Iterate,
  InitialPoint,
  DescentDirection,
  NegativeGradientDirection,
  StepSize,
  LearningRate,
  FixedStepSize,
  DiminishingStepSize,
  AdaptiveStepSize,
  LineSearch,
  BacktrackingLineSearch,
  ArmijoCondition,
  WolfeConditions,
  StrongWolfeConditions,
  LipschitzGradient,
  SmoothObjective,
  ConvexObjective,
  StronglyConvexObjective,
  NonconvexObjective,
  StationaryPoint,
  LocalMinimum,
  SaddlePoint,
  GradientNorm,
  ObjectiveDecrease,
  Convergence,
  LinearConvergence,
  SublinearConvergence,
  StoppingCriterion,
  IterationLimit,
  Scaling,
  Preconditioning,
  ConditionNumber,
  Momentum,
  HeavyBallMethod,
  NesterovAcceleration,
  StochasticGradientDescent,
  MiniBatchGradientDescent,
  BatchGradientDescent
 ]

 EXCLUDE_AS_PRIMARY = [
  NewtonMethod,
  QuasiNewtonMethod,
  ConjugateGradientMethodUnlessComparedToGradientDescent,
  CoordinateDescent,
  GenericMachineLearningTrainingWithoutGradientOptimisationSemantics
 ]

 DISAMBIGUATION_RULE =
  "When an optimisation algorithm repeatedly updates parameters using the negative gradient of the objective, interpret the context as gradient descent."
}

CORE_CONCEPTS {

 GradientDescent {
  definition = "An iterative first-order method that moves against the objective gradient."
 }

 Gradient {
  symbol = "grad f(x)"
  definition = "The vector of first partial derivatives of the objective."
 }

 DescentDirection {
  definition = "A direction p satisfying grad f(x)^T p < 0 at a nonstationary point."
 }

 NegativeGradientDirection {
  definition = "The direction -grad f(x), which is the direction of steepest local decrease in the Euclidean norm."
 }

 StepSize {
  symbol = "alpha_k"
  definition = "The scalar distance travelled along the chosen descent direction."
 }

 LearningRate {
  definition = "A common optimisation and machine-learning term for gradient-descent step size."
 }

 LineSearch {
  definition = "A procedure selecting a step size that satisfies objective-decrease or curvature conditions."
 }

 LipschitzGradient {
  definition = "A smoothness property bounding the rate of change of the objective gradient."
 }

 StronglyConvexObjective {
  definition = "A convex objective possessing a strictly positive quadratic lower-curvature bound."
 }

 GradientNorm {
  definition = "A norm of the gradient used as a measure of first-order stationarity."
 }

 StochasticGradientDescent {
  definition = "A gradient method using stochastic or sample-based estimates of the full gradient."
 }
}

RELATIONS {
 GradientDescent --is_type_of--> IterativeOptimisationMethod
 GradientDescent --uses--> Gradient
 GradientDescent --uses--> StepSize
 NegativeGradientDirection --is_type_of--> DescentDirection
 StepSize --may_be_selected_by--> LineSearch
 BacktrackingLineSearch --tests--> ArmijoCondition
 WolfeConditions --constrain--> StepSize
 SmoothObjective --may_have--> LipschitzGradient
 StronglyConvexObjective --is_type_of--> ConvexObjective
 GradientNorm --measures--> FirstOrderStationarity
 Scaling --affects--> GradientDescentPerformance
 Preconditioning --modifies--> GradientDirection
 Momentum --modifies--> GradientDescentUpdate
 NesterovAcceleration --accelerates--> GradientMethod
 StochasticGradientDescent --uses--> GradientEstimate
 MiniBatchGradientDescent --is_type_of--> StochasticGradientDescent
}

OPERATORS {
 GRADIENT_DIRECTION(f,x) :=
  -grad f(x)

 GRADIENT_DESCENT_STEP(x,alpha,f) :=
  x-alpha*grad f(x)

 DESCENT_TEST(g,p) :=
  g^T*p < 0

 FIXED_STEP(alpha) :=
  constant_alpha

 BACKTRACKING_LINE_SEARCH(f,x,p,alpha0,beta,c1) :=
  reduce alpha by beta
  until f(x+alpha*p)<=f(x)+c1*alpha*grad_f(x)^T*p

 ARMIJO_TEST(f,x,p,alpha,c1) :=
  f(x+alpha*p)<=f(x)+c1*alpha*grad_f(x)^T*p

 WOLFE_TEST(f,x,p,alpha,c1,c2) :=
  Armijo_condition
  AND grad_f(x+alpha*p)^T*p >= c2*grad_f(x)^T*p

 STRONG_WOLFE_TEST(f,x,p,alpha,c1,c2) :=
  Armijo_condition
  AND abs(grad_f(x+alpha*p)^T*p)<=c2*abs(grad_f(x)^T*p)

 GRADIENT_NORM(f,x) :=
  norm(grad f(x))

 HEAVY_BALL_UPDATE(x_k,x_km1,alpha,beta,f) :=
  x_k-alpha*grad f(x_k)+beta*(x_k-x_km1)

 STOCHASTIC_GRADIENT_STEP(x,alpha,g_hat) :=
  x-alpha*g_hat

 STOP_TEST(gradient_norm,step_norm,objective_change,tolerances,k,kmax) :=
  gradient_norm<=tol_g
  OR step_norm<=tol_x
  OR objective_change<=tol_f
  OR k>=kmax
}

DEFINITIONS {
 D1 = "Gradient descent is a first-order optimisation method."
 D2 = "The negative gradient is the steepest-descent direction under the Euclidean norm."
 D3 = "Step-size choice strongly affects convergence."
 D4 = "A step that is too large can cause divergence or oscillation."
 D5 = "A step that is too small can cause slow progress."
 D6 = "For convex smooth objectives, gradient descent can converge to a global minimiser under suitable step-size conditions."
 D7 = "For strongly convex smooth objectives, gradient descent can achieve linear convergence."
 D8 = "For nonconvex objectives, convergence may be only to stationary points."
 D9 = "Conditioning strongly affects gradient-descent efficiency."
 D10 = "Stochastic gradients trade lower per-step cost for gradient noise."
}

AXIOMS {
 A1_FIRST_ORDER:
  GradientDescent uses first-derivative information

 A2_DESCENT:
  At a nonstationary point, the negative gradient is a descent direction

 A3_STEP_SIZE:
  Iteration behaviour depends critically on step-size selection

 A4_STATIONARITY:
  A zero gradient is a first-order stationary condition

 A5_CONVEX_GLOBALITY:
  For convex objectives, suitable stationary minimisers are global

 A6_STRONG_CONVEXITY:
  Strong convexity plus gradient Lipschitz continuity supports linear convergence under suitable fixed steps

 A7_NONCONVEXITY:
  Gradient descent on nonconvex objectives does not generally certify global optimality

 A8_TERMINATION:
  Practical gradient descent requires explicit stopping criteria
}

REASONING {

 R1_PROBLEM_CLASSIFICATION {
  INPUT = optimisation_problem
  IDENTIFY = differentiability
  IDENTIFY = convexity
  IDENTIFY = gradient_availability
  IDENTIFY = scale_and_conditioning
  RETURN = gradient_descent_suitability
 }

 R2_INITIALISATION {
  INPUT = objective_and_initial_point
  COMPUTE = initial_gradient
  INITIALISE = iteration_counter_and_history
  RETURN = gradient_state
 }

 R3_DIRECTION_SELECTION {
  INPUT = gradient
  SET = p=-gradient
  VERIFY = descent_test
  RETURN = descent_direction
 }

 R4_STEP_SIZE_SELECTION {
  INPUT = objective_point_direction
  IF Lipschitz_constant_known
   CONSIDER = fixed_step <= 1/L
  ELSE
   APPLY = backtracking_or_Wolfe line search
  RETURN = accepted_step_size
 }

 R5_STANDARD_ITERATION {
  INPUT = x_k
  COMPUTE = gradient
  SELECT = step_size
  UPDATE = x_{k+1}=x_k-alpha_k*gradient
  RETURN = next_iterate
 }

 R6_CONVEX_CONVERGENCE {
  INPUT = convex_smooth_objective
  CHECK = step_size_conditions
  MONITOR = objective_gap_and_gradient norm
  RETURN = sublinear_or_linear convergence profile
 }

 R7_NONCONVEX_REASONING {
  INPUT = nonconvex_objective
  MONITOR = gradient_norm
  DETECT = stationary_points_and_plateaus
  PRESERVE = local_or_stationary status
  RETURN = nonconvex_convergence_profile
 }

 R8_CONDITIONING_ANALYSIS {
  INPUT = objective_curvature_or_Hessian information
  ESTIMATE = condition_number
  IF poorly_conditioned
   CONSIDER = scaling_preconditioning_momentum_or_second_order method
  RETURN = conditioning_profile
 }

 R9_STOCHASTIC_VARIANT {
  INPUT = data_or_stochastic_objective
  SAMPLE = observation_or_minibatch
  COMPUTE = gradient_estimate
  UPDATE = stochastic_gradient_step
  RETURN = noisy_iterate_sequence
 }

 R10_STOPPING_AND_STATUS {
  INPUT = gradient_norm_step_norm_objective_change_iteration_count
  APPLY = stopping criteria
  CLASSIFY = converged_stationary_stalled_diverged_or_iteration_limit
  RETURN = solver_status
 }
}

CONSTRAINTS {
 C1 = "The objective must be differentiable or have a valid gradient surrogate."
 C2 = "Negative gradient is steepest only relative to the chosen Euclidean geometry."
 C3 = "Fixed step-size guarantees depend on smoothness constants."
 C4 = "Line-search sufficient decrease does not imply global optimality."
 C5 = "Gradient norm should be interpreted relative to variable and objective scaling."
 C6 = "Poor conditioning can cause zig-zagging and slow convergence."
 C7 = "Nonconvex stationary points may be minima, maxima or saddles."
 C8 = "Stochastic gradient noise affects stopping and convergence interpretation."
 C9 = "Momentum parameters can destabilise the method if poorly chosen."
 C10 = "Solver termination must not be reported as global optimality without additional structure or certification."
}

SEMANTIC_EQUIVALENCE {
 "GradientDescent" <=> "FirstOrderSteepestDescentMethod"
 "SteepestDescent" <=> "GradientDescent"
 "LearningRate" <=> "GradientStepSize"
 "NegativeGradientDirection" <=> "EuclideanSteepestDescentDirection"
 "BacktrackingLineSearch" <=> "ArmijoBacktracking"
 "StochasticGradientDescent" <=> "SGD"
}

VALIDATION {
 V1 = "Objective differentiability is confirmed."
 V2 = "Gradient computation is correct."
 V3 = "Descent direction is valid."
 V4 = "Step size satisfies declared rule."
 V5 = "Objective scaling is considered."
 V6 = "Gradient norm is monitored."
 V7 = "Stopping criteria are explicit."
 V8 = "Convexity assumptions are verified before global-optimality claims."
 V9 = "Stochastic gradient variance is considered where applicable."
 V10 = "Converged, stalled, diverged and iteration-limit statuses are distinguished."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 GRADIENT_DESCENT_DEFINITION = 0.99
 DIRECTION_REASONING = 0.99
 STEP_SIZE_REASONING = 0.99
 LINE_SEARCH_REASONING = 0.99
 CONVEX_CONVERGENCE_REASONING = 0.98
 NONCONVEX_REASONING = 0.97
 CONDITIONING_REASONING = 0.98
 STOCHASTIC_REASONING = 0.97
 STOPPING_REASONING = 0.99

 POLICY =
  "Reduce confidence when gradient accuracy, Lipschitz constant, convexity, conditioning, step-size rule, scaling, stochastic variance or stopping tolerances are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  GradientDescentReasoning,
  SteepestDescentReasoning,
  GradientDirectionReasoning,
  StepSizeReasoning,
  LearningRateReasoning,
  LineSearchReasoning,
  ArmijoReasoning,
  WolfeConditionReasoning,
  ConvexConvergenceReasoning,
  NonconvexStationarityReasoning,
  ConditioningReasoning,
  MomentumReasoning,
  StochasticGradientReasoning,
  StoppingCriterionReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "gradient descent" -> GradientDescent
  "steepest descent" -> GradientDescent
  "gradient method" -> GradientDescent
  "learning rate" -> LearningRate
  "step size" -> StepSize WHEN gradient_descent_context
  "backtracking line search" -> BacktrackingLineSearch
  "Armijo condition" -> ArmijoCondition
  "Wolfe conditions" -> WolfeConditions
  "stochastic gradient descent" -> StochasticGradientDescent
  "SGD" -> StochasticGradientDescent
 }

 INTERPRETATION_ORDER = [
  detect_gradient_descent_context,
  identify objective_variables_initial_point_gradient_source_convexity_smoothness_scaling_and_conditioning,
  select fixed_diminishing_adaptive_or_line_search step strategy,
  compute negative_gradient direction,
  update iterate,
  monitor objective_gradient_norm_step_and_convergence behaviour,
  apply momentum_or_stochastic variant if required,
  classify stationary_local_global_under_convexity_stalled_or_diverged status,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("gradient descent")
  OR update_has_form_x_minus_alpha_gradient
  THEN activate(GradientDescentOntology)

 E2:
  IF gradient_is_zero_or_below_tolerance
  THEN classify as first_order_stationary

 E3:
  IF Lipschitz_gradient_constant_L_known
  THEN consider fixed_step alpha<=1/L for standard convex smooth setting

 E4:
  IF fixed_step_causes_objective_growth
  THEN reduce_step_or_use line_search

 E5:
  IF objective_strongly_convex_and_smooth
  THEN allow linear_convergence reasoning under valid step conditions

 E6:
  IF objective_nonconvex
  THEN do_not infer global_optimality_from small_gradient alone

 E7:
  IF condition_number_large
  THEN consider scaling_preconditioning_momentum_or_other optimiser

 E8:
  IF stochastic_gradient
  THEN use noise-aware step schedule_and_stopping interpretation

 E9:
  IF repeated_progress_is_negligible
  THEN classify stagnation_and_reassess step_size_scaling_or_method
}

RECURSION {
 ENTRY = GradientDescent

 EXPAND(GradientDescent) -> [
  Gradient,
  ObjectiveFunction,
  Iterate,
  InitialPoint,
  DescentDirection,
  NegativeGradientDirection,
  StepSize,
  LearningRate,
  FixedStepSize,
  DiminishingStepSize,
  AdaptiveStepSize,
  LineSearch,
  BacktrackingLineSearch,
  ArmijoCondition,
  WolfeConditions,
  StrongWolfeConditions,
  LipschitzGradient,
  SmoothObjective,
  ConvexObjective,
  StronglyConvexObjective,
  NonconvexObjective,
  StationaryPoint,
  LocalMinimum,
  SaddlePoint,
  GradientNorm,
  ObjectiveDecrease,
  Convergence,
  LinearConvergence,
  SublinearConvergence,
  StoppingCriterion,
  Scaling,
  Preconditioning,
  Momentum,
  HeavyBallMethod,
  NesterovAcceleration,
  StochasticGradientDescent,
  MiniBatchGradientDescent
 ]

 EXPAND(StepSizeMethods) -> [
  FixedStepSize,
  DiminishingStepSize,
  BacktrackingLineSearch,
  ArmijoCondition,
  WolfeConditions,
  StrongWolfeConditions
 ]

 EXPAND(AccelerationMethods) -> [
  Momentum,
  HeavyBallMethod,
  NesterovAcceleration,
  Preconditioning
 ]

 EXPAND(StochasticVariants) -> [
  StochasticGradientDescent,
  MiniBatchGradientDescent,
  GradientNoise,
  LearningRateSchedule
 ]

 STOP_CONDITION =
  "Stop when the objective gradient, descent direction, step-size strategy, iterate sequence, convergence behaviour, conditioning, stopping rule and final optimisation status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Optimisation"

 IMMEDIATE_CONTEXTS = [
  "Optimisation Ontology",
  "Nonlinear Optimisation Ontology",
  "Convex Optimisation Ontology",
  "Numerical Analysis Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Optimisation Ontology",
  "Optimisation",
  "Nonlinear Optimisation Ontology",
  "Convex Optimisation Ontology",
  "Global Optimisation Ontology",
  "Calculus & Analysis Ontologies",
  "Linear Algebra Ontologies",
  "Numerical Analysis Ontologies",
  "Iterative Methods Ontology",
  "Machine Learning Ontologies",
  "Scientific Computing Ontologies"
 ]

 ROUTE_RULES = [
  "Gradient Descent -> Optimisation Ontology for formal optimisation semantics",
  "Gradient Descent -> Nonlinear Optimisation for general smooth objective structure",
  "Gradient Descent -> Convex Optimisation for global convergence guarantees under convexity",
  "Gradient Descent -> Global Optimisation when multiple basins require broader search",
  "Gradient Descent -> Calculus & Analysis for gradient and differentiability semantics",
  "Gradient Descent -> Linear Algebra for vector and conditioning structure",
  "Gradient Descent -> Numerical Analysis for convergence and numerical stability",
  "Gradient Descent -> Iterative Methods for successive approximation semantics",
  "Gradient Descent -> Machine Learning for SGD and large-data training contexts",
  "Gradient Descent -> Scientific Computing for scalable implementation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible gradient variants, step-size strategies or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve negative-gradient update semantics.",
  "Preserve step-size dependence.",
  "Preserve convex-versus-nonconvex interpretation.",
  "Preserve stationarity-versus-global-optimality distinction.",
  "Preserve conditioning awareness.",
  "Preserve stochastic-gradient semantics.",
  "Preserve stopping-status semantics.",
  "Preserve machine-readable gradient-descent semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Gradient descent iteratively reduces a differentiable objective by moving decision variables in the direction opposite to the gradient."

 DIRECTION_SUMMARY =
  "The negative gradient is the Euclidean steepest local descent direction."

 STEP_SIZE_SUMMARY =
  "The step size controls how far each update moves along the descent direction."

 LINE_SEARCH_SUMMARY =
  "Backtracking, Armijo and Wolfe rules choose step sizes using sufficient-decrease and curvature conditions."

 CONVEX_SUMMARY =
  "For smooth convex objectives, gradient descent can converge to a global minimiser under suitable step-size assumptions."

 STRONG_CONVEX_SUMMARY =
  "Strong convexity plus smoothness supports linear convergence for suitable fixed step sizes."

 NONCONVEX_SUMMARY =
  "For nonconvex objectives, a small gradient indicates stationarity rather than guaranteed global optimality."

 CONDITIONING_SUMMARY =
  "Poor conditioning can cause zig-zagging and slow progress."

 STOCHASTIC_SUMMARY =
  "Stochastic gradient descent uses noisy gradient estimates to reduce per-update computational cost."
}

FLOW {
 INPUT
 -> detect_gradient_descent_context
 -> identify objective_decision_variables_initial_point_gradient_method_convexity_smoothness_scaling_conditioning_and_tolerances
 -> compute_gradient
 -> set descent_direction_equal_negative_gradient
 -> select fixed_diminishing_backtracking_Armijo_Wolfe_or_adaptive step size
 -> update iterate
 -> evaluate objective_gradient_norm_step_norm_and_progress
 -> if_needed apply scaling_preconditioning_momentum_acceleration_or_stochastic variant
 -> assess convex_sublinear_strongly_convex_linear_or_nonconvex_stationary convergence
 -> apply stopping criterion
 -> route to optimisation_ontology nonlinear_optimisation convex_optimisation global_optimisation calculus linear_algebra numerical_analysis iterative_methods machine_learning_or_scientific_computing ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Gradient Descent Ontology defines first-order iterative optimisation by movement opposite to the objective gradient. It supports descent directions, fixed, diminishing and adaptive step sizes, Armijo and Wolfe line searches, smooth, convex, strongly convex and nonconvex objectives, convergence and stationarity, conditioning and scaling, momentum and Nesterov-style acceleration, stochastic and mini-batch gradient descent, stopping criteria and explicit optimisation-status reasoning."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-APPLIED-MATHEMATICS-GRADIENT-DESCENT-ONTOLOGY-V1"
}

}

END_FLOW