eCommons

 

RADIAL PROJECTIONS, CONVEX FEASIBILITY PROBLEMS AND MARGIN MAXIMIZATION

dc.contributor.authorZhou, Song
dc.contributor.chairRenegar, Jamesen_US
dc.contributor.committeeMemberLewis, Adrianen_US
dc.contributor.committeeMemberDavis, Dameken_US
dc.date.accessioned2024-04-05T18:48:46Z
dc.date.available2024-04-05T18:48:46Z
dc.date.issued2023-08
dc.description142 pagesen_US
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.en_US
dc.identifier.doihttps://doi.org/10.7298/w6h4-0r65
dc.identifier.otherZhou_cornellgrad_0058F_13923
dc.identifier.otherhttp://dissertations.umi.com/cornellgrad:13923
dc.identifier.urihttps://hdl.handle.net/1813/114824
dc.language.isoen
dc.subjectConvex Feasibility Problemen_US
dc.subjectFirst-Order Methoden_US
dc.subjectLinear Regularityen_US
dc.subjectMargin Maximizationen_US
dc.subjectPerceptronen_US
dc.subjectRadial Projectionen_US
dc.titleRADIAL PROJECTIONS, CONVEX FEASIBILITY PROBLEMS AND MARGIN MAXIMIZATIONen_US
dc.typedissertation or thesisen_US
dcterms.licensehttps://hdl.handle.net/1813/59810.2
thesis.degree.disciplineOperations Research and Information Engineering
thesis.degree.grantorCornell University
thesis.degree.levelDoctor of Philosophy
thesis.degree.namePh. D., Operations Research and Information Engineering

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Zhou_cornellgrad_0058F_13923.pdf
Size:
827.63 KB
Format:
Adobe Portable Document Format