Optimal First-Order Algorithms as a Function of Inequalities
Authors: Chanwoo Park, Ernest K. Ryu
JMLR 2024 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we present a novel algorithm design methodology that finds the optimal algorithm as a function of inequalities. Specifically, we restrict convergence analyses of algorithms to use a prespecified subset of inequalities, rather than utilizing all true inequalities, and find the optimal algorithm subject to this restriction. This methodology allows us to design algorithms with certain desired characteristics. As concrete demonstrations of this methodology, we find new state-of-the-art accelerated first-order gradient methods using randomized coordinate updates and backtracking line searches. The paper contains extensive mathematical derivations and proofs (e.g., Section 4.3: Proof of Theorem 1), indicating theoretical research. |
| Researcher Affiliation | Academia | Chanwoo Park EMAIL Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology Massachusetts, United States of America. Ernest K. Ryu EMAIL Department of Mathematical Sciences Interdisciplinary Program in Artificial Intelligence Seoul National University Seoul, Korea. Both authors are affiliated with academic institutions. |
| Pseudocode | Yes | Optimized randomized coordinate updates function value (ORC-F ) is defined as yk+1 = xk 1 Li(k) i(k)f(xk) zk+1 = zk ϕk+1 ϕk Sp Li(k) i(k)f(xk) xk+1 = ϕk+1 ϕk+2 yk+1 + 1 ϕk+1. Optimized backtracking linesearch function value (OBL-F ) is defined as yk+1 = xk 1 Lk+1 f(xk) zk+1 = zk k + 1 xk+1 = 1 2 k + 3 yk+1 + 2 k + 3zk+1. The paper provides structured mathematical definitions of algorithms, which serve as pseudocode. |
| Open Source Code | Yes | As the proofs of A -optimality require lengthy calculations, we provide Matlab scripts verifying them. Specifically, the following scripts show that the derived analytical results agree with the numerical solutions of the SDPs: https://github.com/chanwoo-park-official/A-star-map/. |
| Open Datasets | No | The paper presents theoretical contributions to algorithm design and convergence analysis for convex optimization. It does not conduct experiments on specific datasets, and therefore no dataset access information is provided. |
| Dataset Splits | No | The paper does not involve empirical evaluation on datasets, so there is no mention of training/test/validation splits. |
| Hardware Specification | No | The paper focuses on theoretical algorithm design and analysis. Although it mentions 'computer-assisted proof methodology,' it does not provide specific hardware details (like GPU/CPU models, processor types, or memory amounts) used for any computations or experiments. |
| Software Dependencies | No | The paper mentions 'Matlab scripts' for verifying calculations but does not provide specific version numbers for Matlab or any other software dependencies. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis, rather than empirical experimentation. Therefore, no specific experimental setup details such as hyperparameters, training configurations, or system-level settings are provided. |