Of course, you can use your own CSS and customize the background & foreground color. There's no need for ::ng-deep. (/deep/ and ::ng-deep are both currently deprecated)
With a couple of SCSS here's how my stepper looked: I have added SASS snippets needed for customizing the label and icons below:

Completed step & its label:
.mat-step-header .mat-step-icon-state-done, .mat-step-header .mat-step-icon-state-edit {
background-color: transparent !important;
color: $success;
+.mat-step-label{
color: $success !important;
}
}
In Progress step & its label:
.mat-step-header .mat-step-icon-selected{
// background-color: $primary;
background-color: transparent !important;
color: $primary;
+.mat-step-label{
color: $primary !important;
}
}
Todo/Default step & its label:
.mat-step-header .mat-step-label{
color: rgba(0, 0, 0, .54)
}
.mat-step-header .mat-step-icon {
color: rgba(0, 0, 0, .54);
background-color: transparent;
}
HTML for overriding default icons:
I used font awesome icons to override the defaults:
<mat-horizontal-stepper>
<!-- Icon overrides. -->
<ng-template matStepperIcon="edit">
<i class="fa fa-check-circle"></i>
</ng-template>
<ng-template matStepperIcon="active">
<i class="fa fa-dot-circle-o"></i>
</ng-template>
<ng-template matStepperIcon="done">
<i class="fa fa-dot-circle-o"></i>
</ng-template>
<ng-template matStepperIcon="number">
<i class="fa fa-dot-circle-o"></i>
</ng-template>
</mat-horizontal-stepper>
Note: All SCSS should be in the global stylesheet and not in the component specific stylesheet. If the styles are present inside the angular component's file it will not be applied due to view encapsulation.
Please define the color variables if needed at the start of the SCSS file as below: Replace the HEX values with your theme colors.
$success: #35A255 !default;
$primary: #007CBB !default;