A Scalable Frank-Wolfe-Based Algorithm for the Max-Cut SDP
Authors: Chi Bach Pham, Wynita Griggs, James Saunderson
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In this section, we summarize our computational results from applying Algorithm 2 with C = 1/4LG where LG is the Laplacian of an (unweighted) graph. In all cases, C is diagonally dominant and we set z = 2 diag(C) and αi = (2tr(C))1/2/Cii for all i. For the examples we tried, we found that diagonal shifting did not improve the practical performance. The algorithm was implemented using Julia 1.7.1. All computations were performed on a machine with 4 cores, 8 2.5GHz-CPUs and 16GB of RAM. In all experiments, the starting vector x(0) for Algorithm 2 is given as x(0) = 1/m diag(C) where m is the number of edges. We stop when RFWgap(x(t)) := (f(x(t)),q(t) - x(t)) / f(x(t)) is small enough, where f(x(t)) = infα y>0 Pn i=1 φ(x(t)i, yi) and RFWgap(x(t)) is an easily computed bound on the relative error. |
| Researcher Affiliation | Academia | 1Department of Electrical and Computer Systems Engineering, Monash University, Australia. 2Department of Civil Engineering, Monash University, Australia. Correspondence to: James Saunderson <james.saunderson@monash.edu>. |
| Pseudocode | Yes | Algorithm 1 Frank-Wolfe algorithm; Algorithm 2 Frank-Wolfe with sampling (x, W, s) = FW-sampling(f, C, ϵ, δ, x(0)); Algorithm 3 LMO for SC with additive error δ (q, v) = FACTORED-LMO(y, SC, δ) |
| Open Source Code | No | The paper does not provide an explicit statement about releasing its own source code or a link to a repository for the methodology described. It mentions using 'Julia implementation, Arnoldi Method.jl' but this refers to a third-party tool. |
| Open Datasets | Yes | For our first experiment, we use unweighted graphs from the Gset dataset (gse). To display the results concisely, we grouped the graphs into groups consisting of graphs with similar properties (see Table 1). We tested our method with both the scheduled step size γ(t) = 2/(t+2) and a line search. We stopped when RFWgap < 10^-2.5. UF sparse matrix collection: Gset group. https://www.cise.ufl.edu/research/sparse/matrices/Gset/index.html. Accessed: 2023-01-05. |
| Dataset Splits | No | The paper mentions using the Gset dataset and comparing relative errors but does not specify the training, validation, or test split percentages or methodology for its experiments. It doesn't indicate a split like '80/10/10' or '5-fold cross-validation'. |
| Hardware Specification | Yes | All computations were performed on a machine with 4 cores, 8 2.5GHz-CPUs and 16GB of RAM. |
| Software Dependencies | Yes | The algorithm was implemented using Julia 1.7.1. All computations were performed on a machine with 4 cores, 8 2.5GHz-CPUs and 16GB of RAM. In all experiments, the starting vector x(0) for Algorithm 2 is given as x(0) = 1/m diag(C) where m is the number of edges. We stop when RFWgap(x(t)) := (f(x(t)),q(t) - x(t)) / f(x(t)) is small enough, where f(x(t)) = infα y>0 Pn i=1 φ(x(t)i, yi) and RFWgap(x(t)) is an easily computed bound on the relative error. For the LMO subroutine, in practice we use a Julia implementation, Arnoldi Method.jl, of the Krylov-Schur method (Stewart, 2002). |
| Experiment Setup | Yes | In all experiments, the starting vector x(0) for Algorithm 2 is given as x(0) = 1/m diag(C) where m is the number of edges. We stop when RFWgap(x(t)) := (f(x(t)),q(t) - x(t)) / f(x(t)) is small enough, where f(x(t)) = infα y>0 Pn i=1 φ(x(t)i, yi) and RFWgap(x(t)) is an easily computed bound on the relative error. For the LMO subroutine, in practice we use a Julia implementation, Arnoldi Method.jl, of the Krylov-Schur method (Stewart, 2002). The method terminates when Ax - xλ^2 < tol |λ|, where tol is the tolerance parameter. We initially set tol = 1 and reduce it by a factor of 10^-0.25 every time the RFWgap decreases by a factor of 10^-0.25, while ensuring tol ≤ RFWgap. We tested our method with both the scheduled step size γ(t) = 2/(t+2) and a line search. We stopped when RFWgap < 10^-2.5. |