Plastic deformation of micron-scale crystalline solids exhibits stress-strain curves with significant sample-to-sample variations. It is a pertinent question if this variability is purely random or to some extent predictable. Here we show, by employing machine learning techniques such as regression neural networks and support vector machines that deformation predictability evolves with strain and crystal size. Using data from discrete dislocations dynamics simulations, the machine learning models are trained to infer the mapping from features of the pre-existing dislocation configuration to the stress-strain curves. The predictability vs strain relation is non-monotonic and exhibits a system size effect: larger systems are more predictable. Stochastic deformation avalanches give rise to fundamental limits of deformation predictability for intermediate strains. However, the large-strain deformation dynamics of the samples can be predicted surprisingly well.