6 papers
PAC Learning with Multiple Correct Answers
Steve Hanneke, Farnam Mansouri, Alireza F. Pour +2
We study PAC learning when each example comes with a set of at most correct labels and a prediction is correct if it belongs to this set. Training may reveal the full set, o…
Query Feedback and Teaching for Stable and Certifiable Language Generation
Farnam Mansouri, Alireza F. Pour, Grigoris Velegkas +1
Language generation in the limit studies whether a learner observing an enumeration of an unknown target language can eventually generate only valid, previously unseen elements. We…
Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour
We continue the study of relatively smart learning, introduced by Dughmi and Pour (2026), which asks a supervised learner to compete, marginal by marginal, with every distribution-…
Relatively Smart: A New Approach for Instance-Optimal Learning
Shaddin Dughmi, Alireza F. Pour
We revisit the framework of Smart PAC learning, which seeks supervised learners which compete with semi-supervised learners that are provided full knowledge of the marginal distrib…
Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models
Alireza F. Pour, Farnam Mansouri, Shai Ben-David
We study the problem of learning with multiple correct answers, where each instance admits a set of valid labels. We primarily focus on the online setup, where in each round the le…
A Novel Data-Dependent Learning Paradigm for Large Hypothesis Classes
Alireza F. Pour, Shai Ben-David
We address the general task of learning with a set of candidate models that is too large to have a uniform convergence of empirical estimates to true losses. While the common appro…