Monotonic Learning in the PAC Framework: A New Perspective
This work addresses a foundational theoretical problem in machine learning by providing rigorous proofs for monotonicity in generalization, which is incremental but crucial for advancing learning theory.
The paper tackles the challenge of monotonic learning in machine learning by using PAC learning theory to construct a theoretical risk distribution that proves monotonicity as sample sizes increase, with experiments validating that generalization error monotonically converges to 0 in two classical problems.
Monotone learning describes learning processes in which expected performance consistently improves as the amount of training data increases. However, recent studies challenge this conventional wisdom, revealing significant gaps in the understanding of generalization in machine learning. Addressing these gaps is crucial for advancing the theoretical foundations of the field. In this work, we utilize Probably Approximately Correct (PAC) learning theory to construct a theoretical risk distribution that approximates a learning algorithm's actual performance. We rigorously prove that this theoretical distribution exhibits monotonicity as sample sizes increase. We identify two scenarios under which deterministic algorithms based on Empirical Risk Minimization (ERM) are monotone: (1) the hypothesis space is finite, or (2) the hypothesis space has finite VC-dimension. Experiments on two classical learning problems validate our findings by demonstrating that the monotonicity of the algorithms' generalization error is guaranteed, as its theoretical risk upper bound monotonically converges to 0.