Classical Machine Learning Algorithms Questions

Direct answer

At 10 million samples, an exact RBF-kernel SVM is off the table (kernel methods scale at least quadratically in the number of samples), so the realistic options are: approximate the kernel with an explicit low-dimensional feature map (random Fourier features or Nystrom) and train a linear model on top, or drop the kernel entirely and use a linear SVM with engineered features. Validate that you haven't given up too much accuracy by directly measuring the kernel-approximation error and comparing downstream task metrics against a subsampled exact baseline, not just by trusting the approximation's theoretical guarantee in the abstract.

Structured elaboration

Why exact RBF-SVM fails at this scale. Standard SVM solvers require computing (or repeatedly touching) the full $n \times n$ kernel matrix, giving training cost on the order of $O(n^2)$ to $O(n^3)$ depending on the solver. At $n=10^7$, even $O(n^2)$ is $10^{14}$ kernel evaluations, computationally infeasible on any realistic budget, this isn't a "tune it better" problem, it's a fundamentally different scaling regime that needs a different algorithm.

Option 1: Random Fourier Features (RFF). By Bochner's theorem, a shift-invariant kernel like RBF is the Fourier transform of a probability distribution, which lets you approximate $K(x,x') \approx z(x)^\top z(x')$ using an explicit randomized feature map $z: \mathbb{R}^d \to \mathbb{R}^D$ built from $D$ random frequencies. You then train an ordinary linear SVM on $z(x)$, which costs $O(nD)$, linear in $n$. The approximation error decreases as you increase $D$, at the cost of a larger, denser feature representation.

Option 2: Nystrom approximation. Sample $m$ "landmark" points from the training data, build a low-rank approximation of the kernel matrix from just those landmarks, $K \approx C W^{+} C^\top$, and use that to construct an explicit $m$-dimensional feature map. Cost is roughly $O(nm + m^3)$ (the cubic term is a one-time cost on the landmarks, not the full dataset). Nystrom tends to win over RFF, for the same output dimension, specifically when the true kernel matrix has fast-decaying eigenvalues (a genuinely low effective rank); on data with no such low-rank structure, RFF's more uniform theoretical guarantee holds up better instead, so which one wins is an empirical question about your specific data, not a fixed ranking.

Option 3: switch to a linear model entirely. If a linear SVM (or logistic regression) with reasonable feature engineering already captures most of the signal, it's the cheapest and most scalable option at $O(nd)$, and worth trying as your first baseline before investing in kernel approximation at all; on many high-dimensional, sparse problems a linear model is close enough to the RBF-kernel result that the approximation machinery isn't worth the added complexity.

How to validate the trade-off, concretely. Two independent checks, both needed:

1. Direct approximation error: on a subsample small enough to compute the true kernel matrix (say 300 to a few thousand points), compute the relative Frobenius error $\lVert K - \hat K \rVert_F / \lVert K \rVert_F$ between the true and approximated kernel matrix at your chosen $D$ or $m$, and track how it changes as you scale $D$ or $m$ up.
2. Downstream task metric: fit the approximate model at full scale and compare its held-out AUC/accuracy against an exact RBF-SVM trained on a subsample (not the full 10M, which you can't run exactly, but a subsample large enough to be a fair proxy), to make sure the approximation error you measured in step 1 doesn't translate into a meaningful accuracy loss on the actual task.

Worked example

import numpy as np
from sklearn.kernel_approximation import RBFSampler, Nystroem
from sklearn.metrics.pairwise import rbf_kernel

np.random.seed(54)
n, d = 300, 10
X = np.random.randn(n, d)
gamma = 0.5
K_true = rbf_kernel(X, gamma=gamma)

def approx_error(K_approx, K_true):
    return np.linalg.norm(K_approx - K_true, 'fro') / np.linalg.norm(K_true, 'fro')

rff_errors = {}
for Dd in [50, 200, 800, 3200]:
    Z = RBFSampler(gamma=gamma, n_components=Dd, random_state=0).fit_transform(X)
    rff_errors[Dd] = approx_error(Z @ Z.T, K_true)

nystrom_errors = {}
for m in [10, 40, 160]:
    Z = Nystroem(gamma=gamma, n_components=m, random_state=0).fit_transform(X)
    nystrom_errors[m] = approx_error(Z @ Z.T, K_true)

On this 300-point subsample with $\gamma=0.5$ (verified numerically):

Two things are worth noting honestly from these actual numbers. First, RFF's error roughly halves every time $D$ quadruples (0.59 at $D=800$ to 0.29 at $D=3200$), consistent with the theoretical $O(1/\sqrt{D})$ convergence rate for random Fourier features. Second, on this specific dataset (independent Gaussian noise, no genuine low-rank kernel structure), Nystrom converges more slowly than RFF at a comparable dimension, which contradicts the common "Nystrom usually wins" folklore; that folklore assumes a kernel matrix with fast-decaying eigenvalues, which this synthetic data doesn't have. The honest takeaway is to measure both on your actual data rather than assume one always dominates.

Trade-offs & pitfalls

• Don't skip the direct kernel-approximation-error measurement and jump straight to a downstream metric comparison; if the downstream metric looks fine, you still want to know how much headroom you have before it wouldn't be, especially if the data distribution might shift later.
• RFF and Nystrom both still require you to choose an output dimension ($D$ or $m$); treat this as a real hyperparameter with its own validation curve, not a fixed default.
• A linear-model baseline is worth building even if you're confident the kernel is needed; it's cheap, and "the kernel approximation beat a well-engineered linear baseline by this much" is a far more convincing validation story than "the kernel approximation had low measured error" alone.
• Whichever approximation you choose, it needs periodic re-validation as production data drifts: an approximation validated on data from six months ago can silently degrade if the input distribution's effective rank or scale changes.

Direct answer

Boosting typically gives the largest accuracy gains on tabular data but costs sequential training time; bagging (e.g. random forests) gives smaller, more reliable gains with cheap, embarrassingly parallel training; stacking can squeeze out the most accuracy of the three but multiplies your operational surface area (more models to serve, monitor, and retrain). In production, the extra overhead of any ensemble over a single well-tuned model is worth it when the accuracy gain is directly monetizable and you can afford the added maintenance; it's usually not worth it under tight latency or strict interpretability requirements.

Structured elaboration

Accuracy. Boosting (gradient-boosted trees) is generally the strongest of the three on structured tabular data, because it directly optimizes the loss by sequentially fitting residuals rather than averaging independent learners. Bagging gives smaller but very reliable gains, mainly by reducing the variance of an already-decent high-variance base learner (a deep tree). Stacking's ceiling is the highest of the three because it can combine genuinely different model families (a boosted tree, a linear model, a neural net), each catching errors the others miss, but the gain is conditional on the base models actually being diverse; stacking several near-identical models adds cost with little benefit.

Training and inference cost.

• Bagging: training is parallel across trees (near-linear speedup with more cores), but inference cost is the sum of every base tree's cost, since you must query all of them and average.
• Boosting: training is inherently sequential (each tree depends on the residuals of the previous ones), but a well-regularized boosted model needs fewer, shallower trees than a comparable random forest, often giving a smaller inference footprint than bagging for similar accuracy.
• Stacking: training cost is the sum of all base models plus a meta-learner, and a correctly-implemented stack requires an extra layer of cross-validation to generate out-of-fold predictions for the meta-learner (to avoid leakage), which meaningfully lengthens the training pipeline. Inference means running every base model, then the meta-learner, giving the worst latency of the three.

Interpretability and operational risk. A single boosted model is still explainable via SHAP or built-in feature importances, and it's one artifact to version, monitor, and roll back. Bagged forests are similarly explainable (importance is a little "blurred" across many trees) and have a natural resilience angle: losing or degrading a few trees barely moves the ensemble average. Stacking is the least interpretable and the highest operational risk: a silent distribution shift in one base model's inputs can corrupt the meta-learner's predictions in a way that's hard to trace back to its source, and you now have an entire fleet of models whose CI/CD, versioning, and rollback all need to be kept in sync with each other.

When the overhead is worth it. Reach for boosting as the default "best accuracy for reasonable operational cost" choice on tabular problems. Reach for bagging specifically when stability under resampled or shifting data matters more than squeezing out the last bit of accuracy, and you have spare parallel compute. Reserve stacking for settings where the last percentage point of accuracy has outsized business value (fraud, ad ranking, competition-style leaderboards) and you're willing to fund the added monitoring and retraining pipeline it requires; for most production services, a single well-tuned boosted model, or a bagged forest if latency is generous, beats a stack once you account for the true cost of running it.

Worked example

Consider a fraud-scoring service where a 0.5-point AUC improvement is worth roughly a known dollar figure per month in caught fraud minus false-positive review cost (a number the business can actually quote). If a stack adds that 0.5 points over a single boosted model but doubles inference latency and adds a second on-call surface (the meta-learner's own failure modes), the decision hinges entirely on whether that dollar figure covers the added engineering and infra cost, this is a real cost-benefit calculation the team should be able to write down, not an abstract "more accuracy is always better" argument. By contrast, in a real-time bidding path with a single-digit-millisecond latency budget, a stack's extra inference hop is very often a non-starter regardless of the accuracy gain, and a single boosted model (or even a distilled, single-tree approximation of one) is the realistic ceiling.

Trade-offs & pitfalls

• Don't evaluate ensembles on accuracy alone; the comparison that matters in production is accuracy gain per unit of added latency, memory, and on-call burden.
• Stacking without proper out-of-fold generation for the meta-learner's training data is a common, subtle leakage bug: the meta-learner ends up trained on predictions its base models could never have made "honestly" in production.
• Model distillation (training one small model to mimic a stack's or forest's outputs) is a legitimate way to keep most of the accuracy gain from an ensemble while collapsing the serving cost back down to a single model.
• "More models" is also "more failure surfaces": component-level monitoring, not just end-to-end metrics, is necessary for any of these ensembles, since an end-to-end metric can look fine for a while even after one component silently degrades.

Direct answer

For a modest tabular dataset, I would default to linear regression when I expect roughly linear relationships, need interpretable coefficients, or need fast, predictable inference latency in production. I would reach for KNN when I expect meaningfully non-linear local structure, have relatively low dimensionality, and can tolerate or optimize away its per-query cost.

Structured elaboration

Dataset size and dimensionality. KNN's distance metric becomes less meaningful as dimensionality grows (the curse of dimensionality: in high dimensions, distances between points concentrate, so "nearest" stops being informative). Linear regression's cost and sample requirements scale gently with dimensionality by comparison.

Feature scaling. KNN requires careful standardization since it is entirely distance-based, an unscaled feature with a large numeric range will dominate the distance calculation regardless of its actual predictive relevance. Linear regression doesn't strictly require scaling for correctness, though it helps numerically and makes coefficients comparable.

Interpretability. Linear regression gives directly interpretable coefficients (sign, relative magnitude, confidence intervals). KNN is non-parametric: you can inspect which neighbors drove a prediction, but there's no global "effect of this feature" statement to make.

Inference latency.

Worked example

Take a dataset with n = 1,000 training rows and d = 10 features, a small but realistic tabular size.

Linear regression, per prediction: one dot product of length 10 plus an intercept add.

$O(d) = 10 \text{ multiplies} + 1 \text{ add} = 11 \text{ flops}$

Brute-force KNN, per prediction: a squared-distance computation (d subtractions and multiplies) against every one of the 1,000 training points, ignoring the subsequent top-k selection.

$O(n \cdot d) = 1{,}000 \times 10 = 10{,}000 \text{ flops}$

$10{,}000 / 11 \approx 909$

At this scale, a single KNN prediction does roughly 909 times more arithmetic than a single linear regression prediction, and that ratio grows linearly with n as the dataset gets larger, while linear regression's cost stays fixed at $O(d)$ regardless of how much training data you have.

Trade-offs & pitfalls

• KNN's cost grows with data, linear regression's doesn't. This is the single biggest production consideration: a linear model's latency is flat as you collect more training data; KNN's latency (or memory, if you precompute a structure) keeps growing.
• Regularized linear regression (ridge/lasso) narrows some of the flexibility gap with KNN while keeping the interpretability and latency advantages, worth trying before jumping to a non-parametric method.
• KNN needs an explicit strategy for irrelevant features: unlike a regularized linear model, plain KNN has no built-in way to downweight a noisy or irrelevant dimension, it will happily let that dimension corrupt every distance calculation.
• Pitfall: picking KNN for its simplicity to implement while ignoring that its "training" is trivial but its serving cost is the opposite, an approximate nearest-neighbor index (KD-tree, ball-tree, or ANN library) is close to mandatory once n grows past a few thousand and latency matters.

Direct answer

Logistic regression predicts a probability by taking a linear combination of the features, called the score, and squashing it through the sigmoid function into the range (0, 1). That probability is converted to a class label by comparing it to a threshold, usually 0.5. Its central limitation is that the decision boundary it can draw is always linear in whatever features you give it, so it fails on problems where the true separation between classes is curved unless you engineer non-linear features yourself.

The sigmoid and probabilities

The model first computes a linear score from the features:

Then it maps that score to a probability with the sigmoid function:

The sigmoid squashes any real number into (0, 1): very negative $z$ pushes $p$ toward 0, very positive $z$ pushes $p$ toward 1, and $z=0$ gives exactly $p=0.5$.

Log-odds: the other way to read the same model

Solving the sigmoid equation for $z$ shows that logistic regression is linear regression on the log-odds (logit) of the outcome, not on the probability itself:

This is the useful interpretive lens: a one-unit increase in $x_i$ multiplies the odds $\frac{p}{1-p}$ by $e^{w_i}$, holding everything else fixed. It is also why the model has no closed-form solution for the weights, coefficients are fit by maximizing the likelihood (equivalently minimizing cross-entropy loss), which is convex in the weights, so gradient descent or Newton's method reliably converges to the global optimum.

From probability to a label

Once you have $p$, you compare it to a threshold $t$ (0.5 by default) and predict the positive class if $p \geq t$. The threshold is a separate decision from fitting the model: moving it trades precision for recall, and the right value depends on the relative cost of false positives versus false negatives in the application, not on anything the training procedure chose for you.

Main limitations

• Linear decision boundary. In the raw feature space, the set of points where $p = 0.5$ is a straight line (or hyperplane in higher dimensions). If the true classes are separated by a curve, logistic regression cannot represent that unless you add polynomial or interaction features, or switch to a model that learns non-linear boundaries natively (trees, kernel SVM).
• Sensitive to multicollinearity. Highly correlated features make individual coefficient estimates unstable, even though the model's overall predictions can still be fine.
• Assumes the log-odds are linear in the features, not that the raw relationship between a feature and the outcome is linear, a distinction that is easy to misstate in an interview.

Worked example: from score to label

Suppose a model produces the score $z = 1.2$ for a given input. The predicted probability is:

Converting to odds: $\frac{p}{1-p} = \frac{0.7685}{0.2315} = 3.32$, meaning the model considers the positive class about 3.3 times more likely than the negative class for this input. At the default threshold of 0.5, since $0.7685 \geq 0.5$, the predicted label is 1. If the deployment threshold were instead 0.8 (say, to control false positives), this same input would be labeled 0 despite the model being fairly confident, which is exactly why threshold choice is a separate lever from model fit.

Trade-offs and pitfalls

• Coefficients are only directly comparable across features if those features are on the same scale; a common junior mistake is reading raw coefficient magnitude as "feature importance" on unstandardized data.
• Regularization (L1 or L2 penalty on the weights) trades a small amount of bias for lower variance and, with L1, can zero out irrelevant features, but it also shrinks the coefficients you'd otherwise use for odds-ratio interpretation.
• Logistic regression gives well-calibrated probabilities when the model is close to correctly specified, which is part of why it stays a strong baseline even when a more flexible model wins on raw accuracy.
• The linear-boundary limitation is a feature as much as a bug: it is what makes the model fast, interpretable, and hard to overfit with a small feature set, which is exactly the trade a tree ensemble or kernel method gives up.

Direct answer

For a 100k-row, 200-feature tabular dataset with high-cardinality categoricals, I'd default to gradient boosting (LightGBM/CatBoost) over a neural network with embeddings, because GBMs typically reach strong accuracy on data of this size with less tuning, handle missingness and mixed scales natively, and have native categorical handling that avoids the embedding-design and data-volume concerns a neural net brings. A neural net becomes the better choice mainly when the dataset is substantially larger, the categoricals carry rich learnable semantics worth sharing across tasks, or the model needs to plug into an end-to-end differentiable pipeline.

Structured elaboration

Why sample size at 100k matters. Neural nets, and embeddings for high-cardinality categoricals in particular, need enough examples per category to learn a meaningful representation. With 200 features and 100k rows, a high-cardinality categorical (say, 5,000 distinct values) may only have on the order of 20 examples per category on average, not much for a network to learn a useful embedding vector from scratch, whereas a tree-based split on that same categorical (using target statistics) is a much lower-variance way to extract signal from a similarly sparse per-category sample.

When the neural net does start to win. As data grows well past 100k, embeddings get enough examples per category to learn genuinely useful representations, sometimes capturing similarity structure between categories (e.g. two product SKUs behaving similarly) that a GBM's per-feature splits don't naturally exploit. A neural net is also the better choice when there's a reason to want a differentiable end-to-end pipeline (e.g. joint training with another neural component, or transfer of learned embeddings to a related task), independent of which model wins on raw accuracy.

Worked example

Suppose one of the 200 features is a "merchant ID" categorical with 5,000 distinct values across the 100k rows. With even distribution across categories, that's $100{,}000 / 5{,}000 = 20$ rows per merchant on average. A tree-based split using target statistics (e.g. the historical target rate for that merchant, computed with appropriate regularization/smoothing to avoid leakage) reduces this to a single informative numeric feature per split candidate, requiring only enough examples per category to estimate a stable rate, not enough to fit a multi-dimensional embedding vector. An embedding of size, say, 16 for that same categorical has 16 free parameters per category to learn, i.e. $5{,}000 \times 16 = 80{,}000$ parameters for that one feature alone, competing for signal against only 20 rows per category; that parameter count relative to available data per category is the concrete reason embeddings are data-hungry in exactly the regime this question describes.

Trade-offs and pitfalls

• GBMs can plateau in accuracy once real interaction structure gets very deep or the categorical semantics matter (e.g. two rarely co-occurring categories that behave similarly); a neural net with shared embeddings can sometimes capture that structure a tree-based split cannot.
• Ensembling a GBM and a neural net sometimes captures complementary error patterns and outperforms either alone, but that's a meaningfully larger engineering and maintenance surface for a modest accuracy gain, worth it only when the accuracy gain is validated and the maintenance cost is acceptable.
• A common wrong turn is reaching for embeddings because "neural nets are more powerful" in the abstract, without checking whether the per-category sample size actually supports learning a useful embedding; at 100k rows with high-cardinality categoricals, that assumption often doesn't hold.
• The right first step in almost every case is to fit the GBM as a fast baseline; if it saturates and the use case justifies the added complexity (larger expected future data volume, need for a differentiable pipeline), only then invest in the neural net path.