Summary
This paper introduces a novel optimization problem termed Difference of Max-Structured Weakly Convex Functions (DMax). The DMax problem extends traditional frameworks such as difference-of-weakly-convex (DWC) optimization and weakly-convex-strongly-concave (WCSC) min-max optimization, which are widely utilized in the machine learning community.
Using a Moreau envelope smoothing technique, the authors propose a stochastic algorithm called SMAG for optimizing DMax in non-smooth settings. This approach not only addresses the DMax problem but also applies to DWC and non-smooth WCSC min-max optimization scenarios, demonstrating comparable convergence rates.
Experimental results validate the efficacy of their algorithms across various applications, including Positive-Unlabeled (PU) Learning and partial Area Under the Curve (AUC) optimization with an adversarial fairness regularizer.
Strengths
**Originality:**
The paper introduces a new optimization problem termed Difference of Max-Structured Weakly Convex Functions (DMax), which extends existing frameworks like difference-of-weakly-convex (DWC) optimization and weakly-convex-strongly-concave (WCSC) min-max optimization. This extension demonstrates a significant level of originality in problem formulation within the field of optimization. By addressing a broader class of problems under the DMax framework, the paper contributes novel insights and methodologies that enrich the theoretical foundations of optimization in machine learning and related fields.
**Quality:**
The paper maintains high-quality standards across various aspects. It rigorously establishes the theoretical foundations of the DMax problem and proposes a Moreau envelope smoothing technique for optimization in non-smooth settings. The SMAG algorithm introduced is methodically developed and supported by well-defined lemmas and references, ensuring robustness and reliability in the proposed approach, though I don't check the proofs in detail.
Furthermore, the experimental validation on applications such as Positive-Unlabeled Learning and partial AUC optimization with adversarial fairness regularization underscores the practical relevance and effectiveness of the proposed methods.
**Clarity:**
The clarity of the paper is a notable strength. It effectively communicates complex concepts and methodologies in a clear and accessible manner, making it understandable even for readers with limited expertise in the specific problem domain. The intuitive presentation of algorithms and key steps, coupled with clear explanations of referenced lemmas, enhances readability without sacrificing depth. This clarity not only facilitates comprehension but also promotes transparency in the theoretical derivations and experimental procedures, thereby bolstering the paper's overall impact.
**Significance:**
By addressing challenging optimization problems and providing practical algorithms validated in real-world scenarios, the paper significantly advances both theoretical understanding and practical applications in machine learning optimization.
Weaknesses
**Problem Statement and Novelty:**
The paper introduces a new problem that extends traditional frameworks such as difference-of-weakly-convex (DWC) optimization and weakly-convex-strongly-concave (WCSC) min-max optimization, presenting the SMAG algorithm as a solution. However, the paper could benefit from clearer justification of how this generalization represents a significant departure from incremental advancements. This clarity is pivotal for establishing the theoretical contribution within a novel setting.
**Complexity Analysis:**
Upon examining the complexity results, it is apparent that in non-convex, non-smooth min-max problems, SMAG demonstrates complexity similar to Epoch-GDA under comparable assumptions (Table 2). This finding raises significant concerns about the broader implications for WCSC min-max optimization, particularly considering the emphasis on complexity as a contribution (Line 59). A clearer explanation is needed on how SMAG surpasses existing complexities in this domain, beyond the practical advantage of a single-loop method for tuning, to strengthen the paper's impact solely from a complexity perspective.
**Algorithmic Technique:**
The proof and algorithmic technique employed in this study resemble SBCD, utilizing the Moreau envelope to transform non-smooth problems into smooth ones, thereby enhancing accessibility. Hence, it is crucial to clearly delineate why SMAG achieves superior complexity results compared to SBCD or to identify any overlooked aspects that may explain this discrepancy.
I welcome further discussion on these points to ensure a comprehensive evaluation. Thanks!
Questions
In the experiments section, the authors employ a linear classification model with hinge loss (Line 271). However, this setting appears to be a smooth one, potentially limiting the demonstration of the benefits of the authors' method in non-smooth DWC problems, despite SMAG showing superiority over other methods.
Regarding the large variance in training curves observed, such as in FER 2013 (Figure 1), it raises questions about the stability and robustness of the method in practical applications. To enhance confidence in the results, I suggest exploring parameter tuning to achieve more stable and convincing outcomes.
Limitations
The paper is theoretical, and I believe there is no need to confirm societal impact.