11 papers
Spherical-Design Oracles for Zeroth-Order Optimisation: Deterministic, Variance-Free Gradient Estimation
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1
In this work, we develop a zeroth-order (ZO) method that estimates the gradient with minimal bias and variance. Instead of the random directions often used in the ZO literature, we…
Semi-Explicit Solutions to the Prying-Pedestrian Surveillance-Evasion Differential Game and Extensions to Two Pursuers
Philipp Braun, Daniel Coutinho, Timothy L. Molloy +1
In [1], the authors recently proposed and solved a surveillance-evasion differential game in which an agile pursuer (the prying pedestrian) seeks to remain within a given surveilla…
From open-loop representations to closed-loop feedback implementations in differential games: A numerical case study
Philipp Braun, Timothy L. Molloy, Gal Barkai +1
Solutions to pursuit-evasion and surveillance-evasion differential games are typically computed and expressed using open-loop representations, with the synthesis of feedback strate…
From Cursed to Competitive: Closing the ZO-FO Gap via Input-to-State Stability
Amir Ali Farzin, Philipp Braun, Iman Shames
While it is generally understood that zeroth-order (ZO) algorithms have an extra dependency on their number of iterations for any choice of parameters, compared to their first-orde…
On the Stability Connection Between Discrete-Time Algorithms and Their Resolution ODEs: Applications to Min-Max Optimisation
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1
This work establishes a rigorous connection between stability properties of discrete-time algorithms (DTAs) and corresponding continuous-time dynamical systems derived through $ O(…
Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +2
We consider max-min and min-max problems with objective functions that are possibly non-smooth, submodular with respect to the minimiser and concave with respect to the maximiser.…
Minimisation of Submodular Functions Using Gaussian Zeroth-Order Random Oracles
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +2
We consider the minimisation problem of submodular functions and investigate the application of a zeroth-order method to this problem. The method is based on exploiting a Gaussian…
Minimisation of Quasar-Convex Functions Using Random Zeroth-Order Oracles
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1
This paper explores the performance of a random Gaussian smoothing zeroth-order (ZO) scheme for minimising quasar-convex (QC) and strongly quasar-convex (SQC) functions in both unc…
Properties of Fixed Points of Generalised Extra Gradient Methods Applied to Min-Max Problems
Amir Ali Farzin, Yuen-Man Pun, Philipp Braun +1
This paper studies properties of fixed points of generalised Extra-gradient (GEG) algorithms applied to min-max problems. We discuss connections between saddle points of the object…
Min-Max Optimisation for Nonconvex-Nonconcave Functions Using a Random Zeroth-Order Extragradient Algorithm
Amir Ali Farzin, Yuen Man Pun, Philipp Braun +3
This study explores the performance of the random Gaussian smoothing Zeroth-Order ExtraGradient (ZO-EG) scheme considering \Af{deterministic} min-max optimisation problems with pos…
Prying Pedestrian Surveillance-Evasion: Minimum-Time Evasion from an Agile Pursuer
Philipp Braun, Timothy L. Molloy, Iman Shames
A new surveillance-evasion differential game is posed and solved in which an agile pursuer (the prying pedestrian) seeks to remain within a given surveillance range of a less agile…