pith. sign in

arxiv: 2604.22265 · v1 · submitted 2026-04-24 · 🧮 math.OC

Finite Termination of a Generalized Perceptron Algorithm

Heinz H. Bauschke , Tran Thanh Tung This is my paper

Pith reviewed 2026-05-08 11:16 UTC · model grok-4.3

classification 🧮 math.OC
keywords perceptron algorithmsubgradient methodconvex inequalitiesfinite terminationHilbert spacestrict feasibilityoptimization
0
0 comments X

The pith

A subgradient method for convex inequality systems terminates in finite steps when the system is strictly feasible and subgradients remain bounded.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a simple iterative subgradient method for finding a point that satisfies a collection of convex inequalities in a Hilbert space. It proves that the iteration reaches a feasible point after finitely many steps for several natural choices of step sizes, provided the inequalities are strictly feasible and the subgradients are bounded. This generalizes the classical perceptron algorithm, which corresponds to the special case of linear inequalities. A reader would care because the result supplies a concrete stopping guarantee for an elementary first-order procedure that is otherwise easy to implement but could in principle run forever.

Core claim

Assuming strict feasibility and bounded subgradients, the generalized perceptron algorithm implemented via a subgradient method with several natural step sizes terminates after a finite number of iterations. The linear specialization recovers the classical perceptron algorithm. Without strict feasibility, finite termination can fail even for a single function, and with multiple functions the iterates may converge to a point outside the feasible set.

What carries the argument

The subgradient iteration that subtracts a scaled subgradient of a violated convex inequality at each step, with step-size rules that guarantee progress toward feasibility.

If this is right

  • The method is guaranteed to output a feasible point after finitely many steps whenever the assumptions hold.
  • The classical perceptron algorithm is recovered exactly when all inequalities are linear.
  • Several common step-size choices all inherit the finite-termination property under the same assumptions.
  • Without strict feasibility the iteration need not reach the feasible set even in the limit.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same finite-termination logic may extend to other first-order schemes for convex feasibility problems once similar boundedness and strict-feasibility conditions are verified.
  • The explicit counter-examples without strict feasibility indicate that practical implementations should first test or enforce a feasibility margin before relying on the iteration.
  • Because the setting is any Hilbert space, the result applies directly to infinite-dimensional convex feasibility problems arising in signal processing or partial differential equations.

Load-bearing premise

The convex inequality system must be strictly feasible and all subgradients must be bounded.

What would settle it

A concrete strictly feasible convex inequality system with bounded subgradients on which the subgradient iteration produces an infinite sequence of distinct points would disprove the finite-termination claim.

read the original abstract

Motivated by Ridgway's proof of the perceptron algorithm, we study a simple subgradient method for convex inequality systems in Hilbert space. Assuming strict feasibility and bounded subgradients, we establish finite termination for several natural step sizes. We also examine what can go wrong without strict feasibility: finite convergence may fail even for one function, and with several functions the method may converge to a point outside the feasible set. The linear setting recovers the classical perceptron algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes a subgradient method for solving systems of convex inequalities in Hilbert space, motivated by Ridgway's proof of the classical perceptron algorithm. Under the assumptions of strict feasibility (a uniform negative margin) and globally bounded subgradients, it proves finite termination for several natural step-size rules. The linear case recovers the standard perceptron convergence theorem. The paper also supplies counterexamples showing that finite termination can fail without strict feasibility, even for a single function, and that the iterates may converge to an infeasible point when multiple functions are present.

Significance. If the central finite-termination result holds, the work provides a clean generalization of the perceptron theorem to nonlinear convex inequality systems in infinite-dimensional spaces. The explicit counterexamples are useful for delineating the necessity of the strict-feasibility hypothesis. The approach appears independent of prior parameter-fitting arguments and supplies a potential-function analysis that may be of interest to the optimization community.

major comments (2)
  1. [main theorem] The proof of finite termination (presumably in the main theorem) relies on a potential-function argument that decreases by a fixed amount at each step; it would be helpful to see an explicit lower bound on the decrease that is uniform across the listed step-size choices.
  2. [counterexample section] The counterexample for a single convex function without strict feasibility (showing possible non-termination) is described but its construction should be checked for whether the subgradient remains bounded while the margin stays non-negative.
minor comments (2)
  1. [introduction] Notation for the step-size sequences should be introduced once and used consistently; the abstract mentions 'several natural step sizes' but the precise rules are not restated in the introduction.
  2. [preliminaries] The Hilbert-space setting is stated clearly, but a brief remark on how the result specializes to Euclidean space (beyond the linear case) would aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the suggestion for minor revision. We provide point-by-point responses to the major comments.

read point-by-point responses

  1. Referee: The proof of finite termination (presumably in the main theorem) relies on a potential-function argument that decreases by a fixed amount at each step; it would be helpful to see an explicit lower bound on the decrease that is uniform across the listed step-size choices.

    Authors: The potential function decreases by an amount that depends on the specific step-size rule chosen. For each of the natural step-size rules considered in the theorem, we can derive a positive lower bound on the decrease that is uniform for that rule. We will revise the manuscript to include these explicit bounds explicitly stated for each case, which clarifies the argument and shows the decrease is bounded away from zero independently of the iteration number. revision: yes

  2. Referee: The counterexample for a single convex function without strict feasibility (showing possible non-termination) is described but its construction should be checked for whether the subgradient remains bounded while the margin stays non-negative.

    Authors: We have verified the construction of the counterexample. The function is chosen so that its subgradients are bounded (with norm at most 1), and the margin is non-negative at all points in the sequence (approaching zero), violating strict feasibility but satisfying the other conditions. We will add a paragraph in the counterexample section providing the explicit verification of these properties to address the concern. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in the derivation

full rationale

The manuscript establishes finite termination of a subgradient iteration for convex inequalities in Hilbert space via a potential-function argument that relies on the explicit hypotheses of strict feasibility and bounded subgradients. The derivation recovers the classical perceptron theorem as a special case but does not reduce the general result to any fitted parameter, self-referential definition, or load-bearing self-citation chain. All steps are standard convex-analytic estimates that remain independent of the target conclusion; the motivation from Ridgway's proof supplies context without importing an unverified ansatz or uniqueness theorem from the present authors. Consequently the proof chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on two domain assumptions from convex analysis that are not derived in the paper.

axioms (2)
  • domain assumption Strict feasibility of the convex inequality system
    Invoked to guarantee finite termination of the subgradient method.
  • domain assumption Boundedness of the subgradients
    Required for the finite termination proof with the chosen step sizes.

pith-pipeline@v0.9.0 · 5361 in / 1188 out tokens · 46140 ms · 2026-05-08T11:16:12.672928+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Mathematical Programming81(1), 23–35 (1998)

    Y.I. Alber, A.N. Iusem, and M.V . Solodov: On the projected subgradient method for nons- mooth convex optimization in a Hilbert space,Mathematical Programming81 (1998), 23–35. https://doi.org/10.1007/BF01584842 5Unfortunately, Ridgway’s name is misspelled in [4]. See also [9]. 5

    work page doi:10.1007/bf01584842 1998

  2. [2]

    CMS Books in Mathematics

    H.H. Bauschke and P .L. Combettes:Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edition, Springer, 2017.https://doi.org/10.1007/978-3-319-48311-5

    work page doi:10.1007/978-3-319-48311-5 2017

  3. [3]

    Bauschke, C

    H.H. Bauschke, C. Wang, X. Wang, and X. Xu: On the finite convergence of a projected cutter method,Journal of Optimization Theory and Applications165 (2015), 901–916.https: //doi.org/10.1007/s10957-014-0659-7

    work page doi:10.1007/s10957-014-0659-7 2015

  4. [4]

    Block and S.A

    H.D. Block and S.A. Levin: On the boundedness of an iterative procedure for solving a system of linear inequalities,Proceedings of the AMS26 (1970), 229–235.https://doi.org/ 10.1090/S0002-9939-1970-0265383-5

    work page doi:10.1090/s0002-9939-1970-0265383-5 1970

  5. [5]

    Censor, W

    Y. Censor, W. Chen, and H. Pajoohesh: Finite convergence of a subgradient projections method with expanding controls,Applied Mathematics & Optimization64 (2011), 273–285

    work page 2011

  6. [6]

    row-action

    A.R. De Pierro and A.N. Iusem: A finitely convergent “row-action” method for the convex feasibility problem,Applied Mathematics and Optimization17 (1988), 225–235.https://doi. org/10.1007/BF01448368

    work page doi:10.1007/bf01448368 1988

  7. [7]

    Fukushima: A finitely convergent algorithm for convex inequalities,IEEE Transactions on Automatic Control27 (1982), 1126–1127.https://doi.org/10.1109/TAC.1982.1103081

    M. Fukushima: A finitely convergent algorithm for convex inequalities,IEEE Transactions on Automatic Control27 (1982), 1126–1127.https://doi.org/10.1109/TAC.1982.1103081

    work page doi:10.1109/tac.1982.1103081 1982

  8. [8]

    Minsky and S.A

    M.L. Minsky and S.A. Papert:Perceptrons, reissue of the 1988 expanded edition with a new foreword by L. Bottou, The MIT Press, 2017.https://doi.org/10.7551/mitpress/11301. 001.0001

    work page doi:10.7551/mitpress/11301 1988

  9. [9]

    Ridgway:An Adaptive Logic System with Generalizing Properties, PhD the- sis, Electrical Engineering, Stanford University, 1962.https://www.proquest

    W.C. Ridgway:An Adaptive Logic System with Generalizing Properties, PhD the- sis, Electrical Engineering, Stanford University, 1962.https://www.proquest. com/dissertations-theses/adaptive-logic-system-with-generalizing/docview/ 302118531/se-2 6

    work page 1962