Efficient Optimal PAC Learning
Recent advances in the binary classification setting by Hanneke [2016b] and Larsen [2023] have resulted in optimal PAC learners. These learners leverage, respectively, a clever deterministic subsampling scheme and the classic heuristic of bagging Breiman [1996]. Both optimal PAC learners use, as a subroutine, the natural algorithm of empirical risk minimization. Consequently, the computational cost of these optimal PAC learners is tied to that of the empirical risk minimizer algorithm. In this work, we seek to provide an alternative perspective on the computational cost imposed by the link to the empirical risk minimizer algorithm. To this end, we show the existence of an optimal PAC learner, which offers a different tradeoff in terms of the computational cost induced by the empirical risk minimizer.
Code (0)
등록된 구현이 없습니다.
Tasks
Binary ClassificationPAC learningSimilar Papers 제목 키워드 기반
HJB Optimal Feedback Control with Deep Differential Value Functions and Action Constraints
Learning optimal feedback control laws capable of executing optimal trajectories is essential for many robotic applications. Such policies can be learned using reinforcement learning or planned using optimal control. Whi…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Optimality and Suboptimality of MPPI Control in Stochastic and Deterministic Settings
Model predictive path integral (MPPI) control has recently received a lot of attention, especially in the robotics and reinforcement learning communities. This letter aims to make the MPPI control framework more accessib…
Real-Time Optimal Guidance and Control for Interplanetary Transfers Using Deep Networks
We consider the Earth-Venus mass-optimal interplanetary transfer of a low-thrust spacecraft and show how the optimal guidance can be represented by deep networks in a large portion of the state space and to a high degree…
Optimal sequential tests yield log-optimal e-processes
It has been recently shown that e-processes are sufficient for sequential testing in the following sense: every level-$α$ sequential test can be obtained by thresholding an e-process at $1/α$. However, in the above resul…
On Computable Online Learning
We initiate a study of computable online (c-online) learning, which we analyze under varying requirements for "optimality" in terms of the mistake bound. Our main contribution is to give a necessary and sufficient condit…