Classification with Guaranteed Probability of Error

We introduce a general-purpose learning machine that we call the “Guaranteed Error Machine”, or GEM, and two learning algorithms, a “real GEM algorithm” and an “ideal GEM algorithm”. The real GEM algorithm is for use in real applications, while the ideal GEM algorithm is introduced as a theoretical tool; however, these two algorithms have identical … Read more

Chance-constrained optimization via randomization: feasibility and optimality

In this paper we study the link between a semi-infinite chance-constrained optimization problem and its randomized version, i.e. the problem obtained by sampling a finite number of its constraints. Extending previous results on the feasibility of randomized convex programs, we establish here the feasibility of the solution obtained after the elimination of a portion of … Read more

The Exact Feasibility of Randomized Solutions of Robust Convex Programs

Robust optimization programs are hard to solve even when the constraints are convex. In previous contributions, it has been shown that approximately robust solutions (i.e. solutions feasible for all constraints but a small fraction of them) to convex programs can be obtained at low computational cost through constraints randomization. In this paper, we establish new … Read more