Stochastic Gradient Descent Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Stochastic Gradient Descent Ontology within the Kireth Research Semantic Library. Stochastic gradient descent is a first-order optimisation method that updates parameters using noisy gradient estimates derived from individual samples or mini-batches rather than the full objective gradient. This ontology supports unbiased and biased gradient estimators, mini-batch training, learning-rate schedules, momentum, variance reduction, adaptive gradient methods, stochastic convergence, noise scales, regularisation, stopping criteria, finite precision, verification and reproducibility.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = StochasticGradientDescent
 ENTITY_CLASS = StochasticFirstOrderOptimisationFramework
 PRIMARY_CONTEXT = GradientDescent
 DEFINITION = "Stochastic gradient descent is an iterative optimisation method that updates decision variables using noisy gradient estimates computed from sampled data or random objective components."
 SYMBOLIC_FORMS = [
  "x_(k+1)=x_k-alpha_k*g_hat_k",
  "E[g_hat_k | x_k] approximately grad f(x_k)",
  "g_hat_k=(1/|B_k|)*sum_(i in B_k) grad f_i(x_k)",
  "alpha_k -> 0 under diminishing-step schedules"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for stochastic gradient estimates, sampling, mini-batches, learning-rate schedules, noise, variance, momentum, adaptive updates, convergence, stopping and reproducibility."
}

SCOPE {
 INCLUDE = [
  StochasticGradientDescent,SGD,StochasticOptimisation,
  GradientDescent,FirstOrderMethod,StochasticGradient,
  GradientEstimator,UnbiasedGradientEstimator,BiasedGradientEstimator,
  SampleGradient,PerSampleGradient,MiniBatchGradient,
  MiniBatchGradientDescent,MiniBatch,FullBatchGradient,
  Dataset,Sample,Observation,TrainingExample,
  RandomSampling,UniformSampling,NonuniformSampling,
  SamplingDistribution,WithReplacementSampling,
  WithoutReplacementSampling,Shuffle,RandomPermutation,
  Epoch,Iteration,UpdateStep,BatchSize,
  ObjectiveFunction,EmpiricalRisk,ExpectedRisk,
  FiniteSumObjective,PopulationObjective,
  LossFunction,RegularisedObjective,
  GradientNoise,GradientVariance,NoiseCovariance,
  Variance,VarianceReduction,ControlVariate,
  SVRG,SAGA,SARAH,StochasticAverageGradient,
  LearningRate,StepSize,ConstantLearningRate,
  DiminishingLearningRate,LearningRateSchedule,
  PolynomialDecay,InverseTimeDecay,ExponentialDecay,
  PiecewiseConstantSchedule,Warmup,CosineDecay,
  CyclicalLearningRate,OneCycleSchedule,
  RobbinsMonroConditions,StochasticApproximation,
  Momentum,HeavyBallMomentum,Velocity,
  NesterovMomentum,NesterovAcceleration,
  AdaGrad,RMSProp,Adam,AMSGrad,
  AdaptiveGradientMethod,SecondMomentEstimate,
  FirstMomentEstimate,BiasCorrection,
  WeightDecay,L2Regularisation,L1Regularisation,
  DecoupledWeightDecay,GradientClipping,
  GradientNormClipping,ValueClipping,
  GradientAccumulation,EffectiveBatchSize,
  DistributedSGD,DataParallelSGD,SynchronousSGD,
  AsynchronousSGD,Hogwild,ParameterServer,
  AllReduce,CommunicationCost,StaleGradient,
  DelayedGradient,LocalSGD,FederatedOptimisation,
  ConvexOptimisation,StronglyConvexOptimisation,
  NonconvexOptimisation,SmoothObjective,
  LipschitzGradient,StrongConvexity,
  StationaryPoint,LocalMinimum,SaddlePoint,
  EscapingSaddlePoint,NoiseInducedExploration,
  Generalisation,ImplicitRegularisation,
  Convergence,ExpectedConvergence,
  AlmostSureConvergence,ConvergenceInProbability,
  SublinearConvergence,LinearConvergence,
  GradientNormConvergence,ObjectiveConvergence,
  Regret,OnlineLearning,OnlineGradientDescent,
  LearningRateTuning,Hyperparameter,
  Initialisation,RandomSeed,Determinism,
  Reproducibility,Checkpoint,Restart,
  StoppingCriterion,MaximumEpochs,
  MaximumIterations,GradientTolerance,
  MovingAverageLoss,ValidationLoss,
  EarlyStopping,PlateauDetection,
  Divergence,Oscillation,Stagnation,
  ExplodingGradient,VanishingGradient,
  FloatingPointArithmetic,MachinePrecision,
  RoundOffError,Underflow,Overflow,
  MixedPrecision,LossScaling,
  Verification,Benchmarking,ReferenceSolution,
  SolverStatus,Success,Failure,Warning
 ]
 EXCLUDE_AS_PRIMARY = [
  FullBatchGradientDescentWithoutStochasticSampling,
  DerivativeFreeOptimisationWithoutGradientEstimates,
  PureMonteCarloEstimationWithoutOptimisationUpdates,
  BackpropagationWithoutParameterUpdateSemantics
 ]
 DISAMBIGUATION_RULE = "When optimisation parameters are updated using gradients estimated from randomly sampled objective components or data subsets, interpret the context as stochastic gradient descent."
}

CORE_CONCEPTS {
 StochasticGradientDescent = "First-order optimisation using stochastic or sampled gradient estimates."
 StochasticGradient = "Random gradient estimator derived from sampled objective components."
 MiniBatch = "Subset of data used to estimate a gradient for one update."
 LearningRate = "Step-size parameter controlling the stochastic update magnitude."
 GradientVariance = "Variance of the stochastic gradient estimator around the full gradient."
 VarianceReduction = "Technique reducing stochastic-gradient noise while retaining cheaper updates."
 Epoch = "One conceptual pass through a dataset or equivalent sampling budget."
 RandomSeed = "State controlling reproducible pseudo-random sampling and initialisation."
}

RELATIONS {
 StochasticGradientDescent --is_child_of--> GradientDescent
 StochasticGradientDescent --uses--> StochasticGradient
 StochasticGradient --is_estimated_from--> SampleOrMiniBatch
 MiniBatchGradientDescent --uses--> MiniBatch
 GradientEstimator --has--> GradientVariance
 LargerBatchSize --often_reduces--> GradientVariance
 LearningRate --controls--> UpdateMagnitude
 DiminishingLearningRate --supports_under_conditions--> StochasticConvergence
 Momentum --modifies--> StochasticGradientUpdate
 NesterovMomentum --accelerates--> StochasticGradientMethod
 SVRG --reduces--> GradientVariance
 SAGA --reduces--> GradientVariance
 Adam --uses--> FirstMomentEstimate
 Adam --uses--> SecondMomentEstimate
 DistributedSGD --parallelises--> GradientComputation
 RandomSeed --supports--> Reproducibility
 Verification --checks--> StochasticOptimisationResult
}

OPERATORS {
 SGD_STEP(x,g_hat,alpha) := x_next=x-alpha*g_hat
 MINIBATCH_GRADIENT(B,x) := (1/|B|)*sum_(i in B) grad f_i(x)
 MOMENTUM_UPDATE(v,g_hat,beta,alpha) := v_next=beta*v-alpha*g_hat
 MOMENTUM_STEP(x,v_next) := x_next=x+v_next
 ADAM_MOMENT1(m,g,beta1) := m_next=beta1*m+(1-beta1)*g
 ADAM_MOMENT2(v,g,beta2) := v_next=beta2*v+(1-beta2)*(g⊙g)
 ADAM_STEP(x,m_hat,v_hat,alpha,eps) := x_next=x-alpha*m_hat/(sqrt(v_hat)+eps)
 CLIP_NORM(g,c) := g*min(1,c/||g||)
 GRADIENT_NOISE(g_hat,g) := eta=g_hat-g
}

AXIOMS {
 A1 = "SGD replaces the full gradient with a stochastic estimator."
 A2 = "Stochastic-gradient variance influences update noise and convergence behaviour."
 A3 = "Learning-rate selection is central to stability and convergence."
 A4 = "Mini-batching trades computation and memory for reduced gradient variance."
 A5 = "Diminishing step-size conditions can support asymptotic convergence under standard stochastic-approximation assumptions."
 A6 = "Constant learning rates generally produce a noise-limited neighbourhood rather than exact convergence in stochastic settings."
 A7 = "Momentum and adaptive-gradient methods modify stochastic dynamics rather than removing stochasticity."
 A8 = "SGD results require explicit sampling, learning-rate, convergence and reproducibility semantics."
}

REASONING {
 R1_CONTEXT = identify(objective,data_structure,sampling_scheme,batch_size,smoothness,convexity,scale,accuracy_goal)
 R2_ESTIMATOR = define(stochastic_gradient_estimator_and_bias_variance_properties)
 R3_SAMPLING = choose(with_replacement,without_replacement,shuffled_or_weighted_sampling)
 R4_STEP_CONTROL = choose(constant,diminishing,scheduled,adaptive_or_warmup_learning_rate)
 R5_UPDATE = compute(SGD,momentum,Nesterov,Adam_or_variance_reduced_step)
 R6_REGULARISATION = if_required apply(weight_decay,penalty,clipping_or_projection)
 R7_DISTRIBUTION = if_parallel choose(synchronous,asynchronous,local_or_federated_aggregation)
 R8_MONITOR = track(training_objective,gradient_norm,variance,validation_metric,oscillation_and_divergence)
 R9_CONVERGENCE = assess(expected_progress,noise_floor,stationarity,plateaus_and_resource_limits)
 R10_VALIDATE = repeat_with_controlled_seeds_and_compare(reference_or_benchmark_behaviour)
}

CONSTRAINTS {
 C1 = "A learning rate that is too large can cause stochastic divergence or persistent oscillation."
 C2 = "A learning rate that is too small can make optimisation impractically slow."
 C3 = "Small mini-batches increase gradient noise."
 C4 = "Large mini-batches reduce noise but can increase memory, communication and diminishing-return costs."
 C5 = "Biased gradient estimators require separate convergence reasoning."
 C6 = "Adaptive methods such as Adam have convergence behaviour distinct from plain SGD."
 C7 = "Asynchronous updates can use stale gradients and introduce additional error."
 C8 = "Validation loss can differ from training loss and should not be conflated with optimisation objective convergence."
 C9 = "A fixed random seed improves reproducibility but does not remove all hardware or parallel nondeterminism."
 C10 = "Finite precision and mixed-precision underflow can distort small gradient updates."
}

SEMANTIC_EQUIVALENCE {
 "StochasticGradientDescent" <=> "SGD"
 "MiniBatchGradientDescent" <=> "MiniBatchSGD"
 "StochasticApproximation" <=> "RobbinsMonroStyleOptimisationInSGDContext"
 "HeavyBallMomentum" <=> "MomentumSGD"
 "DistributedSGD" <=> "DistributedStochasticGradientDescent"
}

VALIDATION {
 V1 = "Objective and data or finite-sum structure are explicit."
 V2 = "Sampling scheme is documented."
 V3 = "Batch size is documented."
 V4 = "Learning-rate schedule is documented."
 V5 = "Momentum, adaptive or variance-reduction parameters are documented."
 V6 = "Random seeds and shuffle behaviour are documented where reproducibility matters."
 V7 = "Training and validation metrics are distinguished."
 V8 = "Multiple runs are compared when stochastic variability is material."
 V9 = "Distributed aggregation semantics are documented for parallel SGD."
 V10 = "Results are reproducible to the extent allowed by documented arithmetic and hardware settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 SGD_DEFINITION = 0.99
 SAMPLING_REASONING = 0.99
 LEARNING_RATE_REASONING = 0.99
 MINI_BATCH_REASONING = 0.99
 MOMENTUM_REASONING = 0.98
 VARIANCE_REDUCTION_REASONING = 0.98
 ADAPTIVE_METHOD_REASONING = 0.98
 DISTRIBUTED_SGD_REASONING = 0.97
 POLICY = "Reduce confidence when gradient-estimator bias, sampling scheme, batch size, learning rate, variance, distributed staleness or reproducibility settings are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,OntologyGrounding,StochasticGradientDescentReasoning,
  StochasticGradientReasoning,MiniBatchReasoning,
  LearningRateReasoning,SamplingReasoning,
  GradientVarianceReasoning,VarianceReductionReasoning,
  MomentumReasoning,NesterovReasoning,
  AdaGradReasoning,RMSPropReasoning,AdamReasoning,
  DistributedSGDReasoning,AsynchronousSGDReasoning,
  ConvergenceReasoning,GeneralisationRelationshipReasoning,
  EarlyStoppingReasoning,ReproducibilityReasoning,
  VerificationReasoning,KnowledgeGraphConstruction,
  RetrievalAugmentation,RecursiveInference
 ]
 NORMALISE {
  "stochastic gradient descent" -> StochasticGradientDescent
  "SGD" -> StochasticGradientDescent
  "mini-batch SGD" -> MiniBatchGradientDescent
  "momentum SGD" -> HeavyBallMomentum
  "distributed SGD" -> DistributedSGD
  "variance-reduced SGD" -> VarianceReduction
 }
}

EXECUTION_RULES {
 E1 = "If optimisation updates use sampled or mini-batch gradient estimates, activate StochasticGradientDescentOntology."
 E2 = "Document sampling and batch-size semantics before interpreting convergence."
 E3 = "Choose learning-rate schedules according to smoothness, noise and optimisation horizon."
 E4 = "If gradient variance is high, consider larger batches, momentum or variance-reduction methods."
 E5 = "For adaptive-gradient variants, retain separate semantics for first- and second-moment estimates."
 E6 = "For distributed SGD, document synchronisation, aggregation and gradient staleness."
 E7 = "Use controlled random seeds and repeated runs when stochastic variability is material."
 E8 = "Distinguish optimisation convergence, noise-floor behaviour, early stopping and resource-limit termination."
 E9 = "Validate training dynamics, gradient statistics, reproducibility and benchmark behaviour."
}

RECURSION {
 ENTRY = StochasticGradientDescent
 EXPAND(StochasticGradientDescent) -> [
  SGD,StochasticOptimisation,GradientDescent,StochasticGradient,
  GradientEstimator,UnbiasedGradientEstimator,BiasedGradientEstimator,
  SampleGradient,MiniBatchGradient,MiniBatchGradientDescent,
  MiniBatch,Dataset,Sample,RandomSampling,UniformSampling,
  NonuniformSampling,WithReplacementSampling,WithoutReplacementSampling,
  Shuffle,RandomPermutation,Epoch,BatchSize,EmpiricalRisk,
  ExpectedRisk,FiniteSumObjective,LossFunction,GradientNoise,
  GradientVariance,NoiseCovariance,VarianceReduction,SVRG,SAGA,SARAH,
  LearningRate,ConstantLearningRate,DiminishingLearningRate,
  LearningRateSchedule,PolynomialDecay,ExponentialDecay,
  Warmup,CosineDecay,CyclicalLearningRate,RobbinsMonroConditions,
  Momentum,HeavyBallMomentum,NesterovMomentum,AdaGrad,RMSProp,
  Adam,AMSGrad,FirstMomentEstimate,SecondMomentEstimate,
  WeightDecay,GradientClipping,GradientAccumulation,
  DistributedSGD,SynchronousSGD,AsynchronousSGD,LocalSGD,
  ParameterServer,AllReduce,StaleGradient,DelayedGradient,
  ConvexOptimisation,StronglyConvexOptimisation,NonconvexOptimisation,
  LipschitzGradient,StationaryPoint,SaddlePoint,
  ExpectedConvergence,AlmostSureConvergence,ConvergenceInProbability,
  SublinearConvergence,LinearConvergence,OnlineGradientDescent,
  Initialisation,RandomSeed,Determinism,Checkpoint,EarlyStopping,
  PlateauDetection,Divergence,Oscillation,Stagnation,
  FloatingPointArithmetic,MixedPrecision,LossScaling,
  Verification,Benchmarking,ReferenceSolution,Reproducibility
 ]
 EXPAND(SGDFamilies) -> [
  SingleSampleSGD,
  MiniBatchSGD,
  MomentumSGD,
  NesterovSGD,
  VarianceReducedSGD,
  AdaptiveGradientMethods,
  DistributedSGD,
  OnlineGradientDescent
 ]
 STOP_CONDITION = "Stop when estimator, sampling, batch size, learning rate, stochastic variance, acceleration, distributed execution, convergence and reproducibility are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Gradient Descent Ontology 2"
 RELATED_ONTOLOGIES = [
  "Gradient Descent Ontology 2",
  "Computational Optimisation Ontology",
  "Optimisation Computation",
  "Nonlinear Optimisation Solver Ontology",
  "Numerical Differentiation Ontology 2",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology",
  "Scientific Computing Ontology 2",
  "Artificial Intelligence Mathematics",
  "Probability and Statistics Ontologies"
 ]
 ROUTE_RULES = [
  "Stochastic Gradient Descent -> Gradient Descent for parent first-order semantics",
  "Stochastic Gradient Descent -> Computational Optimisation for algorithmic optimisation context",
  "Stochastic Gradient Descent -> Nonlinear Optimisation Solver for nonconvex objective context",
  "Stochastic Gradient Descent -> Numerical Analysis for stochastic convergence theory",
  "Stochastic Gradient Descent -> Numerical Error for gradient-estimation and round-off error",
  "Stochastic Gradient Descent -> Numerical Stability for learning-rate and finite-precision behaviour",
  "Stochastic Gradient Descent -> Scientific Computing for distributed and parallel execution",
  "Stochastic Gradient Descent -> Artificial Intelligence Mathematics for model-training optimisation",
  "Stochastic Gradient Descent -> Probability and Statistics for sampling, expectation and variance semantics"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible SGD variants, schedules or stochastic reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve full-gradient-versus-stochastic-gradient distinction.",
  "Preserve sample-versus-mini-batch distinction.",
  "Preserve gradient-bias-versus-gradient-variance distinction.",
  "Preserve constant-versus-diminishing learning-rate distinction.",
  "Preserve plain-SGD-versus-momentum-versus-adaptive-method distinction.",
  "Preserve optimisation-objective-versus-validation-metric distinction.",
  "Preserve deterministic-seed-versus-hardware-determinism distinction.",
  "Preserve machine-readable stochastic-gradient-descent semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Stochastic gradient descent updates optimisation variables using gradient estimates computed from randomly sampled objective components or data subsets."
 SAMPLING_SUMMARY = "Sample and mini-batch selection determine the stochastic gradient estimator and its variance."
 STEP_SUMMARY = "Learning-rate schedules control the trade-off between rapid progress, noise and asymptotic convergence."
 VARIANCE_SUMMARY = "Mini-batching and variance-reduction methods reduce gradient noise at additional computational or memory cost."
 ACCELERATION_SUMMARY = "Momentum, Nesterov and adaptive-gradient variants modify SGD dynamics to improve practical optimisation."
 DISTRIBUTED_SUMMARY = "Distributed SGD parallelises gradient computation but introduces communication, aggregation and possible staleness semantics."
 VALIDATION_SUMMARY = "SGD results should be checked through sampling documentation, repeated runs, gradient statistics, convergence behaviour, seeds and reproducibility."
}

FLOW {
 INPUT
 -> detect_stochastic_gradient_descent_context
 -> identify_objective_data_sampling_scheme_batch_size_smoothness_convexity_scale_and_accuracy_goal
 -> define_stochastic_gradient_estimator_and_bias_variance_properties
 -> choose_sampling_and_shuffle_strategy
 -> select_constant_diminishing_scheduled_adaptive_or_warmup_learning_rate
 -> choose_plain_SGD_momentum_Nesterov_variance_reduced_or_adaptive_gradient_update
 -> compute_sample_or_minibatch_gradient
 -> optionally_apply_regularisation_clipping_projection_or_weight_decay
 -> update_parameters
 -> if_distributed_aggregate_gradients_and_handle_staleness
 -> monitor_objective_gradient_statistics_validation_metrics_oscillation_stagnation_and_divergence
 -> assess_expected_convergence_noise_floor_stationarity_and_resource_limits
 -> validate_with_controlled_seeds_repeated_runs_reference_behaviour_and_reproducibility
 -> route_to_related_gradient_descent_optimisation_probability_analysis_error_stability_convergence_scientific_computing_and_AI_mathematics_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Stochastic Gradient Descent Ontology defines first-order optimisation using sampled gradient estimates. It supports single-sample and mini-batch gradients, random and shuffled sampling, epochs, empirical and expected objectives, gradient noise and variance, constant and diminishing learning rates, warmup and decay schedules, Robbins-Monro conditions, momentum and Nesterov updates, AdaGrad, RMSProp, Adam and AMSGrad, variance-reduction methods such as SVRG, SAGA and SARAH, gradient clipping, regularisation, distributed synchronous and asynchronous SGD, stale gradients, convex, strongly convex and nonconvex convergence, online optimisation, early stopping, random seeds, mixed precision, verification, benchmarking and reproducibility."
}

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

}

END_FLOW