Oracle Complexity in Nonsmooth Nonconvex Optimization
Authors: Guy Kornowski, Ohad Shamir
JMLR 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study nonsmooth nonconvex optimization from an oracle complexity viewpoint, where the algorithm is assumed to be given access only to local information about the function at various points. We provide two main results: 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 under a mild assumption an inherent trade-offbetween oracle complexity and smoothness |
| Researcher Affiliation | Academia | Guy Kornowski EMAIL Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot, Israel Ohad Shamir EMAIL Department of Computer Science and Applied Mathematics Weizmann Institute of Science Rehovot, Israel |
| Pseudocode | No | The paper describes theoretical proofs and mathematical derivations. There are no explicit pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not mention releasing any source code or providing links to a code repository. The research is theoretical in nature. |
| Open Datasets | No | The paper focuses on theoretical analysis of nonsmooth nonconvex optimization and does not conduct empirical studies using datasets. It mentions 'training modern neural networks' as a motivation but does not use any specific dataset for its own research. |
| Dataset Splits | No | The paper does not use any datasets for experimental evaluation, therefore, there is no mention of dataset splits. |
| Hardware Specification | No | The paper presents theoretical results and does not describe any experimental setup that would require specific hardware. Thus, no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not involve implementing algorithms or conducting experiments, so no software dependencies or versions are mentioned. |
| Experiment Setup | No | The paper is entirely theoretical, focusing on oracle complexity and proofs. It does not describe any experiments or an experimental setup with hyperparameters or training configurations. |