Posts

• 2023-09-28A converse to Jensen's inequality for sums of powers
  We find a suitable converse to a certain instance of Jensen's Inequality involving sums of powers.
• 2023-06-16Tracking with Cost Constraints
  We extend the problem of tracking weights by adding costs.
• 2023-06-14Concentration Occurs on the Log-scale
  On being rich in expectation yet bankrupt in practise
• 2022-11-24Multivariate Sub-Gaussian Deviation Inequality
  We derive a deviation inequality for multivariate sub-Gaussians using mixture supermartingales and Ville's inequality.
• 2022-10-27Smooth Payoff Matrix yet Non-differentiable Value
  We look at the value of a two-player zero-sum game as a function of its payoff matrix. We see that even if that matrix is a smooth function of some parameter, the value of the game is not differentiable.
• 2021-11-07Regret Against Scaled Comparator Gains
  We perform a minimax analysis of the regret problem with scaled comparator gains.
• 2021-02-08Dot product in Julia
  We implement and profile the dot product in Julia.
• 2021-01-20Tightening the Screws on the FreeGrad Super-Martingale
  We review the recently proposed FreeGrad super-martingale, and improve one of the constants in its definition.
• 2020-10-13Optimal Sparsification
  We review one way to measures sparsity of a data set, and derive the optimal pre-processing step to maximise sparsity.
• 2020-03-04On the Tightness of Pinsker's Bound
  We look into the tightness of Pinsker's bound relating Total Variation distance to Kullback Leibler divergence.
• 2018-11-13Bounded Excess Risk for AdaHedge
  We show that AdaHedge has constant excess risk (aka pseudo-regret) for nice stochastic cases.
• 2018-10-24The Value of Random Game Trees
  We look at an intuitive generative model for game trees. We compute the distribution of the value of the root node, and see how it concentrates with the depth.
• 2018-09-29Solving Two-part Metal Puzzles: Theory and Practice
  A brief look at two metal take-me-apart puzzles.
• 2018-06-11A Dynamical System view of some Exponential Update
  We consider a natural mapping from the simplex to itself, similar to but different from the well-known exponential weights scheme. We investigate the limit behaviour when iterating this mapping.
• 2018-02-21Conference on Learning Theory (COLT) Proceedings
  The proceedings of the Conference On Learning Theory (COLT) 2010 are now online again.
• 2017-09-15Conference on Learning Theory (COLT) Video Archives
  The videos of the 2017 Conference On Learning Theory (COLT) are now online.
• 2017-09-08Bernoulli is Sub-Gaussian
  We show that any Bernoulli random variable is sub-Gaussian with variance factor $\frac{1}{4}$.
• 2017-04-26A Quick and Dirty Finite Time Law of the Iterated Logarithm Result
  The Law of the Iterated Logarithm is an asymptotic uniform deviation bound. We prove a finite time version using martingale arguments.
• 2017-03-20Visualisation of Conformal Mappings
  A visualisation of conformal mappings.
• 2017-03-11Rendering with Droste Effects
  A Droste image contains a smaller copy of itself. We look at how to render such images.
• 2017-01-21The Advantage of Full AdaGrad
  AdaGrad, an adaptive version of Online Gradient Descent, is often used in its diagonal version. In this post we take a look at the full matrix version to understand the benefit of its additional adaptive power.
• 2016-11-10Matrix iProd and Matrix Squint
  We look at extending two recent adaptive online learning strategies, iProd and Squint, to the matrix Hedge setting. The extension is straightforward up to a point, but we end with a nice open problem.
• 2016-10-31AdaFTRL
  We analyse AdaFTRL from the AdaHedge perspective.
• 2016-09-06Exploiting Curvature Using Exponential Weights
  We show how Exponential Weights applies uniformly to convex losses, strongly convex losses and exp-concave losses.
• 2016-09-01A Tractable Bound for Simple Power Inequalities
  We study a simple type of power inequality that pops up in the analysis of learning algorithms. The inequality has no general analytic solution, and we find a tractable bound.
• 2016-08-11Visualising The Escort Probability Map
  A simple visualisation of the escort probability map.
• 2016-04-11The Dual of the von Neumann Relative Entropy
  We compute two duals of the von Neumann relative entropy between PSD matrices.
• 2016-02-21Gradient Descent as Exponential Weights
  We regard gradient descent as an instance of exponential weights.
• 2016-02-01The GADDAG
  We have a look at the GADDAG data structure.
• 2016-01-31The Bregman Divergence Generated by the Absolute Value Function
  We look at the Bregman divergence generated by the prototypical non-differentiable convex function.
• 2016-01-13Mixability Gap Bounds
  A collection of bounds on the mixability gap.
• 2015-12-05An Upper Bound on the Learning Rate for IID Data
  We obtain an upper bound on the learning rate for convergence of the Hedge posterior in a simple iid data scenario.
• 2015-11-29Implementing Squint
  We look at some tricks and considerations that came up during my implementation of Squint.
• 2015-11-19Tight Diagonal Upper Bounds on Dyads
  We look at bounding a symmetric rank one matrix from above by a diagonal matrix.
• 2015-09-29Minimax on the Ball
  We compare two minimax strategies on the ball.
• 2015-09-21Colliding Balls
  Videos from my Newtonian collision simulator
• 2015-09-08Concave-convex vs Convex-convex
  We look at a simple quadratic minimax problem on the Euclidean sphere, and consider what happens when it flips from convex to concave.
• 2015-08-13The Relative Entropy Bound for Squint
  We derive the relative entropy version of the second-order quantile regret bound for Squint.
• 2015-05-25The Hedge Algorithm in Continuous Time
  We look at the Hedge algorithm in a version of continuous time.
• 2015-05-22Exchangeable vs Mixture of IID for a Pair of Binary Outcomes
  We determine which exchangeable distributions are mixtures of IID in the simple case of two binary outcomes.
• 2015-05-13Unknown Games
  We investigate what happens to simple matrix games and their solutions if we either randomly or strategically choose between two games.
• 2015-03-29Convex Duality Illustrated
  Convex duality is an important tool in machine learning. Here I present an insightful arrangement of the graphs of a convex function, its dual and their derivatives.
• 2015-03-08Differentiability of Compositions
  A composition of differentiable functions can be non-differentiable.
• 2015-02-22Close to the Perfect Expert, now Without Outcomes
  We look at one of the simplest online learning problems: making decisions in the presence of a perfect expert. We derive a non-uniform regret bound.
• 2015-02-01Bimatrix Games
  We show that any two-player zero-sum bimatrix game has a saddle point where both players randomise over the same number of strategies.