Black-Box Methods for Restoring Monotonicity
Authors: Evangelia Gergatsouli, Brendan Lucier, Christos Tzamos
ICML 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work we develop algorithms that are able to restore monotonicity in the parameters of interest. Specifically, given oracle access to a (possibly non-monotone) multi-dimensional real-valued function f, we provide an algorithm that restores monotonicity while degrading the expected value of the function by at most ε. The number of queries required is at most logarithmic in 1/ε and exponential in the number of parameters. We also give a lower bound showing that this exponential dependence is necessary. Finally, we obtain improved query complexity bounds for restoring the weaker property of k-marginal monotonicity. |
| Researcher Affiliation | Collaboration | Evangelia Gergatsouli 1 Brendan Lucier 2 Christos Tzamos 1 1University of Wisconsin Madison, WI, USA 2Microsoft Research, Cambridge, MA, USA. |
| Pseudocode | No | The paper describes its algorithms in narrative form with mathematical details but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any information or links regarding the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments on a specific dataset. It refers to theoretical "product distribution of inputs" but does not mention any publicly available or open dataset with access information. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments, so it does not provide details on training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not conduct empirical experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not report on software implementations or specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical experiments, therefore no experimental setup details like hyperparameters or training settings are provided. |