Oracle Complexity in Nonsmooth Nonconvex Optimization
Authors: Guy Kornowski, Ohad Shamir
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We provide two main results (under mild assumptions): First, we consider the problem of getting near -stationary points. This is perhaps the most natural relaxation of finding -stationary points, which is impossible in the nonsmooth nonconvex case. We prove that this relaxed goal cannot be achieved efficiently, for any distance and smaller than some constants. Our second result deals with the possibility of tackling nonsmooth nonconvex optimization by reduction to smooth optimization: Namely, applying smooth optimization methods on a smooth approximation of the objective function. For this approach, we prove an inherent trade-off between oracle complexity and smoothness |
| Researcher Affiliation | Academia | Guy Kornowski Weizmann Institute of Science guy.kornowski@weizmann.ac.il Ohad Shamir Weizmann Institute of Science ohad.shamir@weizmann.ac.il |
| Pseudocode | No | The paper describes algorithms conceptually and discusses theoretical properties, but does not provide any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training on datasets. Therefore, no information about publicly available datasets is provided in this context. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets. Therefore, no dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on oracle complexity, not on the computational performance of implemented algorithms. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and discusses algorithms conceptually without providing implementation details or specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |