PaperlayerView exact revision on arXiv

Source-linked AI summary

Towards Ultrahigh Dimensional Feature Selection for Big Data

Mingkui Tan, Ivor W. Tsang, Li Wang

arXiv:1209.5260v2cs.LG

TL;DR

The paper addresses feature selection when Big Data has ultrahigh dimensionality, where existing methods face computational, scalability, and feature-selection-bias challenges. It introduces adaptive feature scaling reformulated as convex semi-infinite programming and solves it through feature generation with reduced MKL subproblems. Experiments report superior testing accuracy and training efficiency relative to baseline methods, while the method extends to grouped and nonlinear feature selection.

  • Problem

    Ultrahigh-dimensional feature selection is difficult because explicit mappings and complex feature groups increase computational demands, while ℓ1-based and related methods retain scalability and selection-bias problems.

  • Method

    Adaptive feature scaling imposes an ℓ1 constraint on a continuous scaling vector, reformulates the problem as convex SIP, and uses FGM to add informative feature groups before solving reduced MKL subproblems.

  • Results

    Experiments on synthetic and real-world linear and group feature-selection tasks report superior testing accuracy and training efficiency compared with baseline methods.

  • Takeaways & Limitations

    Separately controlling feature-selection sparsity and decision-function complexity can reduce selection bias while making ultrahigh-dimensional selection more suitable for Big Data.

  • Takeaways & Limitations

    The approach still faces challenging large-scale MKL subproblems because storing kernel matrices requires O(n^2) space, and some SMO-MKL formulations retain solution bias.

Abstract

from arXiv · show

In this paper, we present a new adaptive feature scaling scheme for ultrahigh-dimensional feature selection on Big Data. To solve this problem effectively, we first reformulate it as a convex semi-infinite programming (SIP) problem and then propose an efficient \emph{feature generating paradigm}. In contrast with traditional gradient-based approaches that conduct optimization on all input features, the proposed method iteratively activates a group of features and solves a sequence of multiple kernel learning (MKL) subproblems of much reduced scale. To further speed up the training, we propose to solve the MKL subproblems in their primal forms through a modified accelerated proximal gradient approach. Due to such an optimization scheme, some efficient cache techniques are also developed. The feature generating paradigm can guarantee that the solution converges globally under mild conditions and achieve lower feature selection bias. Moreover, the proposed method can tackle two challenging tasks in feature selection: 1) group-based feature selection with complex structures and 2) nonlinear feature selection with explicit feature mappings. Comprehensive experiments on a wide range of synthetic and real-world datasets containing tens of million data points with $O(10^{14})$ features demonstrate the competitive performance of the proposed method over state-of-the-art feature selection methods in terms of generalization performance and training efficiency.

1. Introduction

Ultrahigh-dimensional Big Data makes wrapper-based feature selection computationally difficult, while existing sparse methods face bias, scalability, and accuracy–sparsity trade-offs. The paper proposes adaptive feature scaling with feature generation to select informative features efficiently across linear, grouped, and nonlinear settings.

  • Motivation: Ultrahigh dimensionality increases training memory and computational costs while degrading generalizability, although many features are irrelevant.Explicit mappings can expand dimensionality to O(m^2), and one cited spam-filtering task contains 16 trillion unique features.
  • Motivation: Wrapper methods can outperform filters but are much more computationally expensive, making scalability to Big Data a central challenge.SVM-RFE is also described as monotonic and suboptimal for identifying the most informative subset.
  • Limitations of Existing Methods: ℓ1-regularized methods introduce feature-selection bias and cannot simultaneously achieve sparse and unbiased solutions by changing C.Small C favors sparsity but increases empirical loss, whereas larger C reduces loss while selecting more features.
  • Proposed Approach: The paper introduces adaptive feature scaling with d ∈ [0, 1]^m and an explicit ℓ1 constraint ||d||1 ≤ B to control selected-feature sparsity.The resulting optimization is transformed into a convex semi-infinite programming problem.
  • Proposed Approach: Feature Generating Machine iteratively infers informative features and solves reduced MKL subproblems, while modified accelerated proximal gradients and cache techniques reduce training costs.The paradigm is extended to group selection with complex structures and nonlinear selection using explicit feature mappings.

2. Feature Selection Through Adaptive Feature Scaling

Adaptive feature scaling selects individual features or groups by learning bounded scaling weights under an explicit sparsity constraint. The resulting models support linear, group-structured, overlapping, and tree-structured feature selection.

  • Linear Feature Selection: The method introduces d ∈ [0, 1]^m to scale feature importance and selects feature j when d_j > 0.
  • Linear Feature Selection: The constraint ||d||1 ≤ B explicitly controls the number of selected features, with B representing the desired selection budget.
  • Optimization Formulation: Adaptive feature scaling reformulates the constrained optimization problem as a minimax problem and then as a convex semi-infinite program.
  • Group Feature Selection: Group feature selection replaces individual scaling weights with group weights, selecting all features in a group when that group is selected.
  • Complex Group Structures: Overlapping groups can be handled by duplicating shared features, and the same augmentation strategy extends to tree-structured groups.

3. Feature Generating Machine

The Feature Generating Machine solves the semi-infinite formulation by iteratively adding the most violated feature or group constraint and optimizing only the resulting active subproblem. Under solvability assumptions, this procedure converges globally.

  • Algorithm: Because most constraints are inactive when few features are relevant, the active-set strategy reduces the optimization scale.
  • Algorithm: The method alternates between inferring the most violated feature or group and solving a reduced subproblem over the active constraint set.
  • Convergence: The lower and upper objective bounds satisfy θt ≤ θ* ≤ ϕt, with θt increasing and ϕt decreasing as iterations proceed.
  • Convergence: If the algorithm terminates, its iterate is globally optimal; otherwise, the generated sequence converges to a global optimum under exact subproblem and worst-case solves.

4. Efficient Worst-Case Analysis

Worst-case analysis scores features or groups using the current dual solution and activates the B highest-scoring candidates. Incremental caching and tree structure reduce the analysis cost.

  • Feature Scoring: The worst-case problem is converted into a linear program whose solution selects the B features with the largest feature scores.
  • Group Scoring: For nonoverlapping groups, the same procedure selects groups using group scores derived from the feature scores.
  • Efficient Implementation: Incremental processing maintains a cache of the B largest scores, avoiding full sorting when groups are numerous.
  • Efficient Implementation: For balanced tree structures, the worst-case analysis costs O(n log(m) + B log(p)).

5. Efficient Subproblem Optimization

Each active-set subproblem is formulated as an MKL problem and solved in the primal using a modified accelerated proximal gradient scheme. Block updates, proximal projections, and caching reduce computational and memory costs while supporting de-biased feature selection.

  • Primal Reformulation: The active subproblem contains at most tB selected features after t iterations, making a primal solution practical when tB ≪ n.
  • Primal Reformulation: The MKL subproblem is equivalently expressed as an ℓ2,1-regularized primal problem, with dual variables recoverable for subsequent feature inference.
  • Modified APG: The modified APG method alternates block coordinate updates for weights and bias, using proximal minimization for the nonsmooth weight block.
  • Modified APG: When L_b^t differs substantially from L_t, block-coordinate updating can converge faster than batch updating.
  • Efficiency and Debiasing: The method reduces line-search computation from O(ntB) to O(nt) by scanning selected features once, while retraining supports de-biased solutions and better feature inference.

6. Nonlinear Feature Selection Through Kernels

The paper extends feature generating to nonlinear selection through kernel mappings and additive-kernel group selection, while using approximations and incremental processing to scale ultrahigh-dimensional data.

  • Kernelized feature selection: Kernelized feature generating introduces a scaling vector d to the input before applying a nonlinear mapping, yielding a semi-infinite kernel learning problem.The resulting problem can be solved by the feature-generating algorithm.
  • Additive kernels: For additive kernels, each base kernel corresponds to one feature or feature subset, so selecting kernels becomes group feature selection.The paper introduces group-wise scaling and transforms the resulting problem into a semi-infinite programming problem.
  • Additive kernels: The additive-kernel worst-case analysis can be solved exactly by choosing the B kernels with the largest s_j values.This provides an exact selection rule for the additive-kernel case.
  • Scalable optimization: Approximating base kernels with explicit features or random features reduces MKL to group feature selection, avoids storing O(n^2) kernel matrices, and enables primal optimization.The approximation addresses both memory and computational costs for large training sets.
  • Scalable optimization: For a second-order polynomial mapping with m = 10^6, the feature space has O(10^12) dimensions and requires approximately 1 TB to store w.The incremental implementation partitions data into k subsets, computes feature scores, and updates a cache c_B.

7. Connections to Related Studies

The proposed feature-generating method differs from ℓ1-based, MKL, infinite-kernel, and active-set approaches through bounded adaptive scaling, group-wise activation, and an explicit focus on reducing selection bias.

  • Adaptive feature scaling: At the optimum, d*_j = |w_j|, making an additional ℓ1 constraint on d or w ineffective because the scaling is magnitude-sensitive.The paper contrasts this with the bounded scaling used in its formulation.
  • Adaptive feature scaling: For the group case, each scaling component is bounded by 1, so imposing ||d||_1 ≤ B is meaningless because d is scale-sensitive.The group regularizer inherits the bounded scaling behavior described by Proposition 3.
  • Adaptive feature scaling: Unlike ordinary ℓ1 regularization, the proposed bounded scaling formulation separates sparsity control from over-fitting control, allowing C and B or ε_c to be adjusted independently.In ℓ1-regularized problems, the number of selected features is determined by C, so targeting a small subset can introduce solution bias.
  • Connections to MKL: Compared with ℓq-MKL for q > 1, the proposed formulation can induce sparse solutions and discard non-important kernels or features.The cited comparison states that ℓq-MKL cannot induce sparse solutions when q > 1.
  • Connections to active-set methods: FGM activates B new kernels per iteration and solves a reduced MKL problem, whereas active-set methods add one feature, kernel, or group at a time.The paper positions FGM as especially suitable when many kernels must be selected.
  • Connections to active-set methods: The method differs from existing active-set approaches by starting from an SIP reformulation and addressing solution de-biasing, which active-set methods do not investigate.Active-set methods are described as arising from Lagrangian duality and adding one active variable per iteration.

8. Experiments

The experiments evaluate FGM across linear, nonlinear, and group feature-selection tasks, comparing optimization variants with established baselines. Results show favorable accuracy, feature recovery, convergence, scalability, and efficiency, while revealing trade-offs for batch size and hyperplane shifts.

  • Experimental scope: FGM experiments cover linear feature selection, ultrahigh-dimensional nonlinear feature selection, and group feature selection.The study compares FGM variants with ℓ1-regularized methods, stochastic methods, and group-lasso solvers.
  • Convergence comparison: With ϵin = 1.0×10^-3, Inexact FGM reaches objective values similar to Exact FGM with far fewer APG iterations.A relatively large tolerance accelerates convergence without degrading performance, provided the subproblem is sufficiently optimized.
  • Optimization trade-offs: Larger B generally accelerates PROX-FGM convergence, but excessively large B may include non-informative features and reduce exact sparsity.The experiments also report that PROX-FGM and PROX-SLR can be up to 1,000 times faster than MKL-FGM with SimpleMKL.
  • Small-scale synthetic data: When more than 100 features are selected, FGM-based methods achieve better testing accuracy and recover more ground-truth features than ℓ1-methods.With more than 200 selected features, their testing accuracy also exceeds CD-SVM and CD-LR using all features.
  • Bias and efficiency: FGM reduces feature-selection bias relative to ℓ1-methods, whose testing accuracy improves substantially after debiasing retraining.PROX-FGM matches or exceeds its debiased counterpart and the debiased ℓ1-SVM.
  • Large-scale synthetic data: PROX-FGM and PROX-SLR outperform ℓ1-SVM, ℓ1-LR, and SGD-SLR in testing accuracy and recovered ground-truth features on the large-scale dataset.They also show better training efficiency than coordinate-based and SGD-based methods; FGM uses reduced subproblems with O(ntB) cost plus limited O(mn) analysis.
  • Data-density sensitivity: On denser datasets, PROX-SLR is much more efficient than ℓ1-SVM, while maintaining better best accuracy across the tested data densities.At low data density, ℓ1-SVM has comparable efficiency with PROX-SLR.

8.3 Feature Selection with Shift Consideration

Shift-aware FGM improves objective values and testing accuracy when the data require a shifted hyperplane, while offering strong real-world feature-selection performance and parameter trade-offs. Its sensitivity studies show that moderate C and B values balance accuracy, efficiency, and selection quality.

  • Shift consideration: FGM-SHIFT achieves much lower objective values than FGM on the synthetic and astro-ph datasets, while both methods perform similarly on real-sim.The real-sim result suggests that the shift term is not significant there.
  • Shift consideration: FGM-SHIFT shows significantly better testing accuracy than baseline methods on the synthetic and astro-ph datasets, whereas shift-aware methods are similar or inferior on real-sim.FGM and FGM-SHIFT outperform their corresponding l1-SVM methods across these comparisons.
  • Real-world results: Within 300 selected features, FGM variants obtain comparable or better testing accuracy than l1-methods on all real-world datasets and substantially better accuracy on five datasets.The five datasets are epsilon, real-sim, rcv1.binary, Arxiv astro-ph, and news20.
  • Real-world results: PROX-FGM and PROX-SLR show competitive training efficiency with l1-methods, and are much more efficient than LIBlinear l1-solvers on the dense epsilon dataset.SGD-SLR has comparable efficiency but much worse testing accuracy.
  • De-biasing: PROX-FGM reduces feature-selection bias: it matches or exceeds its de-biased counterpart and outperforms de-biased l1-SVM on the evaluated datasets.The comparison is reported for epsilon, real-sim, and rcv1.
  • Parameter sensitivity: C balances underfitting, overfitting, and selection bias: very small values perform worse, while C = 500 performs much worse than C = 5 and C = 50 on astro-ph.The study tests C ∈ {0.5, 5, 50, 500}; the paper suggests choosing C in [1, 100].
  • Parameter sensitivity: FGM with B = 40 is approximately 200 times faster than FGM with B = 2, but B = 400 sharply degrades testing accuracy; suitable B values such as B ≤100 improve efficiency while maintaining generalization.Active-set methods correspond to the special case B = 1.

8.5 Ultrahigh Dimensional Feature Selection via Nonlinear Feature Mapping

Polynomial feature mappings enable nonlinear feature selection, but their expanded representations create severe computational and storage demands. FGM addresses these demands through smaller optimization problems while retaining competitive accuracy and supporting group-based selection with complex feature expansions.

  • Nonlinear feature mapping: PROX-PFGM is much more efficient than l1-PSVM on medium-dimensional polynomial-mapping problems and remains feasible on the ultrahigh-dimensional kddb dataset.l1-PSVM requires more than 1 TB to store a dense w on kddb, whereas PROX-PFGM finishes training within 1000 seconds.
  • Nonlinear feature mapping: Polynomial mapping substantially improves testing accuracy on mnist38, but provides no significant improvement on real-sim and kddb, likely because those datasets are linearly separable.The reported comparison concerns polynomial mappings versus linear methods.
  • Group feature selection: FGM achieves better testing accuracy than FISTA, BCD, and UFO-MKL on the synthetic group-selection experiment and is generally more efficient than FISTA and BCD.The experiment reports accuracy, training time, and recovered ground-truth groups within 150 selected groups.
  • Group feature selection: On real-world group-selection tasks, FGM and active-set methods achieve superior testing accuracy, while FGM is much more efficient than the active-set method.The groups are produced through explicit kernel feature expansions.
  • Group feature selection: Explicitly storing expanded features becomes infeasible for ultrahigh-dimensional Big Data, whereas FGM handles the problem through a sequence of small-scale optimization problems.FISTA and BCD cannot operate in this setting because they require explicit data representations.

9. Conclusions

The paper introduces adaptive feature scaling and Feature Generating Machine (FGM) for scalable ultrahigh-dimensional feature selection, with proved global convergence and reduced memory demands. Experiments report superior testing accuracy and training efficiency, while the demonstrated scale reaches O(10^14) features and O(10^7) training examples.

  • Adaptive feature scaling: FGM introduces adaptive feature scaling with an ℓ1-norm constraint to control feature-selection sparsity.The scaling vector d ∈ [0, 1]^p is constrained by ||d||1 ≤ B, where B represents the least number of selected features.
  • Feature Generating Machine: FGM transforms the resulting non-convex problem into a convex SIP problem and iteratively solves reduced MKL subproblems after adding informative features or groups.The feature-generating procedure has a proved global convergence guarantee.
  • Scalability and bias: FGM reduces feature-selection bias relative to ℓ1-norm methods by separately controlling model complexity and sparsity.Its reduced subproblems involve only a small subset of features or kernels, making the approach suitable for ultrahigh-dimensional selection.
  • Scalability and bias: FGM's primal modified APG optimization and cache techniques reduce memory demands for MKL tasks with many kernels.The method avoids storing all kernels with explicit feature expansions, enabling previously intractable tasks to become feasible.
  • Empirical evaluation: Extensive synthetic and real-world experiments show superior testing accuracy and training efficiency compared with baseline methods.The experiments cover linear and group feature-selection tasks.
  • Empirical evaluation: FGM tackles Big Data problems with O(10^7) training examples and O(10^14) features.The authors identify SGD-based subproblem optimization for future work on larger datasets with billion- or trillion-scale sample counts.

Appendix A. Proof of Theorem 3

This appendix establishes the dual formulations used in Theorem 3 by expressing the relevant constrained optimization problems through Lagrangian duality and KKT conditions. The resulting forms connect primal and dual formulations for the considered losses.

  • Dual formulation: The proof constructs a dual formulation by introducing Lagrangian variables and applying KKT conditions to the constrained problem.The feasible dual variables include α with α_i ≥ 0 and an equality constraint involving α_i y_i.
  • Squared hinge loss: For the squared hinge loss, substituting the KKT relations yields a 2,1-regularized optimization problem.The derivation proceeds by transforming the primal formulation into the corresponding dual-constrained form.
  • Primal-dual connection: The proof identifies the transformed constraints as an instance of problem (22), establishing the connection between the primal and dual formulations.This connection completes the proof of the theorem.
  • Logistic loss: For logistic loss, the same dual-derivation strategy uses Lagrangian variables and KKT conditions to obtain the corresponding transformed problem.The dual variables include α, γ, ζ_t, and t, and the recovered α variables are expressed through ξ_i.

Appendix B. Proof of Theorem 4

This appendix proves the inequalities underlying the accelerated proximal-gradient analysis by defining quadratic surrogate functions and applying convexity, subgradient, and line-search relations. The argument culminates in the required convergence inequality.

  • Surrogate construction: The proof defines Qτb as a quadratic surrogate for the smooth component with respect to b.The surrogate combines P(v, v̄_b), its gradient term, and a τ_b-scaled quadratic term.
  • Proximal updates: The proximal mappings Sτ and Sτb minimize the corresponding surrogate problems for ω and b.Lemma 5 characterizes Sτ through a subgradient condition, while Lemma 6 uses the separate updates in ω and b.
  • Line-search bound: The line-search relation bounds the updated objective by the surrogate values for the separate ω and b updates.This establishes the inequality used in the subsequent convergence argument.
  • Convexity inequalities: Convexity of P and Ω supplies lower bounds involving gradients, subgradients, and the proximal point Sτ(u, v).These inequalities combine the smooth and nonsmooth components of the objective.
  • Convergence argument: Applying the preceding inequalities and the squared-norm identity yields the final relation required by the theorem proof.The proof then concludes after summing the relevant bounds and invoking Lemma 7.

Appendix C: Linear Convergence of Algorithm 4 for the Logistic Loss

The appendix analyzes Algorithm 4 for logistic loss under a Restricted Eigenvalue Condition. When the lower restricted eigenvalue is bounded below by a positive constant, the method attains linear convergence.

  • Algorithmic reduction: With k = 1, Algorithm 4 reduces to the proximal gradient method for logistic loss.The convergence analysis invokes the Restricted Eigenvalue Condition on the design matrix X.
  • Linear convergence: The logistic loss is strongly convex when γ−(X, tB) > 0, supporting the linear convergence result.The argument also uses an upper bound on the Hessian over a compact set through γ+(X, κ).

Appendix D: Proof of Proposition 3

The proof establishes the proposition by contradiction and verifies optimality through feasibility and KKT conditions. It concludes that the constructed solution satisfies the required bounds and is optimal.

  • The contradiction argument perturbs a minimizer with a zero-weight coordinate to obtain another feasible point with a lower objective, ruling out that case.The construction preserves feasibility before contradicting the assumed minimality.
  • A positive-weight coordinate must have a strictly positive scaling variable; otherwise the objective would not attain a finite minimum.
  • When the support size is at most B, the argument holds trivially; otherwise, the proof restricts attention to the first κ positive-weight coordinates.
  • The restricted minimization problem is convex, so its optimality is characterized using KKT conditions and dual variables for the budget and bound constraints.The dual variables correspond to the constraints on the sum of d_i, positivity, and the upper bound d_i ≤ 1.
  • If κ > B, the budget constraint forces at least one d_i below 1, which implies a nonzero budget multiplier under the KKT conditions.
  • Under ∥w∥1/max{|wi|} ≥ B, setting ν_i = 0 yields γ = ∥w∥1/B and d_i = B|wi|/∥w∥1, satisfying the KKT conditions and proving optimality.The construction also satisfies d_i ≤ 1 because γ ≥ max{|wi|}.
Loading 1209.5260v2…