Skip to content

Use the decremental approach in the hypervolume contribution calculation#6264

Merged
y0z merged 3 commits intooptuna:masterfrom
not522:diff-hv
Sep 5, 2025
Merged

Use the decremental approach in the hypervolume contribution calculation#6264
y0z merged 3 commits intooptuna:masterfrom
not522:diff-hv

Conversation

@not522
Copy link
Copy Markdown
Member

@not522 not522 commented Sep 1, 2025

Motivation

The contribution calculation in _calculate_weights_below_for_multi_objective can be accelerated by using the difference between own hv and intersection's one.

Description of the changes

Using diff in contribution calculation.
Note: contribs[i] = H(S v {i)) - H(S) = H({i}) - H(S ^ {i}).

Benchmark

import optuna

def multi_objective(trial: optuna.Trial) -> tuple[float, float, float, float, float]:
    x = trial.suggest_float("x", -5, 5)
    y = trial.suggest_float("y", -5, 5)
    return x**2 + y**2, (x - 2)**2 + (y - 2)**2, (x + 2)**2 + (y + 2)**2, (x + 2)**2 + (y - 2)**2 , (x - 2)**2 + (y + 2)**2

def objective(trial: optuna.Trial, n_objectives: int) -> tuple[float, ...]:
    values = multi_objective(trial)
    return values[:n_objectives]

n_objectives = 5
sampler = optuna.samplers.TPESampler(seed=0, multivariate=True)
study = optuna.create_study(sampler=sampler, directions=["minimize"]*n_objectives)
study.optimize(lambda trial: objective(trial, n_objectives), n_trials=400)
print((study.trials[-1].datetime_complete - study.trials[0].datetime_start).total_seconds())
dim master PR
2 0.45 sec 0.45 sec
3 0.92 sec 0.90 sec
4 8.88 sec 5.97 sec
5 34.35 sec 12.12 sec

@not522 not522 added the enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. label Sep 1, 2025
@not522 not522 marked this pull request as draft September 1, 2025 12:53
@not522 not522 marked this pull request as ready for review September 1, 2025 22:44
@nabenabe0928
Copy link
Copy Markdown
Contributor

@y0z
Could you review this PR?

@nabenabe0928 nabenabe0928 changed the title Use diff in contribution calculation Use the decremental approach in the hypervolume contribution calculation Sep 2, 2025
@nabenabe0928
Copy link
Copy Markdown
Contributor

Copy link
Copy Markdown
Contributor

@nabenabe0928 nabenabe0928 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mostly LGTM:)
I left a minor comment!

not522 and others added 2 commits September 2, 2025 13:14
Co-authored-by: Shuhei Watanabe <47781922+nabenabe0928@users.noreply.github.com>
Comment on lines +844 to +848
contribs[on_front] = np.prod(ref_point - pareto_sols, axis=-1)
limited_sols = np.maximum(pareto_sols, pareto_sols[:, np.newaxis])
contribs[on_front] -= [
compute_hypervolume(limited_sols[i, loo], ref_point) for i, loo in enumerate(loo_mat)
]
Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Just in case, I confirmed that this part does not fail even if len(pareto_sols) == 1.
The hypervolume contribution in this case must be identical to compute_hypervolume(pareto_sols, ref_point, assume_pareto=True), which we successfully get here.

Note

Since n_below_feasible <= 1 immediately returns weights_below above, pareto_sols will not be empty.

Copy link
Copy Markdown
Contributor

@nabenabe0928 nabenabe0928 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for the update, LGTM!

@nabenabe0928 nabenabe0928 removed their assignment Sep 2, 2025
@nabenabe0928 nabenabe0928 added this to the v4.6.0 milestone Sep 2, 2025
Copy link
Copy Markdown
Member

@y0z y0z left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@y0z y0z merged commit d369746 into optuna:master Sep 5, 2025
14 checks passed
@y0z y0z removed their assignment Sep 5, 2025
@not522 not522 deleted the diff-hv branch September 5, 2025 10:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

enhancement Change that does not break compatibility and not affect public interfaces, but improves performance.

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants