Avoid overfitting in regression: alternatives to regularization Regularization in regression (linear, logistic...) is the most popular way to reduce over-fitting.
When the goal is prediction accuracy (not explaining), are there any good alternatives to regularization, especially suited for big data-sets (mi/billions of observations and millions of features)?
 A: Some additional possibilities to avoid overfitting


*

*Dimensionality reduction
You can use an algorithm such as principal components analysis (PCA) to obtain a lower dimensional features subspace. The idea of PCA is that the variation of your $m$ dimensional feature space may be approximated well by an $l << m$ dimensional subspace.

*Feature selection (also dimensionality reduction)
You could perform a round of feature selection (eg. using LASSO) to obtain a lower dimensional feature space. Something like feature selection using LASSO can be useful if some large but unknown subset of features are irrelevant.

*Use algorithms less prone to overfitting such as random forest. (Depending on the settings, number of features etc..., these can be more computationally expensive than ordinary least squares.)
Some of the other answers have also mentioned the advantages of boosting and bagging techniques/algorithms. 

*Bayesian methods
Adding a prior on the coefficient vector an reduce overfitting. This is conceptually related to regularization: eg. ridge regression is a special case of maximum a posteriori estimation.
A: If you are use a model with a solver, where you can define number of iterations/epochs, you can track validation error and apply early stopping: stop the algorithm, when validation error starts increasing.
A: Two thoughts:


*

*I second the "use a simpler model" strategy proposed by Ben Ogorek. 
I work on really sparse linear classification models with small integer coefficients (e.g. max 5 variables with integer coefficients between -5 and 5). The models generalize well in terms of accuracy and trickier performance metrics (e.g  calibration). 
This method in this paper will scale to large sample sizes for logistic regression, and can be extended to fit other linear classifiers with convex loss functions. It will not handle the cases with lots of features (unless $n/d$ is large enough in which case the data is separable and the classification problem becomes easy).

*If you can specify additional constraints for your model (e.g. monotonicity constraints, side information), then this can also help with generalization by reducing the hypothesis space (see e.g. this paper). 
This needs to be done with care (e.g. you probably want to compare your model to a baseline without constraints, and design your training process in a way that ensures you aren't cherry picking constraints).
A: Two alternatives to regularization:


*

*Have many, many observations

*Use a simpler model


Geoff Hinton (co-inventor of back propogation) once told a story of engineers that told him (paraphrasing heavily), "Geoff, we don't need dropout in our deep nets because we have so much data." And his response, was, "Well, then you should build even deeper nets, until you are overfitting, and then use dropout." Good advice aside, you can apparently avoid regularization even with deep nets, so long as there are enough data.
With a fixed number of observations, you can also opt for a simpler model. You probably don't need regularization to estimate an intercept, a slope, and an error variance in a simple linear regression.
A: Two important points that are not directly related to your question:


*

*First, even the goal is accuracy instead of interpretation, regularization is still necessary in many cases, since, it will make sure the "high accuracy" on real testing / production data set, not the data used for modeling.

*Second, if there are billion rows and million columns, it is possible no regularization is needed. This is because the data is huge, and many computational models have "limited power", i.e., it is almost impossible to overfit. This is why some deep neural network has billions of parameters.

Now, about your question. As mentioned by Ben and Andrey, there are some options as alternatives to regularization. I would like to add more examples.


*

*Use simpler model (For example, reduce number of hidden unit in neural network. Use lower order polynomial kernel in SVM. Reduce number of Gaussians in mixture of Gaussian. etc.)

*Stop early in the optimization. (For example, reduce the epoch in neural network training, reduce number of iterations in optimization (CG, BFGS, etc.)

*Average on many models (For example, random forest etc.)
A: What is regularization, really?
Perhaps you are conflating L1/L2 regularization (aka. Lasso/ridge regression, Tikhonov regularization...), the most ubiquitous type, as the only type of regularization 
Regularization is actually anything that prevents overfitting, that you can do to a learning algorithm [Wikipedia]. Dropout, batch normalization, early stopping, model ensembling, feature selection, and many of the techniques others have pointed out here... are all just different regularization techniques!

Bias-variance tradeoff
Perhaps thinking about this issue in terms of the bias-variance tradeoff, a fundamental machine learning concept, could greatly clarify your thoughts.
If our goal is prediction accuracy, we want to reduce the expected error of a supervised learner $\hat{f}$, which can be decomposed into bias, variance, and irreducible error:
$$
{\displaystyle \operatorname {E} _{D}{\Big [}{\big (}y-{\hat {f}}(x;D){\big )}^{2}{\Big ]}={\Big (}\operatorname {Bias} _{D}{\big [}{\hat {f}}(x;D){\big ]}{\Big )}^{2}+\operatorname {Var} _{D}{\big [}{\hat {f}}(x;D){\big ]}+\sigma ^{2}}
$$
Regularization penalizes complex models, to try to reduce the variance of the estimator (more than the bias is increased), to ultimately reduce the expected error. Philosophically, this is akin to Occam's razor, where we introduce an inductive bias for simplicity on the assumption that "simpler is better".
We usually want to regularize
From a Bayesian viewpoint, we can also show that including L1/L2 regularization means placing a prior and obtaining a MAP estimate, instead of an MLE estimate (see here).
Overfitting is simply when your model is unable to generalize well to your actual data of interest ("test" or "production" dataset), usually because it has fit to your training data too well. We always want to prevent this with some form of regularization.
