PaperlayerView exact revision on arXiv

Source-linked AI summary

Representation Learning for Exact Preimages

Konstantin Hess, Stefan Feuerriegel

arXiv:2609.32018v1cs.LG

TL;DR

Expressive predictors make it difficult to recover and optimize over the complete set of inputs meeting a target. TRIO uses radial preimage factorization to represent learned preimages explicitly and reuse them for downstream optimization. The paper reports exact geometric representations, a closed-form global solution for linear objectives, and broad approximation guarantees.

  • Problem

    For expressive predictors, complete target-level preimages are typically not explicit and are costly to recover or optimize over, creating a challenge across prediction, preimage approximation, and downstream optimization.

    Source: §1 · p. 1

  • Method

    TRIO factors preimages through expressive radial transformations that reduce to scalar radii under inversion, yielding explicit finite unions of ellipsoidal regions.

    Source: §1 · p. 2, §4.1 · p. 5

  • Results

    TRIO provides exact finite-union preimages, closed-form global solutions for linear objectives, universal approximation, and empirically accurate preimages with faster exact inverse optimization.

    Source: §1 · p. 2, §4.1 · p. 5, §4.2 · p. 6

  • Takeaways & Limitations

    The explicit learned preimage representation can be reused for set queries and downstream optimization, including for non-injective predictors with disconnected or nonconvex preimages.

    Source: §1 · p. 2

    Exactness applies to the learned predictor’s preimage and does not guarantee agreement with the unknown ground-truth preimage.

    Source: §3 · p. 3

Abstract

from arXiv · show

Modern neural predictors can model highly nonlinear maps, but many scientific and engineering tasks require reasoning in the opposite direction: given a performance or safety level, the goal is to characterize the preimage, that is, the complete set of inputs which meet the desired target level and optimize over that set. For expressive neural predictors, however, such preimages typically have no explicit representation and are expensive to recover or optimize over. This creates a fundamental three-way challenge between expressive forward prediction, accurate preimage approximation, and tractable optimization over the preimage for downstream tasks. We introduce TRIO (tractable representations for preimage learning and inverse optimization), a framework for learning representations that make these objectives compatible by construction. Our key contribution is a preimage factorization: the forward model remains expressive through nonlinear radial transformations (including neural networks), while, under inversion, each transformation reduces to a single scalar radius, which yields simple geometric level sets. This yields an explicit geometric representation that is reusable for downstream optimization over the preimage, and, for linear objectives, we show that this admits a closed-form global solution. We finally prove a universal approximation theorem which shows that TRIO can approximate any continuous forward map and its entire family of potentially disconnected, nonconvex preimages arbitrarily well. Hence, TRIO combines expressive forward modeling, exact preimage recovery, and tractable global downstream optimization over preimages by design.

1 INTRODUCTION

Science and engineering often require finding and optimizing over all inputs that meet a target, but expressive predictors make those preimages costly to recover. TRIO addresses this challenge with explicit preimage geometry designed to support expressive prediction and tractable downstream optimization.

1 INTRODUCTION

  • TRIO addresses the three-way challenge of expressive prediction, accurate preimage approximation, and tractable optimization by explicitly representing complete learned preimages for reuse.These preimages can be nonconvex or disconnected, without requiring convexity or invertibility.Source: §1 · pp. 1–2
  • TRIO’s preimage factorization lets expressive radial transformations collapse to scalar radii during inversion, yielding exact finite geometric preimages.The forward radial transformations may be parametrized by neural networks.Source: §1 · p. 2
  • The contributions include globally exact downstream optimization over the learned preimage, with a closed-form global solution for linear objectives.The paper also claims exactness of the finite-union representation for every target level.Source: §1 · p. 2
  • TRIO’s universal approximation theorem covers any continuous forward map and its complete family of target-dependent preimages.The claimed approximation can be arbitrarily accurate.Source: §1 · p. 2
  • The paper reports that TRIO learns accurate forward predictors and preimages while substantially accelerating exact inverse optimization over baselines.Source: §1 · p. 2

2 RELATED WORK

Prior approaches address preimage recovery, inverse optimization, and architecture design largely as separate problems. TRIO instead combines expressive prediction, explicit reusable preimages, and tractable optimization without requiring convexity or bijectivity.

2 RELATED WORK

  • Prior work studies preimage recovery, inverse optimization, and architectures for tractable inverse reasoning as three separate directions.The paper identifies approaches that jointly address all three as missing.Source: §2 · pp. 2–3
  • Post-hoc methods approximate whole preimages using backward constraint propagation, branch-and-bound, relaxations [Zhang et al., 2025; Bj¨orklund et al., 2026], probabilistic approximation, or targeted refinement.The paper characterizes these methods as computationally costly.Source: §2 · p. 2
  • Embedding learned predictors in inverse optimization can require nonlinear, mixed-integer, or global methods, while each objective still faces an implicitly defined feasible set.Examples include gradient-based optimization [W¨achter & Biegler, 2006], mixed-integer formulations, and global optimization.Source: §2 · p. 2
  • ICNNs impose convexity, while invertible networks and flows impose bijectivity.These restrictions do not capture complete preimages when mappings are non-injective, nonconvex, or disconnected.Source: §2 · p. 3
  • TRIO combines expressive predictors with exact, explicit, reusable preimages and tractable global optimization over ellipsoidal regions.The paper presents this as addressing the research gap while preserving universal forward and backward approximation.Source: §2 · p. 3

3 SETUP

The setup treats prediction as learning an unknown, potentially nonlinear and non-injective function over an admissible input domain. It defines target-level preimages and frames learning around forward prediction, preimage approximation, and downstream optimization without convexity or injectivity assumptions.

3 SETUP

  • The setup denotes the admissible input domain by X ⊆ R^d and the unknown, potentially nonlinear and non-injective function by f: X → R.Source: §3 · p. 3
  • For target level g, the preimage is the set of inputs whose outputs lie in the lower output set (−∞, g], and these sets are nested as g increases.The setup identifies this mapping of target levels to preimages as inducing a Galois connection.Source: §3 · p. 3
  • The learning goal is accurate forward prediction, approximation of the corresponding preimages, and tractable optimization over them, including when preimages are nonconvex or disconnected.The downstream task is to minimize an objective over inputs satisfying f(x) ≤ g.Source: §3 · p. 3
  • TRIO aims to represent learned preimages exactly, explicitly, and reuseably for querying and globally exact downstream optimization without post-hoc recovery, repeated predictor optimization, or convexity and invertibility assumptions.Here, exactness refers to the learned predictor’s preimage, not agreement with the unknown ground-truth preimage.Source: §3 · p. 3

4 TRIO

TRIO parameterizes forward prediction so that each target-level preimage has an exact finite geometric representation. That representation supports global optimization over the preimage, while the theory also establishes approximation guarantees for forward maps and their preimages.

4.1 EXACT PREIMAGE FACTORIZATION WITH TRIO

  • For any target, TRIO represents the preimage exactly as a finite union of at most Q ellipsoids, with each active radial transformation reduced to a scalar radius.The result holds independently of training accuracy or generalization.Source: §4.1 · p. 5

4.2 EFFICIENT OPTIMIZATION OVER LEARNED PREIMAGES

  • For X = R^d and a linear objective, evaluating a closed-form solution for each active ellipsoid yields a global optimum over the complete, potentially disconnected preimage.More generally, when X and the objective are convex, optimization over the full preimage reduces to finitely many convex problems.Source: §4.2 · p. 6

4.3 UNIVERSAL APPROXIMATION THEOREM

  • A finite TRIO predictor can approximate any continuous forward function and its sublevel-set preimages arbitrarily well, with the preimage inclusions bounded by an arbitrarily small target-level shift.The guarantee holds for a restricted subclass with a shared quadratic coefficient.Source: §4.3 · pp. 6–7
  • For Lipschitz targets, TRIO has a constructive uniform approximation rate of O(Q^-1/d) in the number of radial components Q.The approximation guarantee also holds without expressive radial transformations or learned anisotropic metrics, and one trained predictor supports queries over a continuum of target levels.Source: §4.3 · p. 7

5 EXPERIMENTS

Experiments test forward prediction, preimage reconstruction, and downstream optimization against neural baselines with matched parameter counts, then evaluate an AC power-flow application. They also show that the geometric preimage can be reused across downstream queries after a one-time factorization cost.

5 EXPERIMENTS

  • With a fixed neural backbone, increasing Q from 16 to 256 progressively improves geometric reconstruction and recovers finer nonconvex structures.Different target levels activate different components of the same trained predictor.Source: §5 · p. 7, Figure 4 · p. 7
  • As parameter count increases, TRIO’s forward RMSE quickly approaches the MLP’s, while a same-sized ICNN develops a large performance gap.The comparison varies Q and reports the ratio of forward RMSEs.Source: Figure 5 · p. 7, §5 · p. 8
  • TRIO’s exact preimage reaches 0.96 IoU and takes 0.01 s, while PREMAP2 reaches 0.80 IoU at a larger refinement budget and takes 228.29 s at B = 2048.The table compares exact preimage representation with post-hoc recovery.Source: §5 · p. 8, Table 2 · p. 8
  • For increasingly nonlinear settings, TRIO has the best forward accuracy from p = 6 onward and the highest preimage IoU across all p, with a larger IoU advantage at higher p.The reported metrics are forward RMSE and preimage IoU.Source: §5 · p. 8, Table 3 · p. 8
  • TRIO achieves the lowest objective regret and constraint violation, with substantially lower per-query runtimes than optimization through unrestricted neural predictors.The comparison uses projection onto the learned preimage.Source: §5 · pp. 8–9, Figure 6 · p. 9
  • With Q = 128, downstream optimization remains at 14 ms/query as backbone size grows from 1.2K to 500K parameters, with less than 3% variation.Increasing backbone size slightly raises only the one-time scalar inversion cost.Source: §5 · p. 9, Table 4 · p. 9
  • TRIO alone is AC-feasible and globally optimal across all runs, solving in 7 ms and running 32×–3,855× faster than neural baselines.The criteria are feasibility under the AC power-flow simulator and global optimality for the learned predictor.Source: Table 5 · p. 9, §5 · p. 9

A.1 ARMOTIZED FACTORIZATION

  • TRIO pays the radial-transformation cost once to construct each target’s preimage; later queries reuse its finite geometry without reevaluating those transformations.This amortization becomes negligible when many downstream queries use the same target geometry.Source: §A.1 · p. 12

A.2 APPROXIMATION RATES

The approximation results tie forward error and preimage accuracy to the geometric covering resolution, then give a rate in the number of experts. On bounded d-dimensional domains, the restricted TRIO class achieves a constructive O(Q^-1/d) forward approximation rate.

A.2 APPROXIMATION RATES

  • A covering resolution h yields uniform forward error at most Lh and target-space preimage error of size Lh across all target levels.The same resolution therefore controls both approximation guarantees.Source: §A.2 · p. 13
  • Corollary A.3 expresses the bound through the optimal covering radius hQ(X) using Q centers.Source: §A.2 · p. 13
  • On bounded d-dimensional domains with standard covering-number scaling, the restricted TRIO class achieves the constructive rate ∥Fθ −f∥∞= O(Q−1/d).Source: §A.2 · p. 13

A.3 FROM FORWARD ERRORS TO OPTIMIZATION GUARANTEES

A forward-error bound yields tightened and relaxed learned preimages that enclose the ground-truth feasible set, supporting a feasible solution and a computable suboptimality guarantee. The appendix also describes the backward map and establishes density of a restricted TRIO subclass.

A.3 FROM FORWARD ERRORS TO OPTIMIZATION GUARANTEES

  • The tightened learned preimage contains only ground-truth feasible points, while the relaxed learned preimage contains every ground-truth feasible point.The explicit enclosure propagates to downstream optimization and gives a ground-truth-feasible solution with a computable global guarantee.Source: §A.3 · p. 14
  • The solution's ground-truth suboptimality is bounded by the difference between the tightened- and relaxed-level learned optimal values.Source: §A.3 · p. 14

A.4 A GALOIS PERSPECTIVE

  • For any scalar predictor, the backward map from target levels to input sets is canonical; TRIO makes that map explicitly representable as a finite set.Source: §A.4 · p. 15

A.5 HELPING LEMMAS

  • The restricted isotropic quadratic TRIO subclass is dense in C(X) under the uniform norm.Source: §A.5 · p. 15

B PROOFS

The proofs establish an exact finite-union preimage representation and derive global optimization by solving over its active regions. They also prove that restricted TRIO predictors can approximate continuous functions and their preimages.

B PROOFS

  • The learned preimage is a union of active expert regions, with membership requiring at least one active component.The finite union holds at extended target levels as well, with empty and full-set endpoint cases.Source: B PROOFS · p. 16
  • For a linear objective, the globally optimal value over the generally nonconvex preimage comes from evaluating one closed-form scalar expression per active expert and taking the minimum.Source: B PROOFS · pp. 18–19
  • A single finite TRIO predictor can approximate a continuous function while approximating its entire family of sublevel-set preimages up to an arbitrarily small target-level shift.The result holds in the restricted subclass with identity metrics and a shared quadratic coefficient.Source: B PROOFS · p. 20
  • The suboptimality certificate bounds the ground-truth optimality gap by the difference between relaxed- and tightened-level learned optima.Source: B PROOFS · p. 24
  • The proofs establish that the restricted isotropic quadratic subclass is dense in C(X) under the uniform norm.Source: B PROOFS · p. 26

C.1 DATA-GENERATING PROCESSES AND DATASETS

The experiments use two analytic benchmarks with dense ground-truth preimage evaluation and a nonlinear AC power-flow simulator. The benchmarks span nonconvex and increasingly multimodal preimage geometries.

C.1 DATA-GENERATING PROCESSES AND DATASETS

  • The study evaluates three regression-to-preimage problems: two with analytic ground truth and one using a nonlinear AC power-flow simulator.Table 6 summarizes the domains, data construction, and ground-truth evaluation.Source: §C.1 · p. 27, Table 6 · p. 27
  • The Six-Hump Camel benchmark provides a low-dimensional, strongly nonconvex landscape whose true preimage can be densely visualized.The independent grid is used for ground-truth preimage IoU and auditing extracted preimages.Source: §C.1 · p. 27
  • Increasing the complex-power exponent p produces increasingly oscillatory and multimodal sublevel sets, separating forward approximation from preimage recovery under rising geometric complexity.Figure 7 shows disconnected preimages at different target quantiles and indicates that TRIO can approximate them arbitrarily closely.Source: §C.1 · p. 27, Figure 7 · p. 28
  • The Pandapower benchmark uses a frozen nonlinear AC power-flow simulation for labels and physical-feasibility checks of optimized designs.There is no dense high-dimensional ground-truth grid; global optimality certificates apply only to the learned constraint.Source: §C.1 · pp. 28–29

C.2 TRIO ARCHITECTURES

TRIO combines learned centers and positive-definite quadratic forms with strictly increasing radial functions, so each target-level preimage compiles to a finite union of ellipsoids. Its architectures use different radial backbones across benchmarks, while baseline architectures are parameter-matched where capacities are compared.

C.2 TRIO ARCHITECTURES

  • Each expert combines a learned center and positive-definite quadratic form with a strictly increasing radial function, producing a minimum-envelope predictor.The quadratic form is parameterized through a Cholesky factor; the radial map is anchored and its positive linear component ensures strict monotonicity.Source: §C.2 · pp. 29–30
  • For a fixed target, each active expert’s strictly increasing radial function is inverted once, leaving a detached quadratic representation for membership and downstream optimization.After compilation, those operations require no radial-network evaluation.Source: §C.2 · p. 29
  • The complex-power benchmark uses 128 Broken-Power experts and 1,152 trainable parameters, while Six-Hump Camel uses an anchored monotone Wide-Tanh radial map with eight Tanh units per region.The Pandapower implementation uses the same monotone neural-radial principle with 32 Tanh units per expert.Source: §C.2 · pp. 29–30, Table 7 · p. 29
  • For neural Wide-Tanh variants, half the expert centers use farthest-point sampling across the normalized training set and half use sampling restricted to low-target training points.The training-only initialization is used for Six-Hump Camel and Pandapower; complex-power experiments retain standard Broken-Power initialization.Source: §C.2 · p. 30

C.3 NEURAL BASELINES

  • Baseline widths are chosen to closely match TRIO’s trainable parameter count, with Six-Hump Camel baselines adjusted separately for each expert count.The compared baselines include ReLU CPWL MLPs, Tanh Smooth MLPs, and Softplus ICNNs.Source: §C.3 · p. 31, Table 8 · p. 31, Table 9 · p. 31

C.4 TRAINING HYPERPARAMETERS

All predictors use direct scalar mean-squared-error training with Adam in double precision. TRIO begins with a soft minimum over experts before switching to its hard minimum; baselines use the same initial training shield while training their standard forward maps.

C.4 TRAINING HYPERPARAMETERS

  • All predictors are trained by direct scalar mean-squared error using Adam in double precision, with shared core optimization settings across benchmarks.Table 10 summarizes the shared training hyperparameters.Source: §C.4 · p. 31, Table 10 · p. 31
  • TRIO anneals its soft-min temperature from 0.20 to 0.01 over 120,000 steps, then switches to the hard minimum; validation and reported checkpoints use the hard predictor.Baselines use the same 120,000-step shield before early stopping and checkpoint eligibility while training their standard forward maps throughout.Source: §C.4 · p. 31

C.5 PREIMAGE EXTRACTION AND DOWNSTREAM OPTIMIZATION

The section describes how learned preimages are extracted and optimized, including TRIO’s explicit ellipsoid representation and the procedures used for comparison. It also distinguishes optimization guarantees for learned constraints from physical feasibility in the Pandapower simulation.

C.5 PREIMAGE EXTRACTION AND DOWNSTREAM OPTIMIZATION

  • TRIO represents the complete learned preimage as a finite union of ellipsoids, enabling downstream optimization without evaluating the neural predictor.For complex-power projection, the global solution is found by solving each active ellipsoid’s projection problem and selecting the candidate with smallest distance.Source: §C.5 · pp. 32–33, Table 11 · p. 32
  • At Six-Hump Camel Q = 64 and g = 0.4, TRIO’s model-relative extraction coverage is exactly one; the comparison uses PREMAP2’s certified inner approximation of a parameter-matched CPWL MLP.Certificates are checked on a 1201×1201 evaluation grid, and construction times measure once-per-target extraction rather than subsequent membership queries.Source: §C.5 · p. 32
  • Complex-power projection queries cover three target levels with true sublevel-set masses of 0.2, 0.5, and 0.8, with 20 truly infeasible queries per level and power.The same queries are used across predictors and model seeds.Source: §C.5 · p. 32
  • For Pandapower, the threshold is calibrated on validation data by choosing the largest candidate with false-feasible rate at most 10^-3, and TRIO optimizes the linear objective globally over the compiled union intersected with [0, 1]^5.With box constraints, violated coordinates are fixed at active bounds and the reduced ellipsoidal slice is solved recursively.Source: §C.5 · p. 33

C.6 EVALUATION CONVENTIONS

  • “Exact” TRIO preimages and optimization certificates concern the frozen learned predictor; physical Pandapower feasibility is determined separately by AC power-flow re-evaluation.Returned designs are converted from normalized coordinates to MW for that simulation.Source: §C.5 · p. 33, §C.6 · p. 34

Related papers

Loading 2609.32018v1…