Optimization often feels purely algebraic—a process of minimizing loss functions, balancing constraints, or computing gradients. However, a powerful dual perspective reveals that many foundational problems in machine learning, robotics, and computational geometry are secretly spatial.
Instead of searching for abstract parameters, we can often reframe optimization as finding the minimum distance between convex hulls or identifying the minimum enclosing shape (such as a ball or ellipsoid) of a point set. This geometric viewpoint unifies disparate fields and unlocks highly efficient, closed-form, or accelerated algorithms.
Classification as Distance Between Convex Hulls
Consider the classic problem of training a Support Vector Machine (SVM). Algebraically, we want to find a separating hyperplane that maximizes the margin between two classes of data points. Geometrically, this is exactly equivalent to constructing a convex hull around each class and finding the two closest points between these hulls. The vector connecting these two closest points is orthogonal to the optimal separating hyperplane.
Class A (Convex Hull) Class B (Convex Hull)
/\ /\
/ \ / \
/____* <----------------------*____\
\ /
\ Closest Distance /
This geometric equivalence allows us to swap heavy quadratic programming solvers for direct spatial searches. In The Huller: A Simple and Efficient Online SVM, [Antoine Bordes] et al. leveraged this perspective to design an online kernel learning algorithm. By treating SVM training as an iterative closest-point search between hulls, they achieved competitive classification accuracy in just a single pass over the training data.
When data contains noise or outliers, the convex hulls overlap, destroying the simple minimum-distance interpretation. To fix this, [David J. Crisp] et al. proved in A Geometric Interpretation of v-SVM Classifiers that the $\nu$-SVM formulation corresponds to finding the shortest distance between "soft convex hulls." By strictly capping the influence of any single data point, the soft hulls regularize the representation, providing a physical intuition for how the margin handles outliers.
This geometric duality scales remarkably well to distributed and robust settings:
- Distributed Optimization: In SVM via Saddle Point Optimization: New Bounds and Distributed Algorithms, [Lingxiao Huang] et al. framed SVM optimization as a minimax saddle-point problem over convex hull distances, allowing them to apply proximal coordinate gradient methods that achieve near-optimal communication costs.
- Robust Classification: [Akiko Takeda] et al. unified several classification models (like SVMs and Fisher Discriminant Analysis) in A Unified Robust Classification Model) by showing that finding an optimal decision boundary is equivalent to finding the shortest distance between geometric "uncertainty sets."
- Density Estimation: Even agnostic distribution learning can be viewed this way. [Olivier Bousquet] et al. showed in The Optimal Approximation Factor in Density Estimation that finding an optimal improper learner involves identifying a point within a convex hull that minimizes the discrepancy with a target's distance profile.
Minimax Optimization as Minimum Enclosing Shapes
A minimax optimization problem asks us to minimize the maximum of a set of functions or errors:
$$\min_x \max_i f_i(x)$$
When $f_i(x)$ represents the distance from a center point $x$ to an input point $p_i$, minimizing the maximum error is exactly the problem of finding the Minimum Enclosing Ball (MEB) of that point set. The center of the MEB is the optimal minimax solution.
[Ankan Saha] et al. demonstrated in Efficient Approximation Algorithms for Minimum Enclosing Convex Shapes that this geometric framing allows non-smooth convex optimization tools to solve enclosing problems significantly faster than traditional, purely geometric greedy heuristics.
Conversely, we can use the geometry of the MEB to solve complex minimax problems in computer vision without general-purpose solvers. For instance, in the known rotation problem for Structure-from-Motion, [Qianggong Zhang] et al. (A Fast Resection-Intersection Method for the Known Rotation Problem) showed that the optimal descent direction can be found in closed form. Instead of invoking an expensive optimization routine, they directly calculate the center of the MEB formed by the gradients of the most significant residuals, finding the path of steepest error reduction instantly.
This connection between algebraic bounds and enclosing shapes runs deep across several fields:
- First-Order Optimization: [Dmitriy Drusvyatskiy] et al. (An Optimal First Order Method Based on Optimal Quadratic Averaging) proved a mathematical equivalence between maximizing a quadratic lower bound and finding the minimal enclosing ball of intersecting geometric regions, providing a clean geometric intuition for accelerated first-order methods.
- Topological Data Analysis: In The Morse theory of Čech and Delaunay filtrations, Herbert Edelsbrunner used Karush-Kuhn-Tucker (KKT) conditions on the radius functions of minimum enclosing spheres to characterize the critical points that define underlying Morse gradients.
- Robust Estimation: [Yong Xia 0002] et al. explored the complexity of finding the Chebyshev center—the smallest ball enclosing the intersection of multiple given balls—in Chebyshev center of the intersection of balls: complexity, relaxation and approximation, providing linear programming relaxations for robust estimation.
From Balls to Ellipsoids: Adapting to Volume and Shape
While spheres are isotropic, real-world data often stretches along specific directions. To capture this orientation, we must move from enclosing balls to enclosing ellipsoids. Ellipsoids provide a linear-transformation-invariant way to approximate complex shapes and bound volumes.
In hypergraph complexity, [Aleksandar Nikolov] et al. (Approximating Hereditary Discrepancy via Small Width Ellipsoids) transformed the problem of approximating hereditary discrepancy into finding the minimum width of an enclosing ellipsoid. In power systems engineering, [Pan Li] et al. (A tractable ellipsoidal approximation for voltage regulation problems) used an SVM-like optimization model to learn an ellipsoidal container that maximizes the inclusion of feasible voltage regions while minimizing the inclusion of infeasible ones.
In high-dimensional geometry and lattice cryptography, the M-ellipsoid acts as a crucial computational bridge. An M-ellipsoid is an ellipsoid that can cover a given convex body using a bounded number of its translates. It essentially allows general, complex geometric norms to be efficiently related to the standard Euclidean norm.
Arbitrary Convex Body Approximate M-ellipsoid
.-------. .-------.
/ \ / \
| | ========> / \
\ / \ /
'-------' '-------'
[Daniel Dadush] et al. developed algorithms to construct these approximate M-ellipsoids deterministically (Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms; Near-optimal deterministic algorithms for volume computation via M-ellipsoids). By combining the classical ellipsoid method with deterministic objective evaluations, the authors bypassed the need for randomness, allowing them to extend algorithmic techniques designed for Euclidean spaces to solve lattice enumeration problems under any arbitrary norm (Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings).
Furthermore, finding the optimal alignment of these shapes requires a minimax approach to orientation. [Eli Putterman] et al. (Some new positions of maximal volume of convex bodies) introduced the "saddle-John position," which minimizes the maximum volume of a contained body over all possible rotations. This worst-case orientation yields a standard decomposition of the identity, mirroring classical ellipsoid theorems for arbitrary convex shapes. In machine learning exploration, [Elad Hazan] et al. (Volumetric Spanners: An Efficient Exploration Basis for Learning) proved that any compact set admits a volumetric ellipsoid that serves as an efficient basis for bandit linear optimization.
Algorithmic Unification via Projections and Frank-Wolfe
Recognizing that an optimization algorithm is secretly solving a geometric distance or containment problem allows us to import acceleration techniques directly from convex analysis.
A prime example is collision detection in robotics. To determine if two convex shapes are colliding, the classic Gilbert-Johnson-Keerthi (GJK) algorithm iteratively finds the closest point to the origin within the Minkowski difference of the two shapes. In GJK++: Leveraging Acceleration Methods for Faster Collision Detection, [Louis Montaut] et al. proved that GJK is mathematically equivalent to a fully-corrective Frank-Wolfe optimization process. By framing collision detection as a constrained optimization problem, the authors successfully applied Nesterov and Polyak acceleration techniques, yielding up to a 2x speedup in robotics simulators.
Similarly, complex saddle-point problems in semi-supervised learning can be simplified. [Yu-Feng Li] et al. (Learning Safe Prediction for Semi-Supervised Regression) showed that finding a safe regressor can be viewed as taking a supervised baseline point in space and projecting it onto a convex set formed by candidate regressors. This geometric interpretation transforms a risky optimization gamble into a reliable distance-minimization task.
Even pure differential geometry benefits from this optimization framing. [Guoqing He] et al. (Optimal Inequalities for the Casorati Curvatures...) and Pan Zhang (Casorati Inequalities...) both established fundamental curvature bounds for submanifolds by constructing quadratic polynomials from the second fundamental form and optimizing them subject to linear constraints.
Whether drawing a decision boundary, calculating a robot's trajectory, or bounding a high-dimensional lattice, the underlying principle remains the same: to optimize efficiently, look for the hidden hulls, balls, and ellipsoids defining the space.
Key Foundational Work
The Huller: A Simple and Efficient Online SVM (2005) — contributed 1 concept elements to this direction.
A Geometric Interpretation of v-SVM Classifiers (1999) — contributed 1 concept elements to this direction.