How to decrease training set size? I have a large training set, and it is too big to apply some algorithms due to computation limits. 
What are the common methods to decrease training set size without losing significant amount of  information? 
Edit:
Training examples have 3 features and it is a 0/1 classification task.
 A: The brief answer is random sampling, but the more difficult issue is determining the size of the random sample that you should use.  One efficient solution to that problem is provided by progressive sampling—a method that Foster Provost, Tim Oates, and I developed in the late 1990s [1].  The approach begins with a small sample size and increases sample size according to a sampling schedule, checking whether model accuracy increases at each iteration.  We show that a geometric schedule (e.g., doubling the sample size on each iteration) is asymptotically no worse than knowing the correct sample size in advance.

[1] F. Provost, D. Jensen, and T. Oates (1999). Efficient progressive sampling. Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.
http://pages.stern.nyu.edu/~fprovost/Papers/progressive.ps
A: I believe you need to be more specific. What are you trying to do/classify? How many classes do you have? Usually the training set is too valuable to dismiss. Have you thought of reducing the dimensionality, this is usually a must-do when you have many attributes and it will make computations much faster.
One thing I know people have done is  to select x number of random data points from each class, but again it depends on the problem. You want to make sure you don't add bias to your new training set.
