Unit 4 - Practice Quiz

In machine learning, optimization is the process of finding the model parameters that minimize the loss function, which measures the error between the model's predictions and the actual true values.

A loss function is a mathematical function that measures how far a model's prediction is from the target value. The goal of training is to adjust the model's parameters to make this value as small as possible.

For a convex function, any point that is a local minimum is guaranteed to be the single global minimum. This simplifies optimization, as an algorithm won't get stuck in a suboptimal local minimum.

This is the fundamental definition of a convex set. If you can pick any two points in the set and the straight line between them stays inside the set, the set is convex.

The gradient is a vector that points in the direction where the function's value increases most rapidly. Its magnitude indicates the rate of this increase.

Since the gradient points in the direction of steepest increase, the negative gradient () points in the direction of steepest decrease. Following this direction helps us find a minimum of the loss function.

A zero gradient signifies a 'flat' spot in the loss landscape. This occurs at local minima, maxima, and saddle points, where a small step in any direction does not change the function's value.

The learning rate is a hyperparameter that scales the gradient. It controls how large of a step the algorithm takes in the direction of the negative gradient to update the model's weights.

Batch Gradient Descent processes all training examples for each single update. While it provides a very accurate gradient, it can be extremely slow and computationally expensive for large datasets.

Stochastic Gradient Descent performs one update for each training example. This makes each update much faster but also noisier, leading to a less stable convergence path.

By using a small batch of data instead of the entire dataset, mini-batch gradient descent provides a good balance between the accuracy of the batch gradient and the speed of the stochastic gradient.

Momentum adds a fraction of the previous update vector to the current one. This helps the optimizer build up speed in directions with a consistent gradient and reduces oscillations in other directions, much like a ball rolling down a hill.

In narrow ravines, the gradient often oscillates across the steep sides. Momentum dampens these side-to-side oscillations while accumulating the gradient along the length of the ravine, leading to faster convergence.

Adam (Adaptive Moment Estimation) combines the 'momentum' concept of using a moving average of the gradient with the adaptive learning rate feature of RMSProp, which uses a moving average of the squared gradients.

Adaptive learning rate methods adjust the learning rate for each parameter individually. Parameters that receive large gradients will have their effective learning rate reduced, while parameters with small gradients will have theirs increased.

In Adagrad, the learning rate can become infinitely small over time because it accumulates all past squared gradients. RMSProp fixes this by using an exponentially decaying average, preventing the learning rate from vanishing too quickly.

Batch Gradient Descent is computationally infeasible for very large datasets as it requires loading all data for one update. Mini-batch GD provides a compromise, offering efficient computation and more stable convergence than pure SGD.

Modern deep learning models can have billions of parameters, and training data can be large. A major constraint is the limited amount of high-speed memory (VRAM) on GPUs, which must hold the model, the data batch, and the gradients.

Non-convex problems can have many local minima, and an algorithm like gradient descent might get stuck in one that is not the best overall solution (the global minimum). Convex problems have only one minimum, which is the global minimum.

The gradient from a single sample can be a poor estimate of the true gradient over the whole dataset. This causes the updates to fluctuate and follow a noisy path, though the general direction is still towards the minimum.

Optimization algorithms are usually designed to minimize a function. Maximizing the likelihood is equivalent to maximizing its logarithm (since log is a monotonic function), which in turn is equivalent to minimizing the negative log-likelihood, . This is the standard loss function for logistic regression.

For a convex function, any point where the gradient is zero is a global minimum. This is a key property that makes optimizing convex functions much more reliable than non-convex ones, as there are no local minima that aren't also global.

SGD updates the model parameters using only one data point at a time, making each update much faster but also much noisier than BGD, which uses the entire dataset. This noise can help escape shallow local minima but results in a more erratic convergence path.

The momentum term accumulates a velocity vector in directions of persistent gradient. This helps the optimizer move faster along shallow ravines (consistent gradient direction) and dampens oscillations across steep directions (where the gradient sign flips), leading to faster and more stable convergence.

Adagrad adapts the learning rate for each parameter but accumulates all past squared gradients in the denominator. This causes the learning rate to shrink monotonically and eventually become too small, effectively stopping learning. RMSProp fixes this by using an exponentially decaying average of squared gradients, preventing the learning rate from vanishing.

A function is convex if the line segment between any two points on its graph lies on or above the graph. The sine function oscillates, and a line segment connecting two points (e.g., at and ) will pass below the graph, violating the definition of convexity. The other functions are classic examples of convex functions.

The correct option follows directly from the given concept and definitions.

Mini-batch GD offers a compromise. By using a small batch of data (e.g., 32-512 samples), it reduces the variance of the updates compared to SGD (making convergence more stable) and is computationally more efficient than BGD on large datasets. It also allows for hardware-level vectorization benefits.

Adam (Adaptive Moment Estimation) combines the ideas of Momentum and RMSProp. It uses an exponentially decaying average of past gradients (like Momentum) to estimate the first moment (velocity), and an exponentially decaying average of past squared gradients (like RMSProp) to estimate the second moment (adaptive learning rate).

This describes synchronous data parallelism. The model is copied to each worker. Each worker computes gradients on its own mini-batch of data. These gradients are then aggregated (e.g., averaged) to compute a single update, which is applied to the central model. The updated model is then re-distributed to the workers.

By definition, the gradient vector points in the direction of the steepest ascent of the function . Therefore, the negative gradient, , points in the direction of the steepest descent, which is precisely the direction gradient descent algorithms follow to minimize the function.

Regularization terms add a penalty based on the magnitude of the model's parameters to the loss function. This discourages the model from learning overly complex patterns that fit the training data's noise, thus improving its ability to generalize to new, unseen data (i.e., preventing overfitting).

Standard momentum first calculates the gradient at the current position and then updates the velocity. NAG is smarter; it first makes a temporary jump in the direction of the current velocity (a 'lookahead' point) and then calculates the gradient at that new point to make a more informed correction. This helps it slow down more effectively when approaching a minimum.

The high variance in the loss curve is a classic characteristic of SGD. Because each update is based on a single, randomly chosen data point, the gradient estimate is noisy, causing the loss to fluctuate significantly between iterations even as the overall trend is downward. BGD would produce a much smoother curve.

Jensen's inequality is a fundamental property of convex functions. It states that the function evaluated at a weighted average of points is less than or equal to the weighted average of the function's values at those points. Geometrically, this means the chord connecting two points on the graph of a convex function lies on or above the graph.

The moment estimates ( and ) are exponentially moving averages initialized to zero. In the early stages of training, they are biased towards zero. The bias correction step divides them by and respectively, which scales them up to counteract this initial bias, leading to larger and more accurate updates early in training.

A point where the gradient is zero is called a stationary point. For a general non-convex function, a stationary point can be a local minimum (a valley), a local maximum (a hill), or a saddle point. Without second-derivative information (the Hessian), we cannot distinguish between these possibilities.

Model parallelism involves splitting the model itself across multiple devices. This approach is necessary when a single model's parameters, activations, and gradients are so large that they exceed the available memory (e.g., GPU VRAM) of a single device. Data parallelism is used when the model fits on one device but the dataset is very large.

A high momentum coefficient means the velocity vector places a very heavy emphasis on the previous direction. This can cause the optimizer to build up too much speed and 'overshoot' a minimum, oscillating back and forth across a valley instead of settling into it. It makes the optimizer less responsive to sudden changes in the loss landscape.

When data is highly redundant, the gradient computed from a small batch or even a single sample is a good approximation of the gradient of the entire dataset. Therefore, performing many cheap updates using Mini-batch GD or SGD will lead to much faster convergence in terms of wall-clock time compared to one expensive BGD update, which needlessly re-processes similar information.

The dual SVM problem maximizes an objective function with respect to the Lagrange multipliers (one for each data point). Its dimensionality is (number of samples), not (number of features). This is advantageous when , especially with the kernel trick, as the computation depends on the dot products of feature vectors, not the vectors themselves. The Lagrange multipliers are constrained by and .

A function is defined as convex if its epigraph, which is the set of points lying on or above its graph, i.e., epi(f) = , is a convex set. This is a fundamental definition and the relationship is 'if and only if'.

For a differentiable component , the partial derivative is . For a non-differentiable component , the subdifferential is the interval . Therefore, the subgradient at is the set of vectors , where can be any value in .

For an -smooth function (meaning its gradient is Lipschitz continuous with constant ), Batch Gradient Descent with a fixed learning rate is guaranteed to converge to a stationary point (a point where the gradient is zero). This point could be a local minimum, a local maximum, or a saddle point. Convergence to a global minimum is only guaranteed if the function is also convex.

Classical momentum calculates the gradient at the current position and updates the velocity vector. NAG introduces a 'lookahead' step. It first moves temporarily to , calculates the gradient at this lookahead position, and then uses this gradient to compute the final update. This 'lookahead and correct' mechanism allows it to slow down more effectively when approaching a minimum.

The first and second moment estimates, and , are calculated as exponential moving averages. Since they are initialized to zero, they are biased towards zero, particularly during early training. The bias correction step, and , scales them up to counteract this initialization bias, making the initial updates more accurate.

In Async-SGD, workers compute gradients and update a central parameter server without waiting for other workers. This means an update might be based on a 'stale' version of the model parameters, as other workers may have updated them in the meantime. This staleness introduces noise and variance into the optimization process, which can slow down or destabilize convergence.

The product of two convex functions is not generally convex. For example, let and . Both are convex, but their product is a non-convex function with multiple local minima. Pointwise maximum (A), non-negative weighted sums (B), and composition with a non-decreasing convex outer function (C) are all operations that preserve convexity.

The variance of the stochastic gradient does not necessarily go to zero even when the full batch gradient approaches zero at a minimum. This persistent variance causes SGD with a fixed learning rate to 'bounce around' the minimum rather than converging to the exact point. To achieve convergence to the minimum, the learning rate must be annealed (decreased) over time.

Research has shown that Adam's long-term memory of squared gradients () can be problematic. If large gradients are seen early in training, becomes large, shrinking the effective learning rate. Even if later gradients are small but consistently point to the optimum, the optimizer may fail to make progress because the historical information in keeps the learning rate too small.

The L1 norm, , creates 'kinks' in the loss surface where any weight , making it non-differentiable. Optimizers are often driven into these kinks, which results in sparse solutions (exactly zero weights). The L2 norm, , is a smooth quadratic function, resulting in a smooth loss surface that encourages small, but typically non-zero, weights. This difference in differentiability is the key.

The point lies on the non-differentiable seam where . We use the definition: . Here, and . The function value is . For small , . Thus, . The limit becomes .

Large, sustained oscillations are a classic sign of the momentum term being too high. The optimizer overshoots the minimum in a valley of the loss landscape, and the accumulated momentum carries it too far up the other side. Reducing the momentum coefficient (e.g., from 0.99 to 0.9) dampens this behavior by placing more weight on the current gradient and less on the accumulated history, allowing the optimizer to settle.

Jensen's inequality states that for a convex function , . This means the expectation of the function is greater than or equal to the function of the expectation. If the function is strictly convex and the random variable has non-zero variance (is not a constant), then the inequality becomes strict: .

BGD uses the true gradient, which points steeply across the ravine, causing it to zigzag inefficiently. SGD's high-variance updates, while also causing zigzagging, can have a random component along the ravine's axis, sometimes leading to faster progress in this specific pathology. Mini-batch SGD reduces the variance compared to SGD (less zigzagging) while being more efficient than BGD, offering a good compromise.

AdaGrad scales the learning rate by the square root of the sum of all past squared gradients. This sum grows continuously, causing the learning rate to monotonically decrease. For long training runs, the rate can become so small that learning stops. RMSProp fixes this by using an exponentially decaying moving average of squared gradients instead, allowing the optimizer to 'forget' the distant past and prevent the learning rate from vanishing.

In synchronous distributed training, the time taken to transmit gradients over the network can become a bottleneck. Gradient quantization directly tackles this by reducing the size of the data being communicated. By converting 32-bit floating-point gradients to a lower-precision format (like 8-bit or 16-bit), the total data volume is drastically reduced, thus alleviating the communication bottleneck and speeding up the synchronization step.

The gradient vector points in the direction of steepest ascent. A level set is a surface where the function's value is constant. To move along the level set (in its tangent plane) means moving in a direction where the function value does not change. The directional derivative in any such tangent direction must be zero. Since , the gradient must be orthogonal to all tangent vectors, making it normal to the level set itself.

At a saddle point, the gradient is zero. Standard SGD would halt. However, SGD with Momentum maintains a velocity vector . Even if the current gradient is zero, the term from previous steps will be non-zero. This stored velocity allows the optimizer to 'coast' through the flat region of the saddle point and continue descending, making it much better at escaping saddle points.

While BGD enjoys a fast linear (or geometric) convergence rate on strongly convex problems, SGD's convergence is fundamentally limited by the variance of its gradient estimates. Even with a carefully chosen diminishing learning rate schedule like , the convergence rate for SGD in terms of the objective function value is sublinear, specifically . This is significantly slower than BGD's linear rate, as the inherent noise prevents rapid, direct convergence.