Multiclass Linear Perceptrons with Multiplicative Margins

Motivation

• Linear models remain widely used because they combine simplicity, interpretability, computational efficiency, regularization compatibility, and broad applicability.Fixed randomized nonlinear transformations followed by linear classifiers also support efficient training and inference across diverse vectorized data.Source: §1 · p. 2

Research gap

• Prior multiplicative-margin Perceptrons lacked comprehensive method descriptions and were limited to binary input vectors and constrained class weights.Earlier work omitted associated losses, convergence analysis, non-separable-data behavior, and key design considerations.Source: §1 · p. 4

MMPerc framework

• MMPerc introduces multiclass linear Perceptrons that enforce a multiplicative margin while operating on vector representations of arbitrary format.The framework is positioned for general multiclass classification and HDC-based IoT, TinyML, Edge AI, and AIoT applications.Source: §1 · p. 4

Theory and algorithms

• The framework provides loss functions, learning rules, architecture and algorithm variants, and mistake-bound analysis for separable and non-separable data.These elements address prior work’s omissions in convergence, mistake bounds, non-separable behavior, and design variants.Source: §1 · pp. 4–5

Evaluation

• Across most settings, MMPerc outperforms the standard Perceptron and linear SVM and Ridge baselines on synthetic and real datasets.Evaluation includes real-valued and binarized vectors and hypervector transformations with varying dimensionalities.Source: §1 · pp. 4–5

Design considerations

• The introduction highlights margin-threshold handling, online versus offline training, training duration and stopping criteria, and class-prototype selection for inference as design considerations.These considerations include the number of training epochs and stopping criteria.Source: §1 · p. 5

Experimental evaluation

• MMPerc is evaluated against standard Perceptrons, SVMs, and Ridge classifiers on synthetic and real datasets using real-valued and binary representations across varied dimensionalities.The evaluation also assesses how design considerations affect performance.Source: §1 · p. 5

Future directions

• Future research directions concern architectural and training strategies for large-margin Perceptrons.The introduction frames these as directions for extending the approach.Source: §1 · p. 5

2.1 Classification and Training Settings

• Multiclass learning assigns one label from [K] to each vector input, using online single-pass updates or offline epoch-wise training with stopping criteria.Online training interleaves prediction, feedback, and parameter updates, whereas offline training repeatedly samples the full dataset; both aim to perform well on unseen data from the same distribution.Source: §2.1 · p. 6
• In the realizable online setting, a finite mistake bound implies convergence, with convergence after at most M0 mistakes and no more than M0 epochs in the stated worst case.Non-learnable online settings do not converge and are instead stopped after a predefined number of epochs.Source: §2.1 · pp. 6–7

2.3 Perceptron’s Loss Function

• Direct 0-1-loss minimization is difficult because its indicator is noncontinuous, nonconvex, and nondifferentiable with respect to the class weights.This motivates surrogate-loss optimization through iterative gradient or subgradient methods.Source: §2.3 · pp. 8–9
• The multiclass Perceptron loss is the positive part of the negative score gap, LPerc = [−δ]+, where δ compares the true class with the highest-scoring incorrect competitor.The loss is zero when the true score is at least the strongest incorrect score, positive otherwise, and is continuous, convex, and subgradient-compatible at δ = 0.Source: §2.3 · p. 9
• The Perceptron loss yields the Rosenblatt error-correcting updates when its mistake-case subgradients are used with learning rate η = 1.Correct classifications have zero loss; using the prediction rather than zero loss to identify mistakes also recovers updates at δ = 0.Source: §2.3 · p. 10
• The Perceptron loss is not an upper bound or surrogate for 0–1 loss, so minimizing it need not reduce classification mistakes and can leave maximal 0–1 loss.The loss may approach ε > 0 while L0-1 = 1, and zero initialization produces no update signal because all class scores tie at zero.Source: §2.3 · p. 10
• Zero-margin training can place decision boundaries arbitrarily close to training instances and is noise-sensitive when close scores cause unstable or inconsistent updates.A positive margin threshold δ ≥ β > 0 increases separation from training instances and can improve generalization.Source: §2.3 · p. 11

2.4 Large-Margin Perceptrons

• Large-margin Perceptrons apply a positive threshold to the classification score margin, replacing the Perceptron’s original zero-margin criterion for deciding whether a prediction is correct.Source: §2.4 · p. 11

• The section presents loss functions and learning rules for multiclass large-margin Perceptrons.Source: §3 · p. 12
• It also includes mistake-bound analysis for the proposed large-margin Perceptron methods.Source: §3 · p. 12
• Figure 1 shows that the β-hinge loss upper bounds the scaled 0-1 loss βL0-1.Source: Figure 1 · p. 12

3.1.1 Additive Margin Formulation

• Additive-margin training uses Lβ-hinge, which is positive when the score gap is below β and zero otherwise, triggering standard Perceptron-style updates.For β = 0, the loss recovers the multiclass Perceptron loss; for β > 0, it upper-bounds the scaled 0-1 loss.Source: §3.1.1 · pp. 13–14

3.1.2 Multiplicative Margin Formulation

• The multiplicative loss Lαs-hinge requires the competing-class score to remain below (1 − α) times the true-class score, with α = 0 recovering the standard Perceptron loss.Training detects a mistake when δ < αs_y, equivalently when the multiplicative hinge loss is positive.Source: §3.1.2 · p. 14
• MMPerc-Asm derives an asymmetric update directly from subgradients, while leaving all non-true, non-competing class weights unchanged.The variant is explicitly named the large-margin multiclass Perceptron with the asymmetric learning rule.Source: §3.1.2 · pp. 14–15

3.1.2.1 The asymmetric case with absolute true-class score

• Absolute-score variants replace the true-class score by s_y − α|s_y| so the margin cannot increase the effective true-class score when s_y is negative.This modification addresses the case where negative true-class scores prevent misclassification detection under the ordinary multiplicative formulation.Source: §3.1.2.1 · p. 15
• The absolute multiplicative formulation yields sign-dependent true-class updates: x(1 − α) for positive scores and x(1 + α) for negative scores.The resulting variant with an asymmetric learning rule is called MMPerc-AbsAsm.Source: §3.1.2.1 · pp. 15–16

3.2 Mistake Bounds for the Linearly Separable Case

• The separable analysis assumes ||x^(t)|| ≤ R and a comparator with additive margin γ satisfying the multiclass separation inequalities.The margin condition is equivalent to zero γ-hinge loss on every training instance.Source: §3.2 · pp. 16–17

Theorem 1 (Mistake bounds for large margin Perceptrons in the linearly separable case):

• MMPerc and MMPerc-Abs satisfy M0 = R^2(2 − α)/(γ^2 − αR^2), requiring γ^2 − αR^2 > 0.These are the standard-learning-rule multiplicative-margin bounds.Source: §3.2.1 · p. 17
• MMPerc-Asm has bound M0 = (1 + (1 − α)^2)R^2/(γ − αR)^2, while MMPerc-AbsAsm replaces the numerator by (1 + (1 + α)^2)R^2.Both asymmetric bounds require γ − αR > 0.Source: §3.2.1 · p. 17
• Setting the margin threshold to zero recovers the standard multiclass Perceptron mistake bound.The paper also notes that finite bounds imply offline training convergence in the separable case.Source: §3.2.1 · pp. 17–18
• The multiplicative bounds are finite only when α is below γ^2/R^2 or γ/R, depending on the learning rule, so threshold selection is necessary.Introducing a margin increases the theoretical mistake upper bound relative to the standard Perceptron.Source: §3.2.1 · p. 18

3.3 Mistake Bounds for the Linearly Non-Separable Case

• The non-separable analysis compares each large-margin Perceptron with a fixed linear classifier using the competitor’s cumulative b-hinge loss.The resulting bounds depend on the competitor’s loss, weight norm, input-radius bound, and margin parameters.Source: §3.3 · p. 18, §3.3.1 · p. 19

Theorem 2 (Mistake bounds for large margin Perceptrons in the linearly non-separable case):

• MMPerc and MMPerc-Abs share a bound whose numerator combines bL_b, (2 − α)R^2||U||^2, and a square-root interaction term, divided by b^2 − αR^2||U||^2.The bound is stated for the standard Perceptron learning rule.Source: §3.3.1 · p. 19
• The asymmetric variants use denominators (b − α||U||R)^2 and differ in quadratic factors: 2 − 2α + α^2 for MMPerc-Asm versus 2 + 2α + α^2 for MMPerc-AbsAsm.These expressions retain dependence on competitor loss and norm.Source: §3.3.1 · p. 19
• Unlike separable-case bounds, non-separable mistake bounds grow with the number of training instances T.Setting the margin parameters to zero recovers the known standard multiclass Perceptron bound.Source: §3.3.1 · pp. 19–20
• When the competitor has zero cumulative 1-hinge loss, the bound simplifies to M0 = 2||U||^2R^2 and recovers the classical separable bound M0 = 2R^2/γ^2 after normalization.This connects the non-separable comparator analysis to the standard separable Perceptron result.Source: §3.3.1 · p. 20

3.4.1 On Generalization Error

• The derived mistake bounds can be incorporated into online-learning analyses to obtain generalization bounds for the corresponding multiclass Perceptron variants.This discussion assumes independently and identically distributed samples for expected-loss guarantees.Source: §3.4.1 · p. 20

3.4.2 Additive vs Multiplicative Margin

• In additive-margin Perceptrons, the effective learning rate η/M decreases linearly with the mistake count M as weight norms grow.The paper links this self-regulation to stabilization, convergence, and reduced overshooting.Source: §3.4.2 · p. 21
• The additive effective margin threshold β_eff = β/||(M+1)W|| also decreases with M, weakening the intended margin as training progresses.The paper notes that this behavior can conflict with the original motivation for introducing a margin.Source: §3.4.2 · pp. 21–22
• For AMPerc, β_eff/γ is bounded below by β/[2(R^2 + β)], with equality in the worst case.The discussion states that AMPerc may require many more mistakes to reach β_eff = γ/2 than the standard Perceptron bound.Source: §3.4.2 · p. 22
• MMPerc bases both classification and update decisions on relative class scores, so increasing weight norms does not by itself reduce the enforced multiplicative margin.The same relative margin α continues to be applied as score magnitudes grow.Source: §3.4.2 · p. 22
• MMPerc-Abs has a concrete limitation: when the true-class score is nonnegative and the competing score is negative, no mistake is triggered for any α.When the true-class score is zero, the multiplicative threshold remains zero.Source: §3.4.2 · p. 22

4.1.1 Bias

• Setting the bias component proportional to √D improved classification accuracy over the conventional value of 1 and was critical on certain datasets.The authors attribute this to unnormalized vector norms up to R = Θ(√D), while fixing the scaling to R avoids additional tuning.Source: §4.1.1 · pp. 23–24

4.1.2 Margin Threshold Selection and Training Settings

• The margin threshold α is selected by cross-validation, offline training is adopted, batch size is 1, and the symmetric MMPerc-Abs variant is used for reported results.Offline training typically yields higher accuracy, while preliminary tests found no consistent benefit from larger batches or the asymmetric rule.Source: §4.1.2 · p. 24

4.1.3 Number of Training Epochs and Stopping Criteria

• Training stops at a predefined epoch limit or earlier when training accuracy reaches a specified value, typically 1.0 or near it.Some datasets converge within the first few epochs, especially with a small or zero margin threshold.Source: §4.1.3 · pp. 24–25

4.1.4 Selection of Class Weights for Classifier Evaluation

• For evaluation, the classifier uses weights from the epoch with highest training accuracy rather than automatically using the final epoch.This pocket-like choice can fail to deliver the best testing accuracy across all epochs, although it coincides with final weights after convergence.Source: §4.1.4 · p. 25

4.2.1 Synthetic Datasets from DataGen

• Synthetic DataGen experiments vary dimensionality, class count, and training-set size under controlled, noiseless conditions producing piece-wise linear separable class regions.Instances are generated around sampled class centers, with each class constrained to be closer to its own center than others.Source: §4.2.1 · pp. 25–26

4.2.2 Real Datasets

• The real-data evaluation uses UCIHAR, CTG, ISOLET, and HAND datasets, split into 80% training and 20% testing sets with five-fold cross-validation.HAND comprises five available datasets, HAND1 through HAND5; splits were sourced or created depending on the dataset.Source: §4.2.2 · p. 26

4.2.3 Data Standardization and Transformation

• Synthetic inputs were not standardized, whereas real-valued real-dataset vectors were independently z-scored for training and testing before evaluation.Real-valued inputs were also transformed into hypervectors to compare classification accuracy across varying dimensionalities.Source: §4.2.3 · p. 27
• Random projection maps inputs to the target dimensionality with a Gaussian matrix, followed by optional zero-threshold component-wise binarization without further hypervector standardization.The study selects random projection for simplicity and applies the same basic pipeline to real-valued or binary hypervectors.Source: §4.2.3 · p. 27

4.2.4 Classifiers

• The classifier experiments compare multiclass Perceptron and MMPerc across margin thresholds against one-vs-all SVM and Ridge baselines with matched one-vector-per-class capacity.SVM uses MATLAB defaults, while Ridge varies its regularization hyperparameter.Source: §4.2.4 · p. 27

4.3 Experiments with Synthetic Datasets

• Synthetic trials used d ∈ {2,10}, C ∈ {3,10}, S ∈ {5,50,500,5000}, 500 test instances per class, Gaussian standard deviation 0.1, and D=1000 for hypervector expansion.Training stopped at convergence or after 1000 epochs unless otherwise stated.Source: §4.3 · pp. 27–28

4.3.1 Results on Synthetic DataGen Datasets

• Perceptron perfectly separates training data but places decision boundaries arbitrarily, whereas suitable MMPerc thresholds can better align boundaries with true class regions.MMPerc boundaries adjust smoothly as α varies, and some α-values produce higher accuracy than Perceptron.Source: §4.3.1 · p. 28, §4.3.2 · pp. 28–29
• For small training sets, SVM and Ridge could fail to perfectly separate training data under one-vs-all classification, while MMPerc and Perceptron could achieve stronger separation.Their testing accuracies were also lower in the reported comparisons, with one SVM exception in a transformed C=3, d=10 configuration.Source: §4.3.1 · p. 28, §4.3.2 · p. 29

4.3.2 Discussion of Experimental Results

• Across synthetic DataGen datasets, MMPerc almost always outperformed the standard Perceptron and was generally more accurate than SVM and Ridge.The comparison covers synthetic configurations with varying dimensionality, class count, sample size, and representations.Source: §4.3.2 · pp. 28–29
• Bias was critical for accuracy on unnormalized data, and selecting an appropriate α was likewise essential to realize MMPerc’s benefit.The experiments assessed bias and binarization effects alongside higher-dimensional and random-projection configurations.Source: §4.3.2 · pp. 28–29, §4.3.1 · p. 28
• The synthetic-data conclusions did not establish that these design choices transfer to real datasets, motivating a subsequent real-data evaluation of margin thresholds and bias.This section therefore treats transfer beyond synthetic data as an open question.Source: §4.3.2 · p. 29

4.4 Experiments with Real Datasets

• Real-dataset experiments evaluated original and binarized datasets and their transformations into real-valued and binary hypervectors, using dimensionalities D ∈ {64, 128, 200, 500, 1000, 2000, 4000, 10000}.MMPerc and Ridge used 5-fold cross-validation, and MMPerc tuned α from {0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}.Source: §4.4 · pp. 30–31

4.4.1 Result Example: CTG

• CTG results show that bias improves MMPerc accuracy, whereas bias-free Perceptron and MMPerc variants exhibit noticeable accuracy drops.For CTG, MMPerc with bias achieves the highest accuracy in one comparison, and mean-accuracy results show biased MMPerc variants outperforming the baselines.Source: §4.4.1 · pp. 31–32
• CTG RP accuracy remains stable across dimensionality, consistent with the linearity of the RP transformation.Classifier rankings summarize relative performance across dimensionalities, with MMPerc achieving the best average rank and improving further when bias is included.Source: §4.4.1 · p. 32
• On CTG RP+bin representations, larger dimensionalities allow binary-hypervector classifiers to outperform classifiers trained on original or binarized CTG data.The RP+bin accuracy variation is attributed to local nonlinear features introduced by binarization.Source: §4.4.1 · p. 32

4.4.2 Selected Results, Comparison, and Discussion

• Direct comparison with prior studies is limited by differences in data formats, transformations, evaluation protocols, dataset splits, and dataset versions.The paper emphasizes internally consistent comparisons using identical vectors or hypervectors and dataset splits.Source: §4.4.2 · p. 33
• MMPerc typically outperforms the standard Perceptron when the margin threshold α is properly selected, while HAND datasets show similar performance.Cross-validation tends to select α-values close to optimal on the HAND datasets.Source: §4.4.2 · pp. 33–34
• MMPerc with appropriately chosen α and bias often outperforms both SVM and Ridge under the same one-prototype-per-class memory budget.The overall comparison spans real datasets, binarized data, RP, and RP+bin transformations across dimensionalities.Source: §4.4.2 · p. 34

5 Discussion

• The proposed family applies a multiplicative margin requiring the true-class score to exceed the closest competitor by a fixed proportion of the winning score.This margin is invariant to absolute score magnitude, avoiding explicit adjustment for class-prototype and data-vector norms required by additive margins.Source: §5 · p. 34
• MMPerc achieved competitive accuracy and frequently outperformed standard Perceptron, Ridge, and SVM baselines when bias and margin threshold were properly chosen.On HAND1 without transformation, MMPerc reached 97.85% versus 97.60% for SVM; with random-projection transformation, SVM reached 99.63% versus 99.58% for MMPerc.Source: §5 · pp. 35, 37, Table 4 · p. 35
• MMPerc variants combine minimal computational and operational requirements with conservative updates restricted to mistakes and the true and returned class prototypes.They avoid variable learning rates, weight decay, normalization, and projection, supporting integer and binary data through simple arithmetic or counting operations.Source: §5 · p. 37

5.1.1 Theoretical Extensions

• Future theoretical work should analyze margin-threshold selection, generalization, quantized weights, and connections between large-margin Perceptrons, overparameterization, HDC, and DNNs.HDC is proposed as a high-dimensional testbed for studying implicit regularization, benign overfitting, double descent, and grokking in linear models.Source: §5.1.1 · p. 38

5.1.2 Empirical Comparison of Large-Margin Perceptron Variants

• Further experiments should compare large-margin Perceptron variants on large diverse datasets, including quantized or binary class weights and nonlinear baselines such as Random Forests.Comparisons should use both original features and hypervector representations.Source: §5.1.2 · p. 38

5.1.3 Key Design Considerations

• Margin-threshold selection remains a key challenge because cross-validation over candidate α-values may require dataset-specific tuning, while class-specific thresholds add selection complexity.Best-performing α-values tend to remain stable across nearby dimensionalities, suggesting lower-dimensional estimation or early-epoch selection as practical strategies.Source: §5.1.3 · p. 39
• Because the effective multiplicative margin does not decrease during training, annealing α could improve late-stage boundary stabilization but introduces additional hyperparameters.The naturally decreasing effective learning rate stabilizes training while slowing it down.Source: §5.1.3 · p. 39
• Two-class updates are more efficient than multiclass updates, while multiclass rules may improve training speed or generalization but can be costly with many classes.Updating all margin-violating classes or using softmax-like updates requires more computation, especially for many classes and floating-point operations.Source: §5.1.3 · p. 40
• Weight selection, weight decay, and non-negative constraints remain important design considerations affecting evaluation reliability, computational overhead, score margins, and interpretability.Peak-training-accuracy weights can underperform hindsight-selected weights; weight decay adds operations and norm computations, while non-negative weights address opposite-sign margin issues and can improve interpretability.Source: §5.1.3 · p. 40
• Combining multiplicative margins with multiplicative weight updates or orthogonal Perceptron enhancements is proposed as a route toward sparse, non-negative, accurate, robust, and efficient variants.The paper states that multiplicative updates have not yet been explored with multiplicative margins, while many HDC enhancements are natural integration candidates.Source: §5.1.3 · p. 41

5.1.4 IoT, TinyML, Edge Computing, EdgeAI, AIoT

• Large-margin Perceptrons combine simple models with low training and inference costs, supporting deployment on resource-constrained IoT, TinyML, edge, and AIoT devices.Their large-margin mechanism is also described as improving robustness, generalization, and classification accuracy under limited-resource conditions, with extensions to quantized and binary class weights.Source: §5.1.4 · p. 41

5.1.5 Other Tasks and Applications

• Future applications include weak- or partial-label, multi-label, bandit, selective, abstention-based, and DNN-integrated tasks, with margins potentially guiding confidence-based abstention.HDC representations could also extend classification to structured data such as sequences, trees, and graphs.Source: §5.1.5 · p. 42

• The work presents multiclass Perceptron classifiers with multiplicative margins, including architectural formulations, learning algorithms, loss functions, update rules, and mistake bounds.Source: §6 · p. 42
• The models require no or only minor changes to the standard fixed-unit-rate Perceptron update, making them computationally lightweight.This simplicity supports use with real-valued, quantized, and binary vector data.Source: §6 · p. 42
• The study examines practical design choices including bias, margin-threshold selection, training regimes, epoch control, and classifier weights for inference.Source: §6 · p. 42
• Extensive experiments cover synthetic and real datasets with real-valued and binary inputs across varied dimensionalities and dataset sizes.Source: §6 · pp. 42–43
• MMPerc typically achieves higher classification accuracy than the standard Perceptron, SVM, and Ridge classifiers.Source: §6 · p. 43
• The accuracy gains and implementation simplicity make multiplicative-margin Perceptrons promising for resource-constrained and edge settings, HDC contexts, and linear evaluation of DNNs.Selecting an appropriate margin threshold can require cross-validation and therefore adds computational cost compared with the standard Perceptron.Source: §6 · p. 43

1.1 The Perceptrons of Rosenblatt

• Rosenblatt’s Perceptron used weighted inputs and thresholded sums, with fixed nonlinear transformations optionally preceding a trainable linear output layer.These designs supported pattern classification and regression, while error-correction training could converge on linearly separable data.Source: §1.1 · p. 56

1.2 Multiclass Linear Perceptrons

• Multiclass linear Perceptrons originated with Eldredge et al. (1956), and Kesler’s equivalent two-class representation enabled error-correcting rules and separable-case convergence analysis.The construction concatenates class weight vectors to apply two-class Perceptron analysis.Source: §1.2 · p. 57

1.3 Large Margin Perceptrons

• Additive-margin Perceptrons began with two-class work by Mays (1964) and multiclass work by Nilsson (1965b) and Duda & Fossum (1966), motivating many later variants.Examples include MinOver, PAUM, ROMMA, Passive-Aggressive, MIRA, ALMA, and MICRA, which differ in update rules, constraints, and margin schedules.Source: §1.3 · p. 58
• Large-margin baselines include Passive-Aggressive, which updates multiclass models when the margin is below one, and SVMs, which combine weight-norm regularization with hinge loss.Pegasos approximates SVM training through stochastic subgradient updates, while Ridge regression replaces hinge loss with squared error.Source: §1.3 · p. 58
• Multiplicative margin algorithms had not been explored in prior large-margin Perceptron work, whose methods generally require more complex computations than the paper’s variants.Some existing methods also do not extend from binary to multiclass settings.Source: §1.3 · p. 59

1.4 Fixed Input Nonlinear Transformation

• Fixed nonlinear transformations support linear classifiers such as RVFL (Pao & Takefuji, 1992), ELM, and Reservoir Computing, but SVD-based closed-form solutions do not natively support online or incremental training.These approaches commonly use least-squares solutions, sometimes with Tikhonov regularization.Source: §1.4 · pp. 59–60

1.5 HDC Classifiers

• HDC classification typically uses efficient linear classifiers because hypervector construction is already nonlinear, but existing HDC classifiers generally lack margin-based training.Prototype/centroid classifiers average class hypervectors efficiently but typically achieve modest accuracy because they do not update prototypes to correct misclassifications; later methods may use score margins while maintaining separate binarized prediction weights.Source: §1.5 · pp. 60–61

2.1 Proof of Theorem 1 (Mistake bounds for large margin Perceptrons in the linearly separable case)

• Theorem 1’s proof starts from zero weights, analyzes mistaken updates across the multiclass Perceptron variants, and combines the resulting norm bounds.The proof framework uses a lower bound on ||W|| and an upper bound on ||W|| before solving their combination for each variant’s mistake count.Source: §2.1 · p. 62, §2.1.3 · p. 64

2.1.1 Lower Bound on ||W||

• For the separable proofs, the lower-bound argument accumulates at least γ per mistake for AMPerc, MMPerc, and MMPerc-Abs, while asymmetric variants accumulate γ − αR.Thus, after M mistakes, ⟨U,(M+1)W⟩ ≥ γM for the first three variants and ≥ (γ − αR)M for MMPerc-Asm and MMPerc-AbsAsm, with γ − αR ≥ 0.Source: §2.1.1 · pp. 62–63

2.1.2 Upper Bound on ||W||

• The corresponding upper-bound analysis controls weight growth using the feature-radius constraint R, producing variant-specific quadratic norm bounds after M mistakes.AMPerc has ||(M+1)W||^2 < 2(R^2 + β)M; MMPerc and MMPerc-Abs have R^2(2M + αM^2 − αM); MMPerc-Asm and MMPerc-AbsAsm have (1 +(1−α)^2)R^2M and (1 +(1+α)^2)R^2M.Source: §2.1.2 · pp. 63–64

2.1.3 Combining the Lower and Upper Bounds on ||W||

• The cited derivations give explicit mistake bounds for AMPerc, MMPerc, MMPerc-Abs, and MMPerc-Asm, with MMPerc-Asm requiring γ − αR > 0.AMPerc satisfies M < 2(R/γ)^2(1 + β/R^2); MMPerc and MMPerc-Abs satisfy M < (R^2/γ^2)(2 − α)/(1 − αR^2/γ^2). MMPerc-Asm satisfies M < (1 +(1−α)^2)R^2/(γ − αR)^2.Source: §2.1.3 · p. 64

2.2.1 Lower Bound on U,W

• In the non-separable case, the proof lower-bounds the final Frobenius dot product by accumulated margin b minus hinge losses, with asymmetric variants additionally paying α||U||R per mistake.For AMPerc, MMPerc, and MMPerc-Abs, ⟨U,(T+1)W⟩ ≥ bM − L_b(U); for MMPerc-Asm and MMPerc-AbsAsm, it is at least (b − α||U||R)M − L_b(U).Source: §2.2 · p. 65, §2.2.1 · pp. 65–66

2.2 Proof of Theorem 2 (Mistake bounds for large margin Perceptrons in the linearly non-separable case)

• Theorem 2’s non-separable proof initializes all variants at zero and derives an upper mistake bound by jointly analyzing lower and upper bounds on ⟨U,(T+1)W⟩.The supplied proof portion establishes the lower-bound side through sums of update contributions at the rounds where mistakes occur.Source: §2.2 · p. 65, §2.2.1 · p. 65

2.2.2 Upper Bound on U,W

• The upper bounds differ by algorithm: AMPerc scales linearly with M, MMPerc and MMPerc-Abs include αM^2+(2–α)M, while MMPerc-Asm and MMPerc-AbsAsm use distinct linear coefficients in M.These bounds are obtained after applying the Cauchy–Schwarz inequality and norm bounds on (T+1)W.Source: §2.2.2 · p. 66

2.2.3 Combining the Lower and Upper Bounds on U,W

• The combined derivation gives AMPerc the final mistake bound M < (1/b^2) {b Lb + 2 ||U||^2 (R^2 + β) + [2 b Lb ||U||^2 (R^2 + β)]^1/2}.It follows by combining the additive-margin upper bound with the Lβ- and Lb-hinge-loss terms and solving a quadratic inequality.Source: §2.2.3 · pp. 66–67
• For MMPerc and MMPerc-Abs, solving the quadratic inequality yields M < {b Lb+ (2–α) R^2||U||^2 + [bLb (2–α) R^2 ||U||^2 +αR^2 ||U||^2 Lb^2]^1/2} / (b^2 – αR^2 ||U||^2).The derivation assumes 0 ≤ α < 1 and uses the positive root of the quadratic in M.Source: §2.2.3 · p. 67
• A supported final bound has coefficient 2 – 2α + α^2 in its R^2 ||U||2 term, with denominator (b – α||U||R)^2.Source: §2.2.3 · p. 67

3.1 Results on Synthetic DataGen Datasets

• The synthetic-data extension evaluates RP, RP followed by binarization, and varying bias using configurations C ∈ {3,10} and d ∈ {2,10}.Real-valued RP expands vectors to D=1000, while the experiments additionally examine binarization and bias magnitude.Source: §3.1 · p. 68, §3.1.1 · p. 68

3.1.1 Real-Valued Vectors after RP

• Classification-accuracy trends remained similar to those without RP; in selected configurations, SVM exceeded the best-performing MMPerc, reaching 0.8253 versus 0.8113 for C=3, d=10, S=5.At S=500, Perc achieved 0.9900 versus 0.9927 for the best-performing MMPerc, while SVM improved to 0.9500 from 0.8620 without RP.Source: §3.1.1 · p. 68

3.1.2 Binarized Data after RP

• Binarized RP disrupts DataGen class regions by discarding norms and distances, causing linear decision boundaries to radiate from the origin.Unlike RP, RP+bin retains only vector directions, so points separated by norm differences can map to similar hypervectors.Source: §3.1.2 · pp. 69–70

3.1.3 Bias Term after RP

• MMPerc with bias = normmax consistently outperformed bias = 0 and bias = 1 across tested RP setups, supporting it as a default for unnormalized data.Bias = 0 produced poor origin-centered boundaries, while bias = 1 improved over zero bias but remained inferior to bias = normmax; convergence was also faster with bias = normmax.Source: §3.1.3 · p. 71

3.2.1 UCIHAR

• On UCIHAR, MMPerc outperformed Perceptron overall, achieved the best average rank on RP+bin data, but Ridge and SVM led on non-binary data.For original binarized UCIHAR, MMPerc surpassed Perceptron, SVM, and Ridge; for RP data, MMPerc remained ahead of Perceptron while Ridge achieved the highest accuracy, followed by SVM.Source: §3.2.1 · p. 73, Figure 17 · p. 74

3.2.2 ISOLET

• On original and binarized ISOLET, MMPerc outperformed Perceptron, SVM, and Ridge, while binarization reduced classification accuracy.Bias had comparable effects for MMPerc and Perceptron on the original data, and the same accuracy pattern appeared after binarization.Source: §3.2.2 · p. 74
• On ISOLET, MMPerc (α ∈ [0.9]) outperforms Perceptron, SVM, and Ridge, while achieving the lowest average rank across RP+bin dimensionalities.Accuracy remains approximately constant across classifiers for D > 500, declines for D ≤ 500 on original data, and increases with D for RP+bin.Source: §3.2.2 · pp. 74–75, Figure 22 · p. 75

3.2.3 HAND1

• On HAND1, MMPerc matches or nearly matches Perceptron, improves with bias on original and original+binarized data, and without bias attains the lowest RP+bin average rank.On original data both methods perform on par with SVM and outperform Ridge, whereas on original+binarized data they surpass Ridge and SVM; RP+bin accuracy increases with D.Source: §3.2.3 · p. 76, Figure 27 · p. 77

3.2.4 HAND2

• On HAND2, MMPerc remains comparable to Perceptron, with bias helping noticeably on original+binarized data and both methods outperforming SVM and Ridge there.Bias has little effect on original data, while cross-validated α values remain close to the best-performing α.Source: §3.2.4 · p. 77

3.2.5 HAND3

• On HAND3, MMPerc is comparable to Perceptron, bias substantially improves original-data performance, and SVM is slightly worse than biased MMPerc while Ridge trails it.For original+binarized data, bias produces approximately the same accuracy, while SVM performs substantially worse than Ridge and Ridge remains below the leading methods.Source: §3.2.5 · p. 78

3.2.6 HAND4

• On HAND4, MMPerc matches Perceptron, bias substantially improves both representations, and MMPerc and Perceptron exceed SVM and Ridge on original data.On original+binarized data, SVM performs worse than Ridge, while Ridge remains slightly below MMPerc and Perceptron; cross-validated α is close to the best setting with bias.Source: §3.2.6 · p. 79

3.2.7 HAND5

• Across HAND5, MMPerc remains close to Perceptron, bias substantially improves performance, and bias-free MMPerc attains the lowest RP+bin average rank.RP+bin accuracy increases with D and exceeds HAND5 original and RP from D = 200; on original+binarized data, Ridge is comparable to biased MMPerc and Perceptron while SVM underperforms Ridge.Source: §3.2.7 · pp. 79–80, Figure 38 · p. 81
• Adding bias = normmax substantially improves performance in most cases, except HAND2 orig and HAND3 orig+bin, where results are comparable.MMPerc without bias nevertheless achieves the lowest average rank for HAND1 and HAND5 across D.Source: §3.2.7 · p. 81
• Cross-validated α-values for MMPerc produce accuracies close to those from the best-performing α, particularly when bias is included.Source: §3.2.7 · p. 81
• MMPerc and Perceptron with bias generally outperform SVM and Ridge, although SVM can exceed Ridge on binarized data except HAND2.SVM typically trails MMPerc and Perceptron with bias on original datasets, while Ridge is generally less accurate than both.Source: §3.2.7 · p. 81
• Original HAND1–HAND5 data achieve substantially higher accuracies than binarized versions because binarization limits representational capacity and class separability.The original datasets all have very low dimensionality, d = 4.Source: §3.2.7 · p. 81