Scalable and Adaptive Trust-Region Learning via Projection Convex Hull
Authors: Hongyang Jia
Qingchun Hou
Bojun Du
Xiao Cai
Ning Zhang
Chongqing Kang
Venue: ICLR 2026 Poster (2026)
Keywords: Convex hull learning
boundary-tight separation
scalable polyhedral separation
constraint learning
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We introduce Projection Convex Hull (PCH), a scalable framework that constructs boundary-tight convex hulls, enhancing downstream tasks such as selective classification and constraint learning.

Abstract: Learning compact and reliable convex hulls from data is a fundamental yet challenging problem with broad applications in classification, constraint learning, and decision optimization. We propose Projection Convex Hull (PCH), a scalable framework for learning polyhedral trust regions in high-dimensional spaces. Starting from an exact MINLP formulation, we derive an unconstrained surrogate objective and show that, under suitable weight assignments, the optimal hyperplanes of the MINLP are recovered as stationary points of the surrogate. Building on this theoretical foundation, PCH adaptively constructs and refines hyperplanes by subregion partition, strategic weight assignment, and gradient-based updates, yielding convex hulls that tightly enclose the positive class while excluding negatives. The learned polyhedra can serve as geometric trust regions to enhance selective classification and constraint learning. Extensive experiments on synthetic and real-world datasets demonstrate that PCH achieves strong performance in accuracy, scalability, and model compactness, outperforming classical geometric algorithms and recent optimization-based approaches, especially in high-dimensional and large-scale settings. These results confirm the value of PCH as a theoretically grounded and practically effective framework for trust-region learning. Codes are available at https://github.com/IDO-Lab/trust-region-pch.

Published as a conference paper at ICLR 2026
SCALABLE AND ADAPTIVE TRUST-REGION LEARNING VIA PROJECTION CONVEX HULL
Hongyang Jia', Qingehun Hou? Bojun Du' Xiao Cai*, Ning Zhang' Chongqing Kang' 'Department of Electrical Engineering, Tsinghua University
PZJU-UIUC Institute, Zhejiang University
Department of Electrical and Electronic Engineering, The University of Hong Kong [jhy21, dubj24 24 J0 1s. tss.ssssie.. tsinghua, edu. en (ningzhang, cqkang) @t @ts inguua. edu. cn
houqingchun ju. edu. cn, caix0hku. hk
ABSTRACT
Learning compact and reliable convex hulls from data is a fundamental yet chal- lenging problem with broad applications in classification, constraint learning, and decision optimization. We propose Projection Convex Hull (PCH), scalable framework for learning polyhedral trust regions in high-dimensional spaces. Start- ing from exact MINLP formulation, we derive unconstrained surrogate ob- jective and show that, under suitable weight assignments, the optimal hyperplanes of the MINLP are recovered stationary points of the surrogate. Building on this thcoretical foundation, PCH adaptively constructs and refines hyperplanes by subregion partition, strategic weight assignment, and gradient-basee yielding convex hulls that tightly enclose the positive class while excluding nega- tives. The learned polyhedra tive classification and constraint learning. Extensive experiments on synthetic and real-world datasets demonstrate that PCH achieves strong performance in accu- racy, scalability, and model compactness, outperforming classical geometric algo- rithms and recent optimization-bait based approaches, especially in nigh-dimensional and large-scale settings. These results confirm the value of PCH as theoretically grounded and practically effective framework for trust-region learning. Codes are available at https:: //g:t hubb com/ IDb- rust. regi on-goon-cchh
updates,
as geometric trust regions to enhance selec-
INTRODUCTION
Convex hulls provide fundamental geometric representation for modeling data boundaries (Preparata & Shamos, 2012), with broad applications in binary classification (Astorino et al. [02T]] 2023), constraint learning (Fajemisin et al. 2024; Maragno et al.] (025), and decision optimization (Shen et al.) 2023). In particular, when used trust regions, convex hulls guarantee the inclusion of all positive samples while excluding infeasible regions, thereby characterizing the reliable domain of classification model or defining data-supported feasibility sets in prescriptive decision-making Classical computational geometry algorithms, e.g.. QuickHull (QH) and its variants (Barber et al., 1996 Tzeng & Owens 2012 Goodrich & Kitagawa 2024). construct exact convex hulls in low dimensions, but their complexity grows exponentially with dimensionality, and their facet-based rep- resentations offer little flexibility in controlling the number or arrangement of hyperplanes. These limitations make them unsuitable for modern learning tasks where convex hulls must be compact, controllable, and scalable serve as effective trust regions under label- based supervision.
Recently, data drivaadriennnnn approaches have been proposed to directly learn convex hulls from labeled data (Balestriero et al. 2022. Jia et al. 2024). Projection- based methods (López et al. 201 construct decision boundaries from extreme- point representations, but rely on global geometric operations that do not scale to large datasets. Multi-hyperplane classifiers (Raviv et al. 2018)) improve flexibil- ity by combining multiple linear components, yet offer limited structural regularization and cannot control model complexity. Mixed-integer programming (MIP) formulations (Barbato et al., 2024)
Corrrsponning Authors

---

Published as a conference paper at ICLR 2026
explicitly constrain the number of hyperplanes, but their reliance binary variables quickly be- comes intractable in high dimensions. Across these directions, existing methods still fail to address three fundamental requirements for trust region modeling: (i) scalability to high- sigh-dimensional data, (ii) boundary tightness to align with positive class boundaries, and (iii) structural adaptivity to match data complexity. Moreover, most approaches remain heuristic in nature and lack theoretical foundations that guarantee reliable trust regions, which is crucial in safety-critical applications.
Motivated by these gaps, we ask: Can we learn convex hull that tightly encloses the positive class while excluding as many negatives as possible, under a limited budget of supporting hyperplanes? To that end, our approach builds on the observation that complex nonlinear decision boundaries admit locally linear approximations, allowing each subregion to be modeled efficiently by a supporting hyperplane. Based on theoretical foundation and starting from mixed-integer nonlinear program (MINLP) that characterizes the tightest hull, we derive an unconstrained surrogate objective enabling scalable gradient- based updates. After each update, redundant hyperplanes are pruned, whereas new ones introduced to further refine the boundary and exclude residual negatives. In practice, the surrogate guides hyperplanes toward class boundaries during training, yielding boundary-tight hulls. Together, these ideas form divide-and-conque framework, termed Projection Convex Hull (PCH), which is scalable, adaptive, houndary-tighh and theoretically motivated. An overview of the framework is provided in Figure T and its behavior in 2D illustrated in Figure
Hyperptane
Hyperpione
Hyperplane
Hyperpione
subregions hyperplane
High-dimensionl and lango- scalle uniining datisct
Sabresion
Suhnegins 2
Suhrogion
Salvagion
Design the loss to guide each hyperplane converge laward the boundary the final irust region
and
Loes
Loss 2
Lass
Loss
Gradient descent
combine
Hsperplane
Hyperplase
Hyperpianc
Hypeelanee
Figure Overview of the PCH framework. At each iteration, data are partitioned into subre- gions assigned to hyperplanes, which are updated by gradient descent on the surrogate objective; hyperplanes are dynamically added or pruned, and the final convex hull is obtained by combining the active hyperplanes.
Intakariic
leaid Kuragin patiians
wwwce doceri
Fied abtggin
CD Fial Newes
Figure 2: Illustration PCH training in 2D. Hyperplanes are initialized and iteratively updated through iterative subregion refinement and surrogate optimization, yielding compact convex hull.
Technically, summarize key contributions follows:
2

---

Published as a conference paper at ICLR 2026
1) A principled formulation. We establish link between the intractable MINLP for tight convex hull learning and an unconstrained surrogate objective, providing a theoretically motivated founda- tion for scalable convex hull learning.
2) A scalable wwvid-aadd-ooquee framework. We develop PCH, which iteratively refines subre- gions and their associated hyperplanes through gradient-basse based updates. The framework incorporates (i) partition-base subregion assignment, (ii) surrogate objective to align hyperplanes with class boundaries, and (iii) adaptive hyperplane pruning and addition.
3) Trust regions for learning and decision-making. The learned convex hulls act as compact and reliable trust regions that can be embedded into classification models and constraint learning pipelines, enhancing both generalization and robustness.
4) Extensive empirical validation. Experiments on synthetic and real-world datasets show that PCH achieves high accuracy, superior scalability, and a significantly more compact structure com- pared to classical geometric algorithms and MIP-based baselines. Figure 3 presents key results on polyhedral datasets.
(a) Model accuracy
(b) Training time
(c) Medel complexity
100
10-
800
150
Figure 3: PCH achieves consistent accuracy with scalaiiitylla and compactness. Across increasing dimensions, our method (PCH) maintains high classification accuracy while requiring significantly less training time and fewer hyperplanes than classical geometric and MIP-based base- lines, i.e., QH from (Barber et al. 1996) and CGHC from (Barbato et al.) 2024).
RELATED WORK
We review three lines of related work: classical convex hull construction, data-driven convex hull learning, and applications of convex approximations in machine learning and optimization.
Classical geometric methods. Traditional convex hull algorithms (Barber et al., 1996] Blelloch et al., 2020) compute exact hulls efficiently low dimensions (Chan) 201 Assart et al., 2017 Gæde et al. 2024 Lv et al. 2025), with strong theoretical guarantees. However, the number of facets grows exponentially with dimension, making them impractical in high-dimensiioal or large- scale settings. Approximation methods such as DCH (Blum al.. 2019) alleviate this by selecting sparse representative subsets, but without label supervision cannot ensure inclusion of all positives. Moreover, classical methods produce vertex- based representations, where facet structure is deter- mined implicitly, offering little control over hyperplane number or arrangement. These limitations motivate data-driven approaches.
Data-driven convex hull learning. Projection-based methods (López et al. 2011 Ding et al., 2017] Leng et al. 2019: Nemirko & Dulá (02T) construct boundaries via nearest- -pointt operations, but scale poorly with dataset size and dimension. Classifier -ased polyhedral models. including multi- hyperplane learners YYujian et al. 2010 Wang et al. 2011 Raviv et al. 2018)) [eng et al. [022] and SVM variants (Fan et al. [2008] Varol et 20.1 Gu et al.
[018,Leng
2018). improve flexibility and efficiency but offer little structural regularization or control over boundary tightness. Optimization based for- mulations provide explicit structure: MIP methods (Zhu et al. 2020; Barbato et al.) 2024 Phan et al. 2024) allow control over hyperplane number and arrangement, but their reliance on binary variables makes them intractable at scale. Our method addresses these gaps through surrogate- based divide-and coneeeand-conngee mon-conquer framework that reduces the global task to local hyperplane updates via gradient descent, avoiding binary enumeration.
3

---

Published as a conference paper at ICLR 2026
Applications in machine learning and optimization. Convex hulls serve trust regions in tasks such as selective classification (Ruano et al., 2015: Khosravani et al. 2016
Fajemisin et al. 2024
and constraint learning (Hou al. 2020 Jia et al., 2024 [Sh et al. 20244 Maragno et al.
2025
Jia et al. 2025). Recent neural methods, such as DeepHull (Balestriero et al. 2022: Liang et al, 2024) and Convex Polytope Tree (CPT) (Armandpour with deep networks, but lack explicit linear constraint form (e.g., Ax 2 6), hindering interpretability and complicating optimization embedding. Moreover, they do not enforce full inclusion of positives, leaving gaps in trust region coverage. Our method instead learns polyhedral hulls through surrogate- based optimization, yielding interpretable constraints, dynamic structural refinement, and boundary- tight trust regions with full positive coverage.
al.) 2021). approximate convex regions
In summary, prior work has explored both geometric approximation and data-driven learning, but challenges remain in achieving scalability, adaptivity, and boundary tightness. Our framework ad- dresses these by linking the exact MINLP formulation with scalable surrogate, enabling gradient- based learning of convex hulls that are both compact and theoretically motivated.
3 PROBLEM FORMULATION
For binary classification dataset D (z) 9:))m with ys E (+1, -1,, model a trust region as a polyhedral convex region ("hull")
C= fz Rd a b. 1, S}.
such that all positive samples D+ = {a+ : y = +1} lie inside C. while as many negatives D
{ry y 11 possible are excluded. We A = la!...., a5} R and b [b] b5]
R to denote the collection of hyperplanes. All notations are summarized in Appendix
A standard formulation is -itked-itteger linear program (MILP; see Appendix [B] that minimizes the number of enclosed negatives subject to full coverage of positives (Barbato et al. 2024). How-
ever, such MILP models primarily target negative exclusion and offer limited control over the light- ness of the learned hull.
To encourage geometric tightness, we introduce margin variables and maximize the separation gap between negatives and the hull boundary via the following problem:
max s.t.
Σ. 5
a²
r₁ b² 2
Va, D4, Vs, Vz, Dout Vs, Vxi E Dout Vs,
a r; bs < - + 5
[ = 0, z E (0,1), 0,
Σ 2 > 1.
Vz, Dout vs,
a = 200
where Dout = D_ cD denotes negatives that lie outside the convex hull of positives. Each (a*, b*) defines hyperplane of C. The variable &* is nonnegative margin controlling the signed distance from hyperplane
the negatives separates, and E tracks violation for sample a,; w.r.t. hyperplane The complementarity constraint 2 E 0 enforces that negative marked as separated by hyperplane s (zf = 1) incurs no violation (C. 0); otherwise nonnegative slack allowed. Requiring Σ. 2
ensures that each x; Doutt is separated by at least one hyperplane. Because of the binary-continuout complementarity and the normalization || = 1, Equation is a MINLP problem.
The MINLP is computationally expensive in high dimensions and at large scale, which motivates re- placing it with unconstrained surrogate objective that preserves the essential geometric structure while enabling efficient gradient-based updates.
THEORETICAL FOUNDATION
Building on the MINLP formulation in Equation 2 we establish its connection to a family of un- constrained surrogate objectives by progressively decoupling it into hyperplane-wise subproblems. The goal of this section is threefold: (i) show that the intractable MINLP can be reduced to per- hyperplane separation problems, (ii) construct unconstrained surrogate objective for gradient
4

---

Published as a conference paper at ICLR 2026
descent, and (iii) characterize the weight assignment conditions under which stationary points of the surrogate recover the optimal hyperplanes of the MINLP. Proof of the theoretical foundation can be found in Appendix C
From MINLP to hyperplane subproblems. For each supporting hyperplane s = I,..., S. let D
foz E D_ 2 }} denote the subset of negatives separated by hyperplane in the optimal MINLP solution. Then each hyperplane (a²,b") solves the following constrained separation problem:
max s.t.
c
a
T2 ba 2 0
Va, E D+ Vx, D2,
T Tj D S -
| 1,
which seeks the tightest separating hyperplane for D while ensuring inclusion of all positives.
Lemma (Decomposition). Let (A*, bb)) be the optimal solution to Equation 2 Then each (a**, "o*h,b" b**) an optimal solution the corresponding subproblem Equation 3
From constrained subproblem to unconstrained surrogate. To obtain an unconstrained surro- gate, we adopt a soft-split loss on the local dataset D := D4 UD2. For a candidate hyperplane (a, b) and sample 2; D we define the surrogate objective as:
((a = 1 (E wiphyn) (a.b)
1 (Σ wrp Eupph
min
Ewit
p 1/ efaa (1b//lll)))
pt 1 (1 e ((b-a a(b-aTaa)/lal)) /
Vz, D=
where 8 > 0 controls the sharpness of the soft split. wi denote weight assigned to Z4- Lemma 2 (Surrogate equivalence). Let (a" b²) solve the construined problem Equation Then there exists a weight assignment {wi} such that (a* (b) is stationary point of the surrogate objec- tive Equation 4
Intuition. At a high level, the stationarity conditions of the surrogate Equation 0f and 0f 00 O. Linear constraints such as
4
require both
Ew: -w,=2 2, Σ mu O, Σwsp 1, Σ Ewiphpfu 0,
(5)
can be seen as enforcing scale and class-balancd moments, which ensure the b-direction stationarity condition (a(a) := min a xx. contrast, the a-direction condition is more involved and can be approximated via the fixed-point relation in Lemma 3 Together, these constraints illustrate how suitable weight assignments allow the surrogate to mimic the objective of maximizing the separation gap in Equation 3
Stationarity and weight assignment. The surrogate admits fixed-point characterization:
Σ wi p.pp ys Ti.
(6)
which coincides with the stationarity condition of f(a, b) once the weights satisfy the linear con- Since pi and 2f depend on a, Equation induces a complex coupling.
straints in Equation 5
Lemma 3 (Sufficient fixed-point condition). If (a, and nonnegative weights fwitiED= satisfy
the fixed-poin relation Equation together with the linear constraints Equation stationary point of the surrogate objective Equation 4
5 then (a. b) is
Theorem (Main result). Let (A*, b²) be the optimal solution to the MINLP Equation Then for each hyperplane (a**,b' bb*), there exists a weight assignment {wf] such that (a be is a stationary point of the surrogate objective Equation 4
Proof sketch. Lemma shows that the MINLP decomposes into hyperplane-wiss subproblems. Lemma 2 establishes that the solution to each subproblem can be realized as a stationary point of the surrogate objective under suitable weights. Normalized weights satisfying Equation 5 ensure stationarity in the b-direction. Lemma33)unn further provides a sufficient condition that guarantees sta- tionarity in the a-direction via the fixed-point relation. Combining these results yields the claim.
5

---

Published as a conference paper at ICLR 2026
These results justify the surrogate- based divide-and andee--u-- framework deseribed next, where suit- able weight assignment strategies allow us to implement the theoretical insights in practice. It is important to note that these theoretical results characterize the structural conditions that any MINLP optimum must satisfy. The surrogate leverages these necessary conditions to guide the hyperplane updates and weight assignment toward geometrically consistent stationary configurations.
5
METHODOLOGY
Our PCH framework (Figure 1 motivated by the observation that complex and nonlinear classi- fication boundaries often exhibit regional linearity and can be locally approximated by hyperplanes with small classification error. Identifying the locations of these regional boundaries is straightfor- ward, and fitting them with linear hyperplanes is computationally efficient. By iteratively optimizing such
hyperplanes and combining them, we construct convex hull that is scalable, structurally adaptive, and geometrically tight. Specifically, the PCH framework operates as follows:
Algorithm Projection Convex Hull (PCH)
Require: Labeled dataset D {(,, y:]}, hyperplane budget S
Ensure:
Compact convex hull (A, b) enclosing D+
1: Initialize hyperplanes {a* ] ===1 using PinCHD
2: while not converged do
3: Place each hyperplane at 6" = b² = min TT
4: Subregion assignment: Build local subregions D by Equation 7
5: Strategic weight assignment: Update weights by gradient step w <- w + 1)
BE(w) followed
by projection Ps (w) in Equation 11
6: Apply one-step gradient descent on surrogate objective Equation to update
7: Adaptive structure adjust: Prune redundant hyperplanes, and introduce new ones to further refine the boundary
8: end while
9: return Final convex hull (A, b)
5.1 SUBREGION ASSIGNMENT
For each hyperplane 8, we build a local working set DD on which the surrogate and the weight assignment are optimized. This realizes the hyperplane-wise decoupling suggested by Lemma without solving the MINLP.
place the hyperplane at the positive support through (aa) min a x, so that the hyperplane touches the convex hull of positives. This choice aligns the surrogate update with boundary tightness. Then, we form banded neighborhood around the hyperplane and enforce feasibility with respect to the other active hyperplanes:
Given normal
D = E m <a ba(a)) sm" A
{
x x=
where A and b- stack all other hyperplanes except hyperplane s. The bandwidths m and m chosen adaptively to include the most informative points and ensure that the projected weight assignment can satisfy the linear constraints in Equation 5
To guarantee that De contains sufficiently informative samples, require it include the top d positive points with the largest split mistake vi(b((a) a xx)). Accordingly, we set m7 using order statistics as
n = partition,aI( aT - b=- EE D+}) + Mshiftt
(8)
where partition ()) ()) denotes the d-th order statistic (i.e., the d-th smallest value), ensuring that least d positives are included. The scalar main is tunable hyperparameter that controls the bias of m. Symmetrically, we obtain m using the same idea. In practice, the absolute value of m typically smaller than m and construction improves numerical stability, ensures feasibility of the weight assignment constraints Equation 5 and empirically avoids degenerate configurations.
the symmetric interval [-m" mm) in Equation 7 This

---

Published as a conference paper at ICLR 2026
5.2 STRATEGIC WEIGHT ASSIGNMENT
Having established in Lemma 2 and Lemma that suitable weights enforce l-direction stationarity and guide a toward the optimum of Equation 3 now formulate principled weight assignment strategy. The goal is to ensure that the surrogate objective Equation remains closely aligned with the constrained separation problem Equation
For each subregion D*, we assign weights w [ by maximizing the separation gap, defined the signed margin between the supporting positive and negative samples along the current a(w):
min a(w)" x,E0+
a(w)aa x1
RGED2
max E(w)
||([W]]
s.t. Cw= d, w E Kg+, W E Kg-, w 1u2 0,
where + and - are isotonic cones that enforce monotonicity of weights within the positive and negative subsets, respectively. Here n and n- represent indices sorted by signed distance Trx (a). These constraints ensure that samples closer the boundary are assigned larger weights, emphasizing the role of support vectors. The linear constraints Cw = d (encoding the four scalar equalities in Equation guarantee b-direction stationarity, while maximizing {(w) aligns the weight assignment with the objective of Equation [
Lemma 3 gives a fixed-point relation a = g(a, w). Approximating da 0a/Ow = 0g tw enables a chain rule for the gradient of the separation gap:
(w)) (E( da Ow; IE, w/ p.p yj x3y
8. (2+ x-) (a T (x+ M] MaTx:) xi))
(10)
Ow:
da
|| 1
where x4 = arg mi a_ x and x arg maX a. Jx.
After a gradient update w t- w + 11 - with gradient update rate y,, the weights may violate the
constraints in Equation [
We restore feasibility through successive projections:
Pp(w) Ps (P (PK,- (P+()))), F= Sn R. m Kg+ 0 KK-,,
(11)
where Ps(w) = CT (CCT)- (C - d) enforces the linear constraints in Equation P. (w) = max(w:, ensures nonnegativity, and Pk PK are isotonic regression operators -doo-addaeeent violators algorithm, PAVA (De Leeuw et al. 2010))
This strategic assignment ensures that dynamically guides toward maximizing the separation gap, thereby aligning surrogate optimization with the constrained objective Equation 3 and yielding boundary-tige updates in practice. Feasibility of the proposed projection method discussed in
Appendix D
5.3 ADAPTIVE STRUCTURE ADJUST
To maintain compactness while preserving boundary tightness, PCH dynamically adjusts the num- ber of active hyperplanes. Addition: if the current hull still encloses negative samples and the hyperplane budget is not exceeded, we add a new hyperplane initialized via a variant of the PinCHD algorithm (Leng al., 2019), with robust negative-sane sample selection strategy (details in Appendix E. Pruning: a hyperplane is removed once all samples in its subregion D lie on the nonnegative side, preventing degeneracy and reducing redundancy. This adaptive mechanism ensures scalability without sacrificing geometric tightness.
5.4 INFERENCE AND DOWNSTREAM USAGE
The overall solving algorithm is summarized Algorithm [ and complexity is discussed in Appendix F Although the surrogate objective is nonconvex, the update rules in Algorithm exhibit a structured alternating behavior: the weight update designed to increase the separation gap, while the subsequent gradient step hyperplane parameters decreases the surrogate objective. This yields a bounded alternating process in which both updates consistently improve the margin-based geometric objective.
7

---

Published as a conference paper at ICLR 2026
Once trained, the convex hull serves a polyhedral trust region that can be directly deployed in downstream tasks. In selective classification, predictions are accepted only if the input lies inside the hull, thereby suppressing overconfident errors outside the data-supported region. In constraint learning, the hull provides an explicit linear-feasibility set (Ax 2 b) that can be embedded into optimization models, and helps the classifier trained on in-hull samples to capture finer constraint boundaries. This combination of convex filtering and learned approximation improves robustness and reduces complexity in safety-critical applications.
EXPERIMENTS
6.1 DATASET CONSTRUCTION
We evaluate trust-region learning under controlled synthetic geometries and real-world tabular data. Synthetic. We consider three families: (i) PH (polyhedral): we sample S random halfspaces whose intersection bounded and label points inside as positive; outside are negative. This yields a target hull with at most S facets. (ii) NLC (nonlinear convex): positives form hypersphere of radius (convex but non-poly poepplyyyerr))... inducing linear-facet approximation error. (iii) NLNC (nonlinear nonconvex): positives are the union of multiple convex components, testing the ability to tightly envelope nonconvex regions under facet budget. denote datasets by type, facet count (if applicable), and dimension, e.g., PH_15_8, NLC_N_1 0, NLNC_N_2. Real-world. We further include representative tabular datasets (c.g., Breast Cancer, Spambase, Bace, HIV).
6.2 EXPERIMENTAL. SETUP
We compare PCH against: QH (Barber et al. 1996). CGHC (Barbato et al. 2024). DCH (Blum
jet al. 2019). PinCHD (Leng et al. 2019), and DeepHull (Balestriero al. 2022). QH provides an exact geometric reference. CGHC controls hyperplane structure via integer variables. DCH selects sparse representative vertices without using labels, approximating QH but without guaran- teeing full positive inclusion. PinCHD serves standalone projection-baser baseline. DeepHull learns implicit convex regions through neural networks, which do not yield explicit linear constraints (Ax 2 6) and do not enforce inclusion of all positives. Accuracy is evaluated in two contexts: trust region learning and downstream classification. For trust region learning, accuracy is defined as the product of the classification accuracy and the positive inclusion rate. For downstream classifica- tion, accuracy refers to the standard test classification accuracy. All experiments are conducted on server equipped with an Intel(R) Core(TM) i9- 10980XE CPU (18 cores, 36 threads) and 64 GB of RAM. Details of the fairness protocol and hyperparameter settings are provided in the Appendix G
6.3 PERFORMANCE ON TRUST REGION LEARNING
We evaluate the performance of different methods to construct accurate and compact trust regions across varying datasets. Table [ reports the trust region accuracy and model complexity on both synthetic geometries and real-world tabular data. Compared with other methods, PCH consistently achieves high accuracy across all dimensions while maintaining constant model complexity. These results demonstrate that PCH achieves high accuracy, scalability, and interpretability simultaneously. It maintains a tight approximation of the target region while remaining computationally feasible un- der -igh-dimensional and large-scale settings. More experimental settings and results are provided in Appendix G.3
G.4
G.5
G.6
Further supplementary analyses are provided in the appendix. Appendix G. examines the behavior of PCH on linearly separable data, while Appendix G.2 visualizes the full optimization trajectory on the 2D example in Figure 2 and evaluates robustness under different random initializations. Ro- bustness to injected noise in polyhedral datasets is analyzed in Appendix G.3 The effect of the hyperplane budget is illustrated in Figure 15 within Appendix G.4, and Appendix G.3 discusses disiccuses the behavior of PCH when the positive region is nonlinear and nonconvex. Finally, Appendix G.9 pro- vides additional comparisons with gradient- gradient-based baselines as well as a detailed ablation study of key components.
8

---

Published as a conference paper at ICLR 2026
Table 1: Comparison of convex hull learning methods controlled synthetic geometries and real-world tabular data. Reported are trust-region accuracy (%) and model complexity (number of hyperplanes). PCH achieves consistent accuracy and controlled complexity, while other methods become inefficient or degrade in high dimensions. A dash indicates that methods fail to scale to the corresponding high-dimensional setting.
Trust-region Accuracy
Model Complexity
Dimemsion Problem
QH
CGHC
DCH
PinCHD DeepHull
PCH
QH
CGHC
DCH
PinCHD
DecpHall PCH
PHLIS.2 15.2
100.00
99.71
97.88
99.80
97.01
100.00
37
15
9
11
15
PHL15_8
100.00
87.59
45.26
95.26
82.01
100.00
2.30E+7
6.18E+6
480
Low
NEC
100.00
99.27
95.24
99.41
97.64
99.40
93
16
24
15
N.NCCN.22
92.15
91.83
91.87
91.86
87.05
92.10
27
27
15
High
PH 15 100 NLC.N.100
57.20
57.95
64.39
99.95
15
1499
15
15
68.89
53.75
75.39
99.01
150
Breast Cancer
99.82
99.82
99.82
99.82
5
Real-
Spambase
86.70
91.41
91.55
94.41
world
Bace
98.35
76.80
97.37
98.61
149
5
6.4 DOWNSTREAM USAGE
We evaluate the benefits of the learned regions in downstream tasks, considering representative scenarios: selective classification and constraint learning. PCH is compared with CGHC, which also enforces positive coverage while explicitly controlling the hyperplane budget.
Selective classification. We combine trust region modeling with base classifiers (CART and MLP) filter predictions based on the learned convex hulls. A superscript indicates that the classifier trained on the full dataset and used with trust region filtering during inference; indicates retraining classifier using only the samples within the learned trust region. Table reports classification accuracy across five datasets. In most cases, combining classifiers with PCH improves performance compared to standalone classifiers and CGHC variants, confirming its effectiveness in suppress- ing unreliable predictions outside the trust region. For MLP models retrained under 3, we apply reweighting scheme during training to assign higher weights to in in-region samples, mitigating poten- tial bias. More experimental settings and classification score results provided in Appendix G.7
Constraint learning. We evaluate the utility of convex hulls in constraint learning, where the hull serves safe approximation of the feasible trust region. Table summarizes feasibility rates and the number binary variables introduced by different constraint learners. PCH consistently improves reliability while reducing constraint complexity. For example, MIP with PCH increases feasibility from 88% to 94% and reduces the number of binary variables from 205 to 35. The trust region modeling results are compared in Appendix G.5 Detailed grid search results for constraint learning are provided in Appendix G.8 Overall, PCH offers scalable and reliable trust region for embedding learned constraints into optimization, improving feasibility, simplicity, and compu- tational tractability.
Table Selective classification performance using classifiers trained with without trust region filtering. integrated classifier trained on the full dataset. f; integrated classifier retrained based on the learned trust region. PCH consistently improves accuracy across most classifiers and datasets.
Trust Region
CART-based Classification
MLP-based Classification
Problem
CGHC
PCH
CGHC! CGHC PCH!
PCH
CGHC! CGHC PCH
PCH#
NC.N.N_2
91.40
91.75
98.30
98.40
98.90
98.35
99.00
94.50
94,80
97.70
95.20
98.30
breast_canser
95.61
97.37
91.23
92.
96.49
91.23
95.61
94.74
92.11
91.23
94.74
93.86
spambase
91.10
91.86
93.16
bace hace_cefp
70.63
78.22
74.92
70.96
72.38
75.58
77.56
74.26
72.28
72.94
77.89
78.55
hiv.ccfp
95.68
95.05
96.89
95.81
95.76
96.77
96.13

---

Published as a conference paper at ICLR 2026
Table 3: Constraint learning and embedding performance using models trained with without trust region filtering. i; integrated constraint learning model trained on the full dataset. f integrated model retrained based on the learned trust region. PCH improves both feasibility and model sim- plicity.
CARF-based construint learning
MLP MLsebased constraint learning
Index
CGHC! CGHC
PCH!
PCH
CGHC CGHC PCH! PCH
Feusibility Rate(S))
49.00 .0
69.00
70.00
$7.00
84.00
72.00
88.00
88
90.00
94.00
93,00
Binary Variable Number
33
30
12
28
CONCLUSION
This paper introduces Projection Convex Hull (PCH), a principled framework for trust region leamn- ing that connects the exact MINLP formulation with an unconstrained surrogate objective. Through subregion decomposition and weight assignment, PCH provides theoretical guarantees, while its algorithm, combining subregion partition, weight projection, and gradient-based updates, yields scalable, adaptive, and boundary-tight convex hulls.
Experiments on synthetic and real-world datasets show that PCH achieves consistent tightness and scalability, while remaining compact and interpretable. Beyond standalone learning, the learned hulls benefit downstream tasks such as selective classification and constraint learning, confirming the practical value of theoretically grounded trust region modeling. Future work may extend PCH to nonconvex decompositions for broader safety- safety-critical applications.
ETHICS STATEMENT
This paper focuses on theoretical modeling and algorithmic development for convex hull-based trust region learning. All experiments are conducted publicly available benchmark datasets (e.g. Breast Cancer, Spambase, Bace, and HIV), which not contain private or sensitive information. The proposed methodology does not raise concerns regarding human subjects, discrimination, se- curity, or other ethical issues. We have carefully adhered to the ICLR Code of Ethics in conducting and reporting this research.
REPRODUCIBILITY STATEMENT
The theoretical foundation of Projection Convex Hull (PCH) is fully developed in Section 4 with
all proofs provided in Appendix C The complete algorithmic procedure is described in Section S with detailed pseudocode in Algorithm T
Experimental settings, datasets, and hyperparameter con- figurations are reported in Appendix G All benchmark datasets used are publicly available, and the construction of synthetic datasets follows explicitly specified procedures. Together, these elements provide comprehensive and transparent description that allows independent reproduction of our results.
ACKNOWLEDGMENTS
This work was supported by the National Key R&D 10990.
Program of China under grant
REFERENCES
Mohammadreza Armandpour, Ali Sadeghian, and Mingyuan Zhou. Convex polytope trees. Ad- vances in Neural Information Processing Systems, 34:5038-500 10103 2021.
Benjamin Assarf, Ewgenij Gawrilow, Katrin Hemr Michael Joswig, Benjamin Lorenz, Andreas Paf- fenholz, and Thomas Rehn. Computing convex hulls and counting integer points with polymake. Mathematical Programming Computation, 9:1-38, 2017.
10

---

Published as a conference paper at ICLR 2026
Annabella Astorino, Massimo Di Francesco, Manlio Gaudioso, Enrico Gorgone, and Benedetto Manca. Polyhedral separation via difference of convex (dc) programming. Soft Computing. 25: 12605-12613, 2021.
Annabella Astorino, Matteo Avolio, and Antonio Fuduli. Maximum-margin polyhedral separation for binary multiple instance learning. EURO Journal on Computational Optimization, 1 11:100070, 2023.
Randall Balestriero, Zichao Wang, and Richard Baraniuk. Deephull: Fast convex hull approxi- mation in high dimensions. In ICASSP 2022-2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3888-3892. IEEE, 2022.
Michele Barbato, Alberto Ceselli, and Rosario Messana. Mathematical programming algorithms for convex hull approximation with hyperplane budget. arXiv preprint arXiv:2407. 17341, 2024.
C Bradford Barber, David P Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Softwrr (TOMS), 22(4):469-45) 1996.
Guy E Blelloch, Yan Gu, Julian Shun, and Yihan Sun. Randomized incremental convex hull is highly parallel. In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithmss and Architectures, pp. 103-115, 2020.
Avrim Blum, Sariel Har-Peled and Benjamin Raichel. Sparse approximation via generating point sets. ACM Transactions on Algorithms (TALG), 15(3):1-16, 2019.
Timothy M Chan. Three problems about dynamic convex hulls. In Proceedings tfe twenty-seventh annual symposium on Computational geometry, pp. 27-36, 2011.
Jan De Leeuw, Kurt Hornik, and Patrick Mair. Isotone optimization in r: pool-adjacent-violato algorithm (pava) and active set methods. Journal of statistical software, 32:1-24, 2010.
Shuguang Ding, Xiangli Nie, Hong Qiao, and Bo Zhang, A fast algorithm of convex hull vertices selection for online classification. IEEE transactions on neural networks and learning systems, 29(4):792-806, 2017.
Adejuyigbe O Fajemisin, Donato Maragno, and Dick den Hertog. Optimization with constraint learning: A framework and survey. European Journal of Operational Research, 314(1):1-14, 2024.
Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. Liblinear: A library for large linear classification. the Journal of machine Learning research, 9:1871-1874, 2008.
Emil Toftegaard Gæde, Inge Li Gørtz, Ivor Van Der Hoog, Christoffer Krogh, and Eva Rotenberg. Simple and robust dynamic two -vo-dimensional convex hull. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pp. 144-156. SIAM, 2024.
Michael T Goodrich and Ryuto Kitagawa. Making quickhull more like quicksort: A simple ran- domized output-sensitive convex hull algorithm. arXiv preprint arX1v:2409.1977 2024.
Xiaoqing Gu, Fu-lai Chung, and Shitong Wang- Fast convex-hull vector machine for training on
large-scale nerna data classification tasks. Knowledge- Basedd Systems, 151:149-164, 2018.
Qingchun Hou, Ning Zhang, Daniel S Kirschen, Ershun Du, Yaohua Cheng, and Chongqing Kang. Sparse oblique decision tree for power system security rules extraction and embedding. IEEE Transactions on Power Systems, 36(2):1605-161) 2020.
Hongyang Jia, Qingchun Hou, Pei Yong, Fei Teng, Goran Strbac, Chen Fang, and Ning Zhang- Learning multiple convex voltage stability constraints for unit commitment. IEEE Transactions on Power Systems, 2024.
Hongyang Jia, Qingchun Hou, Jiawei Zhang. Haiyang Jiang, Ning Zhang, Goran Strbac, Fei Teng, and Chen Fang. Converter- stability constrained generation expansion for high ibg- penetrated power systems. IEFE Transactions Power Systems, 2025.
11

---

Published as a conference paper at ICLR 2026
Alex Kantchelian, Michael C T'sshaatzz, Ling Huang, Peter L Bartlett, Anthony D Joseph, and J Doug Tygar. Large-margin convex polytope machine. Advances in Neural Information Processing Systems, 27, 2014.
Hamid Reza Khosravani, AE Ruano, and Pedro M Ferreira. convex hull-based data selection method for data driven models. Applied Soft Computing, 47:515-533, 2016.
Qiangkui Leng, Shurui Wang, Yuping Qin, and Yujian Li. An effective method determine whether point is within a convex hull and its generalized convex polyhedron classifier. Information Sciences, 504:435-444 448, 2019.
Qiangkui Leng, Zuowei He, Yuqing Liu, Yuping Qin, and Yujian Li. A moft- convex polyhe- dron classifier for nonlinear task with noise tolerance. Applied Intelligence, 51:453-466 2021.
Haojian Liang, Shaohua Wang. Song Gao, Huilai Li, Cheng Su, Hao Lu, Xueyan Zhang. Xi Chen, and Yinan Chen. Deephullnet: a deep learning approach for solving the convex hull and concave hull problems with transformer. International Journal of Digital Earth, 17(1):2358843, 2024.
Jorge López, Álvaro Barbero, and José R Dorronsoro. Clipping algorithms for solving the nearest point problem over reduced convex hulls. Pattern Recognition, 44(3):607-614, 2011.
Qi Lv, Boshen Zheng, Shengwei Mei, and Wei Wei. Geometric methods for assessing the value and demands of energy storage in power system operation. Energy Internet, pp. e70000, 2025.
Donato Maragno, Holly Wiberg, Dimitris Bertsimas, Ş iiker Birbil, Dick den Hertog, and Ade- juyigbe O Fajemisin. Mixed-integer optimization with constraint learning. Operations Research, (6(2):011-11223 2025.
AP Nemirko and JH Dulá. Machine learning algorithm based on convex hull analysis. Procedia Computer Science, 186:381-386, 2021.
Dzung T Phan, Lam Nguyen, Jayant Kalagnanam, and Chandra Reddy. Multi-polytope machine for classification. Proceedings of the 2024 SIAM International Conference on Data Mining (SDM), pp. 107 SIAM, 2024.
Franco Preparata and Michael Shamos. Computational geometry: an introduction. Springer Science & Business Media, 2012.
Dolev Raviv, Tamir Hazan, and Margarita Osadchy. Hinge-minimax leamerr for the ensemble of hyperplanes. Journal of Machine Learning Research, 19(62):1-30, 2018
Antonio Ruano, Hamid Reza Khosravani, and Pedro M Ferreira. A randomized approximation convex hull algorithm for high dimensions. ifac-papersonline, 18110 2015.
Yukang Shen, Wenchuan Wu, Bin Wang, and Shumin Sun. Optimal allocation of virtual inertia and droop control for renewable energy in stochastic look-ahead power dispatch. IEEE Transactions on Sustainable Energy, 14(3):1881-189) 2023.
Chenbo Shi, Mohsen Emadikhiav, Leonardo Lozano, and David Bergman. Constraint learning to define trust regions in optimization over pre-trained predictive models. INFORMS Journal on Computing,
2024.
Stanley Tzeng and John D Owens. Finding convex hulls using quickhull on the gpu. arXiv preprint arXiv: 2012.
Erdem Varol, Aristeidis Sotiras, Christos Davatzikos, Alzheimer's Disease Neuroimaging Initiative, et al. Hydra: Revealing heterogeneity of imaging and genetic patterns through a multiple max- margin discriminative analysis framework. Neuroimage. 145:346-6644 16446636,,22 2017.
Zhuang Wang, Nemanja Djuric, Koby Crammer, and Slobodan Vucetic. Trading representability for scalability: adaptive multi- hultii-hpprrplane machine for nonlinear classification. In Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining, pp- 34-32, 2011.
12

---

Published as a conference paper at ICLR 2026
Li Yujian, Liu Bo, Yang Xinwu, Fu Yaozong, and Li Houjun. Multiconlitron: A general piecewise linear classifier. IEEE Transactions on Neural Networks, 22(2):276 289, 2010.
Haoran Zhu, Pavankumar Murali, Dzung Phan, Lam Nguyen, and Jayant Kalagnanam. A scalable mip-based method for learning optimal multivariate decision trees. Advances in neural informa- tion processing systems, 33:1771-1780 2020.
13

---

Published as a conference paper at ICLR 2026
APPENDIX / SUPPLEMENTAL MATERIAL
A Notations
15
MILP formulation of the PCAB
15
C Proofs for theoretical foundation
16
D Feasibility of the proposed methodology
18
Improved hyperplane initialization via reliable negative sample selection
19
F Complexity analysis of the proposed algorithm
20
Experimental details and additional results
G.I Linear separation
21
G.2
Triangle separation for visualization
23
G.3
Polyhedral separation
25
G.4
Nonlinear convex separation
29
G.5
Nonlinear nonconvex separation
33
G.6
Real-world trust region learning
35
G.7
Selective classification
36
G.8
Constraint learning and embedding
38
G.9
Additional gradient-based baselines and ablation study
40
Use of large language models
14

---

Published as a conference paper at ICLR 2026
A NOTATIONS
In the main text and the appendix, use the following notations:
Table 4: Summary of notations used the paper.
Symbol
Description
R*
d-dimensional real space
[a]]
Euclidean norm vector a, ie.. ش
conv(-)
Convex hull of a set of points
partition (ay
smallest value) the input
D
Labeled dataset {(r ]=]] 1=1..;;
R
(-1,+1)
D D
Positive and negative sabsets of
D
Negatiees lying outside conv (D;)
c
Learned polyhedral conves region (trust region) Hyperplane budgel (maximum number of facets)
S
(a".""
Normal vector and bias of the a-th hyperplane
6" (a)
Optimal offset for defined 6" minty P4
[a
Matrix of hyperplanc normals
[6
Vector of hyperplane offsets
A
Hyperplane normals/offsets excluding the s-th facet
Subset of negatives assigned hyperplanc
D
Local subregion
optimizing hyperplanc
za. 777
Lower/upper thresholds fur subregion band selection Hyperparameter controlling bias
Wigh
Separation margin hyperplane 8
Slack variable for negative sample Binary variable indicating whether negative sample is separated by hyperplane s.
hyperplane
f(a.b)
Surrogate objective for hyperplane (o, b)
Lef//rght soft split probahilities for sample Temperature parameter controlling softness of split
B
Weight assigned sample 2; Vector of sample weights [w:] constraints
W
ensuring sumogaate stationarity
K
K
Isotonic cones enforcing monotonic weights within positives/negatives
Ps. P., PK
Projection operators onto lincar, nonnogative, isotonic constraints
Boundary supponing positive and negative samples suhregion D
B MILP FORMULATION OF PCAB
To formalize the task of learning polyhedral convex region that encloses all positives while exclud- ing as many negatives as possible, we recall the Polyhedral Convex Hull Approximation with Budget (PCAB) formulation introduced Barbato et al. (2024).
Given a dataset D = D UD_ -, the goal is to construct a convex region
C= f Rdd Tz b s= s
with at most S hyperplanes, such that D_ C C and the number of negatives from D_ incorrectly included in C is minimized. This leads to the following MILP:
min
Σ
I
S
s.t.
Σ 2/ - Zi:
Vz, D_,
==1
aT
24 b¹ 2 1,
Yz, E D+. Vs.
T 84 11 < -1 EE,
Vxz E D_,, Vs,
(12)
& M (1 =f),
V E D_, VS,
2 2f E (0.1), 2 E 10,1).
Vz, D_, Vs.
Vz, E D_,, Vs.
Vx, E D_.
15

---

Published as a conference paper at ICLR 2026
where 2; is binary indicator of whether negative sample x, is included in the learned hull C. 2 is an auxiliary binary variable indicating whether 2; is separated by hyperplane s. 5f is a nonnegative slack variable capturing violations of separation for x; w.r.. hyperplane s. The big-M constraint ensures that slack с is only active when D2 is not separated by hyperplane 8.
All positives are required to satisfy a T2 - b z for every facet 8, thereby guaranteeing their enclosure within C.
Discussion of properties. Formulation Equation 12 allows explicit modeling of negative inclusion and is compatible with generic MILP solvers (e.g., Gurobi). However, it does not inherently control the geometric tightness of the hull: 1) The constraints impose a fixed separation band of width between positives and negatives. Hyperplanes may therefore be positioned conservatively, leaving unused gaps between C and conv(D+). ). 2) The optimization objective depends only the binary inclusion of negatives (zi), but not on how closely facets align with the positive class boundary. 3) Multiple optimal solutions typically exist with the same objective but very different geometric tight- ness. This non-uniqueness arises because scaling or shifting hyperplanes can preserve feasibility and the binary objective value, yet yield looser or tighter hulls.
Proposition 1. The MILP-baser PCAB formulation admits infinitely many optimal solutions in linearly or polyhedrally separable cases, with potentially large variation in boundary tightness.
Proof. In a linearly separable case, suppose a hyperplane (a*, b²) perfectly separates positives and negatives with zero slack. Then the MILP objective is zero. However, any scaled version (aa*, ab" + E) with a > 1 and E [1 - a, a 1] also satisfies all constraints and yields the same objective, producing infinitely many optimal but geometrically distinct solutions.
In polyhedrally separable case with S hyperplanes, let b+*)) define an optimal separating hull. Replacing (a** 6**) with (2a** 26** + 1) maintains feasibility (same separation margins) and preserves the objective, again yielding different feasible optima with varying tightness.
Implication for trust region learning. Although MILP formulations are powerful for minimiz- ing negative inclusion, they are not sufficient for applications where the trust region must be boundary-tight In safety-critical or generalization-sensitiy tasks, the hull should closely align with conv(D+), not merely avoid negatives. The rigid band constraints in Equation 12 prevent this alignment, especially when S is small or the true boundary is nonlinear. Additionally. ly, their compu- tational complexity grows quickly with both sample size and dimension: each additional negative sample introduces binary variables 2f, and the resulting search space is exponential in |D_ x S. In practice, directly solving Equation| [2 becomes intractable even for small-scale datasets.
This motivates surrogate-based approach: rather than enforcing separation through hard binary variables, we design a differentiable loss that directly guides hyperplanes toward the positive bound- ary, enabling compact, adaptive, and geometrically tight trust regions.
C PROOFS FOR THEORETICAL FOUNDATION
C.I PROOF OF LEMMA D
Consider the global MINLP formulation in Equation
2 which minimizes the total margin penalties Σ.5* under coverage and separation constraints. Let (A*,b") denote optimal solution. By construction, each negative sample
E D_ must be assigned to at least one hyperplane, i.c., (z, E D_ : 2 = 1} as the set of negatives excluded by hyperplane s.
2 = 1. Define D=
Now fix a particular hyperplane The pair (a** 6**) together with *** must satisfy all constraints in the local separation problem Equation restrricee to D4UD" Suppose, for contradiction, that there exists another feasible (a', b') with strictly larger separation margin g 5* Replacing (a** b**) by (a', 8') in the global solution would reduce the overall objective Equation 2 contradicting its optimality. Hence (a** be*) must also be optimal for the corresponding subproblem Equation 3
16

---

Published as a conference paper at ICLR 2026
C.2 PROOF OF LEMMA 2
Fix a local dataset D = D+ U DE and consider the surrogate Equation Define
A = Σ WiPp
B =
Σ wrppy yo,
: ==
Σ Wi.
E = Σ wiyh.
Using p. p the surrogate can be rewritten as
(1(
B
(E (0-B)² N - A
f(a,b) -
+
(13)
A
Step 1: Stationarity in the b-direction. We have dop, -33/1aal) p.Ppp hence
0,A4
Σ
wipPPt
0,
8 Tall
Σ
wayp P
By the chain rule applied to Equation 13
f - (2B(O A - B² (0,A)
2(E - B)(-, (N A) (E 13) ())(-))))
(N A)2
At (a*,b)). choose weights such that
E 0, N - -
(14)
Then B, O and A N A 1, so the two fractions cancel and Ōns(a", (a/"aa,)) b*) 0. Since
b" is placed at the positive support by = min a= x. these linear constraints can enforce boundary-tight stationarity along at (a*.
Step 2: Stationarity in the a-direction. Simplifying the gradient of Equation 13 under E 0, N
2, A = 1 yields
-23 B
23 |aa|
0,5
Σ wi p.ri ys (x, a))
(15)
C'w
Hence 0,ʃ whenever C'w where C' = [pt Mi (x;
1 12,
Step Existence of weights. the weight vector w satisfies the linear constraints Cw = d, then by Step I we have (a b²) = O. By Step 2, fa b*) = 0 holds whenever C"w = 0.
To see that such w exists, stack the constraints as a single linear system
C C²
d
O'w d', C=
d'
where C' E pxxx and d E IR+ encode the four scalar equalities in Equation or Equation and O' uddx has columns p.p.y,
14
T aa*))))) If D* contains at least d+44 near-boundary points from each class in general position, the row space of C" E Rdd+4)xn is generically full, and a solution to C"w = d' exists (not necessarily unique). This solution simultancously satisfies Cw d (so or 0) and C'w surrogate.
(so 0,f 0), making (a* b*) a stationary point of the
Constructive sketch. Suppose we can freely choose samples from the half-space on both sides the optimal hyperplane at by. We can get zÚ+ and zÿ- such that they are symmetric about the optimal hyperplane, i.c.. there exists m such that
a Ijt bt
a x.
by
m,
mm.
1a*
17

---

Published as a conference paper at ICLR 2026
Assign weights Wi+ wi- and wi 0 for all other i. Then
Σ Wi = 2,
Σ Weth O,
Σ wipp = 1, Euittr 0,
Therefore Cw holds.
Since x;+ and 2-- are symmetric about the optimal hyperplane, i.., 2it 2z- = ka for k E R. Consequently,
C'w-phiP Ø++ x-- a= (Igt xz-))
a kak
||a*11 a' púi Pit ka'
|a+122 a
which establishes C'w = 0. Combining Cw d and C'w 0 yields both b- and a-direction stationarity at (a", bb)).
C.3 PROOF OF LEMMA 3
The linear constraints Cw d ensure that Sa b) = and the gradient of Equation which can be re-written as:
can be
deduced into Equation 13
0af(a,b) = 2 ||a|
Σ wi p.Pp
(E wi p. pf
ys v3.)
B
||||2
a
(16)
The term inside the parentheses corresponds exactly to the exed-point mapping Equation namely
6
Σ wi P. ys xs.
If (a, b) and (w:} satisfy Equation 6 then the first term vanishes up projection along a, leaving
TTa
0af(a,b) x
0.
|||
Therefore, under the joint conditions of the fixed-point relation Equation 6 and Cw = d, both 0af = 0 and 0, = hold, so (a, b) is a stationary point of the surrogate objective.
C.4 PROOF OF THEOREM
Let (At,b") be optimal solution of the MINLP Equation By Lemma for each facet (1....,S) the pair (a** b**) solves the local constrained problem Equation on De D D
Fix any By Lemma] 2 there exists weight assignment D such that (a** b**) is stationary
point of the surrogate objective Equation 4 As shown in the proof of Lemma 2 (Step 3), such weights be obtained by solving a linear system that stacks the b-direction constraints Equation and the a-direction normal-equation constraints, and a feasible solution exists under near-boundary coverage assumptions on D Moreover, 3 stationarity when the optimal a** is unknown: the fixed-point relation Equation 6 holds together
sufficient condition for the a-direction with Equation 5 then (a** b²*) is stationary for Equation
ing (a** 6**) stationary point of the surrogate objective. This proves the claim. Therefore, for each hyperplane there exists a (possibly non-unique) weight assignment {we] mak-
D FEASIBILITY OF THE PROPOSED METHODOLOGY
The surrogate formulation in Section reduces the MINLP into a weight assignment problem. In principle, one could solve this problem by repeatedly optimizing f(a, b) until convergence, enforc- ing a Re g(a,w) w) and then updating w so as to maximize the margin Eww). During the process, one after each updating of
should immediately conduct projection through Ps(w) to ensure Cw and w. This would give an iterative scheme directly aligned with the constrained hyperplane prob- lem Equation 3. However, such approach is computationally expensive and numerically unstable: every update of w requires re-solving (a, b) to convergence, and small perturbations in w may lead oscillatory divergent behavior.
18

---

Published as a conference paper at ICLR 2026
Need for additional constraints. To make weight updates meaningful, introduce further straints beyond Cw = 1) Nonnegativity (w 2 0) ensures that weights behave as proportions of contribution; negative weights have physical interpretation: 2) Isotonicity (w E K , - en- forces that samples closer to the boundary receive larger weights, consistent with the role of support vectors. These constraints encode the geometric intuition of the problem and regularize the update process, preventing w from drifting into unrealistic assignments that would destabilize fla,b)
Projection onto multiple constraints. Once these constraints are included, a single projection is insufficient, because the feasible set is the intersection of four convex sets (Ow d. w 0, K K ). We therefore rely on alternating projections (Dykstra's algorithm) to enforce feasibility after each gradient update. This guarantees that the weight assignments remain consistent with both theoretical requirements and geometric intuition.
Approximation for efficiency. A fully exact implementation would require: (i) letting f(a, b) converge at each step, and (ii) applying Dykstra's algorithm until own convergence. In practice this is prohibitively costly. Instead, we adopt pragmatic approximation: perform only one gradient step on f(a, 6), one gradient step on [(w). and then one round of projections. Although this does not ensure exact satisfaction of the exed-point relation = g(a,w), w). empirical evidence shows that the resulting a remains close to the fixed point, while the projections ensure w stays feasible and interpretable. This strikes a balance between theoretical rigor and computational tractability.
Summary. While the approximation 0a/Ow 0g/Ow is not exact, empirical results show that the resulting updates produce stable weight distributions and lead to boundary-tight hyperplanes. Moreover, the incremental update scheme (one step f(a, b) followed by projection of w) is computationally efficient, avoiding repeated full convergence of f(a, b) at every iteration. This trade-off between exact fixed-point satisfaction and practical efficiency makes the methodology fea- sible for large-scale, high- nigh-dimensional problems.
E IMPROVED HYPERPLANE INITIALIZATION VIA RELIABLE NEGATIVE SAMPLE SELECTION
The quality of hyperplane initialization directly affects the convergence and stability of convex hull learning algorithms. Algorithm describes the improved initialization strategy used our frame- work.
This strategy is adapted from the PinCHD method originally proposed Leng et al. (2019), which constructs supporting hyperplanes by iteratively computing the closest point between negative sample and the convex hull of positive samples. The resulting support vector pair is then used to form initial hyperplane. This enables fast initialization of polyhedral trust regions. However, the original method is sensitive to the choice of the negative sample: if the selected negative lies inside conv(D+), the projection becomes ill-posed, producing degenerate hyperplanes leading singularities during subsequent optimization.
To address this, we propose more robust initialization strategy that carefully restricts the choice of negative anchor samples. Specifically, the selected sample must satisfy two conditions: 1) it lies inside the current polyhedral region
C f IRd
T 2 bz, VsJ.
so that corresponds to misclassified negative that ideally should have been excluded, guiding the algorithm to focus problematic regions; 2) belongs at least one local subregion Da defined
in Section 4 ensuring that the anchor is close to the decision boundary and more likely to serve as a meaningful support vector.
19

---

Published as a conference paper at ICLR 2026
Algorithm 2 Trustworthy Hyperplane Initialization (Improved PinCHD)
Require: Positive set D+, local partitions {D" "P*Ja=1, current convex hull C, tolerance
Ensure: A supporting hyperplane (a", b*)
1: Randomly select a negative sample x= E (U==ID)) ne
2: Initialize Fee E D
3: repeat
4: x² < Jeew
5: 2t f arg mi (x-x7) (a""""""""""
-22---11
6: 9 - *-min( 1, (2" -x
-21-
7: Knew x² + g(zt -x²)
8: until |=" - x
1 x <e
9:
(# x )
x0
10: min (a x)
if 3r D+ such that a x TTx
then
12: Randomly re- re-initialize a with ||a|| = 1, set b = min xz)x)
end if
14:
return (a, b)
Once the negative sample x is selected, the algorithm applies an iterative projection process to find the closest point Few conv(D++ to x= This is achieved by repeatedly projecting x onto line segments between x: and candidate positives It. until convergence within a tolerance c. The resulting vector bias b is then set as b = min Tr), ensuring tangency to the positive hull and that all positives remain inside C.
new x defines the normal of the hyperplane, normalized to unit length. The
To safeguard against numerical instability, we check whether all positives satisfy aTx I b 2 -c. If this fails (which typically indicates that x lies within conv(D+)), we fallback random initialization. This ensures robustness against degenerate anchors.
summary, our improved initialization strategy selects only reliable negatives and guarantees ge- ometrically meaningful hyperplanes. This avoids degenerate configurations, stabilizes training, and provides a strong starting point for the surrogate-bart based optimization in the main framework.
COMPLEXITY ANALYSIS OF THE PROPOSED ALGORITHM
We analyze the computational complexity of our PCH framework, as described in Algorithm Let [D] denote the dataset size, d the input dimension, and S the maximum number of hyperplanes. We examine each component in turn.
1) Initialization via improved PinCHD (Algorithm 2). The improved PinCHD algorithm initial- izes each hyperplane by projecting a selected negative sample x E De toward cDnv(D In each iteration, all positive samples are scanned identify the closest supporting point, which requires d(n_d) operations. Assuming convergence within T iterations (empirically small constant), the cost per hyperplane OTTn4d).. Computing the bias b" mingeD, z requires O(n,d) addi- tional operations. Thus, the total initialization cost across all S hyperplanes is O(TSn,d).
2) Bias computation. each iteration, the offset bü, recomputed for every hyperplane, requir- ing minzer, a= x. The per-hyperplane cost is O(+dd), yielding O(Sn4d) d) in total.
3) Subregion assignment (Equation 7). For each hyperplane s, we must identify the local dataset D* by checking whether a= x byg lies within the band [-77", गल" and whether satisfies the other S hyperplane constraints. This requires computing the signed margins {a*T x 5 for all samples, cost O(nSd). Computing mi requires evaluating a across n4 positives and selecting the d-th order statistic, i.c., O(r,d) d) per hyperplane. The overall complexity subregion assignment is therefore O(nSd).
20

---

Published as a conference paper at ICLR 2026
4) Surrogate evaluation and gradient computation (Equation Within each subregion D evaluating the surrogate f(a", ,b)) requires computing the soft-split terms pi p. and aggregating weighted sums. This requires (n,,d) operations, where n, [ Across all hyperplanes, the total cost is Od n,), bounded above by ((nSd).
5) Weight update and projections (Equation 9.
The gradient V.E(w) requires weighted sums of samples in D', which is (n,d)). After the gradient step, the updated w must be projected back onto the feasible set
F= w 1w2200 0, W BEEKKt WE Kx-, Cw = d).
Each projection is efficient: 1) P+ (nonnegativity): ((ns), 2) Pk.+ + Pk,- (isotonic projections via PAVA): (n,,) each, 3) Ps (linear equalities): On..), ) since it reduces to rank-4 update. Thus the overall projection cost is On..) per hyperplane, and O (/=s= na) across all hyperplanes. The dominant cost remains VuE(w), i.e., (nnSd).
6) Gradient descent step for (a") Updating each hyperplane requires (d) operations for a" E Rd and constant time for b". Thus the total cost across S hyperplanes is O which is negligible compared to surrogate evaluation.
Overall Complexity. The total computational cost of PCH consists a one-time initialization phase plus multiple gradient-based iterations. Initialization requires OTT Sn+d). Each iteration involves subregion assignment, surrogate evaluation, weight updates, and parameter updates, dom- inated by (nSd). For / iterations, the overall complexity is therefore ([nSd)), which scales linearly in dataset size, feature dimension, number hyperplanes, and iteration count.
G EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS
G.1 LINEAR SEPARATION
Dataset generation and training settings. This experiment evaluates the ability of our proposed method to learn linear separator between two classes. The dataset is synthetic 2D dataset taining 19,979 samples, randomly generated such that the positive class (blue) and negative class (red) are linearly separable, illustrated in Figure We compare our method (PCH) with the base- line SCDC1 ass fier from scikit-learn, denoted as SGD. Both models are trained for 50 epochs of gradient descent with learning rate of 0.01, where each epoch computes the full-batch gradient over the entire dataset. This ensures a fair comparison under consistent update schedules and optimization dynamics.
Visualization of training. Figure 4 visualizes the learned hyperplanes different iterations. Our method (left) progressively refines the hyperplane direction while consistently positioning it near the boundary of the positive class, resulting rapid convergence toward the maxximum-margee ori- entation. In contrast, although the SGD baseline (right) also minimizes a hinge loss and thus seeks a margin separator, it jointly updates both orientation and bias without explicit geometric con- straints. As result, its convergence is slower, and the leamned hyperplane often remains offset from the true boundary.
Training dynamics. Figure reports the training accuracy and signed separation margin over iterations. We define the signed separation margin (or gap) as max (a (aT.x z;=b), which measures the maximum signed distance from negative samples to the hyperplane. Since the learned hyperplane is always positioned to the positive class boundary, this metric effectively captures the tightness of negative exclusion. Our method steadily improves classification accuracy while simultaneously minimizing the gap, indicating that the learned separator is both accurate and geometrically tight. In contrast, SGD quickly achieves high accuracy but converges to a hyperplane with a larger margin violation, reflecting weaker control over the geometric alignment of the boundary.
21

---

Published as a conference paper at ICLR 2026
(a) PC11
(b) SGD
Figure 4: Evolution of the supporting hyperplane during training. Left: method (PCH); Right: SGD baseline.
Turning Accorscy agains tzech
1.00
Ascarto
6081
0.88
Sepuadi Cup spant bpach
0.43
0.03
204
0.09
0002
600
0003
0.05
0.07
Figure 5: Training accuracy and signed separation gap over training epochs.
Main results. We also report the final results in Table including classification accuracy, runtime, and the signed separation gap. The results confirm that our method (PCH) achieves perfect accuracy while producing a hyperplane that is nearly tangent to the positive class boundary. The negative gap evidences the performance of PCH in excluding negative samples with a bigger separation margin. In contrast, although the SGD baseline reaches comparable accuracy, it converges a slightly worse geometric margin, indicating less precise alignment with the optimal separating boundary. The runtimes of both methods are comparable, suggesting that the additional structure imposed by PCH does not introduce significant computational cost.
solution with
Table 5; Final comparison on lincarly separable task
Method Accuracy (%)
Runtime (s) Signed Separation Gap
PCH
100.00
0.180
-0.00030
SGD
99.95
0.188
+0.00072
Summary.
This experiment demonstrates that proposed method not only matches the clas- sification accuracy standard SGD-based training on linearly separable data, but also achieves superior geometric alignment. By explicitly fixing the bias term to the boundary of the positive class
22

---

Published as a conference paper at ICLR 2026
and updating the hyperplane orientation based gradient descent soojjettedweiight surrogate
loss. PCH offers a more stable and interpretable mechanism for learning individual tight separa- tion hyperplanes, laying solid foundation for constructing compact convex hulls in more complex settings.
G.2 TRIANGLE SEPARATION FOR VISUALIZATION
This ex- tended example serves four purposes: (1) visualizing how the surrogate optimization evolves over iterations, (2) empirically demonstrating the convergence of both hyperplane parameters and weight assignments, (3) examining the robustness of the optimization with respect different initializa- tions, and (4) illustrating how the learned polyhedral separator relates to the MINLP formulation.
We present the full training trajectory of PCH on the same 2D dataset used in Figure 2
Dataset generation and training settings. We construct a simple 2D dataset on a uniform grid over the square [-1, triangular positive region is generated by selecting three supporting directions and forming a regular polygonal boundary. All grid points inside this region are labeled as positive, and the remaining points are labeled as negative. This produces a clean binary classification task with well-defined geometric structure. We train PCH model with three hyperplanes for 100 gradient updates. This setup allows us to capture the full evolution of the hyperplanes and weight assignments throughout the training process.
Training dynamics and convergence behavior. Figure presents the complete optimization tra- jectory PCH on the same 2D triangular dataset used in Figure This extended example visualizes how the three hyperplanes evolve throughout training, how their associated weight assignments sta- bilize.
The top of Figure 6 shows the position and orientation of all three hyperplanes over 100 it- crations, where lighter colors correspond to early iterations and darker colors correspond to later iterations. The hyperplanes move gradually from their random initial orientations toward the true supporting directions that define the convex boundary the positive region. By iteration 30, the hyperplanes have already reached nearly their final geometry, and the remaining 70 iterations only produce very small adjustments. By the final iterations, each hyperplane has moved into tight supporting position: all three hyperplanes pass through the corresponding positive support points and lie nearly flush against the outer boundary of the positive region. The resulting hyperplanes overlap almost perfectly with their limiting orientations, making the convergence of the geometric parameters visible.
The lower rows plot the evolution of the weight assignment for each hyperplane. Although weight assignments are conceptually defined over samples, PCH's formulation allows them to be visualized as a function the signed distance a. x b, because the weight of a sample depends on this signed distance within the surrogate. Thus, each curve shows: for all samples having given signed distance to hyperplane s, what weight is assigned to them during that iteration. Initially, these highly irregular and differ drastically across iterations. As optimization progresses, the curves rapidly collapse into stable profiles, indicating that the weight vector associated with each hyperplane has converged.
23

---

Published as a conference paper at ICLR 2026
beralon procest
INP1
Te-10
Re:20
RE-00
1e-1100
1
Figure 6: Training dynamics of PCH on the 2D triangular dataset.
Robustness to random initialization. Across six independent random initializations, all three hy- perplanes converge to the close supporting configuration on the 2D triangular dataset. Despite large variations in the initial directions, the trajectories rapidly contract toward the correct boundary. The final configurations almost perfectly overlap and each hyperplane simultaneously passes through the corresponding positive support vectors, forming tight outer envelope. This consistent convergence demonstrates that PCH is highly insensitive to initialization, providing strong empirical evidence that the optimization does not become trapped in poor local minima on this task.
Figure Hyperplane trajectories under random initializations.
Relation to the MINLP formulation. Figure 8 compares PCH with several representative base- lines, and the MILP formulation Equation 12 We do not compare the MINLP formulation in in two dimensions. All baseline methods are run with their default hyperparameters. As shown in the figure, PCH is the only method whose learned hyperplanes lie tightly against the positive support points, producing a polyhedron
Equation 2 because the MINLP is extremely difficult to solve
24

---

Published as a conference paper at ICLR 2026
that is visually indistinguishable from the ideal supporting hull. In contrast, the MILP boundary leaves a clear gap between the hull and multiple positive support vectors, and geometric base- lines (QH, DCH, PinCHD) introduce angular distortion overshoot regions. DeepHull produces a smooth implicit boundary that cannot recover the polyhedral structure (Ax 2 b). These compar- isons demonstrate that PCH yields the most geometrically faithful approximation the underlying polyhedral trust region.
PCH
(9)
MILP
DCH
PaCHD
Desptial
Figure 8: Comparison of PCH with MILP relaxation and representative geometric baselines on the 2D triangular dataset.
Summary. The triangular example provides comprehensive view of how PCH operates in prac- tice. The optimization trajectory shows that the surrogate updates drive the hyperplanes toward their tight supporting positions, while the weight assignments quickly stabilize into consistent pro- files. The multi-start experiments further demonstrate that the procedure is highly insensitive to initialization, consistently converging to the same boundary. Finally, the comparison with the MILP relaxation and classical geometric baselines highlights that PCH yields the most faithful reconstruc- tion of the underlying polyhedral trust region. These observations collectively illustrate the stability, robustness, and geometric accuracy of the proposed framework.
G.3 POLYHEDRAL SEPARATION
This experiment evaluates the ability of convex hull learning methods to recover polyhedral decision regions composed of multiple supporting hyperplanes. We construct a family of synthetic datasets named PH, where the positive class forms convex polyhedron in IR bounded by S = 15 randomly generated hyperplanes.
Dataset generation. Each PH dataset contains 40,000 samples uniformly drawn from the hyper- cube 1jd. To define polyhedral region, we randomly generate S = 15 hyperplanes. For each hyperplane j. its normal vector a² is sampled from a uniform distribution over [-1, 1J The bias 69 is set as the 4th percentile of the projection values of all samples on a', ensuring that roughly 4% of the data lies below the hyperplane. point is labeled positive it satisfies all S hyperplane constraints a² x 2 bi; otherwise, it is labeled negative. This results in convex polytope enclosing approximately half of the samples, i.e., (1 4%) 54%.
Training settings. We compare our method (PCH) with QH (Barber et al.) 1996), CGHC (ar- bato et al. 2024), DCH (Blum et al. 2019). PinCHD (Leng et al. 2019), and DeepHull (Balestriero al. a (022). For all datasets, the number of hyperplanes fixed at 15. For PCH, use 15 outer iterations, each with 100 gradient descent steps, a learning rate of 0.1, and a loss smoothing tem- perature of 4. The margin shift coefficient Mishn is set to 0.03, and the weight gradient update rate is set to 0.0001. CGHC is implemented following the main text of Barbato et al. 2024)). The approximation rate of DCH is set 0.05. PinCHD implemented following the main text of [eng et al. (2019). The DeepHull model uses single hidden layer with 7 neurons trained for 1500 epochs.
Main results. Table 6 and Table provide comprehensive comparison of six methods across increasing dimensions in polyhedral separation tasks. We evaluate their trust-region accuracy, along with training time and model complexity to assess scalability and computational efficiency.
25

---

Published as a conference paper at ICLR 2026
PCH achieves consistently high accuracy (above 99% in all settings), stable model complexity (fixed at 15 hyperplanes), and efficient training time that scales gently with dimensionality. This demonstrates that PCH can effectively handle high- dimeeniieninnl data without relying combinato- rial solvers or enumeration strategies, thanks to its continuous optimization formulation and strategic weight assignment. Even 100 dimensions, PCH retains 99.95% accuracy with training time under 2 minutes, highlighting strong scalability and resilience to dimensional growth.
In contrast, CGHC experiences clear degradation as dimensionality increases. While achieves competitive accuracy in low dimensions (99.71 % at 2D), its performance drops to 57.20% at 100D. This decline is accompanied by substantial computational cost, with training time exceeding one hour at 100D. While CGHC attempts to mitigate combinatorial complexity via column generation, its reliance on MILP subproblems with binary variables still incurs a steep increase in computational burden as the problem dimension or sample size grows. The result is low accuracy, solver instability and early termination in high-dimensional cases.
QH achieves perfect trust-region accuracy in low dimensions (up to 8D), as it computes the exact convex hull enclosing all positive samples. However, it quickly becomes intractable as dimension- ality increases. For instance, the number of output facets exceeds 23 million at just 8 dimensions, resulting in excessive memory usage and prohibitive runtime. Beyond 8D, QH fails to complete within reasonable time budget, and results omitted.
Compared with these, DCH, PinCHD, and DeepHull show mixed performance. DCH relies on sparse vertex selection without label supervision, achieving moderate accuracy in low dimensions but degrading rapidly as dimensionality increases, along with exploding model complexity. PinCHD performs consistently better, maintaining relatively high accuracy across dimensions, though its complexity grows with the number of iterations and selected anchors. DeepHull, while efficient due its neural approximation, suffers from lower accuracy and lacks explicit linear constraints, which reduces interpretability and complicates its integration into downstream optimization tasks. For fairness of comparison in Table 7 we convert the learned neural boundary into its equivalent set of linear constraints and report the number of resulting constraints as the model complexity.
Overall, the results validate the core design goals PCH: to provide scalable, structure-awart com- pact trust region modeling with strong performance guarantees in both low- and high- ditheeminnii scenarios. Its consistent accuracy, computational efficiency, and controlled model complexity make it well-suited for practical deployment in large-scale trust region learning tasks.
Comparison on polyhedral separation tasks. PCH maintains stable accuracy, efficiency and complexity across dimensions, while QH and CGHC deteriorate in high dimensions. A dash indicates that QH fails to scale to the corresponding high digh-dimensional setting.
Table 6:
Trust-region Accuracy5%
Training Timak
Model Complexity
Dimension Problem
QH
CGHC
PCH
QH
CGHC
PCH
QH
CGHC
PCH
PIL.15.2
100.00
PH_15_3
100.00
98.74
100.00
0.00
662.00
80.31
532
15
12
PH_15_4
100.00
100.00
0.02
698.43
85.07
4660
Low
PH 5
100.00
92.19
99.52
0.22
497.41
89.74
40700
151
100.00
92.68
100.00
4.15
717.34
90.19
336283
15
PH.15_7
100.00
56.84
407.45
2.66E+6
PHL_15_8
100.00
87.59
100.00
88188
922.55
91.94
2,30E+7
15
15
PH_15_10
82.26
100.00
919.31
93,34
High
PHL15_100
57.20
99.95
13537.29
117.32
Training dynamics. Figure Figure the evolution of trust-region accuracy and cumulative training time against outer iteration count for different dimensional settings. PCH exhibits stable and steady convergence across dimensions, progressively improving its accuracy over iterations without sig- nificant fluctuations. In contrast, CGHC frequently struggles to reach comparable accuracy under the same hyperplane budget. Notably, in several high-dimensional cases, CGHC terminates prema- turely before completing the full 15 iterations. This is due to its reliance and basee termination conditions, which can be sensitive to solver precision and may incor- rectly trigger early stopping when the underlying MILP problem is defined on high-dimensional
dual variable updates
26

---

Published as a conference paper at ICLR 2026
Table 7:
More comparison on polyhedral separation tasks, A dash "_" indicates that models fail to
scale to the corresponding high-ding -ieh-dimeniional setting.
Dimension
Problem
Trust-region Accuracy56
Training Timels
Model Complexity
DCH
PinCHD
DeepHall
DCH
PinCHD
DeepHull
DCH
PinCHD
DeepHull
0.74
4.26
PH 15 3
96.58
97.34
92.62
7.50
63.39
4.08
188
38
15
PH.15.4
94.93
86.31
51.51
92.56
4.05
2.96E+3
Low
PHL15_5
88.38
95.84
86.62
77.62
135.98
4.07
2.52E+4
152
151
76.75
94.35
78.54
81.11
167.70
4.04
1.70E+5
250
PH__5_7
62.83
94.62
82.33
94.12
338.96
4.14
1.0SE+6
351
PHL15_8
45.26
95.26
82.01
185.12
362.87
4.00
6,18E+6
480
15
PH1_5_10
96.11
82,36
495.72
4.00
880
15
High
PHL15_100
57.95
64.39
8741.04
5.08
1.50E+3
and scale datasets. These observations further highlight the robustness and stability of PCH in optimization dynamics.
Ooasil cottor
Dhoer Accuress coart Ievetin
CEC
(0) 21
1500
315
SrafOi
(g) PSL
(3)
P)
KURO
Tec
44 Tee FC1
2000
Teu COR
Figure 9: Trust-region accuracy and time against iteration for PCH and CGHC across dimensions to 100.
Visualization in 2D. We visualize the decision boundaries the 2D PH dataset in Figure I0 PCH able to reconstruct a tight polyhedron that encloses all positive samples and excludes nearly all negatives, while CGHC and other methods show slightly looser boundaries.
27

---

Published as a conference paper at ICLR 2026
CGHC
(d) DCH
PinCHD
DecpHull
Figure 10: Learned convex hulls on 2D polyhedral dataset (PH_15_2). Blue: positive samples; red: negative samples.
Robustness to noise injection. assess robustness under label noise, we construct noisy variants of the polyhedral datasets based on the same ground-truth polyhedra. For each dimension, we first generate the clean dataset as described above. We then draw an additional 2,000 points uniformly from [-1, 1jd and label them according to the same convex hull. Among those labeled as positive, we flip a subset to negative if they lie within a small margin band width 0.1 around at least one supporting hyperplane. All methods trained with exactly the same hyperparameters in the clean polyhedral experiments.
Tables and 9 report the trust-region accuracy. training time, and model complexity the noisy polyhedral datasets. Across all dimensions, PCH maintains very high accuracy (typically around 99%) with fixed budget of 15 hyperplanes and training time the order of one two minutes. Among the baselines, DeepHull is relatively more sensitive to noise. These results indicate that PCH only scales well in the clean polyhedral setting, but also preserves tight and reliable trust regions in the presence of substantial interior noise.
Table 8:
Comparison on noisy polyhedral separation tasks. PCH maintains stable accuracy, effi ciency and complexity across dimensions, while QH and CGHC deteriorate in high dimensions. A
dash " indicates that QH fails to scale to the corresponding high-dimensional setting.
Trust-region Accuracy
Training Time's
Model Complexity
Dimension Problem
QH
CGHC
PCH
QH
CGHC
PCH
QH
CGHC
PCH
PH_15_2_N
99.41
99.08
99.38
0.02
698.74
89.67
37
15
15
PH 1H.15.3.N 35.3.N
99.39
97.10
99.35
0.01
760.21
102.33
534
15
15
PH.15.4.N
99.37
94.87
99.33
544.23
93.29
4.69E+3
15
15
Low
PH_15_S_N
99.44
93.52
99.32
0.23
610.57
93.25
4.11E+4
15
15
PHL.156_N
569.94
3.3914
PI1_15_7_N
99.31
89.42
99.24
59.67
673.50
93.86
2,70E+6
15
15
PH_15_8_N
89.50
601.10
2.35E+7
High
PI1,1511OUN
78.39
98.05
779.69
94.03
15
15
PH_15_100_N
57.71
98.93
19825.01
118.16
15
15
Figure 11 visualizes the learned convex hulls on the noisy 2D dataset. Interior noisy negatives appear as seattered red points inside the positive region. All methods are necessarily forced include some of these points, but there are clear differences in how tightly they follow the outer envelope of the positive region. PCH produces boundary that closely tracks the true outer shape while using the prescribed number of hyperplanes. QH resembles the ground-truth hull without considering any negative points, whereas CGHC. DCH, PinCHD, and DeepHull tend to generate slightly looser or more distorted hulls. This 2D visualization is consistent with the quantitative results: PCH preserves
28

---

Published as a conference paper at ICLR 2026
Table 9: More comparison noisy polyhedral separation tasks. A dash "_" indicates that models fail to scale to the corresponding high-dimensionn setting.
Trust-region Accuracy5%
Training Timels
Model Complexity
Dimension Problem
DCH
PinCHD
DeepHall
DCH
PinCHD
DeepHall
DCH
PinCHD
DeepHull
PIL.15.2.N
99.08
53.29
PH IS 3 N
95.97
97.13
92.67
8.84
94.44
4,66
180
37
15
PH.15.4.N
94.54
95.01
87.61
111.83
2.94E+3
93
Low
PH_15_5_N
88.20
94,56
85.14
80.70
167.53
4.31
2.52E+
144
15
76.93
94.00
79.69
83.03
363.43
4.41
1,71E+5
235
15
PHL_5_7_N
63.15
94.19
80.15
91.73
408.46
4.45
1005++
340
15
PHL15,8.N
45.88
94.86
78:52
184.57
495.74
4.13
6,18E+6
494
15
PHI_1__IOU
95.35
76.97
561.35
4,28
1,02E+3
15
High
PHL15.100..
57.15
74.39
12254.17
5.19
1.50E43
15
a tight outer approximation of the positive class even when noisy negatives are injected inside the positive region.
(4) QH
(b) CGHC
(c) PCH
45
00
(d) DCH
(e) PinCHD
DeepHall
Figure 11: Learned convex hulls on the noisy 2D polyhedral dataset (PH.15_2.N6
Summary. This experiment demonstrates that our method achieves superior scalability, efficiency, and robustness in learning polyhedral trust regions, particularly in high-dimensional and large-scale settings.
G.4 NONLINEAR CONVEX SEPARATION
Dataset construction. Each NLC dataset contains 40,000 samples uniformly drawn from the hy- percube [-1, 1]4. To construct smooth convex region, we compute the Euclidean norm of each sample from the origin and use the median norm value as a threshold. Samples whose norm is be- low the threshold are labeled as positive, while the remaining samples are labeled negative. This produces balanced dataset where the positive class forms hypersphere centered the origin. The resulting boundary is convex but cannot be exactly represented by a small number of linear facets, making it a challenging testbed for learning trust regions with convex hulls.
Training settings. To ensure a fair comparison, we use the same experimental settings in the polyhedral case, except for the hyperplane budget, which is adjusted to scale with input dimension as [15 /d - I]. This scaling strategy provides flexibility to approximate curved convex boundaries in high dimensions, while keeping model size manageable and comparable across methods.
29

---

Published as a conference paper at ICLR 2026
Main results. Table 10 and Table [ summarize the results NLC datasets across different di- mensions. PCH consistently achieves strong trust-region accuracy while maintaining moderate train- ing time and controlled model complexity. Unlike methods that aim to approximate the ground-truth curved boundary, our goal is to learn a compact and tight trust region that encloses all positive sam- ples while excluding as many negative samples as possible, under limited hyperplane budget. The results show that PCH successfully constructs trust regions across all tested dimensions. For in- stance, at 100 dimensions, it achieves 99.01 % accuracy with 150 hyperplanes and a training time of 1747 seconds, demonstrating both scalability and robustness.
Table 10:
Performance comparison on nonlinear convex (NLC) datasets increasing dimension- ality. A dash "_" indicates that QH fails to scale to the corresponding high-dimensional setting.
region Accuracy/S
Training Timess
Model Complexity
Dimension Problem
QH
CGHC
QH
CGHC
QH
2
100.00
99.27
99.40
0.02
629.96
77.51
93
NL.C.N33
100.00
93.09
94.35
0.01
725.49
111.84
1.28F+3
NLC.N.4
100.00
86.11
89.55
0.04
757.8
122.59
1.13E+4
26
26
Low
NLCC
84.61
9.34Fe4
NLC.N.6
100.00
71.60
79.19
8.63
1145.53
166.30
7,23E+5
34
34
NLC.N.7
100.00
66.62
75.11
111.03
1350,59
187.42
5.62E+6
NLC.N.8
100,00
60.38
71.77
1701.16
8804.44
192.31
4.50E+7
40
NLC.N_I0
57.60
69.23
7705.48
235.14
High
NLC N. 100
68.89
99.01
30762.99
1747.66
150
150
Table 11: Performance comparison on nonlinear convex (NLC) datasets of increasing dimension- ality. A dash "_" indicates that models fail to scale to the corresponding high-dimensional setting.
Trust-region Accuracy/%
Training time's
Model Complexity
Dimension Problem
DCH
PinCHD
DeepHull
DCH
PiaCHD
DoepHull
DCH
PinCHD
DeepHull
NLC.N_2
95. 24
99.41
97.64
0.94
26.97
4.23
15
24
15
N.C.N.3
91.01
99.06
93.79
6.88
40.23
3.75
242
125
21
NLC.N
86.02
99.05
92.61
35.45
60.48
3.90
4.39F+3
309
25
Low
NLC.N.5
74.05
99.39
88.
76.77
92.94
4.19
4.05E+4
632
29
NLC.N.6
80.97
1988+5
NLC.N.7
36.48
99.96
86.31
93.50
238.47
4.24
1.03446
1.48E+3
37
NE.C.N_8
22.04
86.75
172.37
6.59F+6
1,50F+3
High
NLC
92.46
85.99
371.34
4.96
1,50E+3
45
NICCN_100
53.75
75.39
8542.03
9.70
1.50F+3
In contrast, CGHC experiences clear degradation as dimensionality increases. While it achieves competitive accuracy in low dimensions (e.g.. 99.27% at 2D), its performance drops significantly to 68.89% 100D. This decline is accompanied by substantial computational cost, with training time exceeding 30,000 seconds. Although CGHC leverages a column generation strategy to heuristically solve its MILP formulation, the underlying MILP formulation still introduces large number of binary decision variables. As dimension and sample size grow, this leads to severe combinatorial complexity, which hinders its scalability in high-dimensional settings.
QH produces perfect separation accuracy for all low-dimensional cases, since it computes the ex- act convex hull of the positive samples. However, it becomes computationally intractable beyond 8D due to exponential growth in output hyperplanes. As result, QH fails to complete within reasonable time budget, and results are omitted.
Compared with these methods, DCH, PinCHD, and DeepHull exhibit clear limitations in the trust region setting. DCH selects sparse representative vertices and internally approximates the convex hull, but since it does not enforce full positive inclusion, its accuracy rapidly degrades as dimen- sion grows and its model complexity explodes. PinCHD provides stronger separation performance through projection-based initialization and iterative refinement, yet it cannot control the number of hyperplanes, leading to unbounded model growth in higher dimensions. DeepHull leverages neural approximations capture convex regions with low training time, but it does not produce explicit lin- ear constraints and similarly fails to guarantee inclusion of all positives, limiting its interpretability and downstream usability.
30

---

Published as a conference paper at ICLR 2026
These findings confirm that PCH effectively supports trust region learning with convex hulls, when the ground boundary is nonlinear. It maintains strong performance in terms of both trust-region accuracy and computational efficiency, making it well suited for large-scale, high- dimensional applications that require compact and adaptive trust region modeling.
Training dynamics. Figure 12 shows the evolution of trust-region accuracy and runtime for CGHC and PCH. The results are similar to the results in the polyhedral datasets. PCH also ex- hibits steady and monotonic improvement in accuracy compared with CGHC, and its runtime scales smoothly across iterations.
N_2
NINCNN 4
Anenny COAC
Tex C2
230
NCC
NL
NO
Oasaiisator Acourcyy agant E010231
Cleciiiation AOD Hendioo
Clocciration Rzc ceart PEREE Toeatie
PO
Computing Tire againe Hanaton
Pd
See
120
120
Clssiication
corpuingg Thee agart to 9030
Dentading The syst Triviin
Computig Tiis tiart Eertte
000
12
12
Figure 12: Trust-region accuracy and runtime against iteration on NLC datasets across dimensions.
Geometric visualization. To further illustrate model behavior, Figure 13 visualizes the learned convex hulls in 2D. QH constructs perfectly tight boundary by computing the exact convex hull of the positive class with excessive hyperplanes. Both PCH and CGHC yield similar trust regions that closely follow the curved boundary, despite using only supporting hyperplanes. Other meth- ods also achieve similar results without controlling supporting hyperplanes. This confirms that in low-dimensional convex tasks, all methods can construct an effective convex hull for trust region modeling, with PCH offering
structured optimization-bn based formulation.
Scalability trends. Figure 14 summarizes performance trends over increasing dimensions. Accu- racy (left), training time (middle), and model complexity (right) compared. PCH retains compet- itive accuracy and model complexity, whereas CGHC suffers from an accuracy drop and exponential computational cost. QH remains exact but becomes infeasible after 8D.
31

---

Published as a conference paper at ICLR 2026
(a) QH
(b) CGHC
(c) PCH
(d)
(0) PinCHD
DeepHull
401
14.
Figure 13: Visual comparison of 2D NLC convex hulls.
Model accuracy
Training time
Model complexity
100
37'
2530
CEPC
2000
37
5909
28
Figure 14: Trends of accuracy, training time, and model complexity against dimensions for NLC datasets.
32

---

Published as a conference paper at ICLR 2026
The effect of the hyperplane budget. To further examine how the hyperplane budget S influences the quality of the learned convex separator, we consider the 2D circular dataset. Because the target set is not polyhedral, any convex-hull based approach necessarily produces a polygonal outer ap- proximation whose tightness depends on the number of available hyperplanes. Figure T5 illustrates the PCH solutions obtained with S ranging from 15.
When S is small (e.g.. S=4-6), the resulting polyhedron is a coarse envelope that captures the global geometry but cannot closely follow the curved boundary. As S increases, the learned polytope becomes progressively sharper and more circular: additional hyperplanes allow the model to place supporting facets at finer angular resolutions, reducing the discrepancy between the polygon and the underlying smooth circular shape. By S=12-15, the separator visually aligns with the circular boundary and achieves high trust-region accuracy, matching the expected behavior of polyhedral approximations to nonlinear convex sets.
This experiment highlights how PCH adapts naturally to nonlinear convex regions: the method always returns a valid convex outer approximation, and the attainable approximation is controlled directly by the hyperplane budget. Larger values of enable tighter geometric fidelity without compromising the convexity or the interpretability of the resulting model.
Summary. This experiment confirms that PCH generalizes effectively to nonlinear convex sepa- ration tasks. It achieves accurate and geometrically compact separation under limited hyperplane budget, maintains competitive performance even in high-dimensions settings, and avoids the com- putational burden of combinatorial solvers. These results highlight the flexibility and scalability of PCH for large-scale trust region modeling with polyhedral convex hull learning.
G.5 NONLINEAR NONCONVEX TRUST REGION LEARNING
Dataset Generation. To evaluate the robustness of our method in handling the highly irregu- lar, nonconvex trust region, we construct two-dimensional synthetic dataset inspired by the tran- sient stability boundaries in power systems. The positive region is defined as the union of two components. The first is a parabolic head consisting of points (1. (22)) with x11) 2 and (r(2) < -001(2(")-8)2---- +88. The second is circular body defined by for (1) < 8. To introduce nonconvexity, lower parabolic constraint ax(2) 2 -1) + +8 is further imposed on the entire region. This compound structure forms a drop-like shape as shown Figure Points within this nonconvex region are labeled positive; others are labeled negative. We generate 10,000 samples uniformly over the [0, 20 grid to construct the dataset.
< 36
Unlike typical classification settings that tolerate exclusion of few positive samples to gain broader separation from negatives, trust region modeling emphasizes full inclusion of the positive class while excluding as many negatives as possible. This distinction is critical: in standard classification, misclassifying few positive samples can be acceptable if helps correctly separate many negatives. In contrast, trust region learning requires full inclusion of feasible examples, as excluding even a few may compromise the reliability of downstream decisions. Therefore, learning compact convex hulls that tightly enclose all positive samples enables safer, bias-resistant modeling in subsequent classification and constraint learning tasks.
Main Results. Table 12 reports the performance of all methods on this nonconvex setting. PCH achieves high classification accuracy (92.10%) while maintaining a compact model with only 15 hyperplanes. Compared to CGHC (91.83)) PCH provides better geometric alignment and lower training time (25.85s vs. 615.35s). QH achieves slightly higher accuracy (92.15%) by tightly en- closing all positive samples, but the cost of significantly larger number of facets (27), and lacks flexibility in controlling model complexity. These results highlight the advantage of PCH in learning compact trust regions with controllable structure, even under nonconvex ground-truth boundaries.
33

---

Published as a conference paper at ICLR 2026
5-)
5-5
5-)
25 (d) S-7
8-)
8-9
(a)
S=12
(a) S-13
(b) $-14
(c) S-15
Figure 15: Effect the hyperplane budget S on 2D nonlinear convex separation.
34

---

Published as a conference paper at ICLR 2026
Table 12: Performance comparison nonconvex dataset (NINC_N_2)
Method
Accuracy (%)
Runtime (s)
Model Complexity
PCH
92.10
25.85
15
QH
92.15
0.00
27
CGHC
91.83
615.34
15
DCH
91.87
2.04
27
PinCHD
91.86
10.78
14
DeepHull
87.05
3.02
15
Visualization. Figure [6] compares the learned trust regions from different methods. QH recovers the exact convex hull of the positive class, closely following the outer envelope of the true non- convex shape. PCH approximates the region using tight piecewise-linear surface with 15 facets, successfully including all positives while excluding most negatives outside conv(D+). CGHC pro- duces noisier and less regular polyhedron under the same hyperplane budget, leading to reduced accuracy. DCH internally approximates QH and thus closely resembles the exact convex hull in low dimensions, but it does not enforce positive inclusion in general. PinCHD also yields a reasonable approximation, but without explicit control of the number of hyperplanes, its structure may become overly complex in higher dimensions. DeepHull generates a smooth neural approximation but lacks explicit facet representation and positive inclusion; as result, its boundary drifts inward and fails to cover part of the positive region, leaving gaps in the trust region.
(b) CGHC
PCH
480
(d) DCH
(c) PinCHD
( DocpHull
1.9
30
400
48
Figure 16: Visualization of convex hulls NLNC dataset.
Summary. This experiment shows that PCH remains effective even when the true positive region nonconvex. While convex polytopes cannot fully represent nonconvex geometry, PCH succeeds in learning compact trust regions that enclose positive samples while excluding as many negatives possible. This highlights its practical utility in trust region modeling, where full positive coverage essential to improve model performance in downstream tasks. The results suggest that PCH can serve reliable tool for safe region construction applications such power system stability assessment and constraint learning, where strict adherence to feasible boundaries critical.
G.6 REAL-WORLD TRUST REGION LEARNING
Datasets. We further evaluate PCH on a broad set real-world datasets, including four tabu- lar benchmarks (Breast Cancer, Spambase, Bace, HIV) and four more complex tasks (MNIST-35.
35

---

Published as a conference paper at ICLR 2026
FMNIST-24, CIFAR-35, Adult Income). The image datasets converted to binary classification problems by restricting the labels to class pairs 3 vs. (MNIST-35), 2 vs. (FMNIST-244), and vs. 5 (CIFAR-35). Table 13 summarizes the sample sizes, feature dimensions, and hyperparameters used for training.
Table 13: Summary of real-world datasets and training settings.
Cancer
Spambuse
MNIST-35
FMNIST:24
CIEAR-35
Adult
Number of samples (ri)
569
4,601
1,513
41.127
13,454
14,000
12,000
48,842
Feature dimension (d)
30
2,048
2,048
784
784
3,072
10S
Hyperplane budget (S)
10
15
10
100
500
Split temperature (i)
4
Learning rate
0.01
0.01
0.001
0.001
0.001
0.001
0.001
0.01
Main results. Table 14 reports the trust-region accuracy, training time, and model complexity. Across all datasets. PCH attains the highest accuracy while maintaining compact model size and moderate training time. On Breast Cancer, all methods reach near near-perfect accuracy, and PCH matches the best result with only 5 hyperplanes. On Spambase, PCH substantially outperforms CGHC (94.41% % vs. 86. 36%70%) while keeping the hyperplane budget at 10 and the runtime below seconds. For the high- high-dimensional Bace dataset, PCH achieves the best accuracy (98.61% 6)) with 5 hyperplanes, whereas CGHC requires over 8000 seconds and PinCHD expands to 149 hyperplanes.
On the larger and more challenging datasets HIV, MNIST-35, FMNIST-24, CIFAR-35, and Adult Income, PCH scales successfully to tens of thousands of samples and up to 3072 features, handling class imbalance and complex data manifolds, while CGHC and PinCHD fail to produce results within a reasonable time. We emphasize that no parallel or specialized hardware implementation is used for PCH in these experiments; the reported runtimes therefore of the method's scalability.
conservative indication
Performance comparison on real-world datasets. Reported trust-region accuracy (%), training time (s), and model complexity (number of hyperplanes). A dash "_" indicates that method failed scale the dataset.
Table 14:
Trust-region Accuracy/%
Training Time/s
Model Complexity
Problem
CGHC PinCHD
PCH
CGHC
PinCHD
PCH
CGHC PinCHD PCH
Breast Cancer
99.82
99.82
99.82
33.00
0.19
2.55
10
Spambase
86.70
91.41
94.41
446.96
9.87
2.58
10
121
10
Bace
98.35
76.80
98.61
8075.50
257.65
155.53
5
149
5
HIV
99.94
1800.67
15
MNIST-35
99.98
390.80
10
FMNIST-24
99.10
1094.22
30
CIFAR-35
92.58
26868.54
100
Adult Income
89.08
4044.94
500
We further provide a complementary comparison with DeepHull on the more complex datasets (MNIST-35, FMNIST-24, CIFAR-35, and Adult Income). As DeepHull is neural convex- approximation model, we focus here on trust-region accuracy and the fraction of positive samples contained inside the learned region. The results in Table 15 show that PCH consistently achieves higher trust-region accuracy and, importantly, guarantees full inclusion of all positive samples (100% positive coverage all four tasks), whereas DeepHull leaves non-negligible portion of positives outside its learned region.
G.7 SELECTIVE CLASSIFICATION
Datasets. To evaluate the performance of our trust region modeling approach, conduct experi- ments on five binary classification datasets. The first dataset, NLNC_N.2, approximates the transient stability boundary of power system, and its generation method was described earlier. The remain- ing datasets are well-established benchmarks for classification tasks: Breast Cancer, Spambase, Bace, and HIV.
36

---

Published as a conference paper at ICLR 2026
Table 15:
Comparison between PCH and DeepHull in trust-region learning. Reported trust-
region accuracy (%) and positive inclusion (% of positives inside the learned region).
Trust-region Accuracy/%
Positive Inclusion/%
Problem
DeepHull
PCH
DeepHull
PCH
MNIST-35
99.84
99.98
99.94
100
FMNIST-22
91.84
99.10
96.43
100
CIFAR-35
68.66
92.58
85.12
100
Adult Income
64.66
89.08
74.10
100
Experimental Setup. Each dataset is split into training and testing sets with a 4:1 ratio, ensuring that the testing set is kept unseen during the training process. We compare the performance of our proposed method (PCH), with that of CGHC for the task of selective classification. The QH method is excluded from the comparison due to its limitations in handling high-dimensional problems and its inflexibility in controlling the number of supporting hyperplanes.
For downstream tasks, (Multi-layer Perceptron). We employ default parameters for the CART model. The hyperparameters of the MLP classifier are selected based on training performance.
classifiers: CART (Classification and Regression Trees) and MLP
We evaluate each classification model (CART and MLP) under five configurations. The baseline configuration, denoted "_", uses the classifier trained on the full dataset without trust region filtering, Configurations marked with use the same classifier but apply trust region filtering during inference: only samples that lie within the trust region (PCH or CGHC) and are predicted positive are classified as positive; all others are classified as negative. Configurations marked with retrain the classifier using only samples inside the corresponding trust region and apply the same filtering strategy.
Table 16: Selective classification results across five datasets using CART and MLP classifiers, with and without convex hull-based trust region filtering. The superscript denotes configurations where the initial classifier, trained on the full dataset, is used in conjunction with trust region filtering during prediction. The superscript denotes configurations where the classifier retrained based on the learned trust region. PCH outperforms CGHC and base classifiers in terms of accuracy, F1
score, and AUC.
Trust Region
CART-based Classification
ML.P-based Classification
Problem
Index
CGHIC
PCI1
CGUCT CGHC! PCI1
PCH1
CGUCT CaHe! PCIT"
PC11
ACC
91.40
91.75
98.30
98.40
98.90
98.35
99.00
94.50
94,80
97.70
95.20
98.30
N.NC.N.2
F17%
88.87
89.28
97.52
97.66
98.41
97.59
98.55
92.29
92.68
96.61
93.20
97.50
AUC/%
93.37
93.64
97.98
98.09
98.92
98.05
99.04
98.87
99.00
98.62
99.04
98.47
Breast Cancer
F1/%
96.50
97.90
92.86
93.43
98
92.65
96.45
95.71
93.43
92.65
95.71
94.96
AUCHE
95.54
97.42
91.57
93.67
98.07
93.62
95.14
99.50
99.47
99.40
99.50
99.11
ACC/%
81.43
89.36
91.10
92.07
91.10
93.27
91.86
93.16
92.62
90.88
93.59
89.79
Spanbuse
89.54
AUC/5
83.57
90.30
90.78
92.33
92.06
92.72
90.46
97.32
97.42
94.70
97.59
93.61
ACC
70.63
78.22
74,92
70.96
72.28
75.58
77.56
74.26
72.28
72.94
77.89
78.55
Bace
F11%
67.87
76.43
72.26
61.40
65.00
69.92
74.05
73.10
64.41
64.35
74.72
74.71
AUC
70.42
78.16
75.78
77.23
72.07
78.12
77.85
82.87
82.46
81.14
83.37
82.44
96.13
HIV
F1/%
1
32.50
40.19
38. 72
42.
42.92
39.77
AUC
68.59
65.59
67.91
74.78
75.60
74.83
Results and Discussion. The results from the selective classification experiments across the five datasets are summarized in Table The table shows that the PCH method consistently outperforms CGHC in terms of accuracy (ACC). F1 score, and AUC across most datasets and classifiers. For instance, the NLNC_N_2 dataset when using CART, the AUC of CART with PCH! is 99.04%, compared to 97.98% for only using CART, highlighting a significant improvement when the trust region utilized.
37

---

Published as a conference paper at ICLR 2026
Moreover, combining the trust region models with the CART classifier generally leads to perfor- mance improvements, particularly when retraining the model using only the samples within the trust region (PCH and CGHC1). This configuration achieves the highest accuracy, F1 score, and AUC across most datasets, clearly demonstrating the advantages of focusing the model's attention on the most relevant data points. However, when comparing the performance of PCH to CGHC, we ob- serve a consistent advantage of PCH across most datasets and classifiers. Specifically, on the Breast Cancer dataset when using MLP.PCH leads to higher classification scores, such as the 78.55% ACC with PCH', compared to the best result of CGHC which only achieves 72.94% ACC in the same configuration. is worth noting that when retraining the MLP model, we assign twice the weight to the samples within the trust region during loss calculation, as compared to the samples outside the trust region. This approach helps avoid potential bias in the classification model.
Interestingly, the need for retraining the model is not always critical for achieving strong perfor- mance. For datasets with simpler, more linear and convex decision boundaries, such as the Breast Cancer dataset, simply applying the trust region as classifier is sufficient to achieve excellent re- sults. In this case, PCH significantly outperforms CGHC, as demonstrated by the higher accuracy (97.37% vs. 95.61% % for CGHC) and F1 score (97.90% vs. 96.50% for CGHC) achieved by PCH.
In contrast, for datasets with more complex decision boundaries, such as NINC_N_2, retraining the model on the trust region (PCH)) results in substantial improvements. This configuration leverages the PCH method's s ability to tightly encapsulate the relevant data, achieving an AUC of 99.04% compared to 98. 98% AUC for CGHC, further highlighting the superiority of PCH in handling more complex classification tasks.
For nigher-dimensional and large-scale datasets, such HIV, CGHC fails successfully initialize and compute the trust region. In contrast, PCH remains effective, demonstrating its robustness and scalability in handling challenging, high-dimensional data, where CGHC struggles to produce valid results.
G.8 CONSTRAINT LEARNING AND EMBEDDING
Datasets. We evaluate the integration of trust-region-assiin assissed constraint learning into optimization workflows using the NLNC_N. dataset, which approximates the transient stability boundary of power system. The convex trust regions constructed by PCH and CGHC are those learned in Sec- tion G.5 and are visualized in Figure I6 The downstream task is formulated as a two-dimensional linear optimization problem, where the decision variable (zx(1) (2) E IR.2 represents key opera- tional states of the power system.
Experimental Setup. To simulate uncertainty in real-world power system operations, we ran- domly sample the upper and lower bounds for each decision variable within predefined ranges. These intervals capture variability in external conditions such as load, generation, or voltage levels. In addition, a random linear cost vector is drawn to reflect fluctuations in economic objectives or op- erational priorities. The goal is to assess whether constraint learning methods, when combined with different trust-region models, can support effective decision-making under uncertainty. Specifically, we evaluate whether the resulting solutions remain feasible, meaning they lie within the transient stability boundary, and whether they are also cost-effective with respect to the given objective.
The optimization problem is formulated as:
() + (2
min (mx()) 2n)
JERZ JERZ
(x(11) (2)) E [L,
(e(1),x(2)) E ReARTMLP.
(zx(1), (2()) E CIR.
where [E, u| denotes the uncertainty interval imposed on the decision variables, REARTMLP represents the feasible region specified by the constraint rule learned from either CART or MLP classifiers. The CART and MLP can be modeled as mixed-integer linear constraints in the optimization problem (Ja CTR is the convex trust region obtained from either PCH or CGHC.
et al. 2025
38

---

Published as a conference paper at ICLR 2026
For CART, vary the maximum tree depth from 6 to 10. For MLP, we adopt two-hidden-layer architecture with hidden layer sizes (h, 5), where h E {15,30, 50, 100, 2003. The MLP is trained using a batch size of 1024, learning rate of 0.001, and 3000 training epochs.
We compare five configurations for constraint embedding in the optimization model. The baseline configuration, denoted "_", uses only the constraint learned from the classifier without incor- porating any trust region. The configurations marked with use the classifier trained on the full dataset and apply trust region filtering at the optimization stage, based on either PCH or CGHC. The configurations marked with F retrain the classifier using only samples within the correspond- ing trust region, and then embed both the updated classifier constraint and the trust region into the optimization problem. When retraining the MLP within the convex trust region, we apply a sample- weighting strategy that assigns twice the loss weight to samples inside the trust region compared to those outside, thereby encouraging the model to focus on local decision boundaries while retaining global generalization.
Table 17: Performance of constraint learning and embedding with CART and MLP under different configurations. The configuration "_" uses only the learned constraint model without any trust region filtering- The superseript denotes configurations where the constraint model is trained on the full dataset and combined with trust region filtering during optimization. The superscript $ denotes configurations where the constraint model is retrained based the corresponding trust
region before embedding.
CART-based constraint leaming
Hidden size
MLP-based constraint learning
Index
Depth
CGHCI CGHC
PCH
PCH+
CGHCI CGHC!
PCH
PCH1
6
93.76
97.65
98.35
98.40
99.55
15
99.20
99.32
98.93
99,36
99.17
Training Accuracy
7
96.46
98.03
98.80
98.74
99.75
30
99.81
99.83
99.80
99.84
99.85
8
97.43
98.48
09.04
99.00
99.89
50
99.84
99.87
99.80
99.92
99. 89
(%)
98
98.95
99.24
99.22
100
99.83
99.3
99.89
99.87
99.94
10
99.30
99.50
99.46
99.69
100.00
200
99.90
99.92
99.90
99.92
99.90
6
69.00
69.00
56.00
84,00
71.00
15
81.00
81.00
85,00
89.00
90.00
Feusibillity Rate
7
66.00
69.00
57.00
82.00
72.00
30
87.00
88.00
90.00
94,00
93.00
8
68.00
70.00
56.00
82.00
70.00
50
83.00
88 38.00
78.00
91.00
89.00
(%)
9
64.00
66.00
$7.00
73.00
70.00
100
86.00
86.00
77.00
91.00
92.00
10
65.00
65.00
$7.00
75.00
70.00
200
87.00
86.00
92.00
90.00
6
5.88
5.97
5.74
6.00
5.76
15
5.78
5.78
5.78
5.78
5.78
Objective Cost
7
5.70
5.77
5.75
5.79
5.76
30
5.77
5.77
5:77
5.77
5.77
8
5.72
5.76
5.73
5.78
5.76
50
5.77
5.77
5.76
5.77
5.77
5.75
5.77
5.76
100
5.77
5.77
5.76
5.77
10
5.72
5.74
5.74
5.76
5.76
200
5.77
5.77
5.77
5.77
5.77
6
75
90
90
90
107
15
85
100
100
100
100
Constraint
7
162
177
158
177
195
30
145
160
160
160
160
Number
8
238
253
290
253
270
50
225
240
240
240
240
9
381
396
409
396
325
100
425
440
440
440
440
10
568
583
463
200
825
6
12
12
12
12
15
20
20
20
20
Rinary Variable
7
24
24
21
24
28
30
35
35
35
35
8
33
33
37
33
37
50
55
55
55
55
55
Number
48
30
48
100
105
105
105
105
10
66
66
55
66
47
200
205
205
205
205
205
Results and Discussion. Table 17 summarizes the results across key metrics, including training accuracy, feasibility rate of the optimized solutions, average objective cost, and model complexity in terms of the number of constraints and binary variables. The feasibility of each optimized solution is evaluated against the ground-truth stability boundary used to generate the NINC N 2 dataset.
The results demonstrate that integrating a trust region into the constraint learning and embedding process significantly improves both safety and efficiency of the downstream optimization. With- out any trust region filtering (denoted by "-"), feasible rates remain relatively low, e.g., 69% for CART and 81-88% for MLP. By incorporating the convex trust region learned via PCH ()), the feasible rates increase substantially, reaching up to 84% for CART and 94% for MLP. Moreover, this improvement is achieved without retraining the classifier and with marginal increase in model complexity. This result highlights that even without retraining, PCH-based trust regions can already provide strong regularization for decision boundaries, enabling safe and efficient optimization.
39

---

Published as a conference paper at ICLR 2026
Compared to CGHC, PCH consistently demonstrates superior performance across all tested config- urations and classifier types in constraint learning and embedding. In terms of feasibility rate, PCH achieves the highest values under both filtering-nnly ()) and retraining (1) settings. For instance, with CART depth 6, the feasible rate increases from 69.0% (no trust region) to 84.0% with PCH*, compared only 69.0% for CGHCt. Similar trends hold for MLP classifiers. At hidden size 30, PCH achieves feasible rate of 94.0%, outperforming CGHC at 90.0%.
Across both CART and MLP configurations, all methods achieve comparable objective cost, with PCH often matching or slightly improving over CGHC. Notably, under deeper tree or wider network settings, PCH tends to reduce the number of binary variables or constraints required to achieve similar performance. For example, at CART depth 10, PCH achieves the same objective value (5.76) as CGHC while reducing the number of binary variables from to 47 and constraints from 463 to 365, and also has higher feasibility rate (70% vs. 57%). These results indicate that PCH can produce more compact constraint representations, improving embedding efficiency downstream optimization without sacrificing feasibility reliability.
G.9 ADDITIONAL GRADIENT-BASED BASELINES AND ABLATION STUDY
We provide additional experimental analyses that complement the main results in this subsection. We first compare PCH with the most relevant gradient-based polytope learners available in the litera- ture. highlighting the differences in modeling assumptions and decision boundaries. We then present an ablation study that isolates the contribution of each major component the PCH framework. To- gether, these results offer clearer view of how PCH relates to existing gradient- baseed approaches and why the full design of the method is necessary for achieving both tightness and scalability.
Training settings. All experiments in this subsection the same polyhedral datasets and the training settings described in Appendix[G.3 For comparison with existing gradient-based polytope learners, include the Convex Polytope Tree (CPT) model of Armandpour et al.) (2021), trained using its default settings for 20 epochs. Although CPT is not designed to output explicit linear con- straints, it represents the closest gradient-based formulation available in the literature. We report results for three depth configurations (CPT_1, CPT_4, _4, CPT_8), corresponding to increasing levels of model capacity. To further isolate the effect of PCH's design choices, we evaluate three ablated variants: PCH_WOP (removing projection-basee weight assignment), PCH. SOS (disabling subre- gion assignment), and PCH WOA (removing adaptive structure adjust). All ablated models share the same training settings as the full PCH model. This unified setup ensures that differences in performance can attributed directly modeling choices rather than implementation details.
Main Results. As shown Table across all tested polyhedral datasets, PCH achieves the high- est trust-region accuracy, demonstrating ability to learn tight and reliable polyhedral separators. The CPT models improve with increasing tree depth but remain noticeably below the performance of a single PCH hull, reflecting the difficulty of recovering explicit polyhedral boundaries through noisy-OR aggregation. The ablation variants further confirm the importance of PCH's key compo- nents: removing projection- baaset weight assignment (PCH. WOP), disabling subregion assignment (PCHLWOS), turning off adaptive structure adjustment (PCH.WOA) leads to substantial perfor- mance degradation, particularly in higher dimensions. These results underscore that the full PCH pipeline is essential for obtaining accurate and geometrically tight polyhedral trust regions.
40

---

Published as a conference paper at ICLR 2026
Trust region accuracy comparison between PCH, CPT models with different tree depths, and ablated variants of PCH on the polyhedral datasets.
Table 18:
Problem
PCH
CPT
CPT 4
CPT
PCH WOP
PCH wos
PCH WOA
PH 2
100.00
74.70
83.67
89.00
95.19
99,41
99.98
PH 15 3
100.00
69.64
79.17
85.98
86.23
99.34
99.98
PH_15_4
100.00
66.81
73.41
80.21
82.90
99.57
99.82
PH_15_5
99.52
68.19
71.94
79.04
83.06
98.96
99.11
PH_15_6
100.00
62.64
69.25
76.24
77.16
98.29
96.29
PHL15.7
99.67
66.56
69.04
75.71
77.61
94.34
97.97
PH_15_8
100.00
71,81
75.01
78.69
79.56
97.01
92.15
PH 15 10
100.00
73.86
74.65
77.08
77.20
98.28
88.72
PH 15 100
99.95
64.34
65.11
65.48
71.03
87.88
55.14
H USE OF LARGE LANGUAGE MODELS
Large language models (LLMs) were used in this work only as general-purpose assistants to aid and polish the writing. All research ideas, technical developments, theoretical results, and experiments were conceived and conducted by the authors. The authors take full responsibility for the entire content of the paper.
41


Reviews:
[{"review_id": "Jyt8HJrBiN", "reviewer": "Reviewer_hxmb", "summary": "This paper introduces the Projection Convex Hull (PCH), a scalable and adaptive framework for learning compact, polyhedral trust regions from data consisting of positive and negative points. The fundamental problem of computing the tight convex hull is actually a Mixed-Integer Nonlinear Program (MINLP). Classical geometric methods suffer from complexity that grows exponentially with dimension, and existing optimization-based approaches lack practical scalability.\n\nThe authors overcome this challenge through a rigorous theoretical decomposition. They first formally express the convex hull problem as a MINLP that explicitly accounts for model compactness. Then, they reduce the problem into multiple subproblems that handle one hyperplane at once. The authors prove that the solution for finding the optimal hyperplanes can be recovered as a stationary point of an unconstrained surrogate objective function under suitable weights. This surrogate loss function is minimized using gradient steps. The weight for each negative point is carefully designed and updated during this process to ensure that minimizing the weighted surrogate function is equivalent to maximizing the intended separation margin of the original MINLP.\n\nIn practice, the PCH framework achieves structural adaptivity: it dynamically manages the model complexity by pruning redundant hyperplanes and adding new ones if the current hull still incorrectly encloses negative samples. This ensures the final model is as compact and accurate as possible.", "questions": "- Lemma 1 does not ensure that the collection of all optimal solutions of the subproblem is the optimal solution of the original problem. How does the proposed algorithm ensure its global optimality?\n- The adaptive strategy adds hyperplane when contains negative points and removes when encounter redundancy. Then how to decide the number S in practice? And what happened when the positive points are not convex (where the convex hull containing negative points are inevitable) ?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is very well written. It solves the problem gradually by breaking it down into simpler, smaller subproblems, makes the algorithm easy to follow.\n- The method is strong in both theory and practice. PCH maintained high accuracy and low running time and its usage benefits the real-world downstream tasks.", "weaknesses": "- More detailed comparison to related gradient-based works are needed.\n- see the question below", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AxjVdMSDqM", "reviewer": "Reviewer_c9H4", "summary": "Motivated by the observation that complex and nonlinear classification boundaries often exhibit regional linearity and can be locally approximated by hyperplanes with small classification error, the paper constructs a convex hull that is scalable,\nstructurally adaptive, and geometrically tight. Specifically, from the MINLP problem formulation, the work establishes its connection to a family of unconstrained surrogate objectives. This enables gradient-based learning of convex hulls that are both compact and theoretically motivated.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper effectively addresses key limitations of prior works in terms of scalability, adaptivity, and boundary tightness, and provides theoretical guarantees to support its claims. Given the intrinsic complexity of the MINLP formulation, it is particularly commendable that the authors decompose the original problem into a series of per-hyperplane subproblems with unconstrained surrogate objectives, making the optimization process more tractable. \nThe final solution is obtained through gradient-based optimization, which further enhances computational efficiency. Moreover, the proposed adaptive structural adjustment introduces principled hyperplane addition and pruning criteria, enabling the model to maintain scalability without sacrificing geometric tightness.", "weaknesses": "The experimental evaluation appears somewhat limited. While the results on the BreastCancer, Spambase, Bace, and HIV datasets demonstrate the feasibility of the proposed approach, these datasets are relatively simple and well-studied binary classification benchmarks. To better assess the generalization ability and robustness of the proposed method, it would be valuable to include experiments on more challenging and diverse datasets, such as those with higher-dimensional features, class imbalance, or more complex data manifolds.\n\nAdditionally, it is not entirely clear whether the optimization process is guaranteed to converge. Since the proposed formulation involves nonconvex components and relies on surrogate objectives and iterative weight updates, a brief theoretical or empirical discussion of the convergence behavior (e.g., monotonicity of the objective, stability of fixed points, or stopping criteria) would strengthen the work and improve the reader’s understanding of the algorithm’s reliability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iaMU8VUiHD", "reviewer": "Reviewer_5jY7", "summary": "The paper proposes an algorithm for learning convex hulls (polyhedral trust regions) from labeled data, ensuring that all positive samples are enclosed while excluding negatives as much as possible. Traditional geometric or MILP approaches fail to scale in high dimensions and lack flexibility, and it aims to design a scalable, theoretically grounded, and adaptive framework to learn boundary-tight convex hulls efficiently. The main contribution is that, the authors propose a divide-and-conquer learning framework that links an exact MINLP problem to an unconstrained surrogate objective, making gradient-based optimization feasible.", "questions": "1. A main contribution concerns the algorithm’s computational complexity. However, it appears to depend on the number of iterations—what is the typical order or empirical scaling of this term?\n\n2. The authors should discuss potential failure cases, such as when the positive region is nonconvex or when the hyperplane budget is insufficient to capture the desired boundary.\n\n3. Is that any small example showing that the surrogate formulation indeed approxiamte the discrete MINLP problem?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a novel gradient-based surrogate formulation for convex hull learning, bridging discrete MINLPs with differentiable optimization. Moreover, its adaptive structure and surrogate update scheme enable practical training in high-dimensional settings, as demonstrated empirically.", "weaknesses": "1. It is unclear how the main theoretical result (Theorem 1) relates to the practical algorithm. The theorem establishes the existence of a certain weight assignment, but it is not evident whether this weight can be computed or approximated by Algorithm 1 or the procedure described in Section 5.2. Although there is some discussion in lines 354–356, the connection remains ambiguous, especially since Equation 3 does not explicitly include a weight term.\n\n2. In addition, no convergence analysis or guarantee (e.g., monotonic improvement) is provided for the surrogate updates.\n\n\n\n3. Since the algorithm is somewhat unintuitive, it would be helpful to include a simple 2D toy example illustrating the evolution of the hyperplane and weight updates over iterations. This visualization would greatly enhance readers’ understanding of the surrogate optimization process.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cFUDvJ8ziz", "reviewer": "Reviewer_G8zX", "summary": "This paper proposes the Projection Convex Hull (PCH) method, a scalable framework for learning polyhedral trust regions in high-dimensional spaces. The link between the intractable MINLP for tight convex hull learning and an unconstrained surrogate objective is established. The PCH framework incorporates (i) partition-based subregion assignment, (ii) a surrogate objective to align hyperplanes with class boundaries,and (iii) adaptive hyperplane pruning and addition. Experiments on synthetic and real-world datasets show that\n PCH achieves high accuracy and superior scalability.", "questions": "See Weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. PCH is proposed with sound theoretical foundation.\n2. PCH scales to high-dimensional and large-scale problems.\n3. Besides convex hull learning, downstream tasks including selective classification and constraint learning are considered.\n4. Figure 1 and Figure 2 intuitively illustrates the main steps of PCH .", "weaknesses": "1. Whether trapping into local minima is possible during the optimization is not discussed.  \n2. How is the robustness of PCH in the presence of data noise?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)