A deterministic rescaled perceptron algorithm

DOI10.1007/s10107-015-0860-yzbMath1332.90202OpenAlexW2009932696MaRDI QIDQ5962726

Javier F. Peña, Negar Soheili

Publication date: 23 February 2016

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-015-0860-y

zbMATH Keywords

rescalingperceptron algorithmcone widthseparation oracle

Mathematics Subject Classification ID

Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Length, area, volume and convex sets (aspects of convex geometry) (52A38) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items (8)

Implementation of a projection and rescaling algorithm for second-order conic feasibility problems ⋮ Examples with decreasing largest inscribed ball for deterministic rescaling algorithms ⋮ Rescaled Coordinate Descent Methods for Linear Programming ⋮ Solving conic systems via projection and rescaling ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ Geometric Rescaling Algorithms for Submodular Function Minimization ⋮ Computational performance of a projection and rescaling algorithm ⋮ Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems

Uses Software

• Pegasos

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Pegasos: primal estimated sub-gradient solver for SVM
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
• A strongly polynomial algorithm for linear systems having a binary solution
• A polynomial-time algorithm for learning noisy linear threshold functions
• Large margin classification using the perceptron algorithm
• Adaptive restart for accelerated gradient schemes
• A Smooth Perceptron Algorithm
• An Efficient Rescaled Perceptron Algorithm for Conic Systems
• The Perceptron: A Model for Brain Functioning. I
• Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem
• The Relaxation Method for Solving Systems of Linear Inequalities
• On the non-polynomiality of the relaxation method for systems of linear inequalities
• Boundedness Theorems for the Relaxation Method
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• A simple polynomial-time rescaling algorithm for solving linear programs

This page was built for publication: A deterministic rescaled perceptron algorithm