On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems
Authors: Michael Muehlebach, Michael I. Jordan
JMLR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our main goal in the current paper is to provide a theoretical foundation to support such a claim. We also present results from a preliminary set of numerical experiments, which include, for example, randomly generated high-dimensional quadratic programs. Comparing the new methods to the interior point solver CVXOPT of Andersen et al. (2011), we find that the complexity of the new methods scales roughly with n2 (where n is the problem dimension), whereas the complexity of the interior point solver scales with n3. When n is large, this may lead to speedups of several orders of magnitude. The remainder of the article is concerned with proving Proposition 2 and Proposition 3, providing context for both algorithms, discussing a particular implementation of Algorithm 1, and illustrating the algorithms with numerical examples. |
| Researcher Affiliation | Academia | Michael Muehlebach EMAIL Learning and Dynamical Systems Group Max Planck Institute for Intelligent Systems 72076 T ubingen, Germany Michael I. Jordan EMAIL Department of Electrical Engineering and Computer Sciences Department of Statistics University of California Berkeley, CA 94720, USA |
| Pseudocode | Yes | Algorithm 1 Implementation of the gradient descent scheme (8). ... Algorithm 2 Implementation of the gradient descent scheme (8). |
| Open Source Code | Yes | The exact implementation in Python and C++ is available as supplementary material. |
| Open Datasets | No | We generate quadratic programs of the following form: ... We generated the training samples in the following way: The points with label +1 were generated in polar coordinates... The paper describes how it generated or defined its own datasets for experiments and does not provide links or citations to publicly available datasets, nor does it state that its generated datasets are publicly available. |
| Dataset Splits | No | The paper describes how the datasets are generated or defined for the experiments (e.g., "randomly generated quadratic programs," "training samples in the following way"), but it does not specify any training/test/validation splits for these datasets or reference standard splits. |
| Hardware Specification | Yes | The experiments were conducted on a Dell Precision Tower 3620 that runs Ubuntu 20.04LTS and is equipped with an Intel Core i7-6700 processor (8x3.4GHz) and 64GB of random access memory. |
| Software Dependencies | Yes | The experiments were conducted on a Dell Precision Tower 3620 that runs Ubuntu 20.04LTS and is equipped with an Intel Core i7-6700 processor (8x3.4GHz) and 64GB of random access memory. Algorithm 2 is implemented in C++ and we use pybind11 (Jakob et al., 2017) as a Python interface. We compare Algorithm 2 with the state-of-the-art interior-point solver CVXOPT (Andersen et al., 2011) for larger problem instances. We also show comparisons to projected gradients and Frank-Wolfe, where the projections and Frank-Wolfe updates are computed with the standard optimization library in Python s scientific computing library (scipy.optimize, Virtanen et al., 2020). |
| Experiment Setup | Yes | Table 1: Parameters of Algorithm 2 used for the experiments, where L and µ refer to the smoothness and strong convexity constants of f. The variable n denotes the number of chain links of the catenary, as defined in Section 8.4. |