  Large-scale data are often characterized by some degree of inhomogeneity as
data are either recorded in different time regimes or taken from multiple
sources. We look at regression models and the effect of randomly changing
coefficients, where the change is either smoothly in time or some other
dimension or even without any such structure. Fitting varying-coefficient
models or mixture models can be appropriate solutions but are computationally
very demanding and often return more information than necessary. If we just ask
for a model estimator that shows good predictive properties for all regimes of
the data, then we are aiming for a simple linear model that is reliable for all
possible subsets of the data. We propose the concept of "maximin effects" and a
suitable estimator and look at its prediction accuracy from a theoretical point
of view in a mixture model with known or unknown group structure. Under certain
circumstances the estimator can be computed orders of magnitudes faster than
standard penalized regression estimators, making computations on large-scale
data feasible. Empirical examples complement the novel methodology and theory.
