Optimization

Optimization Theory

Type	Definition	Key Components	Examples
Unconstrained Optimization	Optimization without explicit constraints on variables	Gradient Descent (Batch, Stochastic, Mini-batch) Momentum, Adagrad, RMSprop, Adam optimizers Newton's Method, Quasi-Newton Methods (BFGS, L-BFGS)	Most machine learning training algorithms
Constrained Optimization	Optimization with explicit constraints on variables	Lagrangian Multipliers, KKT conditions Penalty methods	Resource allocation, portfolio optimization
Convex Optimization	Optimization over convex sets with convex objective functions	Convex sets, convex functions Importance for guaranteeing global optima Applications in SVMs and various regularization techniques	Support Vector Machines, L1/L2 regularization

Cost Loss

Function	Purpose	Formula	Key Characteristics	Use Cases
Mean Squared Error (MSE) / L2 Loss	Regression: minimize squared differences between predicted and actual values	$MSE = \frac{1} {n} \sum_{(i = 1)}^{n} (Y_i - \hat{Y}_i)^2$	Differentiable, convex (for linear regression), sensitive to outliers	Linear regression, continuous value prediction
Mean Absolute Error (MAE) / L1 Loss	Regression: minimize absolute differences between predicted and actual values	$MAE = \frac{1}{n} \sum_{(i = 1)}^{n} |Y_i - \hat{Y}_i|$	Robust to outliers, not differentiable at zero	Regression tasks with outliers, robust error measurement
Binary Cross-Entropy / Log Loss	Binary classification: measure prediction accuracy when output is probability between 0 and 1	$C = - \frac{1}{n} \sum_{(i = 1)}^{n} [Y_i \log(\hat{Y}_i) + (1-Y_i) \log(1-\hat{Y}_i)]$	Penalizes wrong confident predictions, differentiable, pairs with sigmoid activation	Logistic regression, spam detection, medical diagnosis
Categorical Cross-Entropy (Softmax Loss)	Multi-class classification: evaluate predictions across multiple classes	$${n} \sum_{(i = 1)}^{n} \sum_{(j = 1)}^{C} Y_{ij} \log(\hat{Y}_{ij})$$	Extension of binary version, works with softmax, differentiable	Image recognition, NLP tasks, multi-class classification
Hinge Loss	Classification (esp. SVM): maximize margin between classes	$L(y, \hat{y}) = \max(0, 1 - y \cdot \hat{y})$	Zero loss region for confident predictions, not differentiable at all points	Support Vector Machines, margin-based classifiers

Gradient Descent

Variant	Concept	Pros	Cons	Update Rule
Batch Gradient Descent (BGD)	Uses the entire dataset to compute the gradient before each update	Stable convergence Reliable (global minimum for convex, local for non-convex) Deterministic updates	Very slow for large datasets High memory/computation cost Not suitable for online learning	$\theta = \theta - \alpha \nabla J(\theta)$ with all data
Stochastic Gradient Descent (SGD)	Updates parameters after computing gradient for each data point	Fast updates Enables online learning Noise can help escape local minima/saddle points	Noisy updates cause fluctuations May oscillate around minimum Can fail to converge precisely	$\theta = \theta - \alpha \nabla J(\theta; x^{i}, y^{i})$ with one example
Mini-Batch Gradient Descent (MBGD)	Updates based on small batches of examples	Balances stability (BGD) and speed (SGD) Efficient with vectorized ops More stable convergence vs. SGD Some noise helps avoid local minima	Requires selecting/tuning batch size	$\theta = \theta - \alpha \nabla J(\theta; X^{j}, Y^{j})$ with batch
Momentum	Adds a fraction of the previous update to the current update (like rolling a ball downhill)	Accelerates convergence in relevant direction Reduces oscillations Helps escape shallow minima	Adds extra hyperparameter (momentum term) Can overshoot if poorly tuned	Similar to GD but with momentum term accumulated
RMSprop	Divides learning rate by root mean square of historical gradients	Handles differing gradient scales Effective in non-stationary problems Faster convergence than vanilla GD	Learning rate must still be tuned Sensitive to hyperparameters	Adaptive per-parameter learning rate
Adam	Combines Momentum + RMSprop, using first (mean) and second (variance) moments of gradients	Widely used "default" optimizer Fast convergence Works well out-of-box	Sometimes generalizes worse than SGD More hyperparameters (though defaults often okay)	Adaptive moment estimates for update

Convexity

Aspect	Convex Functions	Non-Convex Functions
Shape	Bowl-shaped; "cups upwards"	Complex landscapes with hills, valleys, and plateaus
Mathematical Condition	$f(tx_1 + (1-t)x_2) \le t f(x_1) + (1-t) f(x_2)$	Does not satisfy convex inequality for all points
Local vs Global Minima	Any local minimum is also a global minimum	Multiple local minima, saddle points, and flat regions
Optimization Guarantee	Gradient descent (with proper learning rate) always converges to the global minimum	Gradient descent may get stuck in local minima or saddle points
Sensitivity to Initialization	Low; starting point less critical as all paths lead to same minimum	High; results depend heavily on initial parameter values
Convergence	Deterministic and reliable	Can be slow, with risk of poor solutions
Optimization Methods	Simple methods like gradient descent or closed-form solutions often sufficient	Require advanced optimizers (Adam, RMSprop, SGD with momentum), multiple restarts, or careful initialization
Theoretical Guarantees	Strong; ensures uniqueness and optimality of solution	Weak; solutions may be suboptimal and vary between runs
Examples	Mean Squared Error (linear regression), Cross-Entropy (logistic regression), L2-regularized loss	Deep neural networks, complex non-linear models
Use in Data Analysis	Enables reliable model interpretation and parameter estimates (e.g., regression coefficients)	Powerful for complex models, but less interpretable and harder to optimize

Time Series

Concept	Definition	Purpose	Indicators & Techniques	Use Cases
Stationarity	Statistical properties (mean, variance, autocorrelation) remain constant over time	Ensures model validity, reliable inference, stable forecasting	Strict vs. Weak Stationarity Achieved via differencing, log transforms, seasonal differencing	Core assumption for AR, MA, ARIMA; non-stationarity (trends, seasonality, heteroscedasticity) must be corrected
ACF (Autocorrelation Function)	Correlation of a series with its lagged versions	Reveals lag dependencies; detects seasonality or trends	Slow decay → trend or non-stationarity Sharp drop-off → MA component Spikes at certain lags → seasonality	Crucial for identifying q (MA order) in ARIMA and capturing dependencies
PACF (Partial Autocorrelation Function)	Correlation between series and lagged values with intermediate lags removed	Measures direct lag effects	Sharp drop-off → AR component Helps differentiate AR vs. MA structure	Identifies p (AR order) in ARIMA; builds feature lags for models
ARIMA Models	Combines AR (past values), I (differencing), and MA (errors)	Forecasting sequential data	AR: past value relationships (PACF guides p) I: differencing for stationarity (d) MA: past error terms (ACF guides q)	Widely used for short/medium-term forecasts, benchmark models, trend/seasonality decomposition
Spectral Analysis	Represents data in frequency domain via sinusoidal components	Detects hidden cycles, dominant frequencies	Uses periodogram/Power Spectral Density (PSD) Peaks → dominant periodicities	Identifies seasonality, key for signal processing, feature extraction
Fourier Transform	Converts time-domain signal into frequency-domain representation	Reveals underlying frequencies; enables reconstruction and filtering	Continuous FT, Discrete FT, FFT for computation Inverse FT reconstructs original signal	Used in decomposition, noise filtering, audio/image processing, and advanced time series models

Bayesian Statistics

Aspect	Bayesian Statistics	Frequentist Statistics
Core Idea	Updates beliefs with data; probabilities represent degrees of belief	Focuses on probability of data given a fixed hypothesis; probabilities represent long-run frequencies
Foundation	Bayes' Theorem: $P(H|E) \propto P(E|H) \cdot P(H)$	Hypothesis testing and confidence intervals
Parameters	Treated as random variables with probability distributions	Treated as fixed, unknown quantities
Priors	Incorporates prior knowledge (informative, non-informative, conjugate)	No role for prior probabilities
Inference Result	Full posterior distribution summarizing uncertainty	Point estimates and p-values; intervals are confidence intervals
Hypothesis Testing	Uses posterior probabilities and Bayes factors for model comparison	Uses significance tests and p-values
Uncertainty Quantification	Credible intervals: direct probability statements about parameters	Confidence intervals: indirect interpretation across repeated samples
Computation	Often requires advanced techniques like MCMC (Metropolis-Hastings, Gibbs, HMC)	Closed-form or asymptotic approximations more common
Flexibility	Naturally handles small datasets, expert knowledge, hierarchical models, complex structures	Stronger with large datasets; less flexible for complex prior information
Use Cases	A/B testing, diagnostics, machine learning (Bayesian optimization, networks), risk assessment	Classical hypothesis testing, large-scale statistical inference

Information Theory

Concept	Formula	What it Measures	Key Interpretations	Use Cases
Entropy	$H(X) = - \sum_{(i = 1)}^{n} P(x_i) \log_b(P(x_i))$	Uncertainty/randomness in a probability distribution	High entropy = high uncertainty Zero entropy = completely certain outcome Maximum entropy when outcomes are equally likely	Feature selection (information gain in decision trees) Data compression (lower bound on encoding) Model evaluation for uncertainty Anomaly detection via abnormal entropy levels
Cross-Entropy	$H(P, Q) = - \sum_{(i = 1)}^{n} P(x_i) \log_b(Q(x_i))$	Difference between true distribution $P$ and predicted distribution $Q$	Lower values = predicted distribution closer to true Higher values = greater disagreement Commonly used as a loss function	Binary cross-entropy/log loss for binary classification Categorical cross-entropy for multi-class classification Core loss function in logistic regression, neural networks Optimizing probabilistic outputs during model training
KL Divergence	$H(X) = - \sum_{(i = 1)}^{n} P(x_i) \log_b(P(x_i))$	Information loss when approximating distribution $P$ with $Q$	Always ≥ 0, equals 0 if $P=Q$ Asymmetric: $D_{KL}(P||Q) \neq D_{KL}(Q||P)$ Measures extra bits needed using wrong distribution	Training generative models (VAEs, GANs) Dimensionality reduction (t-SNE) Reinforcement learning (policy optimization) Bayesian inference (info gain from prior → posterior) Comparing model probability outputs

Numerical Methods

Aspect	Key Concepts	Challenges	Use Cases
Floating-Point Arithmetic	Finite precision (float32, float64) Rounding errors (e.g., 0.1 + 0.2 ≠ 0.3) Limited numerical range (inf, NaN)	Accumulation of errors over many operations Catastrophic cancellation (subtracting nearly equal numbers) Loss of significance when adding very small to very large numbers	Impacts stability of optimization Affects statistical metrics (variance, correlation, etc.) Equality checks unreliable (use tolerance) Guides design of numerically stable algorithms
Numerical Stability	Stability means small input errors → small output errors Stability depends on algorithm formulation and problem conditioning	Ill-conditioned problems (e.g., near-singular matrices) Unstable algorithms magnify small errors Floating-point limitations worsen instability	Robust model training Matrix operations (e.g., regression with multicollinearity) Reproducibility across systems Algorithm selection (e.g., np.linalg.solve vs inv(A))
Newton's Method	Uses gradient + Hessian to jump directly toward minima Quadratic convergence near optimum	High computational cost (Hessian inversion) Requires second derivatives Sensitive to initialization	Used in logistic regression, GLMs, statistical modeling Benchmark for fast convergence when parameter size is manageable
Quasi-Newton Methods (BFGS, L-BFGS)	Approximate Hessian using gradient history Faster than gradient descent with curvature info	More costly than simple first-order methods Still heavy for ultra high-dimension problems	Widely used in optimization libraries Commonly applied in fitting smooth loss models L-BFGS practical for large-scale ML
Conjugate Gradient Method	Solves large systems iteratively without explicit Hessian Works along conjugate directions	Limited to quadratic/linear functions Sensitive to poorly conditioned matrices	Linear regression with very large datasets Efficient for sparse systems Applications in scientific computing and PDEs