PaperlayerView exact revision on arXiv

Source-linked AI summary

A Nonconvex Framework for Joint Sparse Sample Weighting and Parameter Estimation

Hassan Nojavan, Chul Moon, Miju Ahn

arXiv:2610.33957v1math.OCcs.LGstat.ML

TL;DR

Training data may contain noise, outliers, and anomalies, while standard algorithms often assume clean datasets. SWAPE jointly estimates model parameters and sample weights using alternating majorization-minimization; experiments report effectiveness across regression, classification, and recommender settings. The stated scope covers specified loss and sparsity-function classes.

  • Problem

    Many standard learning algorithms assume clean data, although training observations can contain noise, outliers, and other anomalies.

    Source: §1 · p. 1

  • Method

    SWAPE jointly optimizes model parameters and per-observation weights, using sparsity regularization and alternating majorization-minimization for the subproblems.

    Source: §1 · p. 2, §2 · p. 3

  • Results

    The authors report SWAPE's effectiveness in regression, classification, and recommender-system settings, including experiments with data anomalies.

    Source: §1 · p. 3, §5 · p. 19

  • Takeaways & Limitations

    The framework adaptively reduces the influence of unreliable observations while preserving informative data points.

    Source: §5 · p. 19

    The stated loss-function scope is limited to two assumed classes.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

We propose a joint sparse sample weighting and parameter estimation (SWAPE) framework that jointly optimizes model parameters and sample weights to train a model while simultaneously assigning an individual weight to each training data point. Our framework accommodates several widely used loss functions for the model parameters, including convex, weakly convex, and difference-of-convex loss, and weakly convex sparsity functions to control the complexity of the sample weights. To solve the resulting bivariate problem, we propose an alternating minimization method in which the subproblems for updating the model parameters and weights are each approximated using majorize-minimize techniques. We provide several approximation methods for the loss functions considered in this paper, and show the overall algorithm's convergence. Numerical experiments on various learning tasks and data anomaly settings demonstrate the effectiveness of the proposed framework in minimizing the impact of undesirable data points compared to benchmark methods.

1 Introduction

Because training-data quality affects predictive models while real datasets can contain noise, outliers, and anomalies, the paper develops sample selection as part of model training. It jointly estimates sample weights and model parameters, with an alternating majorization-based method and experiments across several learning settings.

1 Introduction

  • Alternating minimization updates data weights and model parameters in turn, approximating each subproblem with majorization techniques for DC and Lipschitz-gradient losses.The paper analyzes convergence for the two-block bi-DC case.Source: §1 · pp. 2–3
  • SWAPE generalizes prior tailored approaches by accommodating broad classes of loss and sparsity functions without requiring a priori knowledge of underlying data structure.The motivation contrasts this scope with existing methods often limited to specific convex-loss and sparsity-function pairings.Source: §1 · p. 2
  • The framework assigns each training point a weight and jointly optimizes those weights with model parameters, using sparsity regularizers to select data during training.This creates a bivariate weighted empirical risk minimization problem that can be nonconvex even with a convex loss.Source: §1 · p. 2
  • Experiments test the method in linear regression, neural-network binary classification, and recommender systems under distribution shifts, label contamination, random noise, and adversarial attacks.The paper compares SWAPE with suitable benchmark models.Source: §1 · p. 3
  • The paper organizes its framework and stationarity analysis before the algorithm and convergence results, then reports three numerical studies.Proofs are omitted from the main document and included in the appendices.Source: §1 · p. 3

2 Framework

The framework jointly estimates model coefficients and per-observation weights, with regularization and sparsity penalties shaping the objective. It supports specified nonconvex loss and penalty classes, and uses directional stationarity to analyze the resulting problem.

2 Framework

  • SWAPE minimizes weighted per-sample losses together with model regularization and a penalty on weights, jointly choosing coefficients and weights.Weights are constrained to a box with nonnegative entries; the penalty controls the complexity of the data used.Source: §2 · pp. 3–4

2.1 Assumptions on the loss and penalty functions

  • The loss assumptions cover DC losses, including convex losses and shallow feedforward neural-network losses, and a class with Lipschitz-continuous gradients.Weakly convex functions form a subclass of DC functions, but the converse does not generally hold.Source: §2.1 · p. 4
  • Under stated conditions, the loss is weakly convex when the convex component of its DC representation has a Lipschitz-continuous gradient.The penalty assumptions include shifted folded-concave functions such as SCAD and MCP.Source: §2.1 · pp. 4–5
  • The weight penalty is modified to favor weights of one rather than zero, letting the model use or omit each observation at a penalty.Directly using common zero-promoting sparsity penalties can yield the trivial all-zero-weight solution when the model regularizer is zero.Source: §2.1 · p. 4

2.2 Concept of stationarity

  • The objective is directionally differentiable under the stated loss and penalty assumptions, enabling directional-stationarity analysis despite possible nondifferentiability.Directional stationary solutions are identified as suitable for the structured nonconvex, nonsmooth problem.Source: §2.2 · p. 5
  • The paper introduces directional stationarity for the constrained problem and uses it to analyze the proposed algorithm.The algorithm and its convergence analysis follow this stationarity setup.Source: §2.2 · p. 5

3 Algorithm

The algorithm alternates between parameter and weight updates by minimizing majorizing surrogates; its convergence analysis establishes a convergent subsequence and directional stationarity in case (iii).

3 Algorithm

  • The method alternates parameter and weight updates, minimizing a surrogate upper bound built at the previous iterate for each subproblem.It is a two-block special case of block successive upper-bound minimization.Source: §3 · pp. 5–6, §3.1 · p. 6

3.1 Majorize-minimization framework

  • For the parameter update, the paper constructs majorizers for DC, Lipschitz-gradient, and weakly convex losses, with conditions that ensure the surrogates upper-bound the subproblems.For the Lipschitz-gradient case, cx ≥ Lip∇L; for the weakly convex case, a sufficiently large cx can also make the surrogate convex.Source: §3.1 · pp. 6–7
  • For the weight update, adding a quadratic term makes the surrogate an upper bound and, when cw ≥ γσρ, convex.The bound and convexity conditions are stated in Lemma 6.Source: §3.1 · p. 7

3.2 Convergence analysis

  • Under the stated assumptions, the iterates have a convergent subsequence; in case (iii), its accumulation point is directionally stationary.Case (iii) uses the weakly convex loss approximation; the other listed cases also have convergence guarantees, with stationarity characterized by additional conditions.Source: §3.2 · pp. 7–8

4 Numerical Experiments

This section evaluates SWAPE across synthetic regression and classification tasks and Netflix recommendation under several contamination scenarios, including random noise and bandwagon attacks. The reported results describe strong performance in contaminated settings; on Netflix, its hit-rate and MRR advantage under noise comes with higher MAE, while target-item recommendation metrics are zero under both tested attack strengths.

4 Numerical Experiments

  • Experiments cover regression with vertical and interior-clustered contamination (α = 0.2, 0.3, 0.4; τ = 5, 8), flipped-label classification (α = 0.25, 0.30, 0.35, 0.40, 0.45), and Netflix recommendation without contamination, with random noise, or under bandwagon attack.Recommendation experiments vary random-noise proportions across α = 0.1, 0.3 and artificial-user proportions across α = 0.05, 0.10.Source: §4.1.1 · p. 9, §4.2.1 · p. 13, §4.3 · p. 14

4.1.2 Results

  • At α = 0.4 and τ = 5, SWAPE achieves an F1 score of 0.93, versus 0.21 for Θ-IPOD and 0.76 for LTS, while vertical-contamination MSE stays near 1.03.At α = 0.4, LTS and Θ-IPOD have MSE values of 2.01 and 4.21, respectively; SWAPE retains 54.4% of the data.Source: §4.1.2 · p. 10, Table 2 · p. 11
  • For interior-clustered contamination at τ = 5, SWAPE retains 63.0% and 56.6% of data at α = 0.3 and 0.4 while maintaining strong prediction performance; at τ = 8, its performance improves.LAD is also robust across contamination levels, whereas Θ-IPOD and LTS degrade as α rises and have higher errors than all regression benchmarks at α = 0.4.Source: §4.1.2 · pp. 10–11, Table 3 · p. 12

4.2.2 Results

  • Early stopping is less suitable for SWAPE: it leaves learned weights near their initialization and retains 100% of training data, while SWAPE’s other variants recover decision boundaries aligned with the two-moons structure.Under early stopping, SWAPE and the baseline perform similarly; the other variants’ baseline boundaries are more irregular.Source: §4.2.2 · p. 14, Figure 4 · p. 15
  • In flipped-label classification, SWAPE outperforms the baseline under most variants and contamination levels, with the highest F1 score of 0.828 without regularization at α = 0.25.For no regularization, ℓ2 regularization, and dropout, it retains 73.34–76.19% of training data at α = 0.25 and 61.78–65.28% at α = 0.45.Source: §4.2.2 · p. 14, Table 4 · p. 16

4.3.2 Results

  • For uncontaminated Netflix data at K = 5, SWAPE has the highest hit rate (0.481) and MRR (0.302), improving on SLIM’s hit rate of 0.402 while using 79.1% of data entries.UserKNN and ItemKNN have hit rates around 0.015 but lower MAE than SWAPE and SLIM.Source: Table 5 · p. 17, §4.3.2 · p. 17
  • Under random noise, SWAPE has the highest hit rate and MRR but higher MAE; all methods’ metrics worsen with noise and increasing α.For K = 5, SWAPE’s hit rate decreases from 0.481 to 0.478 as α increases from 0.1 to 0.3.Source: Table 6 · p. 18, §4.3.2 · p. 18
  • At K = 10 and 15, all models improve hit rate and MRR, with SWAPE strongest overall; SLIM-LTS lowers SLIM’s MAE but also its hit rate and MRR.SVD has lower hit rate and higher MAE than SWAPE.Source: §4.3.2 · p. 18
  • Under bandwagon attacks, hit rates and MRR increase as attacker share rises, while MAE changes only marginally across models.The passage attributes the increase to better identification of genuinely popular items when more users give them the highest rating.Source: Table 7 · p. 18, §4.3.2 · p. 18
  • SWAPE records zero target hit rate and target MRR across all K and both bandwagon attack strengths, so injected profiles place no target items in top-K recommendations.A higher target hit rate or MRR indicates greater influence from the bandwagon attack.Source: Table 8 · p. 19, §4.3.2 · p. 19

5 Conclusion

SWAPE jointly computes model parameters and observation weights, allowing training to reduce the influence of unreliable observations while preserving informative ones. The paper reports convergence guarantees under stated assumptions and effective performance across regression, classification, and recommender-system settings.

5 Conclusion

  • SWAPE computes model parameters and observation weights simultaneously to adaptively reduce unreliable observations’ influence while preserving informative data.Source: §5 · p. 19
  • An alternating majorization-minimization algorithm produces non-increasing objective values and subsequence convergence under the stated assumptions.In the weakly convex case, an accumulation point is a directional stationary solution.Source: §5 · p. 19
  • Experiments show competitive performance in regression and classification under overall contaminated settings.Source: §5 · p. 19
  • In recommender systems, SWAPE shows strong ranking performance under no contamination, random noise, and bandwagon attacks.Source: §5 · p. 19
  • Target-specific recommender results indicate that SWAPE limits the effects of adversarial attacks.Source: §5 · p. 19

Data Availability Statement

The authors provide a Python implementation of SWAPE in a public repository.

Data Availability Statement

Appendices

The appendices contain proofs and additional experimental details.

Appendices

  • Appendix A contains proofs, while Appendices B–D provide additional details for the three experiments in Sections 4.1–4.3.Source: Appendices · p. 24

A.1 Proof of Proposition 1

  • The proof of Proposition 1 combines equation (4) with the first-order condition of the convex function.Source: §A.1 · p. 24

A.2 Proof of Lemma 2

The proof uses differentiability in one case and directional derivatives for the other, relying on DC structure to define those derivatives.

A.2 Proof of Lemma 2

  • Under (L2), differentiability of the loss makes it sufficient to establish the case of (L1).Source: §A.2 · p. 24
  • Assumption (L1) makes both ℓ and ρ DC, so their directional derivatives are well-defined [4, Lemma 3.1.5].Source: §A.2 · p. 24
  • The derivation then applies the directional-derivative definition to the objective terms.Source: §A.2 · p. 24

A.3 Proof of Lemma 3

The proof fragments establish convexity of a weight-update surrogate using weak convexity of the sparsity penalty. The other supplied fragments state only that the corresponding lemmas' conditions imply their conclusions.

A.3 Proof of Lemma 3

  • One proof uses convexity of Lcve and states conditions in (7) follow for all x ∈ X; another invokes (L2) and the lemma’s condition to prove its statement for any x ∈ X.Source: §A.3 · p. 25, §A.4 · p. 25

A.5 Proof of Lemma 6

  • Weak convexity of P and linearity of the weight loss yield a convex surrogate for the weight update.The argument uses cw ≥ γσρ.Source: §A.5 · p. 25

A.6 Proof of Theorem 7

Theorem 7’s proof establishes descent and convergence properties for the alternating updates, with accumulation points shown to be directionally stationary in the stated case. The appendix also directs readers to the regression experiment’s data, algorithm, benchmarks, and implementation details.

A.6 Proof of Theorem 7

  • The proof shows successive parameter and weight updates vanish when the descent coefficients are positive.It also uses lower-boundedness of F to establish convergence of the objective sequence.Source: §A.6 · p. 26
  • In case (iii), a convergent subsequence has an accumulation point that is directionally stationary for problem (2).The proof identifies a subsequence converging to (x*, w*) and establishes its stationarity.Source: §A.6 · p. 26

B Regression

  • The regression appendix covers data generation, algorithm and subproblem details, benchmark comparisons, hyperparameter tuning, and computation time.Source: B Regression · p. 27

B.1 Data Generation

The appendix details synthetic regression experiments with two contamination patterns and describes the SWAPE implementations and benchmarks for regression and binary classification. It gives algorithmic update derivations and tuning procedures, but the supplied passages do not report comparative performance outcomes.

B.1 Data Generation

  • Without contamination, the data matrix A ∈ Rⁿˣᵈ and response b ∈ Rⁿ are generated following (17), where b = Ax* + ε and ε ∼ N(0, Iₙ).Source: §B.1 · p. 27

B.2 Details of the Algorithm

  • For regression, SWAPE uses least squares with a shifted MCP weight penalty and majorize-minimize surrogates for both alternating subproblems.The x-update is a proximal weighted least-squares problem with a closed-form solution; the weight update separates into univariate problems.Source: §B.2 · pp. 27–28, §B.2.1 · p. 28, §B.2.2 · p. 28

B.2.2 Closed-Form Solution for w-subproblem (37b)

  • The regression weight update obtains its unique minimizer by checking regions split at 1 − ηθ, 1, and 1 + ηθ.The lower breakpoint is outside the feasible region when ηθ ≥ 1; the update is strongly convex under condition (39).Source: §B.2.2 · pp. 29–30

B.3.1 Comparison Methods

  • Regression benchmarks include least squares, LAD, Huber, LTS, and Θ-IPOD; the appendix specifies LOOCV tuning and reports training time for a vertical-contamination setting.The reported timing setting uses α = 0.3 and τ = 5, with means and standard deviations over 200 replications.Source: §B.3.1 · p. 30, §B.3.2 · p. 31, Table 9 · p. 32

B.3.2 Hyperparameter Selection

  • The regression appendix also specifies benchmark tuning, including LOOCV selection of γ for SWAPE and fixed MCP parameters θ = 1 and η = 3.Θ-IPOD is tuned by LOOCV median MSE; LTS uses h = floor(0.75n).Source: §B.3.2 · p. 31

C.1 Details of the Neural Network in the Binary Classification Formulation

  • The binary-classification formulation uses a two-hidden-layer fully connected network, softplus activations, logistic output, weighted binary cross-entropy, and a shifted LASSO weight penalty.The supplied formulation describes both an unregularized network variant and ℓ2-regularization on edge weights.Source: §C.1 · p. 32

C.2 Details of the Algorithm

  • For binary classification, SWAPE uses the proposed surrogates, solves the parameter subproblem with Adam, and derives a closed-form weight update.The weight subproblem is separable across observations and its update is characterized over intervals including w = 0 and w = 1.Source: §C.2 · p. 33, §C.2.1 · pp. 33–34

C.3.1 Comparison Methods

The supplied appendix passages specify the binary-classification comparison setup and implementation, then describe Netflix Prize data preparation, recommendation-model updates, benchmarks, and tuning. They provide experimental design and method details rather than comparative outcome values.

C.3.1 Comparison Methods

  • The binary-classification comparison tests SWAPE against a same-network baseline with all observation weights fixed to 1, across four regularization and training variants.The variants are no regularization, ℓ2-regularization, dropout, and early stopping.Source: §C.3.1 · p. 34

C.3.3 Implementation

  • The appendix reports training-time tables for the binary-classification experiment and a representative vertical-contamination regression setting.The supplied table captions identify mean and standard deviation across 200 replications but provide no timing values.Source: Table 10 · p. 35

C.3.2 Hyperparameter Selection

  • For the binary-classification experiment, γ is selected separately per replication by 10-fold cross-validation, and both models use matching network initialization.The network has two hidden layers of width 256; the x-subproblem uses Adam with learning rate 10^-3 and mini-batches of 64.Source: §C.3.2 · p. 35, §C.3.3 · p. 35

D.1.1 Pre-processing Netflix Prize Data

  • The Netflix Prize data are pruned and stratified before sampling to form a 1,622-user by 747-movie matrix with 136,579 ratings and 11.27% density.Source: §D.1.1 · pp. 35–36

D.1.2 Generating Random Noise

  • Recommendation experiments inject random rating changes at α = 0.1 and α = 0.3 into observed training entries.An entry is changed to a different rating with probability α.Source: §D.1.2 · p. 36

D.2 Details of the Algorithm

  • The recommender implementation applies the regression-style MCP weight update columnwise and derives a closed-form parameter update for the constrained SLIM problem.The x-update selects a column index minimizing the current objective and solves the remaining components subject to nonnegativity.Source: §D.2 · p. 36, §D.2.1 · pp. 36–37

D.3.1 Comparison Methods

  • Recommendation benchmarks include SVD, UserKNN, ItemKNN, SLIM, and SLIM-LTS, with SLIM-LTS trimming large residuals.The appendix describes user/item similarity methods and an LTS-based SLIM variant that retains the smallest squared residuals.Source: §D.3.1 · pp. 37–38

D.3.2 Hyperparameter Selection

  • Recommendation hyperparameters are selected using five-fold cross-validation on one replication, with final neighborhood settings K = 10 for UserKNN and ItemKNN.The chosen parameters are evaluated by mean HitRate@5 across folds before final training.Source: §D.3.2 · pp. 38–39

D.3.3 Implementation

The appendix reports recommender-system training runtimes and adds analysis showing that strong ranking performance need not mean predicted scores match observed rating magnitudes.

D.3.3 Implementation

  • SLIM and SLIM–LTS used Gurobi Optimizer 12.0 via Python, while SVD, UserKNN, and ItemKNN used the Surprise library.The implementation reports Gurobi and Surprise bibliography markers and, respectively.Source: §D.3.3 · p. 39
  • For runtime comparisons, the proposed method, SLIM, and SLIM–LTS used 128 CPU cores, while SVD and KNN used their internally optimized implementations.The proposed method uses column-wise parallelization across cores.Source: §D.3.3 · p. 39
  • UserKNN and ItemKNN require substantially more training time because computing and applying user/item similarity measures is costly.Table 12 reports wall-clock training times for the first setting, averaged over 30 replications.Source: Table 12 · p. 39, §D.3.3 · p. 39

D.4 Additional Results and Analysis

  • SLIM generally predicts below true ratings, and SVD has a similarly compressed score distribution; strong hit rates need not imply close agreement with observed rating magnitudes.Figure 5 summarizes predicted scores by true rating for observed test user-item pairs in the first recommender-system experiment.Source: §D.4 · p. 39, Figure 5 · p. 40
Loading 2610.33957v1…