A Robust Perceptron Cycling Theorem and Applications
Abstract
The classical perceptron cycling theorem of Block and Levin \cite{BlockLevin1970} bounds correction sequences whose selected updates come from a finite set and have nonpositive inner product with the current state. We prove a robust variant for additive trajectories zk+1=zk+uk, for all integers k≥0, with increments in a finite set U⊂ E, where E is a finite-dimensional real inner-product space and 0∈conv U. Let A: E→ E have positive-definite symmetric part, without requiring symmetry, and let B≥0. If each uk is a B-approximate minimizer of u↦ipAzku over U, then supk≥0normzk≤ C(1+normz0+B), with C=C(E,U,A) independent of the initial state, B, and all admissible update choices. We derive two algorithmic consequences. The first is an O(k−1) last-iterate norm bound for harmonic vertex-returning Frank--Wolfe for affine strongly monotone variational inequalities on polytopes with relatively interior solutions. It extends the quadratic Frank--Wolfe/herding guarantee of Bach, Lacoste-Julien, and Obozinski \cite[Section~4.2]{BachEtAl2012} to nonsymmetric affine operators. The second consequence concerns oblique relaxation for linear inequalities. Greedy corrections through a fixed matrix with positive-definite symmetric part remain bounded even for inconsistent systems. In particular, for a square matrix G with positive-definite symmetric part, repeatedly increasing the coordinate corresponding to a most-violated inequality of Gx≥ b terminates at an exactly feasible point after finitely many unit corrections. This remains true under bounded additive selection errors, provided the stopping test uses the true inequalities.
Related
- Spatial-Sign based Robust Sparse Precision Matrix Estimation and its Applications
- A decomposition theorem for elliptic structures of minimal rank on compact Lie groups and applications
- Alexandrov's Theorem for Integral Varifolds and Applications to Geometric Inequalities
- Angles, orthogonality, and Pythagorean theorem in Banach spaces with two related applications
- Sharp spherical extension theorem in 𝔽q2m and applications
BibTeX
@misc{harks2026robust,
title = {{A Robust Perceptron Cycling Theorem and Applications}},
author = {Tobias Harks},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18342},
eprint = {2609.18342},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18342},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Robust Perceptron Cycling Theorem and Applications
AU - Tobias Harks
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.18342
UR - https://arxiv.org/abs/2609.18342
AB - The classical perceptron cycling theorem of Block and Levin \cite{BlockLevin1970} bounds correction sequences whose selected updates come from a finite set and have nonpositive inner product with the current state. We prove a robust variant for additive trajectories z_k+1=z_k+u_k, for all integers k≥0, with increments in a finite set U⊂ E, where E is a finite-dimensional real inner-product space and 0∈conv U. Let A: E→ E have positive-definite symmetric part, without requiring symmetry, and let B≥0. If each u_k is a B-approximate minimizer of u↦ipAz_ku over U, then sup_k≥0normz_k≤ C(1+normz_0+B), with C=C(E,U,A) independent of the initial state, B, and all admissible update choices. We derive two algorithmic consequences. The first is an O(k^−1) last-iterate norm bound for harmonic vertex-returning Frank--Wolfe for affine strongly monotone variational inequalities on polytopes with relatively interior solutions. It extends the quadratic Frank--Wolfe/herding guarantee of Bach, Lacoste-Julien, and Obozinski \cite[Section~4.2]{BachEtAl2012} to nonsymmetric affine operators. The second consequence concerns oblique relaxation for linear inequalities. Greedy corrections through a fixed matrix with positive-definite symmetric part remain bounded even for inconsistent systems. In particular, for a square matrix G with positive-definite symmetric part, repeatedly increasing the coordinate corresponding to a most-violated inequality of Gx≥ b terminates at an exactly feasible point after finitely many unit corrections. This remains true under bounded additive selection errors, provided the stopping test uses the true inequalities.
ER -