Cornell University
RADIAL PROJECTIONS, CONVEX FEASIBILITY PROBLEMS AND MARGIN MAXIMIZATION
Abstract
dc:description.abstractThis work comprises two parts. Part I focuses on the convex feasibility problem (finding or approximating a point in the intersection of finitely many closed convex sets). We avoid the need for orthogonal projections by using radial projections, introduced by Renegar. The main requirement is that an interior point is known in each of the sets considered. By developing Renegar’s theory, we obtain a family of radial projection-based algorithms for the convex feasibility problem which recover the linear convergence rates of orthogonal projection-based methods. Through studying different assumptions on the emptiness of the interior of the intersection set in the convex feasibility problem, we also exhibit how radial projections can be applied to solve constrained optimization problems when certain conditions are met.Part II can be seen as an application of the theory of radial projections developed in Part I. Here, we revisit the notion of maximal-margin classifiers, from around 2000, but now from a general perspective – the intersections of generic closed convex cones, not just half-spaces (i.e., the perceptron). This requires extending concepts and establishing more general theory of the margin function, which is achieved by applying and refining the results in Part I in the conic case. Even more interestingly, we are led to the first Õ(1/ε) first-order method for approximating, within relative error ε, the margin-maximizer of the intersection cone. Previous results, only in the case of the perceptron, were O(1/ε²), making our result a notable improvement even in the most basic of cases.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Operations Research and Information Engineering
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Operations Research and Information Engineering
- Grantor
- Cornell University
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Zhou, Song
- Chair dc:contributor.chair
-
- Renegar, James
- Committee members dc:contributor.committeemember
-
- Lewis, Adrian
- Davis, Damek
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 16219231
- Dc Identifier Other
-
ProQuest Submission ID: 13923
ProQuest Publication ID: 30630914