Acceleration with a Ball Optimization Oracle
Authors: Yair Carmon, Arun Jambulapati, Qijia Jiang, Yujia Jin, Yin Tat Lee, Aaron Sidford, Kevin Tian
NeurIPS 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We design an accelerated algorithm which attains an ϵ-approximate minimizer with roughly r 2/3 log 1 ϵ oracle queries, and give a matching lower bound. Further, we implement ball optimization oracles for functions with locally stable Hessians using a variant of Newton s method and, in certain cases, stochastic first-order methods. The resulting algorithm applies to a number of problems of practical and theoretical import, improving upon previous results for logistic and ℓ regression and achieving guarantees comparable to the state-of-the-art for ℓp regression. |
| Researcher Affiliation | Academia | Stanford University, {yairc,jmblpati,qjiang2,yujiajin,sidford,kjtian}@stanford.edu. Tel Aviv University, ycarmon@cs.tau.ac.il. University of Washington, yintat@uw.edu. |
| Pseudocode | Yes | Algorithm 1 Monteiro-Svaiter acceleration; Algorithm 2 Monteiro-Svaiter oracle implementation; Algorithm 3 Monteiro-Svaiter accelerated BAll COnstrained Newton s method (MS-BACON); Algorithm 4 High accuracy ℓp regression |
| Open Source Code | No | The paper does not provide any concrete access to source code (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | The paper describes theoretical advancements and complexity analysis for optimization algorithms, which are applied to problem formulations like logistic and ℓp regression, but it does not mention or use any specific publicly available datasets for empirical evaluation, nor does it provide access information for such datasets. |
| Dataset Splits | No | The paper focuses on theoretical analysis and algorithmic design. It does not conduct empirical experiments that would require specifying training/validation/test dataset splits. |
| Hardware Specification | No | The paper describes theoretical algorithms and their complexity analysis. It does not specify any hardware details (e.g., GPU/CPU models, processor types) used for running experiments, as no empirical experiments are described. |
| Software Dependencies | No | The paper focuses on theoretical algorithmic design and complexity analysis. It does not specify ancillary software details with version numbers (e.g., library or solver names with versions) needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical, analyzing algorithmic complexity rather than empirical performance. It does not describe an experimental setup with specific hyperparameters, training configurations, or system-level settings. |