In rule-based (RB) category-learning tasks, the optimal strategy is a simple explicit rule, whereas in information-integration (II) tasks, the optimal strategy is impossible to describe verbally. This study investigates the effects of two different category properties on learning difficulty in category learning tasks--namely, linear separability and variability on stimulus dimensions that are irrelevant to the categorization decision. Previous research had reported that linearly separable II categories are easier to learn than nonlinearly separable categories, but Experiment 1, which compared performance on linearly and nonlinearly separable categories that were equated as closely as possible on all other factors that might affect difficulty, found that linear separability had no effect on learning. Experiments 1 and 2 together also established a novel dissociation between RB and II category learning: increasing variability on irrelevant stimulus dimensions impaired II learning but not RB learning. These results are all predicted by the best available measures of difficulty in RB and II tasks.