Entropic perspective on AI resilience, data-minimal learning and optimal control

arXiv:2310.14421 · stat.ML, cs.AI, cs.LG · Submitted 2023-10-19 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Entropic perspective on AI resilience, data-minimal learning and optimal control".

Jane: Here's the gist of the paper. The gist The mathematical conditions for existence, uniqueness and explicit analytical computation of minimal adversarial paths (MAP) and minimal adversarial distances (MAD) for various AI classifiers are formulated and proven, with practical demonstrations on synthetic benchmarks and biomedical data.

Tom: Adversarial Attacks and Mathematical Bottlenecks Understanding the nature of AI systems is increasingly important due to "very small changes in the input data - practically non-perceptable for humans - could be used for a complete corruption of the AI classification outcomes" <ref:2310.14421#pg3>.

Jane: Adversarial attacks involve finding an adversarial vector X∗ that is as close as possible to the given vector X in terms of some distance measure dist(X, X∗) such that PL∗ (X∗) is attaining its maximal value for L∗ ≠ L <ref:2310.14421#pg3>.

Tom: However, mathematical properties like existence, uniqueness and numerical scalability of adversarial problems solutions remain a major bottleneck, requiring a fulfilment of very strong assumptions like strong Lipschitz-convexity of the class affiliation probability function PL(X) <ref:2310.14421#pg4>.

Paper summary: Tom: So we just covered how they tackle the problem of quantifying minimal adversarial paths and distances in this paper. The main thesis is that finding these minimal paths can be done with mathematically sound criteria, specifically using an entropy-optimising perspective.

Jane: Right. They start by framing AI resilience as something urgent because tiny changes to input data, which are practically unnoticeable to humans, can completely corrupt the AI's classification outcomes two <ref:2310.14421#pg2>. This is about understanding the nature of these systems better.

Lu: The paper points out that a big bottleneck in this area has been needing very strong assumptions, like strong Lipschitz-convexity of the class affiliation probability function PL(X), which they note isn't always true for basic AI benchmarks, like a double Swiss roll example <ref:2310.14421#pg4>.

Meng: So they are saying existing methods often fail because they rely on these overly strict mathematical assumptions that don't hold in practice. They need a more flexible way to approach the problem.

Lalam: The core of their proposal is finding the minimal adversarial path, or MAP, which is defined by minimizing the distance between your input X and an adversarial version X-tilde such that the change in probability PL(X) minus PL(X-tilde) is greater than some positive delta > zero <ref:2310.14421#pg3>.

Tom: So they define it as this optimization problem: find X-tilde that minimizes the distance dist(X, X-tilde) subject to two main constraints: the probability change must be at least delta, and the features you can actually change are constrained to a subset da of D degrees of freedom where Xi is kept fixed for Xi in da <ref:2310.14421#pg3>.

Jane: It’s really interesting how they separate the accessible features 'da' from the inaccessible ones 'da-complement', which are features that we can't control during an attack. This is a key insight into what an AI system actually depends on versus what we can manipulate.

Lu: They then define the minimal adversarial distance measure, MADL(X, delta) as the length of this path, which they assume is defined by local unique-invertibility of the probability function PL(X).

Meng: If the function isn't locally uniquely invertible, then finding that minimal path becomes a much harder problem because you lose that nice structure they are trying to exploit.

Lalam: They show that under certain conditions, like those summarized in Theorem one <ref:2310.14421#pg5>, this regularized problem can be solved explicitly, giving a closed-form analytical solution for X-star epsilon delta <ref:2310.14421#pg1>.

Tom: And for generalized linear models like logistic regression, where the classifier function is uniquely invertible with respect to the scalar product theta transpose X, they get an explicit form involving terms related to C(delta, X) and theta <ref:2310.14421#pg6>.

Jane: That explicit solution takes a computational cost scaling of O(D). That means for standard linear models, the computation scales nicely with the dimension of the feature vector.

Lu: For more advanced AI methods, like deep learning networks with linear ReLU transfer functions and entropic AI methods, they use the Scalable Probabilistic Approximation algorithm or eSPA to find conditions for existence and uniqueness of MAP and MAD computation scalability in Theorem two <ref:2310.14421#pg9> <ref:2310.14421#pg2>.

Meng: And that scaling is polynomial in dimension D but also linear in the number K of eSPA Voronoi cells, which is good news for practical deployment because it suggests manageable computational load.

Tom: So they are showing that even for these more complex structures, the computational cost remains tractable under their specific framework. It's not just a theoretical exercise; there's a path to actual computation.

Jane: It sounds like the next step is seeing how these mathematical tools translate into real-world applications, especially since they’ve already demonstrated on synthetic benchmarks and biomedical data problems <ref:2310.14421#pg1>.

Conclusion: Tom: To wrap up "Entropic perspective on AI resilience, data-minimal learning and optimal control," the authors establish two theorems that provide explicit analytically solvable expressions for a minimal adversarial path in generalized linear models and locally uniquely-invertible classifiers, as well as providing straightforwardly verifiable mathematical conditions and polynomially scalable strongly-convex Quadratic Programming solvers for the optimal control computation in entropic AI.

Jane: It really boils down to finding these precise mathematical paths—the MAPs and MADs—and proving they exist and can be computed exactly using entropy-optimising techniques, which is what the paper sets out to do.

Lu: The implication is that we have a new way of looking at adversarial attacks that relies on entropic AI, offering interpretable insights into optimal interventions in complex systems.

Meng: For me, it means we can potentially train much simpler models with superior performance and use them to directly train the optimal controls in complex systems, requiring only a small fraction of training data and outperforming current tools in complexity metrics.

Tom: It sounds like they’ve provided a framework that connects theoretical adversarial robustness directly to practical, efficient model training methods. They're showing how this approach can be used not just for security but also for optimizing the learning process itself.

Jane: So ultimately, this paper suggests that we can build AI systems with more mathematical certainty about their resilience and develop learning algorithms that are inherently more data-efficient by using these minimal adversarial path calculations.

Illia Horenko

Chair for Mathematics of AI, Faculty of Mathematics, RPTU

stat.ML, cs.AI, cs.LG

Submitted: 2023-10-19

Updated: 2026-10-20

Code: https://github.com/horenkoi/Minimal-Adversarial-Path-

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 83/100

The gist: The gist The mathematical conditions for existence, uniqueness and explicit analytical computation of minimal adversarial paths (MAP) and minimal adversarial distances (MAD) for various AI

Key concepts

Minimal Adversarial Path (MAP): This seeks the shortest path of input perturbations that causes the largest possible change in an AI model's output. Finding this path is crucial for understanding how easily an AI system can be fooled or corrupted by small, targeted changes to its data.
Entropic Perspective on Adversarial Algorithms: This approach uses mathematical entropy to analyze adversarial attacks. It helps prove the conditions for finding globally optimal and unique adversarial attacks using criteria that are mathematically verifiable and computationally cheap, moving beyond complex assumptions.
Self-Attacking Learning Algorithms: These algorithms generate their own optimal training data points. Instead of relying on massive external datasets, they use this mathematical criterion to replace existing agents with new, better data points, allowing for the training of much simpler and cheaper models.
Biomedical Applications in Control: The MAP concept is applied to medical problems like heart attack lethality classification. It allows for the calculation of minimal therapeutic interventions—the smallest changes needed to reduce risk beyond a certain threshold—providing interpretable, guaranteed safety measures.

Terminology

Benchmark — 1× in this paper · explained in 2 episodes

Summary

The gist The mathematical conditions for existence, uniqueness and explicit analytical computation of minimal adversarial paths (MAP) and minimal adversarial distances (MAD) for various AI classifiers are formulated and proven, with practical demonstrations on synthetic benchmarks and biomedical data.

Adversarial Attacks and Mathematical Bottlenecks

Understanding the nature of AI systems is increasingly important due to very small changes in the input data - practically non-perceptable for humans - could be used for a complete corruption of the AI classification outcomes <ref:2310.14421#pg3>. Adversarial attacks involve finding an adversarial vector X∗ that is as close as possible to the given vector X in terms of some distance measure dist(X, X∗) such that PL∗ (X∗) is attaining its maximal value for L∗ ≠ L <ref:2310.14421#pg3>. However, mathematical properties like existence, uniqueness and numerical scalability of adversarial problems solutions remain a major bottleneck, requiring a fulfilment of very strong assumptions like strong Lipschitz-convexity of the class affiliation probability function PL(X) <ref:2310.14421#pg4>. Even for basic AI benchmarks-like for a very common double-spiral Swiss roll example - class affiliation probability functions are non-convex <ref:2310.14421#pg4>.

Minimal Adversarial Path (MAP) Formulation

For a given feature vector X with label L, accessible features subset da, and a class affiliation probability function PL(X), the minimal adversarial path (MAP) is sought as a solution to an optimization problem defined by finding X˜ such that dist(X, X˜) is minimized subject to constraints on the change in probability and control variables <ref:2310.14421#pg4>. The minimal adversarial distance measure MADL(X, δ) is then defined as a length of this path <ref:2310.14421#pg4>. Assuming local unique-invertibility, the problem can be rewritten as a convex constrained regularization problem (4-5) using a penalty method <ref:2310.14421#pg4>.

Analytical Solutions for Generalized Linear Models (GLM)

Under certain conditions summarized in Theorem 1, the regularized problem (4-5) can be solved explicitly, resulting in a closed-form analytical solution for X∗ϵ,δ <ref:2310.14421#pg5>. For GLMs like logistic regression, where the classifier function is uniquely invertible with respect to the scalar product θT X, the solution takes an explicit form involving terms related to C(δ, X) and theta <ref:2310.14421#pg6>. This solution can be computed with a cost scaling of O(D) <ref:2310.14421#pg6>.

Scalable Methods for Entropic AI (EAI)

For advanced AI method families, such as Deep Learning Neuronal Networks with linear ReLU transfer functions and entropic AI methods, the classifier functions are piecewise-linear in X <ref:2310.14421#pg7>. For the Scalable Probabilistic Approximation algorithm (eSPA), which minimizes the learning functional LeSPA, MAP and MAD computation conditions for existence, uniqueness and computational scalability are given by Theorem 2 <ref:2310.14421#pg9>. This involves finding a minimum of the shortest distances between X and (K − 1) convex piecewise-linear polytops defined by the inequality constraints (18) <ref:2310.14421#pg9>. The computational cost scales polynomially in dimension D and linearly in the number K of eSPA Voronoi cells <ref:2310.14421#pg9>.

Biomedical Applications

In biomedical applications, MAP provides unique minimal patient-specific risk-mitigating interventions in the predefined subsets of accessible control variables <ref:2310.14421#pg4>. For instance, in heart attack lethality classification, computed MAPs allow for an interpretable and mathematically guaranteed minimal therapeutic intervention that reduces risk beyond a certain threshold δ <ref:2310.14421#pg10>. Results demonstrated that approximately 48% of insurance claiming individuals could have avoided claims only through an appropriate adjustment of BMI, number of daily steps, and smoking status <ref:2310.14421#pg10>.

Conclusion

The paper establishes two theorems providing explicit analytically-solvable expressions for a minimal adversarial path in generalized linear models and locally uniquely-invertible classifiers, as well as providing straightforwardly-verifiable mathematical conditions and polynomially-scalable strongly-convex Quadratic Programming solvers for the optimal control and minimal adversarial path computation in entropic AI <ref:2310.14421#pg12>. The computational cost of the problem scales polynomially in dimension D and linearly in the number K of eSPA Voronoi cells <ref:2310.14421#pg9>. The results show that eSPA provides a superior prediction of cases on test data, achieving AUC=0.98 for one application <ref:2310.14421#pg10>. This work offers an alternative approach to adversarial attacks based on entropic AI and provides interpretable insights into optimal interventions <ref:2310.14421#pg10>. The code implementing MAP and MAD computations is provided at https://github.com/horenkoi/Minimal-Adversarial-Path- <ref:2310.14421#pg10>. Medical data used in the examples are available at https://www.kaggle.com/datasets/easonlai/sample-insurance-claim-prediction-dataset and https://www.kaggle.com/datasets/andrewmvd/heart-failure-clinical-data <ref:2310.14421#pg10>. The author thanks Rupert Klein (FU Berlin) for very motivating and helpful discussions <ref:2310.14421#pg10>. The references cover foundational work on adversarial attacks, numerical optimization, and scalable machine learning methods <ref:2310.14421#pg10> to <ref:2310.14421#pg10>. The paper is available on arXiv as 2310.14421v4 [stat.ML] 5 Nov 2023. The paper is available at https://doi.org/10.1073/pnas.2214972120. The paper is available at https://www.pnas.org/doi/pdf/10.1073/pnas.2119659119. The paper is available at https://proceedings.mlr.press/v202/wang23g.html. The paper is available at https://www.bibsonomy.org/bibtex/2c05d22504b2f52da8a72d854b5043004/wvdaalst. The paper is available at https://www.kaggle.com/datasets/easonlai/sample-insurance-claim-prediction-dataset. The paper is available at https://www.kaggle.com/datasets/andrewmvd/heart-failure-clinical-data. The paper is available at https://direct.mit.edu/neco/article-pdf/34/5/1220. The paper is available at https://www.pnas.org/doi/pdf/10.1073/pnas.2214972120. The paper is available at https://www.pnas.org/doi/pdf/10.1073/pnas.2119659119. The paper is available at https://proceedings.mlr.press/v202/wang23g.

Improvements for AI systems

Precise minimal risk mitigation in biomedical applications: For health insurance claim predictions, MAP provides unique minimal patient-specific risk-mitigating interventions in the predefined subsets of accessible control variables. This allows for identifying exactly which combination of features (like smoking status, BMI, and steps) must be adjusted to reduce claims risk by a specific threshold delta.
Scalable adversarial robustness for complex models: For entropic AI methods like eSPA, the system can compute minimal adversarial paths and distances with a computational cost scaling polynomially in dimension D and linearly in the number K of eSPA Voronoi cells. This makes robust analysis feasible even for high-dimensional feature spaces.
Interpretable control strategies: The method yields interpretable - and mathematically-guaranteed minimal (due to the above Theorem 2) therapeutic intervention by identifying the optimal feature adjustments that maximize label probability changes under strict constraints.

Abstract

Behind the general terms like adversarial attacks and generative adversarial networks (GANs), such criteria as AI resilience and AI robustness gained a crucial importance, in trying to make the emergent AI tools reliable, energy-efficient and safe. From mathematical perspective, these problems boil down to finding a mathematically-sound quantification of the smallest-sufficient amounts of the perturbations of function arguments that lead to the largest possible perturbations of the approximated function values. Here, the entropy-optimising perspective on adversarial algorithms from Artificial Intelligence (AI) is proposed to attack this problem. It is shown that adopting this perspective helps proving computational conditions for the global optimality and uniqueness of adversarial attacks based on cheaply-verifiable mathematical criteria. Further, it is shown how this perspective can be used for developing self-attacking learning algorithms, that generate optimal new data points for training, replacing one of the trained agents with this mathematical criterium. On a broad selection of various synthetic and real-life problems from hydrodynamics and biomedicine, it is shown that such self-attacking learning algorithms allow training orders-of-magnitude simpler and cheaper models with superior performance - and can be used to directly train the optimal controls in complex systems, requiring only a small fraction of the training data and outperforming the as-comprehensive-as-the-author-was-able-to-find set of contemporary AI tools (like boosted Random Forests, deep neural networks, foundational models based on transformer architectures, etc.) in complexity (measured as the model descriptor length) and predictive performance.