Optimize Lossguide by Levachev · Pull Request #2835 · catboost/catboost

Levachev · 2025-03-21T19:34:21Z

Optimize Lossguide with subtract trick

merge catboost to levachev/catboost

Levachev · 2025-03-21T19:35:55Z

Optimizing Lossguide with the subtract trick.

When testing, it was found that the result will be different(compared to the master version) if you do not set the parameters of CatBoostRegressor
random_strength=0,
bootstrap_type="No",
has_time=True
Otherwise, the result will be different due to the fact that Ctx->LearnProgress->Rand.GenRand() will be different when splitting the leaf

Evgueni-Petrov-aka-espetrov · 2025-03-24T11:37:50Z

-    const TTrainingDataProviders& data,
-    const TFold& fold,
-    ui32 oneHotMaxSize
+        const TTrainingDataProviders& data,


please restore indentation -- once this is done, i will get back with more comments

Levachev · 2025-03-24T15:06:50Z

@Evgueni-Petrov-aka-espetrov restore indentation complete

a-holm · 2025-04-04T14:59:08Z

Minor Nit: The PR description is very brief. Given this is a significant algorithmic optimization replacing the previous GreedyTensorSearchLossguide function entirely, could you add a sentence or two to the description briefly outlining the approach (e.g., reusing parent stats via shared pointers passed down during expansion)? This would improve context for future readers/maintainers looking at the PR history.

Levachev · 2025-04-06T19:01:30Z

@a-holm
The most time-consuming part of the original Lossguide implementation is calculating the statistics separately for each child leaf. Due to the subtraction trick, we only calculate the statistics for the smaller node, and for the larger one we subtract the statistics of the smaller node from the statistics of the parent node.
I hope I have clarified the matter.
Link to subtract trick - https://everdark.github.io/k9/notebooks/ml/gradient_boosting/gbt.nb.html

a-holm · 2025-04-06T21:05:34Z

@Levachev very cool! Thank you

Evgueni-Petrov-aka-espetrov · 2025-04-14T11:17:40Z

+            return;
+        }
+        auto candidatesContextsLeftLeaf = SelectFeaturesForScoring(data, {}, fold, ctx);
+        auto candidatesContextsRightLeaf = SelectFeaturesForScoring(data, {}, fold, ctx);


this should be identical to candidatesContextsLeftLeaf
could we use copy instead of calling SelectFeaturesForScoring?

Evgueni-Petrov-aka-espetrov · 2025-04-14T11:19:17Z

+        }
+    };
+
+    const auto findBestCandidate = [&](TIndexType leftLeaf, TIndexType rightLeaf, const std::shared_ptr<TVector<TBucketStats>> &parent) {


please make this a normal static function to improve readability

Evgueni-Petrov-aka-espetrov · 2025-04-14T11:30:20Z

-        const TCandidateInfo* bestSplitCandidate = nullptr;
-        const double scoreBeforeSplit = CalcScoreWithoutSplit(leaf, *fold, *ctx);
-        SelectBestCandidate(data, *ctx, candidatesContexts, maxFeatureValueCount, *fold, scoreBeforeSplit, &bestScore, &bestSplitCandidate);
-        fold->DropEmptyCTRs();


why does not optimized GreedyTensorSearchLossguide call DropEmptyCTRs anywhere?
it may free some memory

Evgueni-Petrov-aka-espetrov · 2025-04-14T11:31:38Z

-            fold,
-            ctx);
-        const size_t maxFeatureValueCount = CalcMaxFeatureValueCount(*fold, candidatesContexts);
-        CheckInterrupted(); // check after long-lasting operation


why does not optimized GreedyTensorSearchLossguide call CheckInterrupted anywhere?
this call is needed to ensure catboost can be interrupted here

Evgueni-Petrov-aka-espetrov · 2025-04-14T11:41:27Z

+        const bool needSplitLeftLeaf = leafDepth[leftLeaf] < ctx->Params.ObliviousTreeOptions->MaxDepth
+                                       && leftLeafBoundsSize >= ctx->Params.ObliviousTreeOptions->MinDataInLeaf;


please store max depth and min data in leaf in some variables to avoid code duplication

Evgueni-Petrov-aka-espetrov · 2025-04-14T12:13:05Z

+                *parent);
+
+        } else {
+            if(needSplitLeftLeaf) {


need space after if -- please check everywhere

Evgueni-Petrov-aka-espetrov · 2025-04-14T12:13:27Z

+                &rightLeafBestSplitCandidate,
+                &rightLeafBestSplit,
+                *parent);
+


pls remove empty line

Evgueni-Petrov-aka-espetrov · 2025-04-14T12:13:52Z

+                &rightLeafGain,
+                &rightLeafBestSplitCandidate,
+                &rightLeafBestSplit);
+            leftLeafStats = CalculateWithSubtractTrickNoParentQueue(


pls insert empty line before leftLeafStats

Evgueni-Petrov-aka-espetrov · 2025-04-14T12:14:02Z

+                &leftLeafBestSplitCandidate,
+                &leftLeafBestSplit,
+                *parent);
+


pls remove empty line

Evgueni-Petrov-aka-espetrov · 2025-04-14T12:19:07Z

+        TVector<TBucketStats> leftLeafStats;
+        TVector<TBucketStats> rightLeafStats;
+
+        if ((leftLeafBoundsSize <= rightLeafBoundsSize) && isSubtractTrickAllowed && needSplitLeftLeaf && needSplitRightLeaf) {


please structure as follows for better readability

if (isSubtractTrickAllowed && needSplitLeftLeaf && needSplitRightLeaf) { if (leftLeafBoundsSize <= rightLeafBoundsSize) { // ... } else { // ... } } else { if (needSplitLeftLeaf) { // ... } if (needSplitRightLeaf) { // ... } }

Levachev · 2025-04-28T15:55:42Z

I hereby agree to the terms of the CLA available at: link.

Evgueni-Petrov-aka-espetrov · 2025-04-29T05:48:07Z

+    auto leftLeafStatsPtr = MakeSimpleShared<TVector<TBucketStats>>(leftLeafStats);
+    auto rightLeafStatsPtr = MakeSimpleShared<TVector<TBucketStats>>(rightLeafStats);


please avoid unnecessary copy here and in findBestCandidateRoot as follows

leftLeafStatsPtr = MakeSimpleShared<TVector<TBucketStats>>(); leftLeafStatsPtr->swap(leftLeafStats);

Evgueni-Petrov-aka-espetrov · 2025-05-28T07:54:30Z

Since this optim reorders summation of derivatives, canonical outputs of pytest and python-package/ut/medium will change for Lossguide.
Model quality (final prediction error value) is preserved.
However, about 5-10% of predictions drift within 0.1% from their current canonical values.
I will update canonical data on Yandex side before final merge.

Evgueni-Petrov-aka-espetrov · 2025-05-28T08:45:07Z

Shipped!

Levachev and others added 18 commits February 22, 2025 21:25

optimize v1

b3cc3f4

optimize v2 - shared_ptr

1aa1e76

optimize v2 - shared_ptr fixed

d571980

fix queue bug

87efb92

add some debug info

e042718

add some debug info for candidates

baddb4d

add some debug info for scoreWoNoise

6b0d183

add some debug info for scoreWoNoise2

7812710

add some debug info for scoreWoNoise and randSeed

89b37cf

add some debug info for rand

8caf68e

delete logs

f7c532b

delete logs

c2a81a2

some code cleanup

eb10876

rollback not changed file

8da435f

remove debug couts

cac3382

Merge pull request #1 from catboost/master

5fa5fc9

merge catboost to levachev/catboost

Merge remote-tracking branch 'origin/master' into dev

3b1a181

remove debug CB_ENSURE

7e1002e

andrey-khropov added performance objectives and metrics labels Mar 22, 2025

Evgueni-Petrov-aka-espetrov requested changes Mar 24, 2025

View reviewed changes

Levachev added 6 commits March 24, 2025 20:17

rollback code format

81ecbda

rollback code format

e087adb

rollback code format greedy_tensor_search.cpp

02e973f

rollback code format greedy_tensor_search.cpp 2

5566fa5

rollback code format greedy_tensor_search.cpp 3

c9485c4

rollback code format greedy_tensor_search.cpp 4

0f2494f

Evgueni-Petrov-aka-espetrov requested changes Apr 14, 2025

View reviewed changes

fixes

c9f0498

andrey-khropov removed the objectives and metrics label Apr 16, 2025

Levachev added 2 commits April 27, 2025 16:23

fixes2

e979fd7

fixes3

45ac8ab

Evgueni-Petrov-aka-espetrov requested changes Apr 29, 2025

View reviewed changes

Levachev added 9 commits April 29, 2025 19:33

fixes4

eb151ef

fix

79a7366

fix tmp

b4299bf

fix tmp

a46ebee

cout order

28b6341

cout order2

8adac39

cout order3

538daf2

delete prints

30d5ff1

delete prints

d71ff1f

andrey-khropov requested changes May 2, 2025

View reviewed changes

Levachev added 3 commits May 2, 2025 19:26

code cleanup

811e377

code cleanup2

0a747a4

separate depends on lossguide or depthwise

7063c3f

Levachev closed this May 28, 2025

Evgueni-Petrov-aka-espetrov mentioned this pull request May 28, 2025

Optimize Lossguide #2883

Closed

		const bool needSplitLeftLeaf = leafDepth[leftLeaf] < ctx->Params.ObliviousTreeOptions->MaxDepth
		&& leftLeafBoundsSize >= ctx->Params.ObliviousTreeOptions->MinDataInLeaf;

		auto leftLeafStatsPtr = MakeSimpleShared<TVector<TBucketStats>>(leftLeafStats);
		auto rightLeafStatsPtr = MakeSimpleShared<TVector<TBucketStats>>(rightLeafStats);

Conversation

Levachev commented Mar 21, 2025

Uh oh!

Levachev commented Mar 21, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Levachev commented Mar 24, 2025

Uh oh!

a-holm commented Apr 4, 2025

Uh oh!

Levachev commented Apr 6, 2025

Uh oh!

a-holm commented Apr 6, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Evgueni-Petrov-aka-espetrov Apr 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Levachev commented Apr 28, 2025 • edited by Evgueni-Petrov-aka-espetrov Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Evgueni-Petrov-aka-espetrov commented May 28, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Evgueni-Petrov-aka-espetrov commented May 28, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Levachev commented Mar 21, 2025 •

edited

Loading

Evgueni-Petrov-aka-espetrov Apr 14, 2025 •

edited

Loading

Levachev commented Apr 28, 2025 •

edited by Evgueni-Petrov-aka-espetrov

Loading

Evgueni-Petrov-aka-espetrov commented May 28, 2025 •

edited

Loading