A deterministic rescaled perceptron algorithm

DOI10.1007/S10107-015-0860-YMaRDI QIDQ5962726zbMATH OpenOpenAlexFDO

Authors Javier 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 algorithmseparation oraclecone width

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)

Recommendations

• An efficient rescaled perceptron algorithm for conic systems
• An Efficient Re-scaled Perceptron Algorithm for Conic Systems
• A simple polynomial-time rescaling algorithm for solving linear programs
• Examples with decreasing largest inscribed ball for deterministic rescaling algorithms
• A deterministic and polynomial modified perceptron algorithm

Cites work

• scientific article; zbMATH DE number 3542688 (Why is no real title available?)
• scientific article; zbMATH DE number 1009689 (Why is no real title available?)
• scientific article; zbMATH DE number 1046019 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• A polynomial-time algorithm for learning noisy linear threshold functions
• A simple polynomial-time rescaling algorithm for solving linear programs
• A smooth perceptron algorithm
• A strongly polynomial algorithm for linear systems having a binary solution
• Adaptive restart for accelerated gradient schemes
• An efficient rescaled perceptron algorithm for conic systems
• Boundedness Theorems for the Relaxation Method
• First-order algorithm with \({\mathcal{O}(\ln(1/\epsilon))}\) convergence for \({\epsilon}\)-equilibrium in two-person zero-sum games
• Large margin classification using the perceptron algorithm
• On the non-polynomiality of the relaxation method for systems of linear inequalities
• Pegasos: primal estimated sub-gradient solver for SVM
• Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem
• Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem
• The Perceptron: A Model for Brain Functioning. I
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Linear Inequalities
• The Relaxation Method for Solving Systems of Linear Inequalities

Cited in

(14)

• Learning Theory
• A smooth perceptron algorithm
• Computational performance of a projection and rescaling algorithm
• Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
• An Efficient Re-scaled Perceptron Algorithm for Conic Systems
• Implementation of a projection and rescaling algorithm for second-order conic feasibility problems
• Examples with decreasing largest inscribed ball for deterministic rescaling algorithms
• Geometric rescaling algorithms for submodular function minimization
• Rescaling algorithms for linear conic feasibility
• A deterministic and polynomial modified perceptron algorithm
• An improved deterministic rescaling for linear programming algorithms
• Solving conic systems via projection and rescaling
• An efficient rescaled perceptron algorithm for conic systems
• Rescaled coordinate descent methods for linear programming

Describes a project that uses

Uses Software

• Pegasos

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962726)