Pareto Optimization with Robust Evaluation for Noisy Subset Selection

1. Problem Definition

The paper addresses the Noisy Subset Selection Problem with a cardinality constraint.

• Goal: Select a subset $S$ of size at most $k$ from a ground set $V$ to maximize an objective function $f(S)$.
• Constraint: The evaluation of the objective function is noisy. Instead of the true value $f(S)$, the algorithm only observes a noisy random variable $F(S)$, where $\mathbb{E}[F(S)] = f(S)$.
• Context: This problem is fundamental in applications like Influence Maximization (selecting key users in a social network) and Sparse Regression (selecting features to minimize error).
• Challenge: Traditional algorithms (Greedy, POSS) designed for noise-free environments often fail or become unstable in noisy settings because they may discard high-quality solutions due to temporary noise fluctuations. Existing noise-robust methods (like PONSS) suffer from excessive computational overhead due to repeated re-evaluations.

2. Methodology: The PORE Algorithm

The authors propose PORE (Pareto Optimization with Robust Evaluation), a novel multi-objective evolutionary algorithm.

Core Reformulation

PORE reformulates the single-objective subset selection problem into a bi-objective optimization problem:

1. Maximize a Robust Evaluation Function ($f_1$): Instead of using the raw noisy value $F(S)$, PORE calculates a robust score. For a solution $S$, $f_1(S)$ is the average of the noisy function values over all subsets of $S$ that have size $|S|-1$.
   • Rationale: This averaging process smooths out random noise and identifies "well-structured" solutions that perform consistently even when minor structural perturbations occur.
2. Minimize Subset Size ($f_2$): The algorithm simultaneously minimizes the cardinality $|S|$ (formulated as maximizing $-|S|$).

Algorithmic Process

PORE employs a multi-objective evolutionary strategy similar to the POSS and PONSS algorithms:

1. Initialization: Start with an empty set.
2. Mutation: Generate offspring by flipping bits (adding/removing elements) of a parent solution.
3. Robust Evaluation: Evaluate the offspring using the robust averaging method described above.
4. Selection ($\theta$-Domination): Use a noise-aware comparison strategy ($\theta$-domination) to decide whether to keep the new solution. A solution $x$ $\theta$-dominates $y$ if $f_1(x) \geq \frac{1+\theta}{1-\theta} f_1(y)$ and $|x| \leq |y|$.
5. Population Control: If the population size for a specific subset size exceeds a hyperparameter $B$, the algorithm directly discards the individual with the lowest robust evaluation score.
   • Key Difference from PONSS: Unlike PONSS, which performs expensive re-evaluations (sampling multiple times) to resolve ties or remove weak solutions, PORE relies on the precision of the initial robust evaluation to make this decision without extra computational cost.

3. Key Contributions

1. Novel Robust Evaluation Strategy: Introduced a method to estimate solution quality by averaging noisy evaluations of all immediate sub-solutions (size $|S|-1$). This provides a more stable metric than single-point noisy evaluations.
2. Computational Efficiency: PORE significantly reduces the computational overhead compared to PONSS.
   • PONSS requires $2B$ additional evaluations per population update to re-evaluate candidates.
   • PORE requires no re-evaluations during population updates, as the robust evaluation is deemed sufficiently accurate upon the first calculation.
3. Theoretical and Practical Improvements: The method maintains the approximation guarantees of Pareto optimization while handling noise more effectively than greedy or standard evolutionary approaches.

4. Experimental Results

The authors evaluated PORE on real-world datasets for Influence Maximization (Ego-Facebook, HepPh) and Sparse Regression (Protein, YearPredictionMSD).

• Performance: PORE consistently outperformed the classical Greedy algorithm, POSS, and PONSS.
  • In most settings, PORE achieved a >5% performance improvement over state-of-the-art methods.
  • In the Protein dataset for sparse regression, PORE showed >20% improvement across all settings.
• Stability: PORE demonstrated significantly lower variance (standard deviation) across 30 independent runs compared to other algorithms, indicating higher reliability in noisy environments.
• Efficiency: PORE converged to superior solutions faster than PONSS, particularly on large, complex networks (e.g., HepPh), where PONSS exhibited instability.
• Ablation Studies: Removing the robust evaluation (PORE-F) resulted in performance degradation, confirming that the averaging strategy is the primary driver of success.
• Noise Sensitivity: PORE remained stable across varying noise intensities (controlled by simulation runs or sample sizes), whereas Greedy and POSS performance degraded significantly as noise increased.
• Hyperparameter Sensitivity: The algorithm's performance was found to be insensitive to the $\theta$ parameter, making it robust to parameter tuning.

5. Significance

This paper presents a significant advancement in combinatorial optimization under uncertainty.

• Bridging the Gap: It solves the trade-off between robustness and efficiency. Previous robust methods (PONSS) were accurate but computationally expensive; fast methods (Greedy/POSS) were efficient but unstable in noise. PORE achieves both.
• Real-World Applicability: By demonstrating superior results on real-world datasets (social networks, biological data), the method offers a practical tool for applications where data is inherently noisy (e.g., viral marketing, feature selection in high-dimensional data).
• Methodological Insight: The work highlights that "structural robustness" (evaluating a solution based on its neighbors) is a more effective strategy for noise handling than "statistical re-evaluation" (re-sampling the same solution), offering a new direction for future evolutionary algorithm design.