Three Operator Splitting with a Nonconvex Loss Function
Authors: Alp Yurtsever, Varun Mangalick, Suvrit Sra
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems. This section demonstrates the empirical performance of TOS on the quadratic assignment problem (QAP). Figure 1 compares the empirical performance of TOS and FW for solving (23) with chr12a and esc128 datasets from QAPLIB. |
| Researcher Affiliation | Academia | Alp Yurtsever 1 Varun Mangalick 1 Suvrit Sra 1 1Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. Correspondence to: Alp Yurtsever <alpy@mit.edu>. |
| Pseudocode | Yes | Algorithm 1 Three Operator Splitting (TOS) Input: Initial point y1 Rn, step-size sequence {γt}T t=1 for t = 1, 2, . . . , T do zt = proxγtg(yt) xt = proxγth(2zt yt γt f(zt)) yt+1 = yt zt + xt end for Return: Draw τ uniformly at random from {1, 2, . . . , T} and output zτ. |
| Open Source Code | Yes | The source code is available online1. 1https://github.com/alpyurtsever/Nonconvex TOS |
| Open Datasets | Yes | Finally, we illustrate the effectiveness of the proposed method through numerical experiments on quadratic assignment problems. We evaluate TOS on the quadratic assignment problem using the well-known QAPLIB benchmark library (Burkard et al., 1997). |
| Dataset Splits | No | The paper evaluates the method on specific problem instances from the QAPLIB benchmark library, which are not typically split into training/validation/test sets in the manner of machine learning datasets. Therefore, it does not provide details on such dataset splits. |
| Hardware Specification | Yes | Experiments are performed in MATLAB R2018a on a Mac Book Pro Late 2013 with 2.6 GHz Quad-Core Intel Core i7 CPU and 16 GB 1600 MHz DDR3 memory. |
| Software Dependencies | Yes | Experiments are performed in MATLAB R2018a on a Mac Book Pro Late 2013 with 2.6 GHz Quad-Core Intel Core i7 CPU and 16 GB 1600 MHz DDR3 memory. For solving LAP, we employ an efficient implementation of the Hungarian method (Ciao, 2011). |
| Experiment Setup | Yes | For TOS (Algorithm 1), we output the last iterate instead of the random variable xτ. We use γt = 1/Lf step-size (Lf denotes the smoothness constant of f) instead of the more conservative step-size that our theory suggests (which depends on T). We start both methods from the same initial point y1. We construct y1 by projecting a random matrix with i.i.d. standard Gaussian entries onto the Birkhoff polytope via 1000 iterations of the alternating projections method. |