This paper presents a randomized algorithm called Ratchet that asymptotically minimizes (with probability 1) functions that satisfy a "positive--linear--dependent" (PLD) property. We establish the PLD property and a corresponding realization of Ratchet for a generalized loss criterion for both linear machines and linear classifiers. We describe several learning criteria that can be obtained as special cases of this generalized loss criterion, e.g. classification error, classification loss and weighted classification error. We also establish the PLD property and a corresponding realization of Ratchet for the Neyman-Pearson criterion for linear classifiers.
D. Hush and C. Scovel, Learning with the Ratchet Algorithm. Los Alamos National Laboratory Technical Report LA-UR-03-2033. [ Abstract | PostScript (213 KB) | PDF (214 KB) ]
