Ensemble Methods

39 beliefs (38 IN, 0 OUT)

• IN any-positive-inner-product-direction-is-descent
  Any direction with positive inner product with the negative gradient is a valid descent direction (not just the gradient itself), provided the step size is sufficiently small
• IN backprop-backward-vs-forward-complexity
  Backward-mode differentiation multiplies a vector by a matrix at each layer (O(n²) per layer), while forward-mode multiplies a matrix by a matrix (O(n³) per layer), making backward mode computationally superior for computing loss gradients.
• IN backprop-loss-derivative-is-covector
  The derivative of a scalar-valued loss function with respect to a vector of parameters is a covector (row vector), not a column vector.
• IN barzilai-borwein-adaptive-step-size
  The Barzilai-Borwein method computes an adaptive step size using consecutive gradient differences: η_n = |(x_n - x_{n-1})^T[∇f(x_n) - ∇f(x_{n-1})]| / ‖∇f(x_n) - ∇f(x_{n-1})‖², requiring no line search
• IN cauchy-originated-gradient-method
  Cauchy originated the gradient descent method in 1847; Curry formalized steepest descent in 1944
• IN conjugate-gradient-sqrt-kappa-vs-steepest-descent-kappa
  Steepest descent convergence for linear systems is O(κ) iterations while conjugate gradient is O(√κ), where κ is the spectral condition number — this is why conjugate gradient is preferred
• IN convex-functions-local-minima-are-global
  For convex functions, all local minima are global minima, so gradient descent is guaranteed to converge to the global solution
• IN dl-contrastive-divergence-lacks-convergence-guarantees
  Contrastive divergence lacks theoretical convergence and approximation quality guarantees, unlike gradient descent.
• IN double-descent-phenomenon
  Double descent is a phenomenon where test error decreases, increases, then decreases again as model complexity grows far beyond the interpolation threshold, challenging the classical U-shaped tradeoff curve.
• ? exam-fail-q34
  
• IN fisher-information-approximates-hessian
  The Fisher information matrix is used as a practical approximation to the Hessian matrix in second-order neural network optimization methods.
• IN gd-first-order-method-taxonomy
  Optimization methods are taxonomized as function-based (no gradient, e.g. Nelder-Mead), gradient-based/first-order (e.g. gradient descent), and Hessian-based/second-order (e.g. Newton's method)
• IN gd-gradient-flow-ode
  Gradient descent is Euler's method applied to the ODE x'(t) = -∇f(x(t)), connecting optimization to dynamical systems theory
• IN gd-gradient-via-jacobian
  The gradient of f(x) = ½ ||G(x)||² is ∇f = J_G^T · G, where J_G is the Jacobian matrix of the system G
• IN gd-linear-convergence-conditions
  Gradient descent with fixed step size achieves linear convergence (error decreases by a constant factor each iteration) when the objective is both strongly convex and has Lipschitz continuous gradients
• IN gd-momentum-update-rule
  The heavy ball (momentum) update rule is x^(k+1) = x^(k) - η·∇f(x^(k)) + β·(x^(k) - x^(k-1)), adding a fraction of the previous step to dampen oscillation
• IN gd-nonlinear-system-objective
  To solve a nonlinear system G(x)=0 via gradient descent, define the objective f(x) = ½ G^T(x) G(x) and minimize it; a solution corresponds to f(x)=0
• IN gd-saddle-point-limitation
  Gradient descent can slow down or get stuck near saddle points, which is a known limitation for non-convex optimization
• IN gd-unconstrained-method
  Gradient descent is an unconstrained optimization method; constrained problems require different methods such as barrier, penalty, or augmented Lagrangian methods
• IN gradient-descent-cauchy-1847-origin
  Gradient descent is attributed to Augustin-Louis Cauchy (1847), with independent work by Jacques Hadamard (1907) and convergence analysis for nonlinear problems by Haskell Curry (1944)
• IN gradient-descent-conditionally-reliable
  Gradient descent convergence is conditionally reliable — linear convergence is achievable under strong convexity and Lipschitz smoothness, but non-convex landscapes present saddle points that can trap or slow optimization, with momentum methods providing partial mitigation by accumulating velocity across the loss surface.
• IN gradient-descent-finds-local-not-global-minima
  Gradient descent with backpropagation finds local minima only, with no guarantee of reaching a global minimum; however, LeCun et al. argued this is often acceptable in practice for neural networks.
• IN gradient-descent-first-order-negative-gradient
  Gradient descent is a first-order iterative optimization algorithm that moves in the negative gradient direction (steepest descent) to find local minima of differentiable functions
• IN gradient-descent-update-rule
  The gradient descent update rule is x_{n+1} = x_n - η·∇f(x_n), where η is the learning rate (step size) and ∇f is the gradient of the objective function
• IN gradient-orthogonal-to-contour-lines
  The gradient at any point is orthogonal to the contour line (level set) passing through that point
• IN levenberg-marquardt-second-order-faster-convergence
  The Levenberg–Marquardt algorithm uses second-order (Hessian) information and converges faster than first-order gradient descent on complex error landscapes, and may find solutions with smaller network architectures.
• IN loss-function-desirable-properties
  Desirable properties of a loss function include convexity, differentiability, and robustness.
• IN max-norm-constraint-typical-values
  Max norm constraints clamp the L2 norm of weight vectors to an upper bound c (typically 3-4) after each parameter update via projected gradient descent
• IN method-of-moments-global-convergence-vs-em-local
  Method of moments provides global convergence guarantees under certain conditions for latent variable model estimation; EM algorithm can get stuck in local optima
• IN mini-batch-gradient-descent-compromise
  Mini-batch gradient descent is a compromise between stochastic (per-sample) and batch (full-dataset) weight updates.
• IN mirror-descent-generalizes-gd
  Gradient descent is a special case of mirror descent using squared Euclidean distance as the Bregman divergence
• IN nesterov-convergence-rate-optimal
  Nesterov accelerated gradient achieves O(k^-2) convergence rate for convex Lipschitz-smooth objectives, improving over standard gradient descent's O(k^-1), and this is optimal for first-order methods
• IN optimizer-hierarchy-speed-vs-cost
  The optimizer hierarchy in terms of convergence speed vs per-iteration cost is: gradient descent → momentum → Nesterov → quasi-Newton (BFGS)
• IN quasi-newton-approximate-hessian
  Quasi-Newton methods (BFGS, L-BFGS, DFP, SR1) approximate second-order Hessian information without computing the full Hessian, offering faster convergence than plain gradient descent
• IN safe-rl-uses-cvar-constrained-optimization
  Safe RL optimizes policies while respecting safety constraints using CVaR or constrained optimization, but CVaR optimization requires care to avoid gradient bias and 'blindness to success'
• IN sgd-traces-to-robbins-monro-1951
  Stochastic gradient descent traces to Robbins & Monro (1951), 'A Stochastic Approximation Method'.
• IN steepest-descent-linear-systems-spd-step-size
  For steepest descent on SPD linear systems Ax=b, the optimal step size is η = (r^T r)/(r^T A r) where r = b - Ax is the residual, derivable analytically from the quadratic structure
• IN steepest-descent-residuals-orthogonal
  In steepest descent with exact line search, consecutive residual vectors are orthogonal (⟨r_{k+1}, r_k⟩ = 0), which causes characteristic zig-zag convergence behavior
• IN weight-matrix-derivative-of-linear-map
  The derivative of a linear map Wx with respect to the input x is the matrix W itself: (Wx)' = W.