Efficient Regret Minimization in Non-Convex Games
Authors: Elad Hazan, Karan Singh, Cyril Zhang
ICML 2017 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. We give gradient-based methods that achieve optimal regret, which in turn guarantee convergence to equilibrium in this framework. |
| Researcher Affiliation | Academia | 1Computer Science, Princeton University. Correspondence to: Elad Hazan <ehazan@princeton.edu>, Karan Singh <karans@princeton.edu>, Cyril Zhang <cyril.zhang@princeton.edu>. |
| Pseudocode | Yes | Algorithm 1 Time-smoothed online gradient descent; Algorithm 2 Time-smoothed online gradient descent with stochastic gradient oracles; Algorithm 3 Time-smoothed online Newton method; Algorithm 4 Time-smoothed game simulation. |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not describe experiments performed on specific datasets. It discusses theoretical constructs like "loss functions f1, . . . , f T" and a "convex decision set K Rn". |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical experiments, thus no training, validation, or test dataset splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe specific experimental setup details, such as hyperparameters or training configurations for empirical evaluations. |