The increasing availability of large archives of digital images has pushed the need for effective image retrieval systems. Relevance Feedback (RF) techniques, where the user is involved in an iterative process to refine the search, have been recently formulated in terms of classification paradigms in low-level feature spaces. Two main issues arises in this formulation, namely the small size of the training set, and the unbalance between the class of relevant images and all other non-relevant images. To address these issues, in this paper we propose to formulate the RF paradigm in terms of Passive-Aggressive on-line learning approaches. These approaches are particularly suited to be implemented in RF because of their iterative nature, which allows further improvements in the image search process. The reported results show that the performances attained by the proposed algorithm are comparable, and in many cases higher, than those attained by other RF approaches.