Black-box Optimization with a Politician
Authors: Sebastien Bubeck, Yin Tat Lee
ICML 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We demonstrate empirically that our new technique compares favorably with state of the art algorithms (such as BFGS). |
| Researcher Affiliation | Collaboration | S ebastien Bubeck SEBUBECK@MICROSOFT.COM Microsoft Research Yin-Tat Lee YINTAT@MIT.EDU MIT |
| Pseudocode | Yes | Algorithm 1: Geometric Politician, Algorithm 2: +, Algorithm 3: Gonzaga-Karas s variant of Accelerated Gradient Descent, Algorithm 4: BFGS |
| Open Source Code | No | The paper references third-party MATLAB libraries (min Func, TFOCS) used for comparison, providing a URL for minFunc. However, it does not provide any specific access information (e.g., repository link, explicit release statement) for the authors' own implementation code of the 'geometric politician' or 'BFGS+'. |
| Open Datasets | Yes | We consider the binary classification problem on the datasets from (Chang and Lin, 2011). More precisely for a given algorithm we plot x [1, 10] versus the fraction of datasets that the algorithm can solve (up to a certain prespecified accuracy) in a number of iterations which is at most x times the number of iterations of the best algorithm for this dataset. Figure 3 shows the case t = 1 with the targeted accuracy 10 6; Figure 4 shows the case t = 10 4 with the targeted accuracy 10 3. We see that TFOCS is slower than SD for many problems, this is simply because SD uses the line search while TFOCS does not, and this makes a huge difference for simple problems. Among algorithms taking O(n) time per iteration, CG and Geo perform the best, while for the O(nk) algorithms we see that BFGS, BFGS+ and GK+ perform the best. The gap in performance is particularly striking in the non-smooth case where BFGS+ is the fastest algorithm on almost all problems and all other methods (except GK+) are lagging far behind (for 20% of the problems all other methods take 10 times more iterations than BFGS+ and GK+). |
| Dataset Splits | No | The paper refers to using 'LIBSVM datasets' and 'problems in the LIBSVM datasets' for empirical evaluation. While these are public datasets, the paper does not specify how these datasets were split into training, validation, and test sets (e.g., percentages, exact counts, or a reference to a standard split methodology for reproducibility). |
| Hardware Specification | No | The paper does not provide any specific details about the hardware (e.g., GPU models, CPU types, memory) used to run the experiments. It focuses on algorithmic complexity but omits hardware specifications. |
| Software Dependencies | No | The paper mentions using 'min Func (Schmidt, 2012)' and 'TFOCS (Becker et al., 2011)', which are MATLAB libraries. However, it does not provide specific version numbers for these software components, which is necessary for reproducible dependency information. |
| Experiment Setup | Yes | The paper provides specific experimental parameters such as the smoothness parameter 't = 1 and t = 10^-4' and regularization coefficient 'λ = 10^-4, 10^-5, 10^-6, 10^-7, 10^-8' for the binary regression problem. It also describes algorithmic details for the implemented algorithms (e.g., line search, parameter 'α' in Algorithm 3). |