acceptodds
Under review as a conference paper at ICLR 2027

Decision-Focused Clustering

Abstract

Modern platforms often need to make personalized decisions for a large number of instances, repeatedly solving the same optimization problem with different instance-specific parameters. When the number of distinct decisions is limited, a natural approach is to group instances into clusters and assign a shared decision to all instances within each cluster. Standard clustering methods such as -means, however, group instances according to geometric similarity, which need not preserve downstream decision quality. We propose Decision-Focused Clustering (DFC) for linear downstream optimization problems, which forms clusters based directly on the quality of the decisions shared within each cluster. To formalize this objective, we introduce a decision loss that measures the regret of using the decision optimized for one cost vector when the true cost vector is another. Since the resulting clustering problem is NP-hard, we develop an alternating optimization algorithm that iteratively updates cluster representatives and instance assignments. We further establish theoretical convergence guarantees for the proposed algorithm. We evaluate our framework on synthetic shortest-path and portfolio optimization problems and a real-world courier dispatching problem, covering decision problems with different feasible-set structures, including polyhedral and strongly convex settings. Compared with \(k\)-means, DFC consistently achieves lower decision loss in all three application settings.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Decision-Focused Learning, Clustering, Predict-then-Optimize, $k$-means

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_dP7EOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Decision-Focused Clustering, which groups instances based on the regret incurred by sharing decisions in linear downstream optimization problems. The authors establish the problem's NP-hardness and develop an alternating optimization algorithm that updates cluster representatives and instance assignments, with theoretical convergence guarantees.

Critical strengths
  • The paper groups instances according to the quality of their shared downstream decisions, directly addressing the mismatch between geometric similarity and decision quality.

  • The alternating procedure admits an optimal mean-based representative update for each fixed cluster, while its assignment step avoids computing individualized optimal decisions for every instance.

  • The paper establishes NP-hardness and proves convergence of the algorithm’s objective values.

Critical weaknesses
  • The algorithmic contribution requires a substantially more detailed comparison with prior work.
  • Theorems 3 and 4 assume exact global empirical minimization, whereas Algorithm 1 only guarantees monotonic objective descent.
  • The experiments compare only with kk-means. Please include decision-aware baselines, such as greedy decision selection and local search, and report runtime and optimization-oracle calls. The shortest-path experiment has only six feasible paths, making exact optimality-gap evaluation straightforward; larger instances would better demonstrate the method’s effectiveness.
Questions for authors

See weaknesses.

  • How does DFC compare with closely related methods, particularly SPO Trees (Elmachtoub et al., 2020) and Bregman-based clustering (Banerjee et al., 2005; Iyer and Bilmes, 2012), in terms of algorithm design, theoretical guarantees, and empirical performance?
4 comments
AuthorsOpenReview ↗

Author Response (Part 1/3)

We thank the reviewer for the suggestions on related methods, optimization guarantees, and empirical evaluation. We have revised the theoretical positioning and expanded the comparisons. The response below distinguishes results already included in the manuscript from additional larger-grid results reported here.

0. New Results regarding the linear feasible region

We have added a new result, Theorem 2, in the revised manuscript to exploit the clustering structure induced by the parameter space. Theorem 2 establishes conditions under which instances can be pre-grouped based on their locations in the parameter space, potentially reducing the computational complexity of the clustering algorithm. Note that the instances within the same cone may not be grouped into one cluster. Theorem 2 provides a sufficient condition for this pre-grouping method. We provide the detailed analysis in the newly added Appendix A. This result further distinguishes our work from existing approaches, particularly in the setting of linear optimization.

1. Comparison with SPO trees and Bregman-based clustering

Section 1.1 now discusses SPO trees, classical and generalized Bregman clustering, DMOC, and objective-uncertainty KK-adaptability. Table 1 compares their modeled scope, algorithms, statistical guarantees, and use of cost-vector representatives.

WorkFeasible regionInfinitely many candidate optimal pointsAssignment/decision alternationFinite exact identificationFinite-sample risk boundsCost-vector representatives in algorithm ‡Lossless pre-grouping §
DMOC (2021)Convex allowed✓✓————
KK-adaptability (2019)Binary—✓————
SPO trees (2020)Convex allowed✓———✓—
SAA (2002)Finite——✓✓——
Prünte (2020)Compact✓✓✓†———
DFCCompact convex✓✓✓✓✓✓

†: Finite-case consequence of SAA consistency. DFC's exact identification requires a bounded polyhedron, a vertex-selecting oracle, and exact empirical minimization. SAA's risk bounds concern finite feasible regions.

‡: Algorithmic representation only; DMOC and KK-adaptability admit equivalent mean-cost updates for linear objectives.

§: For bounded polyhedra with a vertex-selecting oracle (Theorem 2).

SPO trees. Both methods use the mean cost within a group to obtain a shared decision. SPO trees assign observations through feature-based tree splits when the costs being predicted are unknown. DFC observes the cost vector used for assignment and directly chooses the cheapest shared decision. Thus, the differences concern the available information and the restrictions on assignments, rather than the within-group averaging principle. The current experiments do not include a standalone SPO-tree benchmark; we do not claim empirical superiority over SPO trees.

Generalized Bregman clustering. We now cite both Banerjee et al. (2005) and Iyer and Bilmes (2012). DFC fits within the generalized Bregman framework. To make the relationship explicit, define

F(c)=−min⁡w∈Sc⊤w.F(c)=-\min_{w\in S}c^\top w.

Then −w∗(μ)∈∂F(μ)-w^*(\mu)\in\partial F(\mu) and

=F(c)-F(\mu)-\langle-w^*(\mu),c-\mu\rangle.$$ The generator is determined by the downstream optimization problem and may be nonsmooth. Nonsmoothness alone is not a distinction from generalized Bregman clustering. With this generator, selected subgradients, and matched update conventions, the corresponding generalized Bregman implementation reproduces DFC's objective and core updates. We therefore emphasize the downstream interpretation and explicit population-risk analysis, rather than claim a new alternating mechanism. The revised discussion similarly acknowledges that the shared-decision objective and core updates overlap with $K$-adaptability and linear DMOC.
AuthorsOpenReview ↗

Author Response (Part 2/3)

2. Exact optimality gaps and decision-aware comparisons

Figure 4 and Appendix D.1 now compare DFC with exact enumeration over the six feasible paths. At K=3,4,5K=3,4,5, the exact training optima are 0.22668, 0.06704, and 0.01912, whereas mean DFC training regrets are 0.30375, 0.13174, and 0.04402. The exact optimum is reached in 25/35, 16/35, and 21/35 runs, respectively. These results quantify remaining gaps rather than equate monotonicity with optimality.

For the original six-path problem, we enumerate every subset of at most KK feasible paths and minimize training regret. Appendix D.1, Table 4 reports:

KKExact training optimumMean DFC training regretOptimal runs
30.226680.3037525/35
40.067040.1317416/35
50.019120.0440221/35
600.0005534/35
7–100035/35 for each KK

DFC frequently attains the exact optimum, but the gaps at smaller budgets show that objective descent does not ensure global optimality. The test reference in Figure 4 evaluates the training-optimal shared paths unchanged. On the additional 2×32\times3, 3×33\times3, and 4×34\times3 networks in Appendix D.3 and Figure 8, it reaches the exact training optimum in 73/80 runs. Thus, the exact-hit result does not extend to every tested instance.

We added Ward hierarchical clustering throughout the three applications, portfolio local and swap-based local searches in Appendix E.3, and courier search in Appendix G.1. At 2,000 portfolio training observations, the best searches improve training regret by 0–0.79%; the global gap remains unknown. For courier at K=35K=35, search reduces training regret from 0.038200 to 0.029186 and test regret from 0.045837 to 0.038257 minutes per order, using 5.647 additional seconds and 3,000 additional solves.

3. Exact empirical minimization versus the implemented algorithm

We agree that Theorems 4–5 considers exact global empirical minimization. Section 3 now explicitly distinguishes monotonic empirical objective values from exact empirical minimization (Line 318). Theorem 4 applies the finite-decision SAA argument; Theorem 5 bounds statistical estimation error for exact empirical minimizers.

For an algorithmic output μ~N\widetilde{\boldsymbol\mu}_N, define εN=R^N(μ~N)−min⁡R^N(μ).\varepsilon_N=\widehat R_N(\widetilde{\boldsymbol\mu}_N)-\min \widehat R_N(\boldsymbol\mu).

Under Theorem 5's assumptions, its proof in Appendix B gives, with probability at least 1−δ1-\delta,

\leq BD\sqrt{\frac{2\{Kd\log(1+2N)+\log(2/\delta)\}}{N}} +\frac{4BD}{N}+\varepsilon_N.$$ Here $B$ bounds the cost norm and $D$ is the feasible-region diameter. This separates statistical error from empirical optimization error. The descent guarantee does not bound $\varepsilon_N$. Section 5.2 also states that the Gaussian-based portfolio experiment and its numerical reference do not directly verify the theorem's bounded-cost and exact-minimization assumptions. **4. Greedy selection and larger networks** The additional experiments accompanying this response compare greedy shared-decision selection with DFC and DFC followed by path replacement on $5\times5$ and $8\times8$ grids. Each setting uses 500 training and 500 test observations, $K=3$, and three matched data repetitions. Under IID costs, test regret is: | Method | $5\times5$ grid | $8\times8$ grid | | --- | ---: | ---: | | $k$-means | 9.21291 ± 0.23864 | 22.63478 ± 0.77896 | | DFC | 9.21291 ± 0.23864 | 22.63478 ± 0.77896 | | Greedy selection | 8.92334 ± 0.49668 | 22.43977 ± 0.26452 | | DFC + path replacement local search | 8.82063 ± 0.30589 | 22.00293 ± 0.51993 | Entries are mean ± sample standard deviation. Greedy selection improves on base DFC in these settings, while DFC followed by path replacement has the lowest reported mean. The small number of repetitions does not establish statistical superiority. Under the additional corridor-mixture costs, all four methods achieve essentially zero regret, so those cases do not distinguish their quality. For the IID cases, algorithm time changes from 0.0199 to 0.0208 seconds on $5\times5$ and from 0.0236 to 0.0610 seconds on $8\times8$ when adding path replacement. These times include the starting DFC fit but exclude shared precomputation. Cached candidates avoid additional downstream solves during replacement, but candidate preparation and search are not cost-free.
AuthorsOpenReview ↗

Author Response (Part 3/3)

5. Runtime and optimization-oracle calls

Appendix I reports both total and algorithm-stage costs. Table 11 includes preprocessing and training: DFC takes 0.59461 seconds for shortest path (K=3K=3), 8.27277 seconds for portfolio (K=5K=5), and 37.1364 seconds for courier (K=10K=10), saving 15.7%, 20.5%, and 14.7% relative to matched individualized optimization. The corresponding solve counts are 3,217.06 versus 4,000, 2,186.5 versus 3,000, and 3,346 versus 4,110.

Setting: training/test size; KKIndividualized time (s)DFC time (s)Individualized solvesDFC solvesTime saved
Shortest path: 3200/800; 30.705670.594614,0003,217.0615.7%
Portfolio: 2000/1000; 510.400338.272773,0002,186.520.5%
Courier, split-first: 3288/822; 1043.521937.13644,1103,34614.7%

The measured DFC implementation uses Ntrain+K(T+1)N_{\rm train}+K(T+1) solves, including cached individualized training optima. This cache is unnecessary for assignment but is included in the reported implementation costs. Further assignment to learned shared decisions requires no downstream solves.

Tables 12–17 extend the evaluation across decision budgets and sample sizes, retaining cases where DFC is slower and runs reach the iteration cap. For example, the separate 5000/1000 portfolio campaign is 22.7% slower than individualized optimization at K=35K=35. The revised discussion therefore treats runtime as a tradeoff with decision quality and training effort, rather than a uniform improvement over individualized optimization or geometric clustering.

We thank the reviewer again for the constructive feedback and valuable suggestions. We believe that the revised manuscript and additional experiments provide a more comprehensive comparison with existing methods, clarify the scope of our theoretical guarantees, and address the concerns about empirical optimality and computational efficiency. We hope these revisions and results satisfactorily resolve the reviewer's questions and further clarify the contributions of DFC.

Thanks to the authors for taking the time to respond and revise the manuscript. There appears to be a gap between the theoretical guarantees and the algorithm (and the experiments). Some aspects of the presentation also need improvement—for example, the explanatory text in Figure 8. After considering the rebuttal and revisions, I will maintain my score.

Reviewer_mS3SOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces Decision-Focused Clustering (DFC), a clustering method for settings where many instances must share a limited number of downstream optimization decisions. Instead of grouping instances by geometric proximity DFC clusters them according to the decision loss (regret) caused by using a shared decision. As is evident from linear programming, nearby parameter vectors can lead to different optimal actions.

The authors show the underlying optimization problem to DFC is NP-hard, but develop an alternating algorithm that assigns instances to the representative producing the lowest decision loss and updates each representative using its cluster’s mean cost vector; they also provide convergence and statistical guarantees under stated conditions. In synthetic shortest-path and portfolio tests and a real-world courier-dispatching case, DFC consistently produces lower held-out decision loss than k-means

Critical strengths

1.) Well-motivated formulation. The setup is interesting and recognizes that nearness of vectors does not necessarily correspond to the quality of a shared downstream decision. DFC directly optimizes decision loss, making the objective better aligned with predict-then-optimize use cases.

2.) The authors establish NP-Hardness, give a monotonic alternating optimization method with closed-form representative updates, and provide statistical guarantees. They then test across shortest-path, portfolio, and real-world courier-dispatch settings, where DFC consistently beats k-means on held-out decision loss.

Critical weaknesses

1.) Their Algorithm 1 does not have a guarantee on the quality of its output. On the other hand, the problem it seeks to address is NP-Hard. It is a heuristic with iterations that resemble the typical procedure for k-means clustering.

2.) Under Distribution shift, DFC can be outperformed by k-means.

Questions for authors

This paper is technically solid, but answers to the following questions could help to convince me of its contribution and novelty.

1.) Since the DFC objective is NP-hard and the proposed alternating algorithm is not globally optimal, how sensitive are results to initialization and the number of restarts? Can the authors report runtime, number of downstream solver calls, and scaling with the number of instances, clusters, and decision dimension relative to k-means?

2.) The paper is framed as clustering, but the optimization objective appears to be the design of a finite collection of KK decisions that minimizes average regret, with clusters emerging as assignment regions induced by those decisions. This seems closely related in spirit to KK-adaptability, and related robust/adjustable optimization approaches. Could the authors compare DFC relative to this literature; more precisely, clarify what is uniquely gained by the clustering parameterization through representative cost vectors and compare against decision-menu or KK-adaptability-inspired baselines where applicable?

4 comments
AuthorsOpenReview ↗

Author Response (Part 1/3)

We thank the reviewer for the constructive assessment. We have expanded the analysis of initialization, computational cost, and distribution shift, and clarified DFC's relationship to selecting a limited collection of shared decisions.

1. Solution quality, initialization, and restarts

We agree that Algorithm 1 is a heuristic. Theorem 2 guarantees nonincreasing empirical objective values, but not global optimality. Section 3.1 now explicitly distinguishes this guarantee from the statistical results for exact empirical minimizers. We also clarify in Line 318 that the empirical optimization error contributes an additional term to the finite-sample risk bound.

In the revised manuscript, we include the exact empirical optimum for the shortest-path problem in Figure 4 and the best-found solutions from local search for portfolio optimization and courier dispatching in Figures 5 and 6, respectively. These comparisons show that DFC often achieves the exact optimum in the shortest-path setting, while additional local search yields relatively small improvements in portfolio optimization (Appendix D.3).

Particularly, in the original six-path problem, DFC attains the exact training optimum in 25/35, 16/35, and 21/35 runs at K=3,4,5K=3,4,5 (Appendix D.1, Table 4). Although the global optimality gaps remain unknown for the latter two applications, the results provide further evidence of DFC's empirical solution quality.

Appendix H compares initialization with fitted kk-means centers against randomly sampled training cost vectors, keeping the data and subsequent updates unchanged. Table 10 includes:

Settingkk-means initializationRandom initialization
Shortest path, K=3K=30.3310 ± 0.14280.2917 ± 0.0592
Portfolio, K=35K=350.004756 ± 0.0000260.004777 ± 0.000035
Courier, K=35K=350.05176 ± 0.005620.05265 ± 0.00508

Entries are final training regret, as mean ± standard deviation. Shortest path uses five matched seeds; portfolio and courier use 30. Courier regret is per order; the other values are per instance.

Figure 14 examines the best training regret among the first RR runs. The two initialization strategies generally obtain comparable best-found solutions, with improvements concentrated in the earlier runs. For portfolio, the improvement from the first run to the best of 30 is approximately 0.3%–1.9%. Some shortest-path and courier settings exhibit larger early gains. These observations support empirical stability after multiple starts in the tested settings, not insensitivity of every run or a guarantee that 30 restarts always suffice.

AuthorsOpenReview ↗

Author Response (Part 2/3)

2. Runtime, solver calls, and scaling

Appendix I reports computation including preprocessing, initialization, training, final representative solves, and assignment. The headline comparisons in Table 11 are:

Setting: training/test size; KKDFC total time (s)Individualized total time (s)DFC / individualized solvesTime saved
Shortest path: 3200/800; 30.594610.705673,217.06 / 4,00015.7%
Portfolio: 2000/1000; 58.2727710.400332,186.5 / 3,00020.5%
Courier: 3288/822; 1037.136443.52193,346 / 4,11014.7%

The measured implementation caches individualized training optima. With TT iterations, its solve count is Ntrain+K(T+1)N_{\rm train}+K(T+1), versus KK for kk-means and Ntrain+NtestN_{\rm train}+N_{\rm test} for individualized optimization. The training cache is unnecessary for the assignment rule but is included as executed. Once learned, the shared decisions serve additional observations without downstream solves. These are per-run averages; multiple restarts add fitting costs.

Tables 12–16 extend the comparisons across decision budgets and sample sizes. For example, the courier campaign reports time savings of 8.0%–15.4% across K=2,…,35K=2,\ldots,35.

For scaling with the number of observations, Table 17 fixes a 5×55\times5 grid, d=40d=40, and K=3K=3:

Training observationsDFC algorithm time (s)kk-means algorithm time (s)DFC training precomputation (s)
1000.0206 ± 0.02330.0330 ± 0.05300.2909
5000.0197 ± 0.00350.0131 ± 0.00360.2110
2,0000.0345 ± 0.00260.0255 ± 0.00850.8289

Algorithm times exclude the separately listed precomputation and average three repetitions. DFC executes two iterations in these runs, giving nine representative solves including the final three. This is an observed count, not a general iteration bound. Section 3.1 states the per-iteration requirements: KK downstream solves, O(NKd)O(NKd) assignment operations, and O(Nd)O(Nd) mean-update operations. Appendix D.3 additionally varies network dimension and KK on grids with d=7,12,17d=7,12,17.

Training-time–regret tradeoff. In a separate experiment accompanying this response, we vary the iteration cap at fixed tolerance 10−410^{-4}, using 2,000/1,000 training/test observations and ten matched seeds. At K=35K=35, the results are:

Iteration capTotal time (s)Mean test regretTotal solves
54.6940.0051172,210
105.3270.0050962,385
5006.4710.0050922,889

Reducing the cap from 500 to 5 saves 27.5% of total time with a 0.49% increase in mean test regret. This illustrates how the stopping budget changes the computational benefit.

3. Distribution shift

We agree that DFC need not outperform kk-means under distribution shift. The revised Appendix E.2 retains and expands this limitation. Figures 10–11 evaluate portfolios under changed return-model coefficients and factor loadings, while keeping the feasible region and fitted shared decisions unchanged. DFC's same-distribution advantage does not persist, and additional training data do not consistently improve shifted-test regret.

We separately assess sensitivity to cost perturbations. Appendix D.2 and Figure 7 perturb shortest-path test costs while keeping shared paths unchanged and reassigning each observation using the perturbed costs. DFC retains lower mean regret than both geometric baselines across the tested noise levels and K=3,4,5K=3,4,5.

Appendix F.6 and Figure 13 perturb only imputed courier costs. Under fixed assignments, at K=35K=35 and the largest zero-mean noise scale, regret is 2.9992 minutes per order for DFC, compared with 3.0453 for kk-means and 3.0504 for Ward hierarchical clustering. The relative advantage narrows as noise increases. These findings support robustness to the specified perturbations, not arbitrary distribution shifts.

AuthorsOpenReview ↗

Author Response (Part 3/3)

4. What is gained by the representative-cost formulation?

We agree that the problem selects KK shared decisions, with clusters induced by assignment to their cheapest decision. Section 1.1 explicitly acknowledges the objective and update equivalences with KK-adaptability and linear DMOC.

The representative-cost formulation expresses each group's aggregate objective through its mean and obtains its shared decision using the existing downstream optimization oracle. Appendix B shows that optimizing through these representatives preserves the minimum attainable by directly choosing shared decisions.

Compared with clustering in the decision space, clustering in the cost vector space provides a set of representative samples from the original dataset. These samples can offer decision-makers insights into the underlying data distribution. Intuitively, samples closer to the cluster mean are more likely to be near-optimal under the corresponding clustered decision, whereas samples farther from the cluster mean may exhibit greater uncertainty in their optimal decisions. Such insights cannot be readily obtained through clustering in the decision space.

Our additional analysis quantifies population excess risk over compact convex feasible regions, including infinitely many candidate optimal points. It works through induced decisions despite possible discontinuity or nonuniqueness in their cost-vector representation. Our expanded experiments include direct shared-decision replacement and other local searches, rather than comparisons only against geometric clustering.

We summarize the comparison in the following table.

WorkFeasible regionInfinitely many candidate optimal pointsAssignment/decision alternationFinite exact identificationFinite-sample risk boundsCost-vector representatives
DMOC (2021)Convex allowed✓✓———
KK-adaptability (2019)Binary—✓———
SPO trees (2020)Convex allowed✓———✓
SAA (2002)Finite——✓✓—
Prünte (2020)Compact✓✓✓†——
DFCCompact convex✓✓✓✓✓

A dash means the listed feature or guarantee is not separately provided. Infinitely many candidate optimal points refers to distinct points that can each uniquely minimize a nonzero linear cost, not merely tied points on a polyhedral face. † Finite identification follows in Prünte's finite specialization. DFC's finite identification requires a bounded polyhedron, a vertex-selecting oracle, and exact empirical minimization. SAA's listed finite-sample guarantee concerns a finite feasible region; DFC's also permits infinitely many candidate optimal points. The final column describes algorithmic representation only: linear DMOC and KK-adaptability admit equivalent mean-cost updates.

Reviewer_mS3SOpenReview ↗

Comments Acknowledged, Score Raised

I thank the authors for their efforts to respond to my review, including all the numerics that were shared. Although I still think theoretical results are lacking, the experimental results are impressive. I have raised my score.

Reviewer_A9pTOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes Decision-Focused Clustering (DFC) by grouping instances according to the decision loss incurred by sharing a decision. An alternating optimization algorithm is proposed and statistical guarantees is established for exact empirical minimizers. Experiments show DFC is better than K-mean clustering.

Critical strengths

The paper proposes Decision-Focused Clustering (DFC) by grouping instances according to the decision loss incurred by sharing a decision. An alternating optimization algorithm is proposed and statistical guarantees is established for exact empirical minimizers. Experiments show DFC is better than K-mean clustering.

Critical weaknesses
  1. The paper seems to be missing citations that are critically related:

[1] Zhang et al. (2021), “Decision-making Oriented Clustering: Application to Pricing and Power Consumption Scheduling”, Applied Energy, 297, 117106

[2] Buchheim et al. (2019), "K-adaptability in stochastic combinatorial optimization under objective uncertainty", European Journal of Operational Research, 277(3), 953–963, 2019.

[3] Kleywegt, Anton J., Alexander Shapiro, and Tito Homem-de-Mello. "The sample average approximation method for stochastic discrete optimization." SIAM Journal on optimization 12.2 (2002): 479-502.

More specifically, for example, i) The optimization objective (2) is the same as (mEm) in [2] and is a linear special case of (4) in [1]. ii) The Algorithm 1 proposed in the current manuscript also closely resembles Algorithm 1 of [1] in the sense that they both alternate between assigning samples to their highest-utility decision and maximizing aggregate utility within each cluster. DFC’s mean update is a convenient implementation of the existing cluster-decision update in [1]. iii) Theorem 3 and its proof is essentially the same as Proposition 2.1(ii) of [3].

  1. The experiment section is pretty weak, the author compares proposed algorithm only with K-mean clustering, while there are a number of previous SoTA algorithm such as hierarchical clustering, DMOC methods in [1], etc. that the authors should compare against to demonstrate the performance. Furthermore,
Questions for authors
  1. Can the authors do a more thorough literature review and holistically compare the proposed formulation, algorithm as well as performance guarantees with those of existing literature and illustrate the main technical challenge, novelty from the current paper?

  2. Can the authors do a more thorough comparison with SoTA clustering algorithms such as hierarchical clustering, DMOC, etc. in experiment section?

2 comments
AuthorsOpenReview ↗

Author Response (Part 1/2)

We thank the reviewer for identifying these important references. We have revised the abstract, introduction, Section 1.1, and the statistical discussion to acknowledge the shared foundations and state the additional contribution more precisely. We have also expanded the empirical comparisons.

1. Relationship to the three cited papers

We agree with the specific connections raised in the review.

Formulation. Under the same feasible region and empirical scenario distribution, the objective agrees with the objective-uncertainty KK-adaptability formulation of Buchheim and Pruente (2019), up to normalization and the individualized-regret constant. It is also a linear-cost specialization of offline DMOC (Zhang et al., 2021), and related to Prünte (2020), Malaguti et al. (2022), SPO trees, and generalized Bregman clustering.

Algorithm. The assignment and aggregate-cost updates coincide with linear DMOC and the basic alternating heuristic for objective-uncertainty KK-adaptability when initialization, weights, tie handling, and empty-cluster rules are matched. The mean cost vector summarizes the aggregate linear objective; obtaining the shared decision still requires downstream optimization. We do not claim that averaging alone creates a different update or a speed advantage over an equivalent linear implementation.

Analysis. Theorem 4 is now explicitly attributed to the finite-decision SAA argument of Kleywegt et al. (2002, Proposition 2.1(ii)), both before the theorem and in its proof. That proposition already includes eventual exact population optimality. We also acknowledge the earlier finite-sample SAA guarantees.

We have added a new result, Theorem 2, in the revised manuscript to exploit the clustering structure induced by the parameter space. Theorem 2 establishes conditions under which instances can be pre-grouped based on their locations in the parameter space, potentially reducing the computational complexity of the clustering algorithm. We provide the detailed analysis in the newly added Appendix A. This result further distinguishes our work from existing approaches, particularly in the setting of linear optimization.

2. Technical challenge and additional statistical analysis

Our main analytical contribution is an explicit finite-sample population excess-risk bound for learning shared decisions over compact convex feasible regions, including regions with infinitely many candidate optimal points.

Two issues prevent direct use of the finite-identification argument: infinitely many candidate optimal points need not yield a positive gap between optimal and suboptimal population risks, and the selected optimizer can be discontinuous in its representative cost vector. We control loss differences through distances between induced feasible decisions instead. Compactness then permits a finite approximation of these decisions, without requiring bounded representatives or a continuous optimization oracle.

We also updated Theorem 5, which establishes, with probability at least 1−δ1-\delta,

\leq BD\sqrt{\frac{2\{Kd\log(1+2N)+\log(2/\delta)\}}{N}} +\frac{4BD}{N}.$$ Here $N$ is the sample size, $K$ is the number of shared decisions, $d$ is the cost dimension, $B$ bounds the cost norm, and $D$ is the feasible-region diameter. The bound concerns exact empirical minimizers and gives explicit dependence on these quantities. For an approximate empirical solution, its empirical optimization error is added to this bound. Algorithm 1's monotonicity does not itself control that optimization error. Table 1 summarizes the comparison: | Work | Feasible region | Infinitely many candidate optimal points | Assignment/decision alternation | Finite exact identification | Finite-sample risk bounds | Cost-vector representatives in algorithm ‡ | Lossless pre-grouping § | | --- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | DMOC (2021) | Convex allowed | ✓ | ✓ | — | — | — | — | | $K$-adaptability (2019) | Binary | — | ✓ | — | — | — | — | | SPO trees (2020) | Convex allowed | ✓ | — | — | — | ✓ | — | | SAA (2002) | Finite | — | — | ✓ | ✓ | — | — | | Prünte (2020) | Compact | ✓ | ✓ | ✓† | — | — | — | | **DFC** | Compact convex | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | †: Finite-case consequence of SAA consistency. DFC's exact identification requires a bounded polyhedron, a vertex-selecting oracle, and exact empirical minimization. SAA's risk bounds concern finite feasible regions. ‡: Algorithmic representation only; DMOC and $K$-adaptability admit equivalent mean-cost updates for linear objectives. §: For bounded polyhedra with a vertex-selecting oracle (Theorem 2). Thus, we position DFC as a cost-representative formulation and quantitative statistical analysis of shared decisions, rather than a new best-of-$K$ objective or a new basic alternating scheme.
AuthorsOpenReview ↗

Author Response (Part 2/2)

3. Expanded empirical comparisons

We added Ward hierarchical clustering in all three applications, exact enumeration in the original shortest-path problem, and decision-level and representative-cost local searches. Figures 4–6 and 9 present these comparisons; Appendices D.1, E.3, and G.1 describe the search procedures, while Appendix I reports computation.

For the original shortest-path problem, DFC attains the exact training optimum in 25/35, 16/35, and 21/35 runs for K=3,4,5K=3,4,5, respectively. Single-path replacement reaches that optimum in every recorded run for K=3,…,6K=3,\ldots,6 on this sample. On the additional networks in Appendix D.3, the corresponding exact-hit count is 73/80, showing that local search is not universally exact.

For portfolio with 2,000 training observations, the best additional searches reduce training regret by 0–0.79% relative to the training-selected DFC solutions (Table 5), at additional computational cost. These small improvements do not certify a small global optimality gap. Courier search gives larger gains: at K=35K=35, training and test regret decrease by 23.6% and 16.5%, with 5.647 additional seconds and 3,000 additional solves (Table 9).

An equivalent linear DMOC implementation would reproduce the core DFC updates under matched conventions. We therefore explain the equivalence rather than present it as an independently improved baseline. The additional geometric and search-based comparisons evaluate genuinely different procedures. They also reveal limitations: hierarchical clustering can perform better on some additional small-budget networks, and DFC's advantage does not persist under the portfolio distribution shift (Figures 10–11).

We thank the reviewer again for these valuable comments and suggestions. We believe that the revised literature review, clarified theoretical contributions, and expanded empirical comparisons address the concerns about novelty and the relationship to existing work. We hope these revisions provide a clearer understanding of DFC's contributions and satisfactorily resolve the reviewer's questions.

Reviewer_FmwMOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Decision-Focused Clustering (DFC) for linear downstream optimization problems. DFC reduces aggregate decision loss by alternating between instance assignments and updates of nonempty cluster representatives to cluster means. The authors establish NP-hardness and convergence of objective values. Experiments on shortest-path, portfolio optimization, and a real-world courier-dispatching problem show lower decision loss than k-means under same-distribution holdout evaluation.

Critical strengths
  1. Decision loss captures the cost of sharing decisions. The mean update is simple, and the assignment step avoids computing every instance’s individualized optimal decision.
  2. The NP-hardness and convergence results provide a solid theoretical foundation. The authors explicitly distinguish statistical guarantees under exact empirical minimization from the behavior of Algorithm 1.
Critical weaknesses
  1. The courier preprocessing appears to use all orders before splitting couriers into training and testing sets (Appendix F). This raises a potential information leakage concern. Evaluation also treats imputed delivery times as true costs.
  2. Comparison with k-means alone gives limited evidence about solution quality. The shortest-path experiment has only six feasible paths, making comparison with the exact empirical optimum feasible, but this comparison is missing.
  3. Algorithm 1 requires downstream optimization at each iteration, but no runtime or total number of optimization problems solved is reported.
Questions for authors
  1. How close is DFC to the exact empirical optimum in the shortest-path experiment, particularly for K<6K<6?
  2. How much computation does DFC save relative to individualized optimization after including initialization and training? Please report runtime and the number of downstream optimization problems solved.
2 comments
AuthorsOpenReview ↗

Author Response (Part 1/2)

We thank the reviewer for recognizing the motivation and theoretical foundations of DFC. We have expanded the evaluation to address preprocessing, imputation uncertainty, empirical optimization quality, and computation. All numbered references below refer to the revised manuscript.

1. Courier preprocessing and imputed delivery costs

We agree that the original pooled preprocessing allowed test observations to influence the construction of training cost vectors. Appendix F.5 now reports a split-first experiment: couriers are split before preprocessing, regions and constraints are determined from training data, and training and test profiles are completed separately without cross-split pooling. This produces 3,288 training and 822 test instances.

Table 7 reports the following test regret per order, as mean ± standard deviation over ten runs:

KKDFC, split-firstkk-means, split-firstReduction
20.7016 ± 0.03210.9513 ± 0.000026.2%
50.4039 ± 0.09090.5923 ± 0.114931.8%
100.2075 ± 0.02240.2746 ± 0.041724.4%
200.0993 ± 0.01110.1578 ± 0.018037.1%
350.0550 ± 0.00620.1103 ± 0.009050.1%

These results show that DFC's advantage persists without pooling observations across the training and test sets. We have also updated the main-text results to use the split-first preprocessing protocol.

We also agree that imputed delivery times are estimates, not observed ground truth. To assess sensitivity to imputation errors, Appendix F.6 perturbs only the originally missing test entries, leaving observed entries unchanged. Specifically, we add Gaussian errors with means of zero or one minute and standard deviations up to 8.65 minutes, corresponding to the training-validation RMSE. Perturbed costs are floored at one minute. The experiment uses 30 matched model seeds and ten paired noise realizations at each positive noise level.

Figure 13 distinguishes two evaluations. The upper row fixes both shared decisions and original assignments, treating perturbations as unknown imputation errors. The lower row permits reassignment among the unchanged shared decisions using perturbed costs. DFC retains lower mean regret in the tested cases, although the relative advantage narrows under fixed assignments. At K=35K=35, zero-mean noise with standard deviation 8.65 minutes gives fixed-assignment regret of 2.9992 minutes per order for DFC, 3.0453 for kk-means, and 3.0504 for Ward hierarchical clustering.

These results assess sensitivity to the reconstruction assumptions.

2. Exact empirical optimum and additional comparisons

We now include Ward hierarchical clustering and the exact empirical optimum in Figure 4. For the original six-path problem, we enumerate every subset of at most KK feasible paths and minimize training regret. Appendix D.1, Table 4 reports:

KKExact training optimumMean DFC training regretOptimal runs
30.226680.3037525/35
40.067040.1317416/35
50.019120.0440221/35
600.0005534/35
7–100035/35 for each KK

DFC frequently attains the exact optimum, but the gaps at smaller budgets show that objective descent does not ensure global optimality. The test reference in Figure 4 evaluates the training-optimal shared paths unchanged; it does not select shared paths using test data.

We additionally evaluate single-path replacement using the six cached feasible paths. Accepting moves using training regret only, this search reaches the exact training optimum in every recorded run for K=3,…,6K=3,\ldots,6 on the original sample. Appendix D.3 reports additional networks where some gaps remain, so we do not claim a general optimality guarantee for this search.

AuthorsOpenReview ↗

Author Response (Part 2/2)

3. Runtime and downstream optimization calls, including training

Appendix I now reports total computation, including preprocessing, cached training-individual solves, initialization, all DFC iterations, final representative solves, and assignment. Evaluation-only solves are excluded. Table 11 gives the following per-run averages:

Setting: training/test size; KKIndividualized time (s)DFC time (s)Individualized solvesDFC solvesTime saved
Shortest path: 3200/800; 30.705670.594614,0003,217.0615.7%
Portfolio: 2000/1000; 510.400338.272773,0002,186.520.5%
Courier, split-first: 3288/822; 1043.521937.13644,1103,34614.7%

These averages use 35 shortest-path runs and ten portfolio/courier runs; averaging explains the noninteger solve counts. With TT iterations, the measured implementation uses Ntrain+K(T+1)N_{\rm train}+K(T+1) solves. The first term is implementation overhead: individualized optimal costs cancel in cluster assignment, so this precomputation is not required by the assignment rule. It is nevertheless included because it was executed. Once shared decisions are learned, further assignments require no downstream solves.

These savings apply to the stated configurations, not every decision budget. Tables 12–16 retain slower cases. For example, the separate 5000/1000 portfolio campaign is 22.7% slower than individualized optimization at K=35K=35, and the shortest-path runs at K=7,…,10K=7,\ldots,10 take longer, with some reaching the iteration cap. Absolute times from different campaigns are not directly comparable. The geometric baselines are faster in the headline settings but incur higher regret in the corresponding quality comparisons.

The revised evaluation therefore quantifies both the savings from sharing decisions and their dependence on training effort, decision budget, and stopping behavior.

We thank the reviewer again for these constructive comments. We believe that the revised manuscript and additional experiments address the concerns about preprocessing, empirical optimality, and computational efficiency. We hope these clarifications and results satisfactorily resolve the reviewer's questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.