Information-constrained optimization: can adaptive processing of gradients help?
Authors: Jayadev Acharya, Clement Canonne, Prathamesh Mayekar, Himanshu Tyagi
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We revisit first-order optimization under local information constraints such as local privacy, gradient quantization, and computational constraints limiting access to a few coordinates of the gradient. In this setting, the optimization algorithm is not allowed to directly access the complete output of the gradient oracle, but only gets limited information about it subject to the local information constraints. We study the role of adaptivity in processing the gradient output to obtain this limited information from it, and obtain tight or nearly tight bounds for both convex and strongly convex optimization when adaptive gradient processing is allowed. |
| Researcher Affiliation | Academia | Jayadev Acharya Cornell University acharya@cornell.edu; Clément L. Canonne University of Sydney clement.canonne@sydney.edu.au; Prathamesh Mayekar Indian Institute of Science prathamesh@iisc.ac.in; Himanshu Tyagi Indian Institute of Science htyagi@iisc.ac.in |
| Pseudocode | No | The paper describes the Adaptive Coordinate Descent (ACD) procedure in natural language text but does not present it as a formal pseudocode block or algorithm. |
| Open Source Code | No | The paper states 'If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... Did you include any new assets either in the supplemental material or as a URL? [N/A]'. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and lower bounds for optimization problems. It does not describe experiments that would involve training on specific datasets, nor does it provide access to any public datasets for such purposes. It states 'If you ran experiments... [N/A]'. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with dataset splits. It states 'If you ran experiments... Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]'. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for experiments. It states 'If you ran experiments... Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]'. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions used for experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or system-level training settings. It states 'If you ran experiments... Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]'. |