Skip to content

Use hypervolume difference as upperbound of contribs in HSSP #6131

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wants to merge 6 commits into
base: master
Choose a base branch
from

Conversation

not522
Copy link
Member

@not522 not522 commented Jun 5, 2025

Motivation

Since contribs in HSSP manages the upper bound of contribution for each point, it can be updated by the difference HV with the last selected point and the next candidate. This reduces the number of points that actually require hypervolume calculation.

Description of the changes

  • Use hypervolume difference as upperbound of contribs in HSSP

Benchmark

  • master: 26.196007 sec
  • PR: 21.065669 sec
import optuna


def objective(trial: optuna.Trial) -> tuple[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


sampler = optuna.samplers.TPESampler(seed=42)
study = optuna.create_study(sampler=sampler, directions=["minimize"]*3)
study.optimize(objective, n_trials=1000)
trials = study.trials
print((trials[-1].datetime_complete - trials[0].datetime_start).total_seconds())

@not522 not522 added the enhancement Change that does not break compatibility and not affect public interfaces, but improves performance. label Jun 5, 2025
Copy link
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 PR, I left some comments:)

# Note: H(T v {j}) - H(T) <= H({t} v {j}) - H({t}) = H({j}) - H({t} ^ {j}).
# Here, t is the last selected point and j is the candidate. The inequality comes from
# submodularity and the equality comes from the inclusion-exclusion principle.
single_volume = np.abs(np.prod(pareto_loss_values - reference_point[np.newaxis, :], axis=1))
Copy link
Contributor

Choose a reason for hiding this comment

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

We could precompute single_volume if necessary.
It is an implicit assumption, but the compute_hypervolume function internally checks np.all(pareto_loss_values <= reference_point[np.newaxis, :]), so np.prod(reference_point[np.newaxis, :] - pareto_loss_values, axis=1) is equivalent.

Note

r - a is quicker than r[np.newaxis, :] - a.

In [1]: import numpy as np
   ...: 
   ...: 
   ...: a = np.random.random((30, 3))
   ...: r = np.ones(3)
   ...: %timeit r - a
   ...: %timeit r[np.newaxis, :] - a
   ...: assert np.allclose(r - a, r[np.newaxis, :] - a)
708 ns ± 8.28 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
887 ns ± 10.7 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

@nabenabe0928
Copy link
Contributor

nabenabe0928 commented Jun 6, 2025

I confirmed the reproducibility with the following!

    contribs = np.minimum(
        contribs,
        (
            np.prod(reference_point - pareto_loss_values, axis=1)
            - np.prod(reference_point - np.maximum(selected_vecs[-2], pareto_loss_values), axis=1)
        ),
    )

@y0z y0z self-assigned this Jun 6, 2025
Copy link

codecov bot commented Jun 6, 2025

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 88.42%. Comparing base (1fe6f76) to head (88f93f1).
Report is 45 commits behind head on master.

Additional details and impacted files
@@            Coverage Diff             @@
##           master    #6131      +/-   ##
==========================================
+ Coverage   88.29%   88.42%   +0.13%     
==========================================
  Files         207      207              
  Lines       14034    14043       +9     
==========================================
+ Hits        12391    12418      +27     
+ Misses       1643     1625      -18     

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

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