Monotonic Learning in the PAC Framework: A New Perspective
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Learning TheoryPAC learningSimilar Papers 제목 키워드 기반
LLMs as Noisy Channels: A Shannon Perspective on Model Capacity and Scaling Laws
Existing scaling laws for Large Language Models (LLMs), predominantly monotonic power laws, fail to explain emerging non-monotonic phenomena such as catastrophic overtraining and quantization-induced degradation, where p…
Revisiting the Monotonicity Constraint in Cooperative Multi-Agent Reinforcement Learning
QMIX, a popular MARL algorithm based on the monotonicity constraint, has been used as a baseline for the benchmark environments, such as Starcraft Multi-Agent Challenge (SMAC), Predator-Prey (PP). Recent variants of QMI…
Multi-agent Reinforcement Learningreinforcement-learningReinforcement LearningReinforcement Learning (RL)+3Model-Based Decentralized Policy Optimization
Decentralized policy optimization has been commonly used in cooperative multi-agent tasks. However, since all agents are updating their policies simultaneously, from the perspective of individual agents, the environment …
modelOrder Matters: Agent-by-agent Policy Optimization
While multi-agent trust region algorithms have achieved great success empirically in solving coordination tasks, most of them, however, suffer from a non-stationarity problem since agents update their policies simultaneo…
MuJoCoAdaptive Value Decomposition with Greedy Marginal Contribution Computation for Cooperative Multi-Agent Reinforcement Learning
Real-world cooperation often requires intensive coordination among agents simultaneously. This task has been extensively studied within the framework of cooperative multi-agent reinforcement learning (MARL), and value de…
Multi-agent Reinforcement Learning