Martin Lotz

Dennis Amelunxen, Martin Lotz

We introduce the concept of weak average-case analysis as an attempt to achieve theoretical complexity results that are closer to practical experience than those resulting from traditional approaches. This concept is accepted in other areas such as non-asymptotic random matrix theory and compressive sensing, and has a particularly convincing interpretation in the most common situation encountered for condition numbers, where it amounts to replacing a null set of ill-posed inputs by a "numerical null set". We illustrate the usefulness of these notions by considering three settings: (1) condition numbers that are inversely proportional to a distance of a homogeneous algebraic set of ill-posed inputs; (2) the running time of power iteration for computing a leading eigenvector of a Hermitian matrix; (3) Renegar's condition number for conic optimisation.

Duygu Sap, Martin Lotz, Connor Mattinson · berkeley, oxford

We propose a method for image categorization and retrieval that leverages graphs and a graph attention network (GAT)-based autoencoder. Our approach is representative-centric, that is, we execute the categorization and retrieval process via the representative models we construct for the images and image categories. We utilize a graph where nodes represent images (or their representatives) and edges capture similarity relationships. GAT highlights important features and relationships between images, enabling the autoencoder to construct context-aware latent representations that capture the key features of each image relative to its neighbors. We obtain category representatives from these embeddings and categorize a query image by comparing its representative to the category representatives. We then retrieve the most similar image to the query image within its identified category. We demonstrate the effectiveness of our representative-centric approach through experiments with both the GAT autoencoders and standard feature-based techniques.

Julio Hurtado, Haoran Ni, Duygu Sap et al. · berkeley, oxford

The fashion industry has been identified as a major contributor to waste and emissions, leading to an increased interest in promoting the second-hand market. Machine learning methods play an important role in facilitating the creation and expansion of second-hand marketplaces by enabling the large-scale valuation of used garments. We contribute to this line of work by addressing the scalability of second-hand image retrieval from databases. By introducing a selective representation framework, we can shrink databases to 10% of their original size without sacrificing retrieval accuracy. We first explore clustering and coreset selection methods to identify representative samples that capture the key features of each garment and its internal variability. Then, we introduce an efficient outlier removal method, based on a neighbour-homogeneity consistency score measure, that filters out uncharacteristic samples prior to selection. We evaluate our approach on three public datasets: DeepFashion Attribute, DeepFashion Con2Shop, and DeepFashion2. The results demonstrate a clear performance-efficiency trade-off by strategically pruning and selecting representative vectors of images. The retrieval system maintains near-optimal accuracy, while greatly reducing computational costs by reducing the images added to the vector database. Furthermore, applying our outlier removal method to clustering techniques yields even higher retrieval performance by removing non-discriminative samples before the selection.

Haoran Ni, Martin Lotz

Estimating Mutual Information (MI), a key measure of dependence of random quantities without specific modelling assumptions, is a challenging problem in high dimensions. We propose a novel mutual information estimator based on parametrizing conditional densities using normalizing flows, a deep generative model that has gained popularity in recent years. This estimator leverages a block autoregressive structure to achieve improved bias-variance trade-offs on standard benchmark tasks.

Martin Lotz

The problem of determining the volume of a tubular neighbourhood has a long and rich history. Bounds on the volume of neighbourhoods of algebraic sets have turned out to play an important role in the probabilistic analysis of condition numbers in numerical analysis. We present a self-contained derivation of bounds on the probability that a random point, chosen uniformly from a ball, lies within a given distance of a real algebraic variety of any codimension. The bounds are given in terms of the degrees of the defining polynomials, and contain as special case an unpublished result by Ocneanu.

Felipe Cucker, Raphael Hauser, Martin Lotz

The purpose of this note is to extend the results on uniform smoothed analysis of condition numbers from \cite{BuCuLo:07} to the case where the perturbation follows a radially symmetric probability distribution. In particular, we will show that the bounds derived in \cite{BuCuLo:07} still hold in the case of distributions whose density has a singularity at the center of the perturbation, which we call {\em adversarial}.

Peter Buergisser, Felipe Cucker, Martin Lotz

We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of ε-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a disk of radius σ. Besides εand σ, this bound depends only the dimension of the sphere and on the degree of the defining equations.

Peter Buergisser, Felipe Cucker, Martin Lotz

Smoothed analysis of complexity bounds and condition numbers has been done, so far, on a case by case basis. In this paper we consider a reasonably large class of condition numbers for problems over the complex numbers and we obtain smoothed analysis estimates for elements in this class depending only on geometric invariants of the corresponding sets of ill-posed inputs. These estimates are for a version of smoothed analysis proposed in this paper which, to the best of our knowledge, appears to be new. Several applications to linear and polynomial equation solving show that estimates obtained in this way are easy to derive and quite accurate.