21 Data Science Optimisation Algorithms Interview Questions (ANSWERED)

• Machine learning involves using an algorithm to learn and generalize from historical data to make predictions on new data.
• The problem can be described as approximating a function that maps examples of inputs to examples of outputs.
• Approximating a function can be solved by framing the problem as a function optimization. This is where a machine learning algorithm defines a parameterized mapping function and an optimization algorithm is used to find the values of the parameters that minimize the error of the function when used to map inputs to outputs.
• Function optimisation is a set of inputs that results in the minimum or maximum of an objective function.

• Bayesian Optimization-type Methods build Gaussian process surrogate models to explore the parameter space. The main idea is that parameter tuples that are closer together will have similar function values, so the assumption of a covariance structure among points allows the algorithm to make educated guesses about what best parameter tuple is most worthwhile to try next.
• This strategy helps to reduce the number of function evaluations; in fact, the motivation of BO methods is to keep the number of function evaluations as low as possible while trying to make good guesses about what point to test next.
• Incidentally, this is also a powerful global optimization technique, and as such makes no assumptions about the convexity of the surface. Additionally, if the function is stochastic (say, evaluations have some inherent random noise), this can be directly accounted for in the GP model.
• On the other hand, you'll have to fit at least one Gaussian process at every iteration. Then, the model is used to make (probably thousands) of predictions, usually in the form of multi-start local optimization, with the observation that it's much cheaper to evaluate the Gaussian process prediction function than the function under optimization. But even with this computational overhead, it tends to be the case that even nonconvex functions can be optimized with a relatively small number of function calls.

• A differentiable function is a function where the derivative can be calculated for any given point in the input space.
• The derivative of a function of a value is the rate or amount of change in the function at that point.
• Optimization is significantly easier if the gradient of the objective function can be calculated, and as such, there has been a lot more research into optimization algorithms that use the derivative than those that do not.
• Some groups of algorithms that use gradient information include, Bracketing algorithms, Local descent algorithms, First-Order algorithms, Second-order algorithms, etc.

• Random Search: here, we create a grid of possible values for hyperparameters. Each iteration tries a random combination of hyperparameters from this grid, records the performance, and lastly returns the combination of hyperparameters that provided the best performance.

• Grid search: we also create a grid of possible values for hyperparameters, but in each iteration, we try a combination of hyperparameters in a specific order and the model it fits on each and every combination of hyperparameters possible and records the model performance. Finally, it returns the best model with the best hyperparameters.

• Bayesian Optimization: The idea here is to minimize the loss function of our model by changing model parameters. This approach helps us to find the minimal point in the minimum number of steps.

• There is a simple reason to study Convex optimization, which is that convex optimizations are "easier to solve".
• Convex optimization is faster, simpler, and less computationally intensive, so it is often easier to convexify a problem, than it is to use non-convex optimization.
• For example, gradient descent and algorithms like them are commonly used in machine learning, especially for neural networks, because they work, scale, and are widely implemented in different software, nonetheless they are not the best and have their own pitfalls.
• The difference between a convex and a non-convex function is shown below:

The applicability of batch or stochastic gradient descent depends on the error manifold expected.

• Batch gradient descent computes the gradient using the whole dataset. This is great for convex, or relatively smooth error manifolds. In this case, we move somewhat directly towards an optimum solution, either local or global. Additionally, batch gradient descent, given an annealed learning rate, will eventually find the minimum located in its basin of attraction.
• Stochastic gradient descent (SGD) computes the gradient using a single sample. Most applications of SGD use a minibatch of several samples. SGD works better than batch gradient descent for error manifolds that have lots of local maxima/minima. In this case, the somewhat noisier gradient calculated using the reduced number of samples tends to jerk the model out of local minima into a region that hopefully is more optimal. Single samples are noisy, while mini-batches tend to average a little of the noise out. Thus, the amount of jerk is reduced when using mini-batches. A good balance is struck when the minibatch size is small enough to avoid some of the poor local minima but large enough that it doesn't avoid the global minima or better-performing local minima.

One benefit of SGD is that it's computationally a whole lot faster. Large datasets often can't be held in RAM, which makes vectorization much less efficient. Rather, each sample or batch of samples must be loaded, worked with, the results stored, and so on. Minibatch SGD, on the other hand, is usually intentionally made small enough to be computationally tractable. Usually, this computational advantage is leveraged by performing many more iterations of SGD, making many more steps than conventional batch gradient descent. This usually results in a model that is very close to that which would be found via batch gradient descent, or better.

Regret is the defacto standard in measuring the performance of learning algorithms.

• In the online decision-making scenario, a player has to choose from a pool of available decisions and then incur a loss corresponding to the quality of the decision made. The regret minimization paradigm suggests the goal of incurring an average loss which approaches that of the best-fixed decision in hindsight.
• In online convex optimization, an online player, iteratively chooses a point from a set of Euclidean space denoted $K \subseteq R^n$. We assume that the set K is non-empty, bounded, and closed. We also assume the set K to be convex.
• We denote the number of iterations by T. At iteration t, the online player chooses $x_t \in K$. After committing to this choice, a convex cost function $f_t : K \rightarrow \R$ is revealed. The cost incurred to the online player is the value of the cost function at the point she committed to $f_t(x_t)$. Henceforth we consider mostly linear cost functions, and abuse notation to write $f_t(x) = f_t^T x$.
• The regret of the online player using algorithm A at time T is defined as the total cost minus the cost of the best fixed single decision, where the best is chosen with the benefit of hindsight. We are usually interested in an upper bound on the worst-case guaranteed regret, denoted

• Intuitively, an algorithm performs well if its regret is sublinear in T, that is, $Regret_T(A) = o(T)$, since this implies that "on the average" the algorithm performs as well as the best-fixed strategy in hindsight.
• The running time of an algorithm for online game playing is defined to be the worst-case expected time to produce $x_t$, for an iteration $t \in [T]^2$ in a T iteration repeated game. Typically, the running time will depend on $n, T$ and the parameters of the cost functions and underlying convex set.

• Even when the cost function is expensive to evaluate, a random search can still be useful. Random search is simple to implement. The only choice for a researcher to make is setting the probability p that you want your results to lie in some quantile q; the rest proceeds automatically using results from basic probability.

• Most people recommend n = 60. It is worth noting that n = 60 is comparable to the number of experiments required to get good results with Gaussian Process-based methods when there are a moderate number of parameters. Unlike Gaussian Processes, the number of queries tuples does not change with the number of hyperparameters to search over; indeed, for a large number of hyperparameters, a Gaussian process-based method can take many iterations to make headway.

A few types of stopping conditions are as follows:

• maxit: this is a predetermined maximum number of iterations. Another similar alternative is a maximum number of seconds before timing out. If all you need is an approximate solution, this can be a very reasonable solution.
• abstol: i.e., stop when the function gets "close enough" to zero.
• reltol: this is to stop when the improvement drops below a threshold.

Other possible options for finding lower minima in a reasonable amount of time could include:

• Stochastic gradient descent, which only requires estimating the gradients for a small portion of your data at a time (e.g. one data point for "pure" SGD, or small mini-batches).
• More advanced optimization functions (e.g. Newton-type methods or Conjugate Gradient), which use information about the curvature of your objective function to help you point in better directions and take better step sizes as you move downhill.
• A momentum term in your update rule, so that your optimizer does a better job of rolling downhill rather than bounding off canyon walls in your objective function.

• Generic Algorithms (GA) are a family of heuristics that are empirically good at providing a decent answer in many cases, although they are rarely the best option for a given domain.
• What many standard optimization algorithms have in common is the assumption that the underlying space is a smooth manifold (perhaps with a few discrete dimensions), and the function to optimize is somewhat well-behaved.
• However, not all functions are defined on a smooth manifold. Sometimes you want to optimize over a graph or other discrete structures (combinatorial optimization) -- here there are dedicated algorithms, but GAs would also work.
• The more you go towards functions defined over complex, discrete structures, the more GAs can be useful, especially if you can find a representation in which the genetic operators work at their best (which requires a lot of hand-tuning and domain knowledge).

• Empirically, it can be observed that algorithms like Adam and RMSProp tends to give a higher performance on the validation dataset with respect to SGD.
• However, Adam and RMSProp are highly sensitive to certain values of the learning rate (and sometimes, other hyper-parameters like the batch size) and they can catastrophically fail to converge if e.g. the learning rate is too high.
• On the other hand, in general, SGD does not lead to the highest performance, but they do not catastrophically fail.

• Yes, it is very common to use both tricks. They solve different problems and can work well together.
• One way to think about it is that weight decay changes the function that is being optimized, while momentum changes the path you take to the optimum.
• Weight decay, by shrinking your coefficients toward zero, ensures that you find a local optimum with small-magnitude parameters. This is usually crucial for avoiding overfitting (although other kinds of constraints on the weights can work too). As a side benefit, it can also make the model easier to optimize, by making the objective function more convex.

• In many cases, going to the third derivative does help.
• However, in general, going to higher derivatives adds computational complexity - you have to find and calculate all those derivatives, and for multivariate problems, there are a lot more third derivatives than there are first derivatives! - that far outweighs the savings in step count you get, if any.
• For example, if I have a 3 dimensional problem, I have 3 first derivatives, 6 second derivatives, and 10 third derivatives, so going to a third-order version more than doubles the number of evaluations I have to do (from 9 to 19), not to mention increased complexity of calculating the step direction/size once I've done those evaluations, but will almost certainly not cut the number of steps I have to take in half.
• Now, in the general case with k variables, the collection of $n^{th}$ partial derivatives will number $\left(\begin{matrix} k+n-1 \\ k-1 \end{matrix}\right)$, so for a problem with five variables, the total number of third, fourth, and fifth partial derivatives will equal 231, a more than 10-fold increase over the number of first and second partial derivatives (20). You would have to have a problem that is very, very close to a fifth-order polynomial in the variables to see a large enough reduction in iteration counts to make up for that extra computational burden.

• Gradient descent maximizes a function using knowledge of its derivative.
• Newton's method, a root-finding algorithm, maximizes a function using knowledge of its second derivative. This can be faster when the second derivative is known and easy to compute. However, the analytic expression for the second derivative is often complicated or intractable, requiring a lot of computation.
• Numerical methods for computing the second derivative also require a lot of computation -- if N values are required to compute the first derivative, $N^2$ are required for the second derivative.