Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Clustering is semidefinitely not that hard: Nonnegative SDP for manifold disentangling
Authors: Mariano Tepper, Anirvan M. Sengupta, Dmitri Chklovskii
JMLR 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 3. Analyzing data manifolds with NOMAD: Experimental results In the previous section, we showed that NOMAD recovers the data manifold in an idealized 2D ring dataset. Here, we extend this observation numerically to more complex datasets for which analytical form of the transformation that diagonalizes Q (nor D) is not known, see figs. 1, 5 and 7. We visualize the solution Q by embedding it in a low-dimensional space. While our goal is not dimensionality reduction, we learn the data manifold with NOMAD, and use standard spectral dimensionality reduction to visualize the results. 5.4. Experimental analysis Throughout the iterations of Alg. 2, P Pk 1, see Eq. (18). Thus, we only need to keep track of the constraint Q = P + En 0 and of the value of the objective Tr (DP). We illustrate with two typical examples the empirical convergence of these values in Fig. 13. the convergence the objective value is clearly superlinear, while we observe a linear convergence for the nonnegativity constraint. Accelerating the latter rate is an interesting line of future research. |
| Researcher Affiliation | Academia | Mariano Tepper EMAIL Flatiron Institute, Simons Foundation, NY, USA Anirvan M. Sengupta EMAIL Dept. of Physics and Astronomy, Rutgers University, NJ, USA Flatiron Institute, Simons Foundation, NY, USA Dmitri Chklovskii EMAIL Flatiron Institute, Simons Foundation, NY, USA NYU Langone Medical Center, New York, NY |
| Pseudocode | Yes | 3.1. Manifold disentangling with multi-layer NOMAD The recursive application of NOMAD, with successively decreasing values of K, enhances its manifold-disentangling capabilities. The pseudocode is as follows: Algorithm 1: Conditional gradient algorithm for SDPs with an orthogonality constraint Algorithm 2: Conditional gradient algorithm for NOMAD |
| Open Source Code | Yes | Our software is publicly available at https://github. com/simonsfoundation/sdp_kmeans. |
| Open Datasets | Yes | 3. Analyzing data manifolds with NOMAD: Experimental results ...The trefoil knot in Fig. 1(a) is a 1D manifold in 3D... We also present examples using real-world high-dimensional datasets, recovering in every case structures of interest, see Fig. 6. In figs. 6(a) to 6(c), NOMAD respectively uncovers the camera rotation, the orientation of the lighting source, and specific handwriting features. (b) Yale Faces (K = 16) (c) MNIST digits (K = 16) |
| Dataset Splits | No | The paper does not explicitly provide details about training/test/validation dataset splits (e.g., percentages, sample counts, or predefined split references). It describes the datasets used and modifications like adding noise, but not how they were partitioned for experimental evaluation or reproduction. |
| Hardware Specification | Yes | It is important to point out that, in theory, the speed difference grows significantly larger. This is hard to show in practice as standard solvers either run out of memory very quickly (SCS) or are implemented to time out for big instances (SDPNAL+); the proposed solver has a much more efficient use of memory. We highlight the extended computational capabilities of the proposed conditional gradient method with an example that cannot be handled by standard SDP solvers. We use as input the 9603 9603 Gramian formed by all (vectorized) images of the digit zero in MNIST. The proposed algorithm is able to compute a solution to NOMAD with ease for a problem size about 100 times larger than the upper size limit for standard solvers. In the 2D embedding of the solution (see Sec. 3 for details about its computation), shown in Fig. 16, we can clearly see that the images are organized by their intrinsic characteristics (elongation and rotation). Fig. 15...in our desktop with 128GB of RAM... |
| Software Dependencies | No | In Fig. 15, we present the speed comparison of computing NOMAD with three different methods: two state-of-the-art SDP solvers, SCS (O Donoghue et al., 2016b) and SDPNAL+ (Yang et al., 2015), the low-rank Burer-Monteiro solver (discussed in Sec. 4), and the proposed conditional gradient method. The nonconvex solver is much faster than the convex ones. Unfortunately, it may yield different results, see Fig. 12, and may not converge to the global maximum. The conditional gradient algorithm proposed in this paper is much faster than SCS and SDPNAL+ (about three times faster for n = 103) but guarantees converging to the global optimum. Additionally, the proposed algorithm handles large problems seamlessly: in our desktop with 128GB of RAM, SCS (running under CVXPY) runs out of memory with instances larger than n = 1200) while SDPNAL+ times out before converging for instances larger than n = 4000. |
| Experiment Setup | Yes | Algorithm 2: Conditional gradient algorithm for NOMAD input : matrix D, scale parameter k. output : solution Q to NOMAD. 1 Initialize P0 = 0; Γ 0; γ = 1; 2 for t = 1, . . . , do 3 for tinner = 1, . . . , Ninner do 4 Let g(P, Γ) = D + Γ + γ [P + En] ; 5 Let A = (I 1 n11 ) g(P, Γ)(I 1 6 Let v be the smallest algebraic eigenvector of A, such that v 1 = 0; 7 H (K 1)vv ; 8 α 2/(t + tinner + 2); 9 P (1 α)P + αH; 10 Γ [Γ + τ (P + En)] ; 11 if converged then break ; 12 Q P + En When using the method of multipliers, it is often not necessary (nor desirable) to solve the inner problem to a high precision (Goldstein and Osher, 2009). In our implementation we set Ninner = 10. |