🔢 mathematics

Non-Archimedean Polydisc Spaces and Applications to Optimisation

This paper introduces a novel framework for optimization over non-Archimedean polydisc spaces inspired by Berkovich geometry, establishing their metric properties, demonstrating their capacity to embed hierarchical data and support universal approximation, and providing both theoretical guarantees for minimizers and an accompanying open-source Julia library for implementation.

Original authors: Paul Lezeau, Yiannis Fam, Anthea Monod, Yue Ren

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Paul Lezeau, Yiannis Fam, Anthea Monod, Yue Ren

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a massive library of information. In the real world, we often use flat maps (like a city grid) or 3D models to understand how things relate. But some data, like family trees, evolutionary histories, or the way words build into sentences, isn't flat. It's a hierarchy: a branching structure where everything splits into smaller and smaller groups.

The problem is that our standard math tools (based on real numbers) are terrible at handling these branching trees. To force a tree onto a flat map, you have to stretch it out so much that the distances between items become distorted. It's like trying to flatten a globe onto a piece of paper without tearing it; you end up with a mess.

This paper introduces a new way to handle this kind of data using a special kind of math called Non-Archimedean geometry. Think of this as a "tree-native" math system where the rules of distance are different. In this world, if you have three points, the two furthest apart are never further than the longest single step between any two of them. This creates a natural, perfect tree structure.

However, there's a catch: while this "tree math" is great for representing data, it's terrible for optimization (finding the best solution). The tree is so full of sharp corners and disconnected branches that standard "gradient descent" (the method computers use to slide down a hill to find the lowest point) gets stuck or breaks. You can't slide smoothly down a tree; you have to jump from branch to branch.

The Solution: Polydisc Spaces

The authors propose a clever workaround. They build a new geometric space called Polydisc Spaces.

The Analogy: Imagine the tree is a skeleton. The authors wrap this skeleton in a soft, continuous "skin" or "fog."
What it does: This new space keeps the perfect tree structure of the original data (so the hierarchy is preserved), but it fills in the gaps. Now, instead of jumping between disconnected branches, you can walk smoothly along a path (a "geodesic") from one point to another.
The Result: You get the best of both worlds: the data stays in its natural tree shape, but you can now use smooth, continuous math to find the best solutions.

The Tools: "Absolute Polynomials"

To find the best solution (the minimum) in this new space, the authors invented a special type of function called an Absolute Polynomial.

The Metaphor: Think of these functions as "smart rulers." In standard math, a ruler measures distance linearly. In this new space, these rulers are made of pieces of straight lines that snap together.
Why it matters: These rulers are flexible enough to approximate almost any shape of data you throw at them (a "Universal Approximation" property), but they are also simple enough that a computer can calculate them quickly. They turn a messy, complex problem into a series of simple, piecewise steps.

How to Find the Best Solution (Optimization)

Once they have the space and the rulers, they needed a way to actually find the "lowest point" (the best answer). Since the space is still a tree at its core, they adapted several search strategies:

Best-First Descent: Like a hiker who always chooses the steepest path down. They look at all the immediate next steps and pick the one that lowers the value the most.
Gradient Descent: Using the "slope" of their smart rulers to decide which direction to move, similar to how a ball rolls down a hill.
Monte-Carlo Tree Search (MCTS): This is like a chess computer. Instead of just looking one step ahead, it simulates many possible future paths, explores the most promising ones, and balances between trying new paths (exploration) and sticking to the ones that look good (exploitation).
Deterministic Optimistic Optimisation: This method assumes the best possible outcome in unexplored areas and systematically narrows down the search, ensuring it doesn't miss hidden treasures.

The Proof: A Software Library

The authors didn't just write theory; they built a software library (written in the Julia programming language) called NonArchimedeanMachineLearning.jl.

They tested their ideas on various problems:

Solving Equations: Finding the roots of polynomials (where the answer is zero).
Fitting Data: Finding the best line or curve to fit a set of points (like linear regression).
Learning Functions: Trying to guess the rule behind a set of random data points.

The Results:
Their experiments showed that the Monte-Carlo Tree Search (MCTS) method was generally the most effective. It was better at navigating the complex, branching landscape than the simpler "greedy" methods that just look one step ahead. However, the simpler methods were faster. The library proved that you can actually do machine learning and optimization on these "tree-native" spaces efficiently.

Summary

In short, this paper says: "If your data is a tree, don't force it onto a flat map. Build a new mathematical world that is a tree but acts like a smooth surface. In this world, we can define simple rules to find the best answers, and we have built a computer program that proves it works."

They provide the math, the algorithms, and the code to make this possible, opening the door for better analysis of hierarchical data like family trees, language structures, and complex networks.

Technical Summary: Non-Archimedean Polydisc Spaces and Applications to Optimisation

1. Problem Statement

Hierarchical data analysis is ubiquitous in fields ranging from phylogenetics and genomics to linguistics and sociology. While hierarchical structures naturally induce non-Archimedean geometric structures (often visualized as metric trees), capturing these structures faithfully over the real numbers ( $\mathbb{R}$ ) is difficult. Embedding such data into $\mathbb{R}^n$ often requires high-dimensional spaces or hyperbolic geometry, which may not preserve the intrinsic ultrametric properties.

Conversely, working directly over non-Archimedean fields (such as the $p$ -adic numbers $\mathbb{Q}_p$ ) preserves the hierarchical structure but presents significant challenges for optimisation. The topology of these fields is totally disconnected, prohibiting the use of standard continuous optimisation techniques like gradient descent. Consequently, optimisation problems over non-Archimedean spaces frequently reduce to computationally expensive combinatorial searches.

The central problem addressed by this paper is the lack of a geometric framework that simultaneously:

Faithfully represents hierarchical data via non-Archimedean geometry.
Provides a continuous, path-connected domain suitable for standard optimisation techniques (e.g., geodesics, convexity, gradients).

2. Methodology and Framework

The authors propose a new framework inspired by Berkovich geometry, introducing polydisc spaces ( $B^n$ and $H^n$ ) as the domain for optimisation.

2.1 Polydisc Spaces

Instead of working directly in the non-Archimedean space $K^n$ , the authors define polydisc spaces as products of closed balls over a non-Archimedean field $K$ (e.g., $\mathbb{Q}_p$ or fields of Laurent series).

Structure: $B^n$ consists of polydiscs $B_B(a, r)$ (absolute radius) or $B_H(a, v)$ (valuative radius).
Geometry: These spaces retain the rigid hierarchical structure of $K^n$ $K^{n}$ (nested, non-overlapping sets) while acquiring desirable geometric features absent in $K^n$ $K^{n}$ :
- Path Connectedness: The space is connected via geodesics.
- Geodesics: The space is uniquely geodesic (for $n=1$ or $1 < p < \infty$ ), allowing for the definition of paths between any two points.
- Convexity: A notion of convex hulls is defined based on geodesics.
- Tangent Directions: A calculus-like structure is introduced via tangent directions, defined as equivalence classes of geodesics emanating from a point. This allows for the definition of directional derivatives.

2.2 Function Theory

The authors introduce a class of real-valued functions called absolute polynomials and valuation polynomials.

Definition: Given a polynomial $f$ with coefficients in the field of polydiscs, the function maps a polydisc $B$ to the supremum of $|f(z)|$ (or infimum of $val(f(z))$) over $z \in B$ .
Properties: These functions admit explicit evaluation formulas. Crucially, they are piecewise polynomial (in the absolute case) or piecewise linear/tropical (in the valuation case) along geodesics.
Universal Approximation: The authors prove a universal approximation theorem (Theorem 45), showing that linear combinations of absolute polynomials can approximate any continuous function on compact subsets of $B^n$ .

2.3 Embedding Metric Trees

The paper establishes that metric trees can be naturally and often isometrically embedded into the hyperbolic polydisc space $H^1$ .

Criteria: An isometric embedding exists if the maximum degree of the tree vertices is bounded by $|K| + 1$ and edge lengths correspond to values in the valuation group of $K$ .
Field Extension: If these conditions are not met, the framework provides a constructive procedure to extend the base field $K$ (by extending the value group or residue field) to enable the embedding without modifying previously embedded subtrees.

2.4 Optimisation Theory

The paper develops a theory for minimising functions of the form $\ell = \sum a_i |f_i|$ , where $a_i > 0$ and $f_i$ are polynomials.

Existence of Minimisers: Theorems 52 and 55 establish conditions under which global minima exist. Specifically, if the projective closures of the zero loci of the polynomials intersect within the affine space $K^n$ , or if they never intersect, a global minimum exists.
Localization: In the univariate case, all global minima are confined to a bounded region determined by the coefficients of the polynomials (Theorem 62).
Algorithms: The authors adapt several optimisation strategies to the polydisc setting:
- Best-First Descent: Greedy refinement of polydiscs.
- Best-First Gradient Descent: Uses directional derivatives to select the steepest descent branch.
- Deterministic Optimistic Optimisation (DOO): Balances exploration and exploitation using upper confidence bounds derived from the Lipschitz properties of the functions.
- Monte-Carlo Tree Search (MCTS): Adapts MCTS to the polydisc space, including a DAG-MCTS variant to handle the directed acyclic graph structure of higher-dimensional polydiscs where nodes may have multiple parents.

3. Key Contributions

Geometric Framework: The introduction of polydisc spaces ( $B^n, H^n$ ) as a computationally tractable, path-connected domain for non-Archimedean optimisation, bridging the gap between discrete hierarchical data and continuous optimisation.
Function Class: The definition and analysis of absolute and valuation polynomials, proving their piecewise structure along geodesics and their universal approximation capabilities.
Optimisation Theory: Proofs of the existence of global minima for positive linear combinations of absolute polynomials under specific geometric conditions on zero loci, and the derivation of explicit bounds for minimisers in the univariate case.
Algorithmic Adaptation: The formulation of optimisation algorithms (Best-First, Gradient Descent, DOO, MCTS) tailored to the hierarchical, branching geometry of polydisc spaces.
Software Implementation: The development and release of NonArchimedeanMachineLearning.jl, an open-source Julia library implementing the geometric objects, function classes, and optimisation algorithms.

4. Results and Experimental Findings

The authors conducted computational experiments using their Julia library to validate the theoretical framework:

Polynomial Root Finding: Algorithms successfully converged to roots of polynomials over $\mathbb{Q}_p$ . MCTS and Best-First methods showed faster convergence than DOO in simple root-finding tasks.
Absolute Polynomial Sum Minimisation: The algorithms were tested on minimizing sums of absolute values of polynomials. MCTS and DAG-MCTS generally outperformed greedy methods in terms of final loss, particularly in scenarios with more complex loss landscapes, though at a higher computational cost.
Polynomial Interpolation: The framework successfully solved interpolation problems (finding coefficients for a polynomial passing through given points) by minimising the squared error loss.
Function Learning: The authors demonstrated the ability to learn functions (approximating binary labels) using absolute polynomials as the hypothesis class.
Performance: MCTS-based methods achieved the best average ranks across various tasks but required more function evaluations and runtime compared to greedy descent methods. The experiments confirmed that increasing the number of simulations in MCTS improves performance.

5. Significance and Claims

The paper claims to provide a mathematical and computational foundation for optimisation and machine learning on non-Archimedean spaces. Its significance lies in:

Unifying Representation and Optimisation: It offers a single space ( $B^n$ ) that serves both as a natural representation for hierarchical data (via isometric tree embeddings) and as a domain for optimisation (via geodesics and gradients).
Overcoming Topological Barriers: By moving from the totally disconnected field $K^n$ to the path-connected polydisc space $B^n$ , the authors enable the use of gradient-based and tree-search methods that were previously inapplicable to non-Archimedean optimisation.
Practical Viability: The development of the NonArchimedeanMachineLearning.jl library demonstrates that these theoretical constructs are computationally feasible, providing a tool for future research at the intersection of non-Archimedean geometry, optimisation, and machine learning.

The authors note that while the current framework focuses on absolute polynomials, the approach is modular and could be extended to broader function classes. They position this work as a proof-of-concept for a new paradigm in handling hierarchical data, distinct from existing hyperbolic or high-dimensional Euclidean approaches.