Source author record

Javier Peña

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC math.NA Artificial Intelligence Machine Learning Numerical Analysis

Catalog footprint

Research overview

5works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Towards A Deeper Geometric, Analytic and Algorithmic Understanding of Margins

Given a matrix $A$ , a linear feasibility problem (of which linear classification is a special case) aims to find a solution to a primal problem $w: A^Tw > \textbf{0}$ or a certificate for the dual problem which is a probability distribution $p: Ap = \textbf{0}$ . Inspired by the continued importance of "large-margin classifiers" in machine learning, this paper studies a condition measure of $A$ called its \textit{margin} that determines the difficulty of both the above problems. To aid geometrical intuition, we first establish new characterizations of the margin in terms of relevant balls, cones and hulls. Our second contribution is analytical, where we present generalizations of Gordan's theorem, and variants of Hoffman's theorems, both using margins. We end by proving some new results on a classical iterative scheme, the Perceptron, whose convergence rates famously depends on the margin. Our results are relevant for a deeper understanding of margin-based learning and proving convergence rates of iterative schemes, apart from providing a unifying perspective on this vast topic.

preprint2015arXiv

Margins, Kernels and Non-linear Smoothed Perceptrons

We focus on the problem of finding a non-linear classification function that lies in a Reproducing Kernel Hilbert Space (RKHS) both from the primal point of view (finding a perfect separator when one exists) and the dual point of view (giving a certificate of non-existence), with special focus on generalizations of two classical schemes - the Perceptron (primal) and Von-Neumann (dual) algorithms. We cast our problem as one of maximizing the regularized normalized hard-margin ( $ρ$ ) in an RKHS and %use the Representer Theorem to rephrase it in terms of a Mahalanobis dot-product/semi-norm associated with the kernel's (normalized and signed) Gram matrix. We derive an accelerated smoothed algorithm with a convergence rate of $\tfrac{\sqrt {\log n}}ρ$ given $n$ separable points, which is strikingly similar to the classical kernelized Perceptron algorithm whose rate is $\tfrac1{ρ^2}$ . When no such classifier exists, we prove a version of Gordan's separation theorem for RKHSs, and give a reinterpretation of negative margins. This allows us to give guarantees for a primal-dual algorithm that halts in $\min\{\tfrac{\sqrt n}{|ρ|}, \tfrac{\sqrt n}ε\}$ iterations with a perfect separator in the RKHS if the primal is feasible or a dual $ε$ -certificate of near-infeasibility.

preprint2013arXiv

Solving second-order conic systems with variable precision

We describe and analyze an interior-point method to decide feasibility problems of second-order conic systems. A main feature of our algorithm is that arithmetic operations are performed with finite precision. Bounds for both the number of arithmetic operations and the finest precision required are exhibited.

preprint2011arXiv

A Complementarity Partition Theorem for Multifold Conic Systems

Consider a homogeneous multifold convex conic system $Ax = 0, \; x\in K_1\times...\times K_r$ and its alternative system $$ A\transp y \in K_1^*\times...\times K_r^*, $$ where $K_1,..., K_r$ are regular closed convex cones. We show that there is canonical partition of the index set ${1,...,r}$ determined by certain complementarity sets associated to the most interior solutions to the two systems. Our results are inspired by and extend the Goldman-Tucker Theorem for linear programming.

preprint2010arXiv

Applying Metric Regularity to Compute a Condition Measure of a Smoothing Algorithm for Matrix Games

We develop an approach of variational analysis and generalized differentiation to conditioning issues for two-person zero-sum matrix games. Our major results establish precise relationships between a certain condition measure of the smoothing first-order algorithm proposed by Gilpin et al. [Proceedings of the 23rd AAAI Conference (2008) pp. 75-82] and the exact bound of metric regularity for an associated set-valued mapping. In this way we compute the aforementioned condition measure in terms of the initial matrix game data.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.