Summary
This paper handles the problems of non-smooth weakly-convex compositional optimization. The first problem, referred to as FCCO (Finite-sum coupled compositional minimization), is given by
$$ \min_{w \in \mathbb{R}^d} F(w) \triangleq \frac{1}{n} \sum_{i=1}^n f_i(\mathbb{E}_{\xi\sim \mathcal{D}_i}[g_i(w; \xi)])$$
The second problem, referred to as TCCO (Tri-level coupled compositional minimization), is given by,
$$ \min_{w \in \mathbb{R}^d} F(w) \triangleq \frac{1}{n_1} \sum_{i=1}^{n_1} f_i\left(\frac{1}{n_2}\sum_{j=1}^{n_2} g_i( \underset{\xi \sim \mathcal{D}{i,j}}{\mathbb{E}} [h_{i,j}(w; \xi)])\right)$$
Here, the outer functions $f_i$ and $g_i$ are Lipschitz and weakly convex which has not been considered by previous works and significantly complicates the analysis.
The authors propose two algorithms, SONX and SONT for the two problems respectively. For the first problem, FCCO, $u_{i,t}$ are the estimates of $g_i(w_t)$, $\forall i \in \{1,2,\ldots, n\}$, which are required for an unbiased estimate of the the complete function $F(w)$. In each step, a batch $B$ of coordinates from $\{1,2,\ldots, n\}$ is sampled and only the estimates in this batch, $u_{i,t}, i\in B$, are updated using a Variance-reduced estimator. Using the estimates, a single gradient step is computed for $w_t$. The estimator has been adapted from [1].
As the functions are weakly convex, the authors show convergence to an $\epsilon$-stationary point of the Moreau envelope of $F$ at a rate of $\mathcal{O}(\epsilon^{-6})$.
The authors show that both problems can be mapped exactly to Two-way partial AUC (TPAUC) maximization of a parametrized network, even deep networks, with the TCCO problem mapping to a multi-instance learning version. TPAUC is the area under the ROC curve when False Positive rate $\leq \beta$ and True Positive Rate $\geq \alpha$. Over a set of medical datasets, the authors show that SONX and SONT out-perform baselines for TPAUC maximization as the baselines use poor approximations of TPAUC.
**References**
1. Jiang et al 2022. Multi-block-single-probe variance reduced estimator for coupled compositional optimization
Strengths
- **Easy to Implement**: The algorithms are single-loop and use moderately sized batches which makes it easy to implement. Also, the algorithms can also be parallelized over the coordinates $i$.
- **Better Rates**: In addition to being easy to implement, the algorithms achieve the best possible rates for this class of functions. Existing works obtain similar or worse rates under an easier problem setting or with multiple loops or using large batches.
- **Mapping to TPAUC**: The authors describe the TPAUC problem comprehensively and show the exact mapping with the two optimization problems.
- **Detailed presentation**: The convergence analysis, the mapping to TPAUC and the related works are very detailed which helps in understanding the paper.
Weaknesses
- **Experimental and Theoretical Baselines do not match**: For theory, the baselines for comparisons are algorithms for simpler problem settings, for instance with smoothness or convexity. For experiments, the baselines for TPAUC maximization are used which do not match the theoretical baselines. It is unclear, if some theoretical baseline can be applied to TPAUC and perform better. This should not be the case ideally but it has not been verified.
Questions
- Is there a lower bound for this problem setting, which can be used to verify if the rates are optimal and cannot be improved?
- Why is the dependence on $\frac{n_1}{B_1}$ worse for SONT as compared to SONT?
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Described in Weaknesses