Approximate optimization of convex functions with outlier noise
Authors: Anindya De, Sanjeev Khanna, Huan Li, MohammadHesam NikpeySalekde
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the problem of minimizing a convex function given by a zeroth order oracle that is possibly corrupted by outlier noise. Specifically, we assume the function values at some points of the domain are corrupted arbitrarily by an adversary, with the only restriction being that the total volume of corrupted points is bounded. The goal then is to find a point close to the function s minimizer using access to the corrupted oracle. We first prove a lower bound result showing that, somewhat surprisingly, one cannot hope to approximate the minimizer nearly as well as one might expect, even if one is allowed an unbounded number of queries to the oracle. Complementing this negative result, we then develop an efficient algorithm that outputs a point close to the minimizer of the convex function, where the specific distance matches exactly, up to constant factors, the distance bound shown in our lower bound result. |
| Researcher Affiliation | Academia | Anindya De University of Pennsylvania anindyad@cis.upenn.edu Sanjeev Khanna University of Pennsylvania sanjeev@cis.upenn.edu Huan Li University of Pennsylvania huanli@cis.upenn.edu Hesam Nikpey University of Pennsylvania hesam@cis.upenn.edu |
| Pseudocode | Yes | Algorithm 1: GRADIENTCOMP, Algorithm 2: GDSTAGEI, Algorithm 3: GDSTAGEII |
| Open Source Code | No | The paper does not contain any statements about providing open-source code for the described methodology, nor does it include links to a code repository. |
| Open Datasets | No | This paper is theoretical in nature and presents algorithms and proofs. It does not involve empirical studies, dataset training, or public datasets. |
| Dataset Splits | No | This paper is theoretical and does not perform empirical experiments with datasets that would require training, validation, or test splits. No such information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and proofs. It does not describe any empirical experiments, and therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments. Consequently, it does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and proofs, rather than empirical evaluation. Therefore, it does not describe experimental setup details such as hyperparameters, training configurations, or system-level settings. |