Water column stratification and eutrophication are two major factors affecting coastal water oxygen depletion. Discerning their relative importance to oxygen depletion is critical to mitigating the deoxygenation problem but remains challenging because the two factors are often correlated on different time scales. This work aims to provide a machine learning-based protocol to isolate and quantify the contributions of stratification and eutrophication to the interannual variability of coastal deoxygenation. The method is applied to a highly dynamic system, the Hong Kong waters in southern China, using a 21-year (2000~2020) time series of monthly water quality data at 65 monitoring stations. Specifically, we adopt interpretable machine learning methods to estimate how much stratification explains the spatial variability in apparent oxygen utilization (AOU), based on which we isolate the contributions of stratification and eutrophication to interannual variability of summertime oxygen depletion. Results show that the combined effect of stratification and eutrophication explains 52% and 58% of the year-to-year variability of AOU in river plume-affected region and far-field region, respectively. The model also suggests a regional difference in the relative importance of stratification and eutrophication, with the plume-affected region experiencing a stronger stratification control while the far-field region being more affected by eutrophication. In both regions, variations of surface-bottom salinity difference are the most important factors regulating the interannual variability of summer stratification intensity, whereas water turbidity is most critical to controlling the variability of eutrophication effect. Our findings reveal that the dominant contributor to interannual variation of oxygen depletion varies in different areas of coastal waters, underlining the need to provide region-specific management strategies to meet water quality goals.