Optimization Techniques in Machine Leaning (AL-503 (C)) - Unit 1 Short Notes

I. Introduction to Deep Learning and Machine Learning Paradigms

Deep Learning (DL) is a subset of machine learning (ML) that uses deep neural networks (multiple hidden layers) to learn hierarchical representations of data automatically.

Historical Milestones:

• 1943: McCulloch-Pitts neuron model.

• 1958: Perceptron by Rosenblatt.

• 1986: Backpropagation popularized by Rumelhart, Hinton, Williams.

• 2006: Deep Belief Networks (Hinton) – pretraining for deep networks.

• 2012: AlexNet wins ImageNet – GPU + ReLU + Dropout.

• 2015: ResNet – residual connections for very deep networks.

• 2017: Transformer architecture (Attention Is All You Need).

Learning Paradigms:

Key Difference (RL vs Supervised): RL uses delayed, sparse rewards and learns from interaction with an environment, not fixed input-label pairs.

Representation Learning: Automatically discovering useful features/representations from raw data (e.g., CNN layers learning edges → textures → objects).

Applications: Computer vision, NLP, speech recognition, recommendation systems, autonomous vehicles.

[!TIP]

Exam Focus: Distinguish supervised (labeled data) vs unsupervised (unlabeled) vs RL (reward-based). Mention AlexNet/ResNet as milestones.

II. Neural Network Fundamentals

Artificial Neuron Model: Computes weighted sum + bias, applies activation function:

$$ z = \mathbf{w}^T \mathbf{x} + b, \quad a = f(z) $$

Perceptron: Single-layer neuron with step activation.
Learning Rule: $$\displaystyle w_{new} = w_{old} + \eta (y - \hat{y}) x $$
Limitations: Only linearly separable problems; no multi-class output.

Multilayer Perceptron (MLP): Fully connected network with ≥1 hidden layer.
Feedforward Neural Network: Information flows forward, no cycles.
Forward Propagation: Compute layer-by-layer:

$$ \mathbf{a}^{(l)} = f^{(l)}(\mathbf{W}^{(l)} \mathbf{a}^{(l-1)} + \mathbf{b}^{(l)}) $$

Universal Approximation Theorem: An MLP with a single hidden layer (sufficient neurons) can approximate any continuous function on compact subsets of $$\displaystyle \mathbb{R}^n $$, given appropriate activation (e.g., sigmoid).

Logistic Regression: Single-layer neural network with sigmoid activation for binary classification:

$$ P(y=1|\mathbf{x}) = \sigma(\mathbf{w}^T\mathbf{x} + b) = \frac{1}{1+e^{-(\mathbf{w}^T\mathbf{x}+b)}} $$

Recursive Neural Networks (RvNN): Tree-structured network; same weights applied recursively to merge child representations into parent. Used for syntactic parsing, sentiment analysis.

[!TIP]

Exam Focus: Know perceptron rule, MLP forward pass equation, universal approximation statement, logistic regression as single-layer network. RvNNs are for tree data, not sequences.

III. Activation Functions

Purpose: Introduce non-linearity; without it, deep networks collapse to linear transformations.

Selection Criteria:

• Hidden layers: ReLU (default), Leaky ReLU/PReLU if dying ReLU suspected.

• Output layer: Sigmoid (binary), Softmax (multi-class).

• RNNs: tanh or Sigmoid for gating (LSTM/GRU).

[!TIP]

Exam Focus: Memorize equations/derivatives for sigmoid, tanh, ReLU. Know vanishing gradient (sigmoid/tanh) vs dying ReLU. Softmax for multi-class output.

IV. Loss Functions and Gradient Descent

Common Loss Functions:

• Mean Squared Error (MSE): Regression

$$ \text{MSE} = \frac{1}{N} \sum_{i=1}^N (y_i - \hat{y}_i)^2 $$

• Binary Cross-Entropy: Binary classification

$$ \mathcal{L} = -\frac{1}{N} \sum_{i=1}^N \left[ y_i \log(\hat{y}_i) + (1-y_i) \log(1-\hat{y}_i) \right] $$

• Categorical Cross-Entropy: Multi-class

$$ \mathcal{L} = -\frac{1}{N} \sum_{i=1}^N \sum_{c=1}^C y_{ic} \log(\hat{y}_{ic}) $$

($$\displaystyle y_{ic} $$: one-hot encoded true label, $$\displaystyle \hat{y}_{ic} $$: predicted probability)

Gradient Descent Variants:

Challenges in Loss Landscape:

• Local Minima: Rare in high-D; usually saddle points.

• Saddle Points: Gradient near zero but not minimum; common in high-D.

• Plateaus: Flat regions; slow progress.

[!TIP]

Exam Focus: Write MSE and cross-entropy formulas. Know mini-batch GD is standard. Distinguish binary vs categorical cross-entropy.

V. Backpropagation Algorithm

Core Idea: Apply chain rule to compute gradients of loss w.r.t. weights in a feedforward network.

Step-by-Step Procedure:

1. Forward Pass: Compute activations for all layers.

2. Compute Loss: $$\displaystyle \mathcal{L} = \mathcal{L}(\hat{\mathbf{y}}, \mathbf{y}) $$.

3. Backward Pass:

   • Output layer: $$\displaystyle \delta^{(L)} = \nabla_{\mathbf{a}^{(L)}} \mathcal{L} \odot f'^{(L)}(\mathbf{z}^{(L)}) $$

   • Hidden layers: $$\displaystyle \delta^{(l)} = (\mathbf{W}^{(l+1)})^T \delta^{(l+1)} \odot f'^{(l)}(\mathbf{z}^{(l)}) $$

   • Gradients: $$\displaystyle \nabla_{\mathbf{W}^{(l)}} \mathcal{L} = \delta^{(l)} (\mathbf{a}^{(l-1)})^T $$, $$\displaystyle \nabla_{\mathbf{b}^{(l)}} \mathcal{L} = \delta^{(l)} $$

4. Weight Update: $$\displaystyle \mathbf{W}^{(l)} \leftarrow \mathbf{W}^{(l)} - \eta \nabla_{\mathbf{W}^{(l)}} \mathcal{L} $$

Backpropagation Through Time (BPTT): Unfolds RNN across time steps, applies backpropagation. Gradients can vanish/explode over long sequences.

Vanishing/Exploding Gradients:

• Cause: Repeated multiplication of small/large Jacobians (sigmoid/tanh saturation, deep networks).

• Impact: Vanishing → early layers learn slowly; Exploding → unstable training.

• Solutions: ReLU, gradient clipping, batch normalization, residual connections.

Gradient Checking: Numerically approximate gradient via finite differences to verify backprop implementation:

$$ \frac{\partial \mathcal{L}}{\partial \theta_i} \approx \frac{\mathcal{L}(\theta_i + \epsilon) - \mathcal{L}(\theta_i - \epsilon)}{2\epsilon} $$

Compare with analytical gradient; should be nearly equal.

[!TIP]

Exam Focus: Derive backprop equations for a 2-layer MLP. Explain BPTT for RNNs. Vanishing gradient: sigmoid/tanh saturation; solutions: ReLU, ResNet. Gradient checking formula.

VI. Optimization Algorithms

Momentum:

• Accumulates past gradients: $$\displaystyle \mathbf{v}_t = \gamma \mathbf{v}_{t-1} + \eta \nabla_\theta \mathcal{L}(\theta_t) $$

• Update: $$\displaystyle \theta_{t+1} = \theta_t - \mathbf{v}_t $$

• Benefit: Accelerates across shallow valleys, dampens oscillations.

AdaGrad:

• Adapts learning rate per parameter: $$\displaystyle G_t = G_{t-1} + (\nabla_\theta \mathcal{L})^2 $$

• Update: $$\displaystyle \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot \nabla_\theta \mathcal{L} $$

• Drawback: $$\displaystyle G_t $$ accumulates → learning rates decay to zero.

RMSProp:

• Fixes AdaGrad by using exponential moving average of squared gradients:

$$ G_t = \beta G_{t-1} + (1-\beta) (\nabla_\theta \mathcal{L})^2 $$

• Update: $$\displaystyle \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{G_t + \epsilon}} \nabla_\theta \mathcal{L} $$

Adam (Adaptive Moment Estimation):

• Combines Momentum (1st moment) and RMSProp (2nd moment) with bias correction:

$$ m_t = \beta_1 m_{t-1} + (1-\beta_1) g_t $$

$$ v_t = \beta_2 v_{t-1} + (1-\beta_2) g_t^2 $$

$$ \hat{m}_t = \frac{m_t}{1-\beta_1^t}, \quad \hat{v}_t = \frac{v_t}{1-\beta_2^t} $$

$$ \theta_{t+1} = \theta_t - \frac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t $$

• Defaults: $$\displaystyle \beta_1=0.9 $$, $$\displaystyle \beta_2=0.999 $$, $$\displaystyle \epsilon=10^{-8} $$.

Learning Rate Schedules:

• Step Decay: $$\displaystyle \eta_t = \eta_0 \cdot \gamma^{\lfloor t / s \rfloor} $$

• Exponential Decay: $$\displaystyle \eta_t = \eta_0 e^{-kt} $$

• Cosine Annealing: $$\displaystyle \eta_t = \eta_{min} + \frac{1}{2}(\eta_{max}-\eta_{min})(1+\cos(\frac{T_{cur}}{T_{max}}\pi)) $$

Second-Order Methods (Brief):

• Newton’s Method: $$\displaystyle \theta_{t+1} = \theta_t - \mathbf{H}^{-1} \nabla \mathcal{L} $$ (uses Hessian $\mathbf{H}$). Fast but expensive ($$\displaystyle O(n^3) $$).

• L-BFGS: Quasi-Newton; approximates Hessian using limited memory; suitable for full-batch.

[!TIP]

Exam Focus: Adam is default. Know momentum (velocity), RMSProp (EMA of squares), AdaGrad’s flaw. Write Adam update with bias correction. Cosine annealing popular for SGDR.

VII. Regularization Techniques

Bias-Variance Tradeoff:

• Underfitting (High Bias): Model too simple; high train/test error.

• Overfitting (High Variance): Model too complex; low train error, high test error.

Regularization Methods:

Regularization in Autoencoders:

• Sparse Autoencoder: Add KL divergence penalty to encourage sparse latent codes.

• Denoising Autoencoder: Train to reconstruct clean input from corrupted version.

• Contractive Autoencoder: Add penalty on Frobenius norm of Jacobian of latent w.r.t. input.

[!TIP]

Exam Focus: Dropout: randomly drop units during training, use all at test (scale activations). Batch Norm: normalize per mini-batch, then scale/shift. L1 vs L2: sparsity vs small weights.

VIII. Data Preprocessing

Importance: Neural networks are sensitive to input scale; preprocessing stabilizes and speeds up training.

Normalization (Min-Max Scaling):

$$ x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}} $$

• Output range: [0,1]

• Use when features have bounded ranges (e.g., pixel values).

Standardization (Z-score):

$$ x' = \frac{x - \mu}{\sigma} $$

• Output: zero mean, unit variance.

• Use when features have different scales/outliers.

Handling Missing Values: Imputation (mean/median), or treat as separate category.

Encoding Categorical Variables:

• One-Hot Encoding: For low-cardinality features.

• Embeddings: For high-cardinality (e.g., words); learned dense vectors.

Train-Validation-Test Split: Typical ratios 60-20-20 or 70-15-15. Shuffle before splitting to avoid ordering bias.

[!TIP]

Exam Focus: Normalization vs standardization formulas. One-hot for categories, embeddings for high-cardinality. Always shuffle before split.

IX. Convolutional Neural Networks (CNNs)

Motivation: Exploit spatial locality and translation invariance; reduce parameters via weight sharing.

Convolution Operation:

• Kernel/Filter: Weights $\mathbf{W}$ of size $$\displaystyle k \times k \times C_{in} \times C_{out} $$.

• Stride ($s$): Step size; output size: $$\displaystyle \left\lfloor \frac{W - k + 2p}{s} \right\rfloor + 1 $$.

• Padding ($p$):

  • Valid: No padding ($$\displaystyle p=0 $$); output shrinks.

  • Same: Output size = input size; $$\displaystyle p = \frac{k-1}{2} $$ (for odd $k$).

Feature Maps: Each filter produces one 2D activation map; depth = number of filters.

Pooling Layers:

• Max Pooling: Output max in window; preserves dominant features.

• Average Pooling: Output average; smoother.

• Benefits: Dimensionality reduction, translation invariance, larger receptive field.

CNN Architectures Overview:

Applications Beyond Images:

Advantages over FC Networks: Parameter sharing → fewer parameters; locality → efficient; translation invariant.

[!TIP]

Exam Focus: Convolution equation, stride/padding formulas. Max vs average pooling. ResNet’s residual block. Table of data formats (as per past question).

X. Recurrent Neural Networks (RNNs)

Sequential Data: Variable-length inputs where order matters (text, time series).

Vanilla RNN:

• Hidden state update: $$\displaystyle h_t = \tanh(W_{hh} h_{t-1} + W_{xh} x_t + b_h) $$

• Output: $$\displaystyle y_t = \text{softmax}(W_{hy} h_t + b_y) $$

• Parameters shared across time steps.

Backpropagation Through Time (BPTT):

1. Unfold network for $T$ time steps.

2. Compute loss at each (or final) step.

3. Backpropagate gradients through time.

4. Sum gradients across time for weight update.

Vanishing/Exploding Gradients in RNNs:

• Gradients multiplied by $$\displaystyle \frac{\partial h_t}{\partial h_{t-1}} = \text{diag}(f'(h_{t-1})) W_{hh}^T $$ repeatedly.

• If eigenvalues of $$\displaystyle W_{hh} < 1 $$ → vanish; $$\displaystyle >1 $$ → explode.

• Impact: Cannot learn long-range dependencies (>10-20 steps).

Long Short-Term Memory (LSTM):

• Cell State $$\displaystyle \mathbf{C}_t $$: "Highway" for long-term memory.

• Gates:

  • Forget gate: $$\displaystyle f_t = \sigma(W_f \cdot [h_{t-1}, x_t] + b_f) $$

  • Input gate: $$\displaystyle i_t = \sigma(W_i \cdot [h_{t-1}, x_t] + b_i) $$

  • Candidate: $$\displaystyle \tilde{C}_t = \tanh(W_C \cdot [h_{t-1}, x_t] + b_C) $$

  • Update: $$\displaystyle C_t = f_t \odot C_{t-1} + i_t \odot \tilde{C}_t $$

  • Output gate: $$\displaystyle o_t = \sigma(W_o \cdot [h_{t-1}, x_t] + b_o) $$

  • Hidden: $$\displaystyle h_t = o_t \odot \tanh(C_t) $$

Gated Recurrent Unit (GRU): Simplified LSTM; no separate cell state; update and reset gates:

• $$\displaystyle z_t = \sigma(W_z \cdot [h_{t-1}, x_t]) $$ (update)

• $$\displaystyle r_t = \sigma(W_r \cdot [h_{t-1}, x_t]) $$ (reset)

• $$\displaystyle \tilde{h}_t = \tanh(W_h \cdot [r_t \odot h_{t-1}, x_t]) $$

• $$\displaystyle h_t = (1-z_t) \odot h_{t-1} + z_t \odot \tilde{h}_t $$

Deep RNNs: Stack multiple RNN layers; each layer processes sequence from previous layer’s outputs.

Applications: Machine translation, speech recognition, time series forecasting, sentiment analysis.

[!TIP]

Exam Focus: Write vanilla RNN equations. Explain why vanishing gradients occur in BPTT. LSTM cell state and gates (forget, input, output). GRU vs LSTM: GRU merges cell/hidden state, fewer gates.

XI. Autoencoders

Architecture:

• Encoder: $$\displaystyle \mathbf{z} = f_{\text{enc}}(\mathbf{x}) $$ (maps input to latent code $\mathbf{z}$).

• Decoder: $$\displaystyle \hat{\mathbf{x}} = f_{\text{dec}}(\mathbf{z}) $$ (reconstructs input).

• Bottleneck: Latent space $\mathbf{z}$ (low-dimensional).

Training Objective: Minimize reconstruction loss:

$$ \mathcal{L} = \frac{1}{N} \sum_{i=1}^N \ell(x_i, \hat{x}_i) $$

where $\ell$ = MSE (real-valued) or cross-entropy (binary).

Types:

Comparison with PCA/SVD:

Applications: Dimensionality reduction, feature extraction, anomaly detection (high reconstruction error), pretraining for deep nets.

[!TIP]

Exam Focus: Autoencoder = encoder + decoder. Reconstruction loss. When to use autoencoder over PCA: non-linear relationships, complex data (images). Sparse/denoising/contractive mechanisms.

XII. Generative Models: GANs and VAEs

Generative Adversarial Networks (GANs):

• Generator $G$: Takes noise $$\displaystyle \mathbf{z} \sim p_z(\mathbf{z}) $$, outputs fake data $G(\mathbf{z})$.

• Discriminator $D$: Classifies real vs fake: $D(\mathbf{x}) \in [0,1]$.

• Minimax Game:

$$ \min_G \max_D V(D,G) = \mathbb{E}_{x\sim p_{data}}[\log D(x)] + \mathbb{E}_{z\sim p_z}[\log(1-D(G(z)))] $$

• Training: Alternate: (1) fix $G$, maximize $V$ w.r.t. $D$; (2) fix $D$, minimize $V$ w.r.t. $G$.

• Challenges: Mode collapse, training instability, vanishing gradients for $G$.

Variational Autoencoders (VAEs):

• Probabilistic Encoder: $$\displaystyle q_{\phi}(\mathbf{z}|\mathbf{x}) $$ (approximate posterior).

• Decoder: $$\displaystyle p_{\theta}(\mathbf{x}|\mathbf{z}) $$ (generative model).

• Latent Variable Model: $$\displaystyle p(\mathbf{x}) = \int p(\mathbf{x}|\mathbf{z}) p(\mathbf{z}) d\mathbf{z} $$ (intractable).

• Reparameterization Trick: Sample $$\displaystyle \mathbf{z} = \mu_{\phi}(x) + \sigma_{\phi}(x) \odot \epsilon $$, $\epsilon \sim \mathcal{N}(0,I)$.

• Loss (ELBO):

$$ \mathcal{L} = \mathbb{E}_{q_{\phi}}[\log p_{\theta}(x|z)] - D_{KL}(q_{\phi}(z|x) \| p(z)) $$

(Reconstruction loss + KL divergence to prior $$\displaystyle p(z)=\mathcal{N}(0,I) $$).

Comparison:

When to Choose:

• GANs: Need high-fidelity samples (e.g., faces, art); willing to handle instability.

• VAEs: Need structured latent space, likelihood estimation, stable training; accept blurrier samples.

[!TIP]

Exam Focus: GAN: generator vs discriminator, minimax objective. VAE: reparameterization trick, ELBO loss (reconstruction + KL). Compare: GAN sharp but unstable; VAE stable but blurry.

XIII. Reinforcement Learning with Deep Learning

Markov Decision Process (MDP): $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$

• $\mathcal{S}$: states, $\mathcal{A}$: actions

• $P(s'|s,a)$: transition probability

• $R(s,a,s')$: reward

• $\gamma \in [0,1]$: discount factor

Value Function: $$\displaystyle V^{\pi}(s) = \mathbb{E}_{\pi}[\sum_{t=0}^{\infty} \gamma^t R_{t+1} | S_0=s] $$ Policy: $\pi(a|s)$ – probability of action $a$ in state $s$.

Dynamic Programming (Assume known $P$):

• Value Iteration:

$$ V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)[R(s,a,s') + \gamma V_k(s')] $$

Converges to optimal $$\displaystyle V^* $$; policy $$\displaystyle \pi^*(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V^*(s')] $$.

• Policy Iteration:

  1. Policy Evaluation: Solve $$\displaystyle V^{\pi}(s) = \sum_{s'} P(s'|s,\pi(s))[R + \gamma V^{\pi}(s')] $$ (linear system).

  2. Policy Improvement: $$\displaystyle \pi_{new}(s) = \arg\max_a \sum_{s'} P(s'|s,a)[R + \gamma V^{\pi}(s')] $$.

  Comparison: Policy iteration often converges faster but each iteration costly (solve linear system). Value iteration cheaper per iteration but may require more iterations.

Q-Learning (Off-policy TD Control):

Learn action-value $Q(s,a)$:

$$ Q_{new}(s,a) \leftarrow Q(s,a) + \alpha \left[ r + \gamma \max_{a'} Q(s',a') - Q(s,a) \right] $$

Policy: $\epsilon$-greedy on $Q$.

Deep Q-Networks (DQN):

• Use deep network to approximate $Q(s,a;\theta)$.

• Experience Replay: Store transitions $(s,a,r,s')$ in buffer; sample mini-batches to break correlations.

• Target Network: Separate network $Q'$ with parameters $$\displaystyle \theta^- $$; update slowly: $$\displaystyle \theta^- \leftarrow \tau \theta + (1-\tau)\theta^- $$; stabilizes targets.

Advanced DQN Variants:

• Double DQN: Decouple action selection and evaluation to reduce overestimation bias:

$$ y = r + \gamma Q(s', \arg\max_{a'} Q(s',a';\theta); \theta^-) $$

• Dueling DQN: Separate streams for value $V(s)$ and advantage $A(s,a)$; combine: $$\displaystyle Q(s,a) = V(s) + A(s,a) - \frac{1}{|\mathcal{A}|}\sum_{a'} A(s,a') $$.

Least Squares Policy Iteration (LSPI):

• Use linear function approximation for $Q$: $$\displaystyle Q(s,a) = \phi(s,a)^T \theta $$.

• Solve least-squares for policy evaluation instead of TD updates; sample-efficient.

Applications: Atari games (DQN), Go (AlphaGo), robotics.

[!TIP]

Exam Focus: MDP components. Value iteration vs policy iteration (convergence speed vs per-iteration cost). DQN: experience replay + target network. Double DQN reduces overestimation; Dueling DQN separates value/advantage.

XIV. Advanced Topics and Optimization Challenges

Vanishing Gradient Problem:

• Causes: Sigmoid/tanh saturation (derivative near 0); deep networks multiply many small gradients.

• Solutions:

  • Activation: ReLU family.

  • Architecture: Residual connections (ResNet) – identity shortcuts ease gradient flow.

  • Normalization: Batch normalization.

  • Initialization: He initialization for ReLU.

Exploding Gradients:

• Cause: Large weights → large Jacobians.

• Solution: Gradient clipping (by norm or value).

Weight Initialization:

• Xavier/Glorot: For tanh/sigmoid: $$\displaystyle \mathcal{U}\left[-\frac{\sqrt{6}}{\sqrt{n_{in}+n_{out}}}, \frac{\sqrt{6}}{\sqrt{n_{in}+n_{out}}}\right] $$.

• He: For ReLU: $$\displaystyle \mathcal{N}\left(0, \sqrt{\frac{2}{n_{in}}}\right) $$.

Deep Dream:

• Gradient ascent on input to maximize activations of specific layers/filters.

• Produces surreal, hallucinatory images revealing what neurons "see".

Directed Graphical Models (Bayesian Networks):

• Directed acyclic graph (DAG) representing conditional dependencies among random variables.

• Conditional Independence: Node independent of non-descendants given parents.

Deep Belief Networks (DBNs):

• Stacked Restricted Boltzmann Machines (RBMs).

• Pretraining: Greedy layer-wise unsupervised pretraining (was crucial before ReLU/ResNet).

Auto-regressive Models:

• NADE (Neural Autoregressive Distribution Estimator): Factorizes $$\displaystyle p(\mathbf{x}) = \prod_{i=1}^d p(x_i | x_{<i}) $$; uses neural nets for each conditional.

• MADE (Masked Autoencoder for Distribution Estimation): Autoencoder with masks to enforce autoregressive property; efficient sampling.

Representation Learning:

Learning features that capture underlying factors of variation. Deep nets inherently do this via hierarchical abstraction.

[!TIP]

Exam Focus: Vanishing gradient: ReLU/ResNet/BN. Exploding: gradient clipping. Initialization: He for ReLU, Xavier for tanh. Deep Dream: gradient ascent on input. DBNs: stacked RBMs, pretraining history.

XV. Computational Efficiency and Model Compression

GPU Acceleration:

• Parallel matrix operations (CUDA cores).

• Batch operations fit GPU memory; mixed precision (FP16) for speed.

Randomized SVD:

• Approximate SVD using random projections; faster for large matrices.

• Algorithm: $$\displaystyle Y = A \Omega $$ (random matrix $\Omega$), QR decompose $Y$, $$\displaystyle B = Q^T A $$, SVD $$\displaystyle B = U\Sigma V^T $$ → approximate $$\displaystyle A \approx U\Sigma V^T $$.

• Applications: PCA on large data, low-rank approximations.

Model Pruning:

• Weight Pruning: Remove small-magnitude connections (unstructured).

• Unit/Filter Pruning: Remove entire neurons/filters (structured, hardware-friendly).

• Need: Reduce model size, inference time, energy consumption.

Quantization:

• Reduce precision of weights/activations (e.g., FP32 → INT8).

• Post-training Quantization: Calibrate after training.

• Quantization-Aware Training: Train with simulated low-precision.

Knowledge Distillation:

• Train small student network to mimic large teacher network.

• Use softened softmax outputs (temperature $T$): $$\displaystyle p_i = \frac{e^{z_i/T}}{\sum_j e^{z_j/T}} $$.

• Loss: $$\displaystyle \mathcal{L} = \alpha \cdot \text{CE}(y, p_s) + (1-\alpha) \cdot \text{KL}(p_t, p_s) $$.

[!TIP]

Exam Focus: Randomized SVD: random projection → QR → small SVD. Unit pruning vs weight pruning (structured vs unstructured). Quantization: reduce precision. Distillation: student learns from teacher’s soft targets.