Differentiable bilevel programming for stackelberg congestion games
A Stackelberg congestion game (SCG) is a bilevel program in which a leader aims to
maximize their own gain by anticipating and manipulating the equilibrium state at which …
maximize their own gain by anticipating and manipulating the equilibrium state at which …
Polyak–Łojasiewicz inequality on the space of measures and convergence of mean-field birth-death processes
The Polyak–Łojasiewicz inequality (PŁI) in R d is a natural condition for proving
convergence of gradient descent algorithms (Karimi et al. in: Frasconi et al.(eds) Machine …
convergence of gradient descent algorithms (Karimi et al. in: Frasconi et al.(eds) Machine …
On centralized and distributed mirror descent: Convergence analysis using quadratic constraints
Mirror descent (MD) is a powerful first-order optimization technique that subsumes several
optimization algorithms including gradient descent (GD). In this work, we leverage quadratic …
optimization algorithms including gradient descent (GD). In this work, we leverage quadratic …
A fast adaptive online gradient descent algorithm in over-parameterized neural networks
A Yang, D Li, G Li - Neural Processing Letters, 2023 - Springer
In recent years, deep learning has dramatically improved state of the art in many practical
applications. However, this utility is highly dependent on fine-tuning of hyperparameters …
applications. However, this utility is highly dependent on fine-tuning of hyperparameters …
Configurable Mirror Descent: Towards a Unification of Decision Making
Decision-making problems, categorized as single-agent, eg, Atari, cooperative multi-agent,
eg, Hanabi, competitive multi-agent, eg, Hold'em poker, and mixed cooperative and …
eg, Hanabi, competitive multi-agent, eg, Hold'em poker, and mixed cooperative and …
A Mirror Descent Perspective of Smoothed Sign Descent
S Wang, D Klabjan - arXiv preprint arXiv:2410.14158, 2024 - arxiv.org
Recent work by Woodworth et al.(2020) shows that the optimization dynamics of gradient
descent for overparameterized problems can be viewed as low-dimensional dual dynamics …
descent for overparameterized problems can be viewed as low-dimensional dual dynamics …
Reusing combinatorial structure: faster iterative projections over submodular base polytopes
Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its
variants enjoy near-optimal regret bounds and convergence rates, but suffer from a …
variants enjoy near-optimal regret bounds and convergence rates, but suffer from a …
First-Order Algorithms for Optimization over Graph Laplacians
T Maunu - 2023 International Conference on Sampling Theory …, 2023 - ieeexplore.ieee.org
When solving an optimization problem over the set of graph Laplacian matrices, one must
deal with a large number of constraints as well as the large objective variable size. In this …
deal with a large number of constraints as well as the large objective variable size. In this …
Characterizing linear convergence in optimization: Polyak-Łojasiewicz inequality and weak-quasi-strong-convexity
F Alimisis, B Vandereycken - openreview.net
We give a complete characterization of optimization problems that can be solved by gradient
descent with a linear convergence rate. We show that the well-known Polyak-Łojasiewicz …
descent with a linear convergence rate. We show that the well-known Polyak-Łojasiewicz …