Parametric Dual Maximization for Non-Convex Learning Problems

Yuxun Zhou, Zhaoyi Kang, Costas J. SpanosAAAI 2017 · DOI

TL;DR

This paper introduces Parametric Dual Maximization (PDM), a novel algorithm that efficiently finds global optima for a class of non-convex learning problems, a significant improvement over existing methods that often get stuck in local minima. PDM reformulates these problems as convex maximization problems and leverages parametric analysis to achieve global optimality with user-defined approximation levels.

What Problem Does This Paper Address?

Many modern machine learning tasks, such as semi-supervised learning, learning with hidden structures, and robust learning, lead to non-convex optimization problems. Traditional Support Vector Machines (SVMs) are convex and well-behaved, but their extensions to handle more complex data structures introduce non-convexity. This non-convexity makes it difficult to find the globally optimal solution, often leading to suboptimal performance and hindering scalable deployment. Existing approaches like alternating optimization (AO), concave-convex procedure (CCCP), and stochastic gradient descent (SGD) typically converge to local minima, which can be highly sensitive to initialization. While methods like Branch and Bound (B&B) can find global optima, they suffer from poor scalability due to combinatorial search. This paper aims to bridge this gap by providing an efficient method for finding global optima in these non-convex learning scenarios.

Methods

The core of the proposed method, Parametric Dual Maximization (PDM), lies in a two-pronged approach:

  1. Parametric Analysis for Convex Reformulation: The authors first show that a class of non-convex learning problems, characterized by jointly optimizing regularized hinge loss and auxiliary variables, can be reformulated. Through parametric analysis, they demonstrate that these problems are equivalent to a non-smooth convex maximization problem. This is a key insight, transforming a difficult non-convex problem into a more tractable convex one.
  2. Global Optimality Condition and Algorithm: Building on the convex reformulation, PDM utilizes a necessary and sufficient condition for global optimality. This condition allows the algorithm to efficiently approach the global optimum. The algorithm iteratively refines a candidate solution by exploring "critical regions" and using a series of linear programs to find an improved direction. An "approximate level set" technique is employed to manage the complexity of calculating the exact level set of the objective function.

Datasets

The paper evaluates PDM on several datasets for two main applications:

  • Semi-Supervised SVM (S³VM):
    • 2moons (D1)
    • Coil (D2)
    • Robot (D3)
    • 2spiral (D4)
  • Latent SVM (LSVM):
    • Vowel (D5)
    • Music (D6)
    • Bank (D7)
    • Wave (D8)

These datasets vary in size and dimensionality, with some requiring a simulator for data generation (D4 and D8). The paper notes that for LSVM, a latent data structure is assumed, with only grouped binary labels known.

Key Insights and Ideas

  • Non-convex to Convex Equivalence: The most significant insight is the demonstration that a broad class of non-convex learning problems can be elegantly reformulated as non-smooth convex maximization problems through parametric analysis. This opens up new avenues for optimization.
  • Parametric Analysis as a Tool: The paper highlights the power of parametric analysis not just for solving the immediate problem but also as a reusable technique for other machine learning tasks, such as calculating solution paths.
  • Global Optimality Condition: The development of a practical global optimality condition for non-smooth convex maximization is crucial. This condition provides a clear criterion for assessing progress and guiding the search for the optimum.
  • Approximation for Tractability: The use of an "approximate level set" is a clever way to handle the computational challenges of exact level set calculations, allowing the algorithm to function effectively in practice.
  • Improved Generalization: The results strongly suggest that global optima lead to significantly better generalization performance compared to local optima, a well-known but often difficult-to-achieve benefit.

Key Results

  • Optimization Performance: PDM consistently achieves normalized objective values closer to the optimal (often 1.00, indicating near-optimal or optimal solutions) compared to other methods like Gradient Descent (GD), CCCP, and Alternating Optimization (AO). For instance, on the 2moons dataset for S³VM, PDM achieved an objective value of 1.00, while GD was 2.39 and CCCP was 2.82.
  • Generalization Performance: PDM demonstrates superior generalization performance, achieving significantly lower error rates. On datasets where methods like Branch and Bound (BB) failed or were infeasible due to scale, PDM provided near-optimal solutions with excellent accuracy. For example, on the 2moons dataset (D1), PDM achieved an error rate of 0.2%, while GD was 51.4% and CCCP was 60.0%.
  • Scalability: While PDM's running time is longer than local optimization methods, it remains scalable for large datasets (e.g., D4 and D8 with 10⁵ samples), unlike Branch and Bound which becomes computationally prohibitive.
  • Convergence: The PDM algorithm is shown to converge to an approximate maximizer in a finite number of steps, with the approximation level controlled by a user-specified parameter 'm'.

Limitations and Future Work

  • Computational Cost: While PDM is scalable, its running time is longer than local optimization methods. The paper suggests that reusing explored critical regions can mitigate this.
  • Approximation Degree 'm': The choice of the approximation degree 'm' involves a tradeoff between accuracy and computational cost. The paper suggests a range for 'm' (0.1 to 0.2 of the parameter dimension) as a good balance.
  • Future Work: The paper mentions that further acceleration can be achieved by "enlarging" critical regions, which is discussed in the supplementary material. The authors also suggest that the parametric analysis techniques developed could be reused for other tasks, such as solution path calculation.

Summary updated

BibTeX
@inproceedings{zhou2017parametric,
  author = {Yuxun Zhou and Zhaoyi Kang and Costas J. Spanos},
  title = {{Parametric Dual Maximization for Non-Convex Learning Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10781},
}
Figure