In machine learning, we frequently encounter a painful compromise: we must choose between the objective function we actually want to optimize and the objective function we can computationally afford to optimize.
Consider the classic problem of binary classification. We want to minimize the 0-1 loss—the actual number of misclassifications. However, the 0-1 loss is discontinuous and non-convex, making direct minimization NP-hard. The standard workaround is to swap the 0-1 loss for a convex surrogate, such as the hinge loss in Support Vector Machines or the logistic loss in logistic regression. As Michele Sebag notes in a historical overview, traditional kernel methods map input data into high-dimensional feature spaces to make complex boundaries linearly separable, but they still typically rely on these convex surrogates to ensure tractability.
The downside to surrogates is that they introduce a fundamental gap between the proxy objective and the true target. What if, instead of changing the loss function to fit our optimization space, we changed the optimization space to fit our loss function?
A powerful research direction addresses this by using improper learning and kernel-based space expansion to convexify inherently non-convex optimization problems. By embedding the hypothesis class or the loss function itself into a carefully constructed Reproducing Kernel Hilbert Space (RKHS), non-convex and non-linear objectives can be linearized, rendering them globally solvable.
The Core Intuition: Convexification via Space Expansion
To understand why this works, consider a non-convex landscape in a low-dimensional space. If you are restricted to finding a simple solution—like a linear halfspace—minimizing a non-convex loss is notoriously difficult because of local minima and discontinuities.
However, if we expand our search to a much larger, higher-dimensional hypothesis space (a strategy known as improper learning), the geometry of the problem changes. In a sufficiently rich RKHS, a non-linear or discontinuous loss function can be represented as a linear evaluation or an inner product. Because linear functions are inherently convex, optimization in this expanded space becomes a tractable, convex Empirical Risk Minimization (ERM) task.
Low-Dimensional Space High-Dimensional RKHS
[ Non-Convex / Discontinuous Loss ] ---> [ Linear Operator / Inner Product ]
(Optimization Hard) (Convex & Solvable)
Bypassing the Hardness of the 0-1 Loss
This strategy was leveraged by Shai Shalev-Shwartz et al. in a series of foundational papers, including Learning Kernel-Based Halfspaces with the Zero-One Loss and Learning Linear and Kernel Predictors with the 0-1 Loss Function.
The authors focused on agnostically learning halfspaces under the true 0-1 loss. They demonstrated that if the learner is allowed to return a classifier from an expanded kernel hypothesis class rather than a strict linear halfspace, the computational hardness can be bypassed.
To achieve this, the authors constructed a composition kernel structured as a rational function of the input vectors' inner product. This specific algebraic structure maps the data into an expanded RKHS where smooth approximations of the 0-1 loss function are linearized. As a result, the non-convex objective transforms into a tractable linear optimization problem.
While a fully polynomial-time solution for any arbitrary data distribution remains cryptographically impossible—as proven by Shai Shalev-Shwartz et al. in Learning Kernel-Based Halfspaces with the 0-1 Loss—this space expansion yields finite-time guarantees for a fixed uncertainty width. Furthermore, Aharon Birnbaum et al. demonstrated in Learning Halfspaces with the Zero-One Loss: Time-Accuracy Tradeoffs that this kernel-induced framework allows practitioners to smoothly interpolate between fast, low-accuracy algorithms and slower, high-accuracy ones, completely bypassing the accuracy limitations inherent to traditional convex surrogates.
Generalizing to Non-Linear Losses and Decision Making
The utility of kernel-based loss representation extends far beyond classification. The same underlying principle—representing non-linearities as linear operators in an RKHS—has been applied across several domains to tame complex optimization landscapes:
1. Online Learning and Bandits
In adversarial bandit settings, dealing with non-convex or non-linear reward/loss functions is exceptionally difficult. Niladri S. Chatterji et al. addressed this in Online learning with kernel losses by embedding non-linear loss functions as inner products within an RKHS. By leveraging the eigenvalue decay of the kernel to form finite-dimensional approximations, the authors extended standard linear bandit frameworks to handle complex quadratic or posynomial losses, achieving provable sub-linear regret.
2. Decision Calibration
When calibrating machine learning models for complex downstream tasks, standard calibration methods break down if the evaluation loss is non-linear (such as risk-averse utility functions). Jingwu Tang et al. bypassed this in Dimension-Free Decision Calibration for Nonlinear Loss Functions by representing non-linear loss functions as linear operators in an RKHS. This mathematical linearization allowed them to design calibration algorithms whose sample complexity is entirely independent of the outcome's dimensionality.
3. Neural Networks and Control
In distributed robotics, optimizing Graph Neural Networks (GNNs) with non-linear activation functions introduces severe non-convexity. In Convexified Graph Neural Networks for Distributed Control in Robotic Swarms, Saar Cohen 0001 et al. introduced a relaxation that maps the GNN's non-linearities into an RKHS. This reduces the complex distributed learning problem to a convex, linear formulation, ensuring rapid convergence in dynamic environments.
4. Measure Optimization and Robustness
For minimax problems like distributionally robust optimization (DRO), Pavel Dvurechensky et al. developed the Kernel Mirror Prox algorithm in Analysis of Kernel Mirror Prox for Measure Optimization. By embedding functional variables within an RKHS, they ensured that non-linear losses behave as convex functionals, providing strong convergence guarantees even when the underlying data loss is highly non-convex. Similarly, in the context of robust classification, Mingzhi Dong et al. demonstrated in A Maximum K-Min Approach for Classification that integrating kernel functions into a $k$-max loss objective allows a non-linear, outlier-robust classification problem to be solved globally as a quadratically constrained linear program.
Why It Works: The Riesz Representation Perspective
The unifying mechanism behind all of these applications is the structural property of Reproducing Kernel Hilbert Spaces.
By definition, an RKHS possesses a reproducing kernel $\kappa(x, \cdot)$ such that any function evaluation can be written as an inner product:
$$f(x) = \langle f, \kappa(x, \cdot) \rangle_{\mathcal{H}}$$
When we encounter a non-convex loss function $\ell(\theta, x)$ that is non-linear in our parameters $\theta$, we are trapped in a difficult optimization landscape. However, if we can find a feature mapping $\Phi(x)$ and a representation of our parameters in an expanded space $\mathcal{H}$ such that the loss can be rewritten as:
$$\ell(\theta, x) = \langle W_\theta, \Phi(x) \rangle_{\mathcal{H}}$$
the objective becomes completely linear with respect to the new optimization variable $W_\theta$.
By shifting our perspective from finding a simple parameter vector $\theta$ in the original space to finding an expanded operator or function $W_\theta$ in the RKHS, we trade a low-dimensional non-convex problem for a high-dimensional (or infinite-dimensional) convex problem. This space expansion is the core engine that allows modern learning frameworks to directly optimize the metrics we care about most without getting lost in local minima.
Key Foundational Work
Learning Kernel-Based Halfspaces with the Zero-One Loss (2010) — contributed 4 concept elements to this direction.
Learning Kernel-Based Halfspaces with the 0-1 Loss (2011) — contributed 3 concept elements to this direction.
Learning Linear and Kernel Predictors with the 0-1 Loss Function (2011) — contributed 2 concept elements to this direction.