Safety vs. Performance: How Multi-Objective Learning Reduces Barriers to Market Entry
Meena Jagadeesan Michael I. Jordan Jacob Steinhardt



: Assessing Contextual Integrity Norms in Language Models
    
Yan Shvartzshnaider

York University


Vasisht Duddu

University of Waterloo


John Lacalamita

York University



    
=======================================================================================================================



§ ABSTRACT 
Emerging marketplaces for large language models and other large-scale machine learning (ML) models appear to exhibit market concentration, which has raised concerns about whether there are insurmountable barriers to entry in such markets. In this work, we study this issue from both an economic and an algorithmic point of view, focusing on a phenomenon that reduces barriers to entry.  Specifically, an incumbent company risks reputational damage unless its model is sufficiently aligned with safety objectives, whereas a new company can more easily avoid reputational damage. To study this issue formally, we define a multi-objective high-dimensional regression framework that captures reputational damage, and we characterize the number of data points that a new company needs to enter the market. Our results demonstrate how multi-objective considerations can fundamentally reduce barriers to entry—the required number of data points can be significantly smaller than the incumbent company's dataset size. En route to proving these results, we develop scaling laws for high-dimensional linear regression in multi-objective environments, showing that the scaling rate becomes slower when the dataset size is large, which could be of independent interest.
    




§ INTRODUCTION



Large language models and other large-scale machine learning (ML) models have led to an important shift in the information technology landscape, one which has significant economic consequences.  Whereas earlier generations of ML models provided the underpinnings for platforms and services, new models—such as language models—are themselves the service. This has led to new markets where companies offer language models as their service and compete for user usage. As in other markets, it is important to reason about market competitiveness: in particular, to what extent there are barriers to entry for new companies.

A widespread concern about these markets is that new companies face insurmountable barriers to entry that drive  market concentration <cit.>. The typical argument is that incumbent companies with high market share can purchase or capture significant amounts of data and compute,[Large companies can afford these resources since the marketplace is an economy of scale (i.e., fixed costs of training significantly exceed per-query inference costs). They also generate high volumes of data from user interactions.] and then invest these resources into the training of models that achieve even higher performance <cit.>. This suggests that the company's market share would further increase, and that the scale and scope of this phenomenon would place incumbent companies beyond the reach of new companies trying to enter the market. The scale is in fact massive—language assistants such as ChatGPT and Gemini each have hundreds of millions of users <cit.>. In light of the concerns raised by policymakers <cit.> and regulators <cit.> regarding market concentration, it is important to investigate the underlying economic and algorithmic mechanisms at play.
 
While standard arguments assume that market share is determined by model performance, the reality is that the incumbent company risks reputational damage if their model violates safety-oriented objectives. For example, incumbent companies face public and regulatory scrutiny for their model's safety violations—such as threatening behavior <cit.>, jailbreaks <cit.>, and releasing dangerous information <cit.>—even when the model performs well in terms of helpfulness and usefulness to users. In contrast, new companies face less regulatory scrutiny since compliance requirements often prioritize models trained with more resources <cit.>, and new companies also may face less public scrutiny given their smaller user bases. 

In this work, we use a multi-objective learning framework to show that the threat of reputational damage faced by the incumbent company can reduce barriers to entry. For the incumbent, the possibility of reputational damage creates pressure to align with safety objectives in addition to optimizing for performance. Safety and performance are not fully aligned, so improving safety can reduce performance as a side effect. Meanwhile, the new company faces less of a risk of reputational damage from safety violations. The new company can thus enter the marketplace with significantly less data than the incumbent company, a phenomenon that our model and results formalize. 



  
Model and results.
We analyze a stylized marketplace based on multi-objective linear regression (Section <ref>). The performance-optimal output and the safety-optimal output are specified by two different linear functions of the input x. The marketplace consists of two companies: an incumbent company and a new company attempting to enter the market. Each company receives their own unlabelled training dataset, decides what fraction of training data points to label according to the performance-optimal vs. safety-optimal outputs, and then runs ridge regression. The new company requires a less stringent level of safety to avoid reputational damage than the incumbent company. We characterize the market-entry threshold  (Definition <ref>) which captures how much data the new company needs to outperform the incumbent company.

First, as a warmup, we characterize  when the new company faces no safety constraint and the incumbent company has infinitely many data points (Section <ref>). Our key finding is that the new company can enter the market with finite data, even when the incumbent company has infinite data (Theorem <ref>; Figure <ref>). Specifically, we show that the threshold  is finite; moreover, it is increasing in the correlation (i.e., the alignment) between performance and safety, and it is decreasing in a problem-specific scaling law exponent. 

Next, we turn to more general environments where the incumbent has finite data < ∞ (Section <ref>). We find that the threshold  scales sublinearly with the incumbent's dataset size , as long as  is sufficiently large. In fact, the threshold  scales at a slower rate as  increases: that is, = Θ(^c) where the exponent c is decreasing in  (Theorem <ref>; Figure <ref>). For example, for concrete parameter settings motivated by language models <cit.>, the exponent c decreases from 1 to 0.75 to 0 as  increases. In general, the exponent c takes on up to three different values depending on , and is strictly smaller than 1 as long as  is sufficiently large.

 
Finally, we turn to environments where the new company also faces a nontrivial safety constraint, assuming for simplicity that the incumbent company again has infinite data (Section <ref>). We find that  is finite as long as the new company faces a strictly weaker safety constraint than the incumbent. When the two safety thresholds are closer together, the new company needs more data and in fact needs to scale up their dataset size at a faster rate: that is, = Θ(D^-c), where D measures the difference between the safety thresholds and where the exponent c increases as D decreases 
(Theorem <ref>; Figure <ref>). For the parameter settings in <cit.>, the exponent c changes from -2.94 to -3.94 to an even larger value as D decreases. In general, the exponent c takes on up to three different values. 





  
Technical tool: Scaling laws. 
To prove our results, we derive scaling laws for multi-objective high-dimensional linear regression, which could be of independent interest (Section <ref>; Figure <ref>). We study optimally-regularized ridge regression where some of the training data is labelled according to the primary linear objective (capturing performance) and the rest is labelled according to an alternate linear objective (capturing safety).

We characterize data-scaling laws for both the loss along the primary objective and the excess loss along the primary objective relative to an infinite-data ridgeless regression. Our scaling laws quantify the rate at which the loss (Theorem <ref>; Figure <ref>) and the excess loss (Theorem <ref>; Figure <ref>) decay with the dataset size N, and how this rate is affected by the fraction of data labelled according to each objective and other problem-specific quantities. Our analysis improves upon recent works on scaling in multi-objective environments <cit.> by allowing for non-identity covariances and problem-specific regularization, which leads to new insights about scaling laws as we describe below.  

Our results reveal that the scaling rate becomes slower as the dataset size increases, illustrating that multi-objective scaling laws behave qualitatively differently from classical single-objective environments. While a typical scaling exponent in a single-objective environment takes on a single value across all settings of N, the scaling exponent for multi-objective environments decreases as N increases. In particular, the scaling exponent takes on three different values depending on the size of N relative to problem-specific parameters. 
The intuition is that the regularizer must be carefully tuned to N in order to avoid overfitting to training data labelled according to the alternate objective, which in turn results in the scaling exponent being dependent on N (Section <ref>). 




  
Discussion.
Altogether, our work highlights the importance of looking beyond model performance when evaluating market entry in machine learning marketplaces. Our results highlight a disconnect between market entry in single-objective environments versus more realistic multi-objective environments. More broadly, a company's susceptibility to reputational damage affects how they train their model to balance between different objectives. As we discuss in Section <ref>, these insights have nuanced implications for regulators who wish to promote both market competitiveness and safety compliance, and also generalize beyond language models to online platforms.






 §.§ Related work


Our work connects to research threads on competition between model providers as well as scaling laws and high-dimensional linear regression. 




  
Competition between model providers. Our work contributes to an emerging line of work studying how competing model providers strategically design their machine learning pipelines to attract users. Model-provider actions range from choosing a function from a model class <cit.>, to selecting a regularization parameter <cit.>, to choosing an error distribution over user losses <cit.>, to making data purchase decisions <cit.>, to  deciding whether to share data <cit.>, to selecting a bandit algorithm <cit.>. While these works assume that model providers win users solely by maximizing (individual-level or population-level) accuracy, our framework incorporates the role of safety violations in impacting user retention implicitly via reputational damage. Moreover, our focus is on quantifying the barriers to market entry, rather than analyzing user welfare or the equilibrium decisions of model providers. 


Other related work includes the study of competition between algorithms <cit.>, retraining dynamics under user participation decisions <cit.>, the bargaining game between a foundation model company and a specialist <cit.>, and the market power of an algorithmic platform to shape user populations <cit.>. 

Our work also relates to platform competition <cit.>, the emerging area of competition policy and regulation of digital marketplaces <cit.>, the study of how antitrust policy impacts innovation in classical markets <cit.>, and industrial organization more broadly <cit.>. For example, recent work examines how increased public scrutiny from inclusion in the S&P 500 can harm firm performance <cit.>, how privacy regulation impacts firm competition <cit.>, how regulatory inspections affect incentives to comply with safety constraints <cit.>,  and how data-driven network effects can reduce innovation <cit.>. 



  
Scaling laws and high-dimensional linear regression. Our work also contributes to an emerging line of work on scaling laws which study how model performance changes with training resources. Empirical studies have demonstrated that increases to scale often reliably improve model performance <cit.>, but have also identified settings where scaling behavior is more nuanced <cit.>. We build on a recent mathematical characterization of scaling laws based on high-dimensional linear regression 
 <cit.>. However, while these works focus on single-objective environments where all of the training data is labelled with outputs from a single predictor, we consider multi-objective environments where some fraction of the training data is labelled according to an alternate predictor. 

We note that a handful of recent works similarly move beyond single-objective environments and study scaling laws where the training data comes a mixture of different data sources. <cit.> study high-dimensional ridge regression in a similar multi-objective environment to our setup. However, these results assume an identity covariance and focus on fixed regularization or no regularization. In contrast, we allow for richer covariance matrices that satisfy natural power scaling (Section <ref>), and we analyze optimally tuned regularization. Our analysis of these problem settings yields new insights about scaling behavior: for example, the scaling rate becomes slower with dataset size (Theorems <ref>-<ref>). Other related works study scaling laws under mixtures of covariate distributions
<cit.>, under data-quality heterogeneity <cit.>, under data addition <cit.>, under mixtures of AI-generated data and real data <cit.>, and with respect to the contribution of individual data points <cit.>.

More broadly, our work relates to collaborative learning <cit.>, federated learning <cit.>, optimizing data mixtures <cit.>, and adversarial robustness <cit.>. 
Finally, our work relates to non-monotone scaling laws in strategic environments <cit.>, where increases to scale can worsen equilibrium social welfare. 





§ MODEL


We define our linear-regression-based marketplace (Section <ref>),   justify the design choices of our model (Section <ref>), and then delineate our statistical assumptions (Section <ref>).



 §.§ Linear regression-based marketplace


We consider a marketplace where two companies fit linear regression models in a multi-objective environment. 



  
Linear regression model. To formalize each company's machine learning pipeline, we consider the multi-objective, high-dimensional linear regression model described below. This multi-objective environment aims to capture how ML models are often trained to balance multiple objectives which are in tension with each other, and we consider linear regression since it has often accurately predicted scaling trends of large-scale machine learning models (see Section <ref> for additional discussion). 

More concretely, given an input x ∈ℝ^P, let ⟨β_1, x⟩ be the output that targets performance maximization, and let ⟨β_2, x⟩ be the output that targets safety maximization. Given a linear predictor β, the performance loss is evaluated via a population loss, () = 𝔼_x ∼[(⟨, x⟩ - ⟨β, x⟩)^2], and the safety violation is captured by a loss () = 𝔼_x ∼[(⟨, x⟩ - ⟨β, x⟩)^2], where  is the input distribution. 

The model provider implicitly determines how to balance β_1 and β_2 when determining how to label their training dataset. In particular, each model provider is given an unlabelled training dataset X ∈ℝ^N × P with N inputs drawn from . To generate labels, they select the fraction α∈ [0,1] of training data to label according to each objective. They then sample a fraction  of the training data uniformly from X and label it as Y_i = ⟨β_1, X_i⟩; the remaining 1 - fraction is labelled as Y_i = ⟨β_2, X_i⟩. The model provider fits a ridge regression on the labelled training dataset with least-squares loss ℓ(y, y') = (y-y')^2, and thus solves: (, , X) = _β(1/N∑_i=1^N (Y_i - ⟨β, X_i ⟩)^2 +  ||β||^2_2 ). 



  
Marketplace.
The marketplace contains two companies, an incumbent company I already in the market and a new (entrant) company E trying to enter the market. At a high level, each company C ∈{I, E} 
faces reputational damage if their safety violation exceeds their safety constraint τ_C. Each company company C is given N_C unlabelled data points sampled from , and selects a mixture parameter _C and regularizer _C to maximize their performance given their safety constraint τ_C. We assume that the incumbent company I faces a stricter safety constraint, <, due to increased public or regulatory scrutiny (see Section <ref> for additional discussion). 

When formalizing how the model providers choose hyperparameters, we make the following simplications. First, rather than work directly with the performance and safety losses of the ridge regression estimator, we assume for analytic tractability that they approximate these losses by ^* := ^*(β_1, β_2, , , N, α) and ^* := ^*(β_1, β_2, , α) defined as follows. 

    
  * Performance: We define ^* to be a deterministic equivalent ^(β_1, β_2, Σ, , N, α) which we derive in Lemma <ref>. The deterministic equivalent  <cit.> is a tool from random matrix theory that is closely linked to the Marčenko-Pastur law <cit.>. Under standard random matrix assumptions (Assumption <ref>), the deterministic equivalent asymptotically approximates the loss L_1(β̂(α, λ, X)) when X is constructed from N i.i.d. samples from  (see Appendix <ref> for additional discussion). 
    
  * Safety: For analytic simplicity, in the main body of the paper, we define ^* to be the safety violation of the infinite-data ridgeless regression estimator with mixture parameter α.[The infinite-data ridgeless regression estimator is 
    _β(α·𝔼_x ∼[⟨β - β_1, x⟩^2] + (1-α)·𝔼_x ∼[⟨β - β_2, x⟩^2] ). For this specification, the dataset size N and the regularization parameter  only affect ^* and not ^*, which simplifies our analysis in Sections <ref>-<ref> and enables us to obtain tight characterizations.] In Appendix <ref>, we instead define ^* analogously to ^*—i.e., as a deterministic equivalent L_2^det(β_1, β_2, , λ, N, α)—and extend our model and results to this more complex setting.[We directly extend our results in Section <ref>, and we also show relaxed versions of our results in Section <ref>.]

Second, we assume that (β_1, β_2) ∼ for some joint distribution  and that the model providers take expectations when choosing hyperparameters, since it will be easier to specify assumptions in Section <ref> over distributions of predictors. 

Within this setup, a company C faces reputational damage if the safety violation exceeds a certain threshold: 

    𝔼_(β_1, β_2) ∼ [L_2^*(β_1, β_2, , α_C)] > τ_C.

We assume that the safety thresholds for the two companies satisfy the following inequalities: 

    >_(A)≥_(B)𝔼_(β_1, β_2) ∼[^*(β_1, β_2, , 0.5)].

Here, inequality (A) captures the notion that the incumbent needs to achieve higher safety to avoid reputational damage. Inequality (B) guarantees that both companies, C ∈{I, E }, can set the mixture parameter _C ≥ 0.5 without facing reputational damage, and thus ensures that the safety constraint does not dominate the company's optimization task.[More specifically, inequality (B) ensures that the safety constraint still allows both companies to label 50% of their training data according to the performance-optimal outputs.]  


The company selects ∈ [0.5,1] and ∈ (0,1) to maximize their performance subject to their safety constraint, as formalized by the following optimization program:[Technically, the optimum might be achieved at = 0 or = 1, and the min should be replaced by a inf.] 

    (_C, _C) = _∈ [0.5, 1], ∈ (0,1)𝔼_[^*(β_1, β_2, , , N_C, α)]  s.t. 𝔼_[^*(β_1, β_2, , α)] ≤τ_C.







  
Market-entry threshold. We define the market-entry threshold to capture the minimum number of data points  that the new company needs to collect to achieve better performance than the incumbent company while avoiding reputational damage. 


The market-entry threshold (, , , , )
is the minimum value of ∈ℤ_≥ 1 such that 𝔼_[^*(β_1, β_2, , , , )] ≤𝔼_[^*(β_1, β_2, , , , )].  


The goal of our work is to analyze the function (,, , ,  ). 






 §.§ Model discussion


Now that we have formalized our statistical model, we discuss and justify our design choices in greater detail. We defer a discussion of limitations to Section <ref>.



  
Presence of competing objectives. Our multi-objective formulation is motivated by how  ML models are often trained to balance multiple objectives which are in tension with each other. In some cases, the pretraining objective is in tension with the finetuning objective <cit.>. For example, the fine-tuning of a language model to be more aligned with user intent can degrade performance—e.g., because the model hedges too much—which creates an “alignment tax” <cit.>. In other cases,  fine-tuning approaches themselves balance multiple objectives such as helpfulness (which can be mapped to performance in our model) and harmlessness (which can be mapped to safety in our model) <cit.>. These objectives can be in tension with one another, for example if the user asks for dangerous information. 



  
High-dimensional linear regression as a statistical model. We focus on high-dimensional linear regression due to its ability to capture scaling trends observed in large-scale machine learning models such as language models, while still retaining analytic tractability. In particular, in single-objective environments, scaling trends for high-dimensional linear regression recover the empirically observed power-law scaling of the loss with respect to the dataset size <cit.>. Moreover, from an analytic perspective, the structural properties of high-dimensional linear regression make it possible to characterize the loss using random matrix machinery (see Appendix <ref>). 




  
Impact of market position on model provider constraint τ. Our assumption that > (inequality (A) in (<ref>)) is motivated by how large companies face greater reputational damage from safety violations than smaller companies. One driver of this unevenness in reputational damage is regulation: for example, recent regulation and policy <cit.> places stricter requirements on companies that use significant amounts of compute during training. In particular, these companies face more stringent compliance requirements in terms of safety assessments and post-deployment monitoring. Another driver of uneven reputational damage is public perception: we expect that the public is more likely to uncover safety violations for large companies, due to the large volume of user queries to the model. In contrast, for small companies, safety violations may be undetected or subject to less public scrutiny. 







 §.§ Assumptions on linear regression problem


To simplify our characterization of scaling trends, we follow prior work on high-dimensional linear regression <cit.> and make the following empirically motivated power-law assumptions. Let Σ = 𝔼_x ∼[xx^T] be the covariance matrix, and let λ_i and v_i be the eigenvalues and eigenvectors, respectively. We require the eigenvalues to decay with scaling exponent γ > 0 according to λ_i = i^-1-γ for 1 ≤ i ≤ P. 
For the alignment coefficients ⟨β_j, v_i⟩, it is cleaner to enforce power scaling assumptions in expectation, so that we can more easily define a correlation parameter. We require that for some δ > 0, the alignment coefficients satisfy 𝔼_[⟨β_j, v_i ⟩^2] = i^-δ, where v_i is the ith eigenvector of Σ, for j ∈{1,2} and 1 ≤ i ≤ P. We also introduce a similar condition on the joint alignment coefficients, requiring that for some ρ∈ [0,1), it holds that 𝔼_[⟨β_1, v_i ⟩⟨β_2, v_i ⟩ ] = ρ· i^-δ. Finally, we assume an overparameterized limit where the number of parameters P →∞ approaches infinity. Below, we provide an example which satisfies these assumptions. 


Suppose that the covariance Σ is a  diagonal matrix with diagonal given by λ_i = i^-1-γ. Let the joint distribution over β_1 and β_2 be a multivariate Gaussian such that:

    𝔼_[ (β_j_1)_i_1 (β_j_2)_i_2] = 
    
     0     if   1 ≤ j_1, j_2 ≤ 2, 1 ≤ i_1 ≠ i_2 ≤ P 
    
      i_1 ^-δ    if  1 ≤ j_1 = j_2 ≤ 2, 1 ≤ i_1 = i_2 ≤ P 
    ρ· i_1 ^-δ    if  1 ≤ j_1 ≠ j_2 ≤ 2, 1 ≤ i_1 = i_2 ≤ P.

This implies that 𝔼_[⟨β_j, v_i ⟩^2] = i^-δ and 𝔼_[⟨β_1, v_i ⟩⟨β_2, v_i ⟩ ] = ρ· i^-δ. 


We adopt the random matrix theory assumptions on the covariance matrix and linear predictors from <cit.> (see Assumption <ref> in Appendix <ref>), which guarantee that the Marčenko-Pastur law holds <cit.>. That is, the covariance (Σ̂ + λ I)^-1 of the samples can be approximated by a deterministic quantity (see Appendix <ref> for a more detailed discussion). We leverage this Marčenko-Pastur law to derive a deterministic equivalent L_1^ for the performance loss L_1(β̂(α, λ, X)) of the ridge regression estimator (Lemma <ref>). 










§ WARM UP: INFINITE-DATA INCUMBENT AND UNCONSTRAINED ENTRANT
 



As a warmup, we analyze the market entry  threshold in a simplified environment where the incumbent has infinite data and the new company faces no safety constraint. In this result, we place standard power-law scaling assumptions on the covariance and alignment coefficients (Section <ref>) and we characterize the threshold  up to constants (Theorem <ref>; Figure <ref>). 


Suppose that power-law scaling holds for the eigenvalues and alignment coefficients, with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0,1), and suppose that P = ∞. 
Suppose that the incumbent company has infinite data (i.e., = ∞), and that the entrant faces no constraint on their safety (i.e., = ∞). Suppose that the safety constraint  satisfies (<ref>). Then, it holds that:[Throughout the paper, we allow Θ() and O() to hide implicit constant which depends on the scaling exponents γ, δ.]

    (∞, , ∞, , ) = Θ((√(L^*(ρ)) - √(min(, L^*(ρ))))^-2/),

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ), and where := min(2(1+γ), δ + γ). 


The intuition is as follows. The safety constraint  forces the incumbent company to partially align their predictor with the safety objective β_2. Since β_1 and β_2 point in different directions, this reduces the performance of the incumbent along β_1 as a side effect, resulting in strictly positive loss with respect to performance. On the other hand, since the new company faces no safety constraint, the new company can optimize entirely for performance along β_1. This means that the new company can enter the market as long as their finite data error is bounded by the incumbent's performance loss. We formalize this intuition in the following proof sketch.


The incumbent chooses the infinite-data ridgeless estimator β(α, 0) with mixture parameter α∈ [0,1] tuned so the safety violation is  (Lemma <ref>). The resulting performance loss is √(L^*(ρ)) - √(min(, L^*(ρ))). Since the new company has no safety constraint, they choose the single-objective ridge regression estimator where α = 1 and where  is chosen optimally.[We formally rule out the possibility that α≠ 1 using our multi-objective scaling law in Theorem <ref>.] Theorem <ref> (or alternatively, 
existing analyses of high-dimensional linear regression <cit.>) demonstrate the loss follows a scaling law of the form inf_ > 0 L_1(β̂(1, , X)) = Θ(
N^-) where :=min(2(1+γ), δ +γ). The full proof is in Appendix <ref>. 


Theorem <ref> reveals that the market-entry threshold is finite as long as (1) the safety constraint  places nontrivial restrictions on the incumbent company and (2) the safety and performance objectives are not perfectly correlated. This result captures the notion that the new company can enter the market even after the incumbent company has accumulated an infinite amount of data. 



Theorem <ref> further illustrates how the market-entry threshold changes with other parameters (Figure <ref>). When safety and performance objectives are more correlated (i.e., when ρ is higher), the market-entry threshold increases, which increases barriers to entry. When the safety constraint for the incumbent is weaker (i.e., when  is higher), the market-entry threshold also increases. Finally, when the power scaling parameters of the covariance and alignment coefficients increase, which increases the scaling law exponent , the market-entry threshold decreases. 




 

§ GENERALIZED ANALYSIS OF THE MARKET-ENTRY THRESHOLD
 


To obtain a more fine-grained characterization of the market-entry threshold, we now consider more general environments. Our key technical tool is multi-objective scaling laws, which capture the performance of ridge regression in high-dimensional, multi-objective environments with finite data  (Section <ref>). Using these scaling laws, we characterize the market-entry threshold when the incumbent has finite data (Section <ref>) and when the new company has a safety constraint (Section <ref>).

Our results in this section uncover the following conceptual insights about market entry. First, our main finding from Section <ref>—that the new company can enter the market with significantly less data than the incumbent—applies to these generalized environments.  Moreover, our characterizations of  exhibit a power-law-like dependence with respect to the incumbent's dataset size (Theorem <ref>) and the difference in safety requirement for the two companies (Theorem <ref>). Interestingly, the scaling exponent c is not a constant across the full regime and instead takes on up to three different values. As a consequence, the new company can afford to scale up their dataset at a slower rate as the incumbent's dataset size increases, but needs to scale up their dataset at a faster rate as the two safety constraints become closer together. Proofs are deferred to Appendix <ref>.  




 §.§ Technical tool: Scaling laws in multi-objective environments


In this section, we give an overview of multi-objective scaling laws (see Section <ref> for a more formal treatment and derivations). Our scaling laws capture how the ridge regression loss L_1(β̂(α, λ, X)) along the primary objective β_1 scales with the dataset size N, when the regularizer  is optimally tuned to both N and problem-specified parameters. We show scaling laws for both the loss inf_∈ (0, 1)𝔼[L_1(β̂(α, λ, X))] and the excess loss  inf_∈ (0, 1) (𝔼[L_1(β̂(α, λ, X)) - L_1(β(α, 0))]) where β(α, 0) is the infinite-data ridgeless regression estimator. 








  
Scaling law for the loss.
We first describe the scaling law for inf_∈ (0, 1)𝔼[L_1(β̂(α, λ, X))] (Theorem <ref>; Figure <ref>). 


Suppose that the power-law scaling assumptions from Section <ref> hold with exponents γ, δ > 0 and correlation coefficient ρ∈ [0,1). Suppose also that P = ∞ and α≥ 0.5. Then, a deterministic equivalent for the expected loss  under optimal regularization  inf_∈ (0, 1)𝔼[L_1(β̂(α, λ, X))] scales according to N^-^*,  where the scaling exponent ^* is defined to be:   

    ^* =
        if  N ≤ (1-α)^-1/(1-ρ)^-1/
    / + 1    if  (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-2+/ (1-ρ)^-1/
    
    0     if  N ≥ (1-α)^-2+/ (1-ρ)^-1/,

for := min(2(1+γ), δ+γ). 


Theorem <ref> (Figure <ref>) illustrates that the scaling rate becomes slower as the dataset size N increases. In particular, while the scaling exponent in single-objective environments is captured by a single value, Theorem <ref> illustrates that the scaling exponent  ^* in multi-objective environments takes on three different values, depending on the size of N relative to other parameters. 
When N is small (the first regime), the scaling exponent ^* = is identical to that of the single-objective environment given by β_1. When N is a bit larger (the second regime), the scaling exponent reduces to ^* = /( + 1) <. To make this concrete, if we take = 0.34 to be an empirically estimated scaling law exponent for language models <cit.>, this would mean that ^* ≈ 0.34 in the first regime and ^* ≈ 0.25 in the second regime. Finally, when N is sufficiently large (the third regime), the scaling exponent reduces all the way to ^* = 0 and the only benefit of additional data is to improve constants on the loss. 



  
Scaling law for the excess loss.
We next turn to the excess loss, inf_∈ (0, 1) (𝔼[L_1(β̂(α, λ, X)) - L_1(β(α, 0))]), which is normalized by the loss of the infinite-data ridgeless predictor β(α, 0). We show that the excess loss exhibits the same scaling behavior as the loss when N is sufficiently small, but exhibits different behavior when N is sufficiently large (Theorem <ref>; Figure <ref>). 


Suppose that the power-law scaling assumptions from Section <ref> hold with exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1). Suppose also that P = ∞ and α≥ 0.75. Then, a deterministic equivalent for the expected loss  under optimal regularization  inf_∈ (0, 1) (𝔼[L_1(β̂(α, λ, X)) - L_1(β(α, 0))]) scales according to N^-^*,  where the scaling exponent ^* is defined to be:   

    ^* =
        if  N ≤ (1-α)^-1/(1-ρ)^-1/
    / + 1    if  (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-'+1/ - '(1-ρ)^-'+1/ - '
    '/' + 1    if  N ≥  (1-α)^-'+1/ - '(1-ρ)^-'+1/ - ',

for := min(2(1+γ), δ+γ) and ' := min(1+γ, δ+γ).



 Theorem <ref> (Figure <ref>) again shows that the scaling rate can become slower as the dataset size N increases, and again reveals three regimes of scaling behavior. While the first two regimes of Theorem <ref> resemble the first two regimes of Theorem <ref>, the third regime of Theorem <ref> (where N ≥  (1-α)^-'+1/ - '(1-ρ)^-'+1/ - ') behaves differently. In this regime, the scaling exponent for the excess loss is '/' + 1, rather than zero—this captures the fact that additional data can nontrivially improve the excess loss even in this regime, even though it only improves the loss up to constants. In terms of the magnitude of the scaling exponent '/' + 1, it is strictly smaller than the scaling exponent ν/ν +1 when δ > 1 and equal to the scaling exponent  ν/ν +1 when δ≤ 1. 





 §.§ Finite data for the incumbent


We compute  when the incumbent has finite data and the new company has no safety constraint (Theorem <ref>; Figure <ref>). The market-entry threshold  depends on the incumbent's dataset size , the incumbent's performance loss G_I if they were to have infinite data but face the same safety constraint, the scaling exponents γ, δ, and the correlation coefficient ρ.  


Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Assume that = ∞. Suppose that the safety constraint  satisfies (<ref>). Then we have that = (, , ∞, , ) satisfies: 

    := 
    Θ()     if ≤ G_I^-1/2  (1-ρ)^-1/2
    Θ(^1/+1· G_I^-1/2(+1) (1-ρ)^-1/2(+1))      if  G_I^-1/2  (1-ρ)^-1/2≤≤ G_I^-1/2 - 1/(1-ρ)^1/2
    Θ(G_I^-1/)      if ≥ G_I^-1/2 - 1/(1-ρ)^1/2,

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ), where G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and where = min(2(1+γ), δ + γ).



The market-entry threshold in Theorem <ref> exhibits three regimes of behavior depending on . In particular, the market-entry threshold takes the form = Θ(^c) where c decreases from 1 (in the first regime) to 1/ν + 1 (in the second regime) to 0 (in the third regime) as  increases. To connect this to large-language-model marketplaces, we directly set = 0.34 to be the empirically estimated scaling law exponent for language models <cit.>; in this case, the scaling exponent c ranges from 1 to 0.75 to 0. The fact that there are three regimes come from the scaling law derived in Theorem <ref>, as the following proof sketch illustrates. 


The key technical tool is the scaling law for the loss inf_∈ (0, 1)𝔼[L_1(β̂(α, λ, X))] (Theorem <ref>), which has three regimes of scaling behavior for different values of N. We apply the scaling law to analyze the performance of the incumbent, who faces a safety constraint and has finite data. Analyzing the performance of the new company—who faces no safety constraint—is more straightforward, given that the new company can set = 1. We compute  as the number of data points needed to match the incumbent's performance level.  The full proof is deferred to Appendix <ref>. 








Theorem <ref> reveals that the new company can enter the market with = o() data, as long as the incumbent's dataset is sufficiently large (i.e., ≥ G_I^-1/2  (1-ρ)^-1/2). The intuition is when there is sufficient data, the multi-objective scaling exponent is worse than the single-objective scaling exponent (Theorem <ref>).
The incumbent thus faces a worse scaling exponent than the new company, so the new company can enter the market with asymptotically less data. 

The three regimes in Theorem <ref> further reveal that the market-entry threshold  scales at a slower rate as the incumbent's dataset size  increases (Figure <ref>). The intuition is that the multi-objective scaling exponent ^* faced by the incumbent decreases as dataset size increases, while the single-objective scaling exponent faced by the new company is constant in dataset size (Theorem <ref>). The incumbent thus becomes less efficient at using additional data to improve performance, while the new company's efficiency in using additional data remains unchanged. 

Theorem <ref> also offers finer-grained insight into the market-entry threshold in each regime. In the first regime, where the incumbent's dataset is small, the threshold   matches the incumbent dataset size—the new company does not benefit from having a less stringent safety constraint.  In the second (intermediate) regime, the new company can enter with a dataset size proportional to ^1/(+1). This polynomial speedup illustrates that the new company can more efficiently use additional data to improve performance than the incumbent company.  A caveat is that this regime is somewhat restricted in that the ratio of the upper and lower boundaries is bounded. In the third regime, where the incumbent's dataset size is large, the market-entry threshold  matches the market-entry threshold from Theorem <ref> where the incumbent has infinite data.









 §.§ Safety constraint for the new company


We compute  when the new company has a nontrivial safety constraint and the incumbent has infinite data. For this result, we strengthen the conditions on  and  from (<ref>), instead requiring: 

    >_(A)≥_(B)𝔼_(β_1, β_2) ∼[^*(β_1, β_2, , 0.75)],

where (<ref>) replaces the 0.5 with a 0.75 in the right-most quantity.[Inequality (B) in (<ref>) requires that the safety constraint still allows both company to label 75% of their training data according to performance-optimal outputs. We make this modification, since our analysis of multi-objective scaling laws for the excess loss assumes α≥ 0.75 (see Section <ref>).] 


We state the result below (Theorem <ref>; Figure <ref>). The market-entry threshold  depends on the incumbent's safety constraint , the performance loss G_I (resp. G_E) if the incumbent (resp. new company) had infinite data and faced the same safety constraint, the difference D = G_I - G_E in infinite-data performance loss achievable by the incumbent and new company, the scaling exponents γ, δ, and the correlation coefficient ρ. 









Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Suppose that the safety constraints  and  satisfy (<ref>).
Then it holds that = (∞, , , , ) satisfies: 

    := 
    Θ(D^-1/ )     if  D ≥ G_E^1/2 (1-ρ)^1/2
    Θ(D^-+1/ G_E^1/2 (1-ρ)^1/2)     if  
    G_E^/2( - ')  (1-ρ)^/2( - ')≤ D ≤  G_E^1/2 (1-ρ)^1/2
    Θ((D · G_E^-1/2 (1-ρ)^-1/2)^-'+1/')     if  D ≤ G_E^/2( - ')  (1-ρ)^/2( - '),

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β)] = Θ(1 - ρ), where = min(2(1+γ), δ + γ) and ' = min(1+γ, δ + γ), where 
G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 and G_E := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and where D := G_I - G_E. 


The market-entry threshold in Theorem <ref> also exhibits three regimes of behavior depending on the difference D in the infinite-data performance loss achievable by the incumbent and new company. In particular, the market-entry threshold takes the form = Θ(D^-c) where c increases from 1/ to +1/ to '+1/' as D decreases. (The third regime only exists when δ > 1.) To connect this to large-language-model marketplaces, if we take = 0.34 to be the empirically estimated scaling law exponent for language models <cit.>, then c would range from 2.94 to 3.94 to potentially even larger. The fact that there are three regimes come from the scaling law derived in Theorem <ref>, as the following proof sketch illustrates. 



The key technical tool is the scaling law for the excess loss inf_∈ (0, 1) (𝔼[L_1(β̂(α, λ, X)) - L_1(β(α, 0))]) (Theorem <ref>),  which has three regimes of scaling behavior for different values of N. We apply the scaling law to analyze the performance of the new company, who faces a safety constraint and has finite data. Analyzing the performance of the incumbent—who has infinite data—is more straightforward, and the incumbent's performance loss is G_I = D + G_E. We compute the number of data points  needed for the new company to achieve an excess loss of D. The full proof is deferred to Appendix <ref>. 
 


Theorem <ref> illustrates that the new company can enter the market with finite data , as long as the safety constraint  placed on the new company is strictly weaker than the constraint  placed on the incumbent company (inequality (A) in (<ref>)). This translates to the difference D being strictly positive. The intuition is that when the new company faces a weaker safety constraint, it can train on a greater number of data points labelled with the performance objective β_1, which improves performance. 


The three regimes in Theorem <ref> further reveal that the market-entry threshold  scales at a faster rate as the difference D between the two safety constraints decreases (Figure <ref>). The intuition is  since the new company needs to achieve an excess loss of at most D, the new company faces a smaller multi-objective scaling exponent ^* as D decreases (Theorem <ref>). The new company thus becomes less efficient at  using additional data to improve performance. 





§ DERIVING SCALING LAWS FOR MULTI-OBJECTIVE ENVIRONMENTS
 

We formalize and derive our multi-objective scaling laws for the loss (Theorem <ref>) and excess loss (Theorem <ref>). Recall that the problem setting is high-dimensional ridge regression when a fraction α of the training data is labelled according to β_1 and the rest is labelled according to an alternate objective β_2. First, following the style of analysis of single-objective ridge regression <cit.>, we first compute a deterministic equivalent of the loss (Section <ref>). Then we derive the scaling law under the power scaling assumptions on the eigenvalues and alignment coefficients in Section <ref>, both for the loss (Section <ref>) and for the excess loss (Section <ref>). Proofs are deferred to Appendix <ref>.




 §.§ Deterministic equivalent


We show that the loss of the ridge regression estimator can be approximated as a deterministic quantity. This analysis builds on the random matrix tools in <cit.> (see Appendix <ref>). Note that our derivation of the deterministic equivalent does not place the power scaling assumptions on the eigenvalues or alignment coefficients; in fact, it holds for any linear regression setup which satisfies a standard random matrix theory assumption (Assumption <ref>). 

We compute the following deterministic equivalent (proof deferred to Appendix <ref>).[Following <cit.>, the asymptotic equivalence notation u ∼ v means that u/v tends to 1 as N and P go to ∞.]  


Suppose that N ≥ 1, P ≥ 1, , β_1, and β_2 satisfy Assumption <ref>. Let Σ be the covariance matrix of , and let ∈ [0,1] and ∈ (0,1) be general parameters. Let Σ_c = (Σ + c I) for c ≥ 0, let 1 = β_1 β_1^T, let = (β_1 - β_2)(β_1 - β_2)^T, and let 1 = (β_1 - β_2) β_1^T. Let κ = κ(λ, N, Σ) from Definition <ref>. Then, it holds that 

    L_1(β̂(α, λ, X)) ∼ L_1^(β_1, β_2, , , N, α) =: T_1 + T_2 + T_3 + T_4 + T_5/,

where:

    T_1 := κ^2 ·(ΣΣ_κ^-21) ,     T_2 := (1-α)^2 ( (Σ_κ^-2Σ^3 ))


    T_3 := 2 (1-α) κ·(Σ_κ^-2Σ^2 1) ,     T_4 := -2 (1-α)  κ1/N(Σ^2 Σ_κ ^-2) ·(Σ_κ^-1Σ1) ,


    T_5 := (1-α) 1/N(Σ^2 Σ_κ ^-2) ·((Σ)- 2 (1-α) ( Σ_κ^-1Σ^2 ) ),       := 1 - 1/N(Σ^2 Σ_κ ^-2).




Lemma <ref> shows that the loss can be approximated by a deterministic quantity L_1^(β_1, β_2, , , N, α) which is sum of five terms, normalized  by the standard degrees of freedom correction ^-1 <cit.>. The sum T_1 + T_2 +T_3 is the loss of infinite-data ridge regression with regularizer κ. Terms T_4 and T_5 capture additional error terms. 

In more detail, term T_1 / captures the standard single-objective environment error for N data points <cit.>: i.e., the population error of the single-objective linear regression problem with regularizer λ where all of the N training data points are labelled with β_i. Term T_2 is similar to the infinite-data ridgeless regression error but is slightly smaller due to regularization. Term T_3
is a cross term which is upper bounded by the geometric mean of term T_1 and term T_2. Term T_4 is another cross term which is subsumed by the other terms. Term T_5 captures an overfitting error which increases with the regularizer κ and decreases with the amount of data N. 



  
From deterministic equivalents to scaling laws. In the following two subsections, using the deterministic equivalent from Lemma <ref>, we derive scaling laws. We make use of the the power scaling assumptions on the covariance and alignment coefficients described in Section <ref>, under which the deterministic equivalent takes a cleaner form (Lemma <ref> in Appendix <ref>). 
We note that strictly speaking, deriving scaling laws requires controlling the error of the deterministic equivalent relative to the actual loss; for simplicity, we do not control errors and instead directly analyze the deterministic equivalent.




 §.§ Scaling law for the loss


We derive scaling laws for the loss L_1^ := L_1^(β_1, β_2, , , N, α). We first prove the following scaling law for a general regularizer  (proof deferred to Appendix <ref>). 


Suppose that the power-law scaling assumption holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume that α≥ 0.5 and λ∈ (0,1). 
Let L_1^ := L_1^(β_1, β_2, , , N, α) be the deterministic equivalent from Lemma <ref>. Let := min(2(1+γ), δ+γ). 
Then, the expected loss satisfies: 

    𝔼_[L_1^] =Θ( max(λ^/1+γ, N^-)_finite data error + (1-α)^2 · (1 - ρ)_mixture error +   (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ)
    _overfitting error).




Theorem <ref> illustrates that the loss is the sum of a finite data error, an overfitting error, and a mixture error. The finite data error for L_1^ matches the loss in the single-objective environment for N data points labelled with objective β_1.  The mixture error equals the loss of the infinite-data ridgeless regression predictor β(α, 0). The overfitting error for L_1^ equals the error incurred when the regularizer  is too small. This term is always at most (1-α)^-1 times larger than the mixture error, and it is smaller than the mixture error when  is sufficiently large relative to N. 



Due to the overfitting error, the optimal loss is not necessarily achieved by taking → 0 for multi-objective linear regression. In fact, if the regularizer decays too quickly as a function of N (i.e., if = O(N^-1-γ)), then the error would converge to (1-α)(1-ρ), which is a factor of (1-α)^-1 higher than the error of the infinite-data ridgeless predictor β(α, 0). 
The fact that → 0 is suboptimal reveals a sharp disconnect between the multi-objective setting and the single-objective setting where no explicit regularization is necessary to achieve the optimal loss <cit.>.[Tempered overfitting <cit.> can similarly occur in single-objective settings with noisy observations. In this sense, labelling some of the data with the alternate objective β_2 behaves qualitatively similarly to noisy observations. ]

In the next result, we compute the optimal regularizer and derive a scaling law under optimal regularization as a corollary of Theorem <ref>.


Consider the setup of Theorem <ref>. 
Then, the loss under optimal regularization can be expressed as:

    inf_∈ (0,1)𝔼_[L_1^]  = Θ(N^-)     if  N ≤ (1-α)^-1/(1-ρ)^-1/
    Θ((N/(1-α)(1-ρ))^-/ + 1)     if  (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-2+/ (1-ρ)^-1/
    Θ((1-α)^2(1-ρ))     if  N ≥ (1-α)^-2+/ (1-ρ)^-1/,

where := min(2(1+γ), δ+γ). 


The scaling law exponent ^* ranges from , to /(+1), to 0 (Figure <ref>). To better understand each regime, we provide intuition for when error term from Theorem <ref> dominates, the form of the optimal regularizer, and the behavior of the loss. 

    
  * Regime 1: N ≤ (1-α)^-1/(1-ρ)^-1/. Since N is small, the finite data error dominates regardless of . As a result, like in a single-objective environment, taking = O(N^-1-γ) recovers the optimal loss up to constants. Note that the loss thus behaves as if all N data points were labelled according to β_i: the learner benefits from all of the data, not just the data is labelled according to β_i. 
    
  * Regime 2: (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-2+/ (1-ρ)^-1/. In this regime, the finite error term and overfitting error dominate.  Taking = Θ(((1-α) (1-ρ)/N)^1+γ/ + 1), which equalizes the two error terms, recovers the optimal loss up to constants. The loss in this regime improves with N, but at a slower rate than in a single-objective environment. 
    
  * Regime 3: N ≥ (1-α)^-2+/ (1-ρ)^-1/.
   Since N is large, the mixture and the overfitting error terms dominate. Taking = Θ((N(1-α))^-1-γ), which equalizes the two error terms, recovers the optimal loss up to constants. The loss behaves (up to the constants) as if there were infinitely many data points from the mixture distribution with weight α. This is the minimal possible loss and there is thus no additional benefit for data beyond improving constants.

The full proof of Corollary <ref> is deferred to Appendix <ref>. 



 §.§ Scaling law for the excess loss


Now, we turn to scaling laws for the excess loss 𝔼_[L_1^(β_1, β_2, , , N, α) - L_1(β(α, 0))], , which is normalized by the loss of the infinite-data ridgeless predictor β(α, 0). We first prove the following scaling law for a general regularizer , assuming that α≥ 0.75 (proof deferred to Appendix <ref>).[The assumption that α≥ 0.75 simplifies the closed-form expression for the deterministic equivalent of the excess loss in Lemma <ref>. We defer a broader characterization of scaling laws for the excess loss to future work.] 


Suppose that the power-law scaling assumption holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume that α≥ 0.75 and λ∈ (0,1). 
Let L_1^ := L_1^(β_1, β_2, , , N, α) be the deterministic equivalent from Lemma <ref>. Let := min(2(1+γ), δ+γ) and let ' = min(1+γ, δ+γ) 
Then, the expected loss satisfies: 

    𝔼_[L_1^ - L_1(β(α, 0))]  
       =  Θ( max(λ^/1+γ, N^-)_finite data error + (1-ρ) (1-α) max(λ^'/1+γ, N^-')_mixture finite data error +   (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ)
    _overfitting error).



Theorem <ref> illustrates that the loss is the sum of a finite data error, an overfitting error, and a mixture finite data error. In comparison with Theorem <ref>, the difference is that the mixture error is replaced by the mixture finite data error. Interestingly, the mixture finite data error exhibits a different asymptotic dependence with respect to λ and N than the finite data error: the asymptotic rate of decay scales with ' rather than . In fact, the rate is slower for the mixture finite data error than the finite data error as long as δ > 1 (since this means that ' <). 

Since the optimal excess loss is also not necessarily achieved by taking → 0, we compute the optimal regularizer for the excess loss and derive a scaling law under optimal regularization as a corollary of Theorem <ref>.


Consider the setup of Theorem <ref>. 
The excess loss under optimal regularization can be expressed as:

    inf_∈ (0,1) (𝔼_[L_1^ - L_1(β(α, 0))]) 
       = Θ(N^-)     if  N ≤ (1-α)^-1/(1-ρ)^-1/
    Θ((N/(1-α)(1-ρ))^-/ + 1)     if  
    (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-'+1/ - '(1-ρ)^-'+1/ - '
    Θ((1-α) (1-ρ) N^-'/'+1)     if  N ≥ (1-α)^-'+1/ - '(1-ρ)^-'+1/ - ',

where := min(2(1+γ), δ+γ) and ' = min(1+γ, δ + γ). 



The scaling law exponent ^* ranges from , to /(+1), to '/('+1) (Figure <ref>). The first two regimes behave similarly to  Corollary <ref>, and the key difference arises in the third regime (when N is large). In the third regime (N ≥ (1-α)^-'+1/ - '(1-ρ)^-'+1/ - '), the mixture finite data error and the overfitting error terms dominate. Taking = Θ(N^-1+γ/'+1)—which equalizes these two error terms—recovers the optimal loss up to constants. The resulting scaling behavior captures that in this regime, additional data meaningfully improves the excess loss, even though additional data only improves the loss in terms of constants. The full proof of Corollary <ref> is deferred to Appendix <ref>. 



§ DISCUSSION


We studied market entry in marketplaces for machine learning models, showing that pressure to satisfy safety constraints can reduce barriers to entry for new companies. We modelled the marketplace using a high-dimensional multi-objective linear regression model. Our key finding was that a new company can consistently enter the marketplace with significantly less data than the incumbent. En route to proving these results, we derive scaling laws for multi-objective regression, showing that the scaling rate becomes slower when the dataset size is large. 




  
Potential implications for regulation. Our results have nuanced design consequences for regulators, who implicitly influence the level of safety that each company needs to achieve to avoid reputational damage. On one hand, our results suggest that placing greater scrutiny on dominant companies can encourage market entry and create a more competitive marketplace of model providers. On the other hand, market entry does come at a cost to the safety objective: the smaller companies exploit that they can incur more safety violations while maintaining their reputation, which leads to a race to the bottom for safety. Examining the tradeoffs between market competitiveness and safety compliance is an important direction for future work. 






  
Barriers to market entry for online platforms. While we focused on language models, we expect that our conceptual findings about market entry also extend to recommendation and social media platforms. 

In particular, our motivation and modeling assumptions capture key aspects of these online platforms. Policymakers have raised concerns have been raised about barriers to entry for social media platforms <cit.>, motivated by the fact that social media platforms such as X and Facebook each have over a half billion users <cit.>. Incumbent companies risk reputational damage if their model violates safety-oriented objectives—many recommendation platforms have faced scrutiny for promoting hate speech <cit.>, divisive content <cit.>, and excessive use by users <cit.>, even when recommendations perform well in terms of generating user engagement. This means that incumbent platforms must balance optimizing engagement with controlling negative societal impacts <cit.>. Moreover, new companies face less regulatory scrutiny, given that some regulations explicitly place more stringent requirements on companies with large user bases: for example the Digital Services Act <cit.> places a greater responsibility on Very Large Online Platforms (with over 45 million users per month) to identify and remove illegal or harmful content. 

Given that incumbent platforms similarly face more pressure to satisfy safety-oriented objectives, our results suggest that multi-objective learning can also reduce barriers to entry for new online platforms. 



  
Limitations. Our model for interactions between companies and users makes several simplifying assumptions. For example, we focused entirely whether the new company can enter the market, which leaves open the question of whether the new company can survive in the long run. Moreover, we assumed that all users choose the model with the highest overall performance. However, different users often care about performance on different queries; this could create an incentive for specialization, which could also reduce barriers to entry and market concentration. Finally, we focused on direct interactions between model providers and users, but in reality, downstream providers sometimes build services on top of a foundation model. Understanding how these market complexities affect market entry as well as long-term concentration is an interesting direction for future work. 

Furthermore, our model also made the simplifying assumption that performance and safety trade off according to a multi-objective regression problem. 
However, not all safety objectives fit the mold of linear coefficients within linear regression. For some safety objectives such as privacy, we still expect that placing greater scrutiny on dominant companies could similarly reduce barriers to entry. Nonetheless, for other safety or societal considerations, we do expect that the implications for market entry might be fundamentally different. For example, if the safety objective is a multi-group performance criteria, and there is a single predictor that achieves zero accuracy on all distributions, then a dominant company with infinite data would be able to retain all users even if the company faces greater scrutiny. Extending our model to capture a broader scope of safety objectives is a natural direction for future work.




§ ACKNOWLEDGMENTS

We thank Alireza Fallah, Jiahai Feng, Nika Haghtalab, Andy Haupt, Erik Jones, Jon Kleinberg, Ben Laufer, Neil Mallinar, Judy Shen, Alex Wei, Xuelin Yang, and Eric Zhao for useful feedback on this project. This work was partially supported by an Open Philanthropy AI fellowship and partially supported by the European Union (ERC-2022-SYG-OCEAN-101071601).


plainnat









§ PROOFS FOR SECTION <REF>


In this section, we prove Theorem <ref>. First, we state relevant facts (Appendix <ref>) and prove intermediate lemmas (Appendix <ref>), and then we use these ingredients to prove Theorem <ref> (Appendix <ref>). Throughout this section, we let 

    L^*(ρ) = 𝔼_[(β_1 - β_2) Σ (β_1 - β_2)^T].

Moreover, let  

    β(α, λ) = _β(α·𝔼_X ∼[(⟨β - β_1, X ⟩)^2] + (1-α) ·𝔼_X ∼[(⟨β - β_2, X ⟩)^2] + λβ_2^2 )
  be the infinite-data ridge regression predictor.



 §.§ Facts


We can explicitly solve for the infinite-data ridge regression predictor 

    β(α, λ)    =  _β(α·𝔼_x ∼[⟨β - β_1, x⟩^2] + (1-α)·𝔼_x ∼[⟨β - β_2, x⟩^2] +  ||β||^2_2 ) 
       = Σ (Σ + λ I)^-1 (αβ_1 + (1-α) β_2).

A simple calculation shows that 𝔼_[L_1(β(α, 0))]  = (1-α)^2 L^*(ρ) and 𝔼_[L_2(β(α, 0))]  = α^2 L^*(ρ). Thus, it holds that: 

    α𝔼_[L_1(β(α, 0))] + (1-α) 𝔼_[L_2(β(α, 0))] = α (1-α) L^*(ρ).
 Moreover, by the definition of the ridge regression objective, we see that:

    α𝔼_[L_1(β(α, λ))] + (1-α) 𝔼_[L_2(β(α, λ))] ≥α𝔼_[L_1(β(α, 0))] + (1-α) 𝔼_[L_2(β(α, 0))].




 §.§ Lemmas


The first lemma upper bounds the performance loss when there is regularization.  


Suppose that power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1) and suppose that P = ∞. Let L^*(ρ) = (β_1 - β_2)^T Σ (β_1 - β_2)^T.  Let 

    β(α, λ) = _β(α·𝔼_X ∼[(⟨β - β_1, X ⟩)^2] + (1-α) ·𝔼_X ∼[(⟨β - β_2, X ⟩)^2] + λβ_2^2)
  be the infinite-data ridge regression predictor. Assume that α≥ 1/2. Then it holds that

    𝔼_[L_1(β(α, λ))] ≥ (1-α)^2 L^*(ρ)

and 

    𝔼_[L_1(β(α, λ))]/𝔼_[L_2(β(α, λ))]≥(1-α)^2/α^2.



We define the quantities: 

    A    := λ^2 ∑_i=1^P λ_i/(λ_i + λ)^2 i^-δ
    
      B    := (1-α)^2 (1-ρ)^2 ∑_i=1^P λ^3_i/(λ_i + λ)^2 i^-δ
    
      C    := λ (1-ρ) ∑_i=1^P λ^2_i/(λ_i + λ)^2 i^-δ.

We compute the performance loss as follows: 

    𝔼_[L_1(β(α, λ))] 
       = 𝔼_[(Σ (β_1 - β(α, λ)) (β_1 - β(α, λ))^T) ] 
       = 𝔼_[((Σ + λ I)^-2Σ( λβ_1 + Σ· (1-α) (β_1 - β_2) ) ( λβ_1 + Σ· (1-α)(β_1 - β_2) )^T)]  
       = 𝔼_[((Σ + λ I)^-2Σ·( λβ_1 + Σ· (1-α) (β_1 - β_2) ) ( λβ_1 + Σ· (1-α) (β_1 - β_2) )^T)] 
       = λ^2 𝔼_[((Σ + λ I)^-2Σ·β_1 β_1^T)] + (1-α)^2 𝔼_[((Σ + λ I)^-2Σ^3 · (β_1 - β_2) (β_1 - β_2)^T) ] 
        + λ (1-α) 𝔼_[((Σ + λ I)^-2Σ^2 ·β_1 (β_1 - β_2)^T )] 
       = λ^2 ∑_i=1^P λ_i/(λ_i + λ)^2𝔼_[⟨β_1, v_i ⟩^2] + (1-α)^2 ∑_i=1^P λ^3_i/(λ_i + λ)^2𝔼_[⟨β_1 - β_2, v_i ⟩^2]
        + λ (1-α) ∑_i=1^P λ^2_i/(λ_i + λ)^2𝔼_[⟨β_1, v_i ⟩⟨β_1 - β_2, v_i⟩] 
       = λ^2 ∑_i=1^P λ_i/(λ_i + λ)^2 i^-δ + (1-α)^2 (1-ρ)^2 ∑_i=1^P λ^3_i/(λ_i + λ)^2 i^-δ + λ (1-α) (1-ρ) ∑_i=1^P λ^2_i/(λ_i + λ)^2 i^-δ
       = A + (1-α)^2 B + (1-α) C.

An analogous calculation shows that the safety violation can be written as:

    𝔼_[L_2(β(α, λ))] = A + α^2 B + α C

Since α≥ 1/2, then it holds that:

    𝔼_[L_1(β(α, λ))]/𝔼_[L_2(β(α, λ))] =  A + (1-α)^2 B + (1-α) C/A + α B + α C≥(1-α)^2/α^2.

Combining this with the facts from Appendix <ref>—which imply that α𝔼_[L_1(β(α, λ))] + (1-α) 𝔼_[L_2(β(α, λ))] ≥α (1-α) L^*(ρ)—we have that 𝔼_[L_1(β(α, λ))] ≥ (1-α)^2 L^*(ρ) as desired.  


The following lemma computes the optimal values of  and  for the incumbent. 


Suppose that power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1) and suppose that P = ∞. Let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T]. Suppose that = ∞, and suppose that the safety constraint  satisfies (<ref>). Then it holds that α_I =  √(min(, L^*(ρ))/L^*(ρ)), and _I = 0 is optimal for the incumbent. Moreover, it holds that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α_O)] = (√(L^*(ρ)) - √(min(, L^*(ρ)))^2.



First, we apply Lemma <ref> with N = ∞ to see that:

    𝔼_[L^*_1(β_1, β_2, , , ∞, α)] = 𝔼_[L_1(β(α, λ))]

and apply the definition of L_2^* to see that:

    𝔼_[L^*_2(β_1, β_2, , α)] = 𝔼_[L_2(β(α, 0))].


Let α^* =√(min(, L^*(ρ))/L^*(ρ)). By the assumption in the lemma statement, we know that:

    α^* ≥√(𝔼_[^*(β_1, β_2, , 0.5)]/L^*(ρ)) = 0.5.


We show that (α_I, _I) = (α^*, 0). Assume for sake of contradiction that (α, ) ≠ (α^*, 0) satisfies the safety constraint 𝔼_[^*(β_1, β_2, , α)] ≤ and achieves strictly better performance loss:

    𝔼_[^*(β_1, β_2, , , ∞, )] <  𝔼_[^*(β_1, β_2, , 0, ∞, ^*)].

We split into two cases: α^* = α, ≠ 0 and α^* ≠α. 



  
Case 1: α^* = α, ≠ 0. 
By Lemma <ref>, we know that 

    𝔼[L^*_1(β_1, β_2, , , ∞, α^*)] = 𝔼_[L_1(β(α^*, λ))] ≥ (1-α^*)^2 L^*(ρ).

Equality is obtained at = 0, which is a contradiction. 



  
Case 2: α≠α^*. 
By Lemma <ref>, it must hold that α > α^* in order for the performance to beat that of (α^*, 0). However, this means that the safety constraint 

    𝔼_[^*(β_1, β_2, , α)] = α^2 L^*(ρ) > (α^*)^2 L^*(ρ) =

is violated, which is a contradiction. 



  
Concluding the statement. This means that(α_I, _I) = (α^*, 0), which also means that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α_I)]    = 𝔼_[L_1(β(α_I, λ_I))]
       = (1-α_I)^2  𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] 
       = (√(L^*(ρ)) - √(min(, L^*(ρ)))^2.

    


The following claim calculates 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)]. 


Suppose that the power-law scaling assumption holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Then it holds that: 

    𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)]  = 2 (1-ρ) (∑_i=1^P i^-δ-1-γ) = Θ(1-ρ).



Let Σ = V Λ V^T be the eigendecomposition of Σ, where Λ is a diagonal matrix consisting of the eigenvalues. We observe that 

    𝔼_[⟨β_1 - β_2, v_i⟩^2] = 𝔼_[⟨β_1 , v_i⟩^2] + 𝔼_[⟨β_2, v_i⟩^2] - 2 𝔼_[⟨β_1 , v_i⟩⟨β_2, v_i⟩]  = i^-δ + i^-δ - 2 ρ i^-δ = 2(1-ρ) i^-δ.


This means that: 

    𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)]    = (Σ𝔼_[(β_1 - β_2) (β_1 - β_2)^T]) 
       = (Λ𝔼_[V^T (β_1 - β_2) (β_1 - β_2)^T V] ) 
       = ∑_i=1^P  i^-1-γ𝔼_[⟨β_1 - β_2, v_i⟩^2]
       = 2 (1 - ρ) ∑_i=1^P i^-δ-1-γ
       = Θ(1-ρ).






 §.§ Proof of Theorem <ref>


We prove Theorem <ref> using the above lemmas along with Corollary <ref> (the proof of which we defer to Appendix <ref>). 



We analyze (α_C, _C) first for the incumbent C = I and then for the entrant C = E. 



  
Analysis of the incumbent C = I.
To compute α_I and _I, we apply Lemma <ref>. 
By Lemma <ref>, we see that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α_I)] = (√(L^*(ρ)) - √(min(, L^*(ρ)))^2.




  
Analysis of the entrant C = E. Since the entrant faces no safety constraint, the entrant can choose any α∈ [0.5, 1]. We apply Corollary <ref> to see that:

    𝔼_[L^*_1(β_1, β_2, , _E, N, α_E)] = inf_α∈ [0.5, 1]inf_ > 0𝔼_[L^*_1(β_1, β_2, , , N, α)] = Θ(
    N^-),

which means that:

    ^*(∞, , ∞, , ) = Θ((√(L^*(ρ)) - √(min(, L^*(ρ)))^-2/)

as desired. 
We can further apply Claim <ref> to see that L^*(ρ) = Θ(1-ρ). 







§ PROOFS FOR SECTION <REF>





 §.§ Proofs for Section <ref>


We prove Theorem <ref>. The main technical tool is Theorem <ref>, the proof of which we defer to Appendix <ref>. 



We analyze (α_C, _C) first for the incumbent C = I and then for the entrant C = E. Like in the theorem statement, let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ) (Claim <ref>) and G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and = min(2(1+γ), δ + γ).



  
Analysis of the incumbent C = I. Recall from the facts in Appendix <ref> that:

    L_1^*(β_1, β_2, , α) = α^2 L^*(ρ).

This means that the safety constraint is satisfied if and only if _I ≤√(min(, L^*(ρ))/L^*(ρ)) =: α^*. The bound in Corollary <ref> implies that:

    𝔼_[L^*_1(β_1, β_2, , _I, , α_I)] 
       = inf_α∈[0.5, α^* ]inf_ > 0𝔼_[L^*_1(β_1, β_2, , ,  , α)]  
       = Θ(
    inf_ > 0𝔼_[L^*_1(β_1, β_2, Σ, ,  , α^* )] ) 
       = Θ(^-)     if ≤ (1-α^* )^-1/(1-ρ)^-1/
    Θ((/(1-α^* )(1-ρ))^-/ + 1)     if  (1-α^* )^-1/(1-ρ)^-1/≤≤  (1-α^* )^-2+/ (1-ρ)^-1/
    Θ((1-α^* )^2(1-ρ))     if ≥ (1-α^* )^-2+/ (1-ρ)^-1/,
    
       = Θ( ^-)     if ≤ G_I^-1/2 (1-ρ)^-1/2
    Θ(^-/+1· G_I^/2(+1) (1-ρ)^/2(+1))      if  G_I^-1/2 (1-ρ)^-1/2≤≤ G_I^-1/2 - 1/(1-ρ)^1/2
    Θ(G_I)      if ≥ G_I^-1/2 - 1/(1-ρ)^1/2.




  
Analysis of the entrant C = E. Since the entrant faces no safety constraint, the entrant can choose any α∈ [0.5, 1].  We apply Corollary <ref> to see that:

    𝔼_[L^*_1(β_1, β_2, , _E, N, α_E)] = inf_α∈ [0.5, 1]inf_ > 0𝔼_[L^*_1(β_1, β_2, , , N, α)] = Θ(
    N^-),

which means that:

    ^*(, , ∞, , ) = Θ()     if ≤ G_I^-1/2 (1-ρ)^-1/2
    Θ(^1/+1· G_I^-1/2(+1) (1-ρ)^-1/2(+1))      if  G_I^-1/2 (1-ρ)^-1/2≤≤ G_I^-1/2 - 1/(1-ρ)^1/2
    Θ(G_I^-1/)      if ≥ G_I^-1/2 - 1/(1-ρ)^1/2.

as desired.  






 §.§ Proofs for Section <ref>


We prove Theorem <ref>. When the the safety constraints of the two firms are sufficiently close, it no longer suffices to analyze the loss up to constants for the entrant, and we require a more fine-grained analysis of the error terms than is provided in the scaling laws in Corollary <ref>. In this case, we turn to scaling laws for the excess loss as given by Corollary <ref>. 





We analyze (α_C, _C) first for the incumbent C = I and then for the entrant C = E. Like in the theorem statement, let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ) (Claim <ref>), G_I = (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, G_E = (√(L^*(ρ)) - √(min(, L^*(ρ))))^2,
D = G_I - G_E, and = min(2(1+γ), δ + γ).



  
Analysis of the incumbent C = I. Since the incumbent has infinite data, we apply Lemma <ref> to see that: 

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, _I)]    = (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 
       = D + G_E.





  
Analysis of the entrant C = E. Recall from the facts in Appendix <ref> that:

    L_1^*(β_1, β_2, , α) = α^2 L^*(ρ).

This means that the safety constraint is satisfied if and only if ≤√(min(, L^*(ρ))/L^*(ρ)) =: α^*. The bound in Corollary <ref> implies that:

    𝔼_[L^*_1(β_1, β_2, , _E, N, α_E)] 
       = inf_α∈[0.5, α^* ]inf_ > 0𝔼_[L^*_1(β_1, β_2, , ,  N, α)]  
       = inf_α∈[0.5, α^* ](inf_ > 0(𝔼_[L^*_1(β_1, β_2, , ,  N, α) - L_1(β(α, 0))]) + 𝔼_[L_1(β(α, 0))] ) 
       = inf_α∈[0.5, α^* ](inf_ > 0(𝔼_[L^*_1(β_1, β_2, , ,  N, α) - L_1(β(α, 0))]) + (1-α)^2 L^*(ρ) ) 
       = Θ(
    inf_ > 0(𝔼_[L^*_1(β_1, β_2, , ,  N, α) - L_1(β(α^*, 0))]) ) +  (1-α^*)^2 L^*(ρ)  
       = 
     (1-α^*)^2 L^*(ρ)  + Θ(N^-)     if  N ≤ (1-α^*)^-1/(1-ρ)^-1/
    
     (1-α^*)^2 L^*(ρ)  + Θ((N/(1-α^*)(1-ρ))^-/ + 1)     if  
    (1-α^*)^-1/(1-ρ)^-1/≤ N ≤  (1-α^*)^-'+1/ - '(1-ρ)^-'+1/ - '
    
    (1-α^*)^2 L^*(ρ)  + Θ((1-α^*) (1-ρ) N^-'/'+1)     if  N ≥ (1-α^*)^-'+1/ - '(1-ρ)^-'+1/ - ',
    
       = 
    G_E + Θ(N^-)     if  N ≤ (1-α^*)^-1/(1-ρ)^-1/
    
    G_E  + Θ((N/(1-α^*)(1-ρ))^-/ + 1)     if  
    (1-α^*)^-1/(1-ρ)^-1/≤ N ≤  (1-α^*)^-'+1/ - '(1-ρ)^-'+1/ - '
    
    G_E + Θ((1-α^*) (1-ρ) N^-'/'+1)     if  N ≥ (1-α^*)^-'+1/ - '(1-ρ)^-'+1/ - ',
    .


Using this, we can compute the market-entry threshold as follows: 

    (∞, , , , ) 
       = Θ(D^-1/ )     if  D ≥ (1-α^*) (1-ρ) 
    Θ(D^-+1/ (1-α^*) (1-ρ) )     if  
    (1-α^*)^/ - '(1-ρ)^/ - '≤ D ≤  (1-α^*) (1-ρ)  
    
    Θ((D/(1 - α^*)(1-ρ))^-'+1/')     if  D ≤ (1-α^*)^/ - '(1-ρ)^/ - '
       = Θ(D^-1/ )     if  D ≥ G_E^1/2 (1-ρ)^1/2
    Θ(D^-+1/ G_E^1/2 (1-ρ)^1/2)     if  
    G_E^/2( - ')  (1-ρ)^/2( - ')≤ D ≤  G_E^1/2 (1-ρ)^1/2
    Θ((D/G_E^1/2 (1-ρ)^1/2)^-'+1/')     if  D ≤ G_E^/2( - ')  (1-ρ)^/2( - ')
 







§ PROOFS FOR SECTION <REF>



In this section, we derive a deterministic equivalent and scaling laws for high-dimensional multi-objective linear regression. Before diving into this, we introduce notation, derive a basic decomposition, and give an outline for the remainder of the section.



  
Notation. Recall that (X_i, Y_i) denotes the labelled training dataset. Let the sample covariance be: 

    Σ̂ = 1/N∑_i=1^N X_i X_i^T.
 
We also consider the following reparameterization where we group together inputs according to how they are labelled. For j ∈{1,2}, we let X_1,j, …, X_N_j,j be the inputs labelled by _j. 
We let 

    Σ̂_1    = 1/N_1∑_i=1^N_1 X_i, 1 X_i,1^T 
    Σ̂_2    = 1/N_2∑_i=1^N_2 X_i, 2 X_i,2^T.

It is easy to see that Σ = αΣ̂_1 + (1-α) Σ̂_2. Moreover, 𝔼[Σ̂] = 𝔼[Σ̂_1] = 𝔼[Σ̂_2] = Σ. Furthermore, Σ̂_1 and Σ̂_2 are fully independent. We let ∼ denote asymptotic equivalence following <cit.>. 



  
Basic decomposition. A simple calculation shows that the solution and population-level loss of ridge regression takes the following form.  


Assume the notation above. Let 1 = β_1 β_1^T, let = (β_1 - β_2)(β_1 - β_2)^T, and let 1 = (β_1 - β_2) β_1^T. 
The learned predictor takes the form:

    β̂(α, λ, X) = (Σ̂ + λ I)^-1 (αΣ̂_1 β_1 + (1-α) Σ̂_2 β_2).

Moreover, it holds that: 

    L_1(β̂(α, λ, X))    = λ^2 ((Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-11)_(T1) + (1-α)^2 (Σ̂_2 (Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1Σ̂_2 )_(T2)
       + 2 λ (1-α) ·((Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1Σ̂_2 1)_(T3).



For 1 ≤ i ≤ N, let Y_i be the label for input X_i in the training dataset. For i ∈{1, 2} and 1 ≤ i ≤ N_i, let Y_i,j := ⟨β_i, X_i, j⟩ be the label for the input X_i, j according to β_i. 

For the first part, it follows from standard analyses of ridge regression that the learned predictor takes the form:

    β̂(α, λ, X)    = (Σ̂ + λ I)^-1(1/N∑_i=1^N X_i Y_i ) 
       = (Σ̂ + λ I)^-1(1/N∑_i=1^N X_i, 1 Y_i,1 + 1/N∑_i=1^N X_i, 2 Y_i,2) 
       = (Σ̂ + λ I)^-1(αΣ̂_1 β_1 + (1-α)Σ̂_2 β_2)

as desired. 

For the second part, we first observe that the difference β_1 - β̂(α, λ, X) takes the form:

    β_1 - β̂(α, λ, X)    = β_1 -  (Σ̂ + λ I)^-1(αΣ̂_1 β_1 + (1-α)Σ̂_2 β_2)  
       = (Σ̂ + λ I)^-1(λβ_1 + (1-α) Σ̂_2 (β_1 - β_2) ).

This means that:

    L_1(β̂(α, λ, X))
       = (β_1 - β̂(α, λ, X)^T Σ  (β_1 - β̂(α, λ, X) 
       =  (λβ_1 + (1-α) Σ̂_2 (β_1 - β_2) )^T (Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1(λβ_1 + (1-α) Σ̂_2 (β_1 - β_2) ) 
       = λ^2 ·β_1^T Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1β_1 + (1-α)^2 · (β_1 - β_2)^T Σ̂_2 Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1Σ̂_2 (β_1 - β_2)  
        + 2 λ (1-α) ·β_1^T Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1Σ̂_2 (β_1 - β_2) 
       = λ^2 ((Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-11)+ (1-α)^2 (Σ̂_2 (Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1Σ̂_2 ) 
        + 2 λ (1-α) ·((Σ̂ + λ I)^-1Σ (Σ̂ + λ I)^-1Σ̂_2 1).

as desired. 





  
Outline for the rest of this Appendix. The bulk of our analysis in this section boils down to analyzing Term 1 (T1), Term 2 (T2), and Term 3 (T3) in Claim <ref>. Our main technical tool is the random matrix machinery from Appendix <ref>. In Appendix <ref>, we provide useful sublemmas about intermediate deterministic equivalents that we apply to analyze Terms 2 and 3. We then analyze Term 1 (Appendix <ref>), Term 2 (Appendix <ref>), and Term 3 (Appendix <ref>), and use this to prove Lemma <ref> (Appendix <ref>). 

We apply the power scaling assumptions to derive a simpler expression for the deterministic equivalent  (Lemma <ref> in Appendix <ref>). We then apply Lemma <ref> to prove Theorem <ref> (Appendix <ref>), and we prove Corollary <ref> (Appendix <ref>). We also apply Lemma <ref> to prove Theorem <ref> (Appendix <ref>), and we prove Corollary <ref> (Appendix <ref>). We defer auxiliary calculations to Appendix <ref>. 





 §.§ Useful lemmas about intermediate deterministic equivalents


The results in this section consider Z_1 := α/1-αΣ̂_1 + /1-α I, which we introduce when conditioning on the randomness of Σ̂_1 when analyzing (T2) and (T3). We derive several properties of Z_1 and the effective regularizer κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2) below. 


The first set of lemmas relate the trace of various matrices involving κ_1 and Z_1 to deterministic quantities. A subtlety is that κ_1 and Z_1 are correlated, so we cannot directly apply Marčenko-Pastur, and instead we must indirectly analyze this quantity. 


Consider the setup of Lemma <ref>, and assume the notation above. Assume α < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I, and let κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2). Suppose that  B has bounded operator norm. 

    κ_1 ((Σ + κ_1 Z_1)^-1  B   ) ∼(1-α)  κ/λ((Σ + κ I)^-1 B )
  

 
By Claim <ref>, we know that: 

    (1-α) ((Σ̂ + λ I)^-1 B )    = ((Σ̂_2  + Z_1 )^-1 B ) 
       ∼_(A)κ_1 ((Σ  + κ_1 I )^-1 B ).

where (A) applies Lemma <ref> and Claim <ref>. 

Furthermore, by Lemma <ref>, it holds that: 
 
    λ((Σ̂ + λ I)^-1 B ) ∼κ((Σ + κ I )^-1 B ) .


 Putting this all together yields the desired result.





Consider the setup of Lemma <ref>, and assume the notation above.  Assume α < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I, and let κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2). Suppose that A and B have bounded operator norm. Then it holds that:
 
    (κ_1)^2 (((Σ + κ_1 Z_1 )^-1 A (Σ + κ_1 Z_1)^-1 B ) + E_1  )
        ∼(1-α)^2 κ^2/λ^2(((Σ + κ I )^-1 A (Σ + λ I )^-1 B ) + E_2 )

 where 
 
    κ   = κ(λ, N, Σ) 
    
      E_1    =    1/N (1-α)(A  (Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1)/1 - 1/N (1-α)( (Σ + κ_1 Z_1)^-1) Σ (Σ + κ_1 Z_1)^-1Σ·((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1  B ) 
    
      E_2    =  1/N(A Σ (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)·((Σ + κ I)^-1Σ (Σ + κ I)^-1  B )




By Claim <ref>, we know that: 

    (1-α)^2 ((Σ̂ + λ I)^-1 A (Σ̂ + λ I)^-1 B )    = ((Σ̂_2  + Z_1 )^-1 A (Σ̂_2  + Z_1 )^-1 B ) 
       ∼_(A)κ_1^2 ( ((Σ  + κ_1 Z_1 )^-1 A (Σ  + κ_1 Z_1  )^-1 B ) + E_1).

where (A) applies Lemma <ref> and Claim <ref>.  

Furthermore, by Lemma <ref>, it holds that: 
 
    λ^2((Σ̂ + λ I)^-1 A (Σ̂ + λ I)^-1 B ) ∼κ^2 (((Σ + κ I )^-1 A (Σ + κ I )^-1 B ) + E_2 ).


 Putting this all together yields the desired result.
    





Consider the setup of Lemma <ref>, and assume the notation above.  Assume α < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I, and let κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2). Then it holds that: 

    κ_1^2 ((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)/1 - 1/N(1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)∼(1-α)^2 κ^2/λ^2 (Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)
  


  
By Claim <ref>, we know that: 

    (1-α)^2 ((Σ̂ + λ I)^-1Σ(Σ̂ + λ I)^-1Σ) 
       =  ((Σ̂_2  + Z_1 )^-1Σ(Σ̂_2  + Z_1 )^-1Σ) 
       ∼_(A)κ_1^2 (1 + 1/N(1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)/1-1/N(1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)) ((Σ  + κ_1 Z_1 )^-1Σ(Σ  + κ_1 Z_1  )^-1Σ) 
       = κ_1^2 ((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)/1 - 1/N(1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)

where (A) applies Lemma <ref> and Claim <ref>.    


Furthermore, by Lemma <ref>, it holds that: 

    λ^2 ((Σ̂ + λ I)^-1Σ(Σ̂ + λ I)^-1Σ) 
       ∼_(A)κ^2 (1 + 1/N(Σ^2(Σ + κ I)^-2)/1-1/N(Σ^2(Σ + κ I)^-2) ((Σ + κ I )^-1Σ(Σ + κ I )^-1Σ) 
       =  κ^2 ((Σ^2 (Σ + κ I )^-2)/1-1/N(Σ^2(Σ + κ I)^-2) .

where (A) applies Lemma <ref>. 

 Putting this all together yields the desired result.  


Next, we relate the random effective regularizer κ_1 to the deterministic effective regularizer κ(, N, Σ). 


 Consider the setup of Lemma <ref>, and assume the notation above.  Assume α < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I, and let κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2). Let κ = κ(, N, Σ). Then, it holds that κ_1 ∼κ.   



Recall that κ_1 = κ(1,  N (1-α), Z_1^-1/2Σ Z_1^-1/2) is the unique value such that:

    1/κ_1 +  1/ N (1-α)((Z_1^-1/2Σ Z_1^-1/2 + κ_1 I)^-1 Z_1^-1/2Σ Z_1^-1/2) = 1.

We can write this as:

    1 +  κ_1/ N (1-α)((Σ + κ_1 Z_1)^-1Σ) = κ_1.

Now we apply Lemma <ref> to see that:

    κ_1 = 1 +  κ_1/ N (1-α)((Σ + κ_1 Z_1)^-1Σ) ∼ 1 +  1/ N (1-α)(1-α) κ/λ((Σ + κ I)^-1Σ).

We can write this to see that:

    κ_1 ∼κ/λ(λ/κ + 1/N((Σ + κ I)^-1Σ) ) = κ/λ.

This implies that λκ_1 ∼κ as desired. 




The proofs of these results relied on the following facts. 


Consider the setup of Lemma <ref>, and assume the notation above.  Assume α < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I. Then it holds that:

    (Σ̂ + λ I)^-1 = (1-α)^-1 (Σ̂_2 + Z_1)^-1.



We observe that:

    (1-α)  (Σ̂ +  I)^-1   = (1-α) (αΣ̂_1 + (1-α) Σ̂_2  +  I)^-1
       = (1-α) (1-α)^-1(Σ̂_2  + α/1-αΣ̂_1 + /1-α I)^-1
       = (Σ̂_2  + Z_1 )^-1,

where Z_1 = α/1-αΣ̂_1 + /1-α I.    



Consider the setup of Lemma <ref>, and assume the notation above.  Assume α < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I. Then it holds that Z_1 and Z_1^-1 both have bounded operator norm. 


 Since Σ̂_1 is PSD, we observe that: 

    Z_1_op = α/1-αΣ̂_1_op + /1-α.

The fact that Σ̂_1_op is bounded follows from the boundedness requirements from Assumption <ref>. This proves that Z_1_op is bounded. 

To see that Z_1^-1 is also bounded, note that:

    Z_1^-1_op≥1-α/






 §.§ Analysis of Term 1 (T1)


We show the following deterministic equivalent for term 1. This analysis is identical to the analysis of the deterministic equivalent for single-objective linear regression <cit.>, and we include it for completeness. 


Consider the setup of Lemma <ref>, and assume the notation above. Then it holds that: 
 
    λ^2 ((Σ̂ +  I)^-1Σ (Σ̂ +  I)^-11)     ∼κ^2/1 - 1/N(Σ^2 (Σ + κ I)^-2)·(Σ (Σ + κ I)^-21)
 


We apply Lemma <ref> to see that:

    λ^2 ((Σ̂ +  I)^-1Σ (Σ̂ +  I)^-11) 
       ∼κ^2 ((Σ + κ I)^-1Σ (Σ  + κ I)^-11) + 1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)
       = κ^2/1 - 1/N(Σ^2 (Σ + κ I)^-2)·(Σ (Σ + κ I)^-21),

as desired. 




 §.§ Analysis of Term 2 (T2)


We show the following deterministic equivalent for term 2. 


Consider the setup of Lemma <ref>, and assume the notation above. Then it holds that: 
 
    (1-α)^2 (Σ̂_2 (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 )  
       ∼(1-α)^2/1 - 1/N(Σ^2 (Σ + κ I)^-2)( (( Σ + κ I )^-1Σ( Σ + κ I  )^-1ΣΣ)) 
       + (1-α)1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)·((Σ)- 2 (1-α) ( (Σ+ κ I)^-1ΣΣ))
 


The key idea of the proof is to unwrap the randomness in layers. First, we condition on Σ̂_1 and replace the randomness Σ̂_2 with a deterministic equivalent where the effective regularizer κ_1 depends on Σ̂_1 (Lemma <ref>). At this stage, we unfortunately cannot directly deal with the randomness Σ̂_1 with deterministic equivalence due to the presence of terms κ_1 which depend on Σ̂_1, and we instead apply the sublemmas from the previous section. 

The following lemma replaces the randomness Σ̂_2 with a deterministic equivalent. 


Consider the setup of Lemma <ref>, and assume the notation above. Assume that < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I, and let κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2). Then it holds that:
 
    (1-α)^2 ( Σ̂_2 (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 ) 
       ∼(( Σ + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1  )^-1ΣΣ)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)
       + 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)·((Σ) - 2 (Σ (Σ + κ_1 Z_1)^-1Σ) ).



By Claim <ref> we have that:

    (1-α)^2 ( Σ̂_2 (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 )    = (Σ̂_2 (Σ̂_2  + Z_1 )^-1Σ(Σ̂_2  + Z_1 )^-1Σ̂_2 ) 
       ∼_(A)(Σ (Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ) + E
       = ((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1ΣΣ) + E

where (A) follows from Lemma <ref> and Claim <ref>, and E is defined such that 

    E    :=1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)/1 - 1/N (1-α)(Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)· (κ_1)^2 (Z_1 ( Σ  + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1 )^-1 Z_1 ).

and κ_1 = κ(λ, N(1-α), Z_1^-1/2Σ Z_1^-1/2).

Note that:

    (κ_1)^2 (Z_1 ( Σ  + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1 )^-1 Z_1 ) 
       = ((κ_1 Z_1) ( Σ  + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1 )^-1 (κ_1 Z_1) ) 
       =  (( I - Σ (Σ + κ_1 Z_1)^-1) Σ( I - Σ  (Σ + κ_1 Z_1)^-1)^T ) 
       = (Σ) - 2 ((Σ + κ_1 Z_1)^-1ΣΣ) + ((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1ΣΣ).


Note that:

    ((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1ΣΣ) 
       + ((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1ΣΣ) ·1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)/1 - 1/N (1-α)(Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)
       =   ((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1ΣΣ)/1 - 1/N (1-α)(Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ)




Now we are ready to prove Lemma <ref>.

The statement follows trivially if α = 1. By Lemma <ref>, it holds that:
 
    (1-α)^2 ( Σ̂_2 (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 ) 
       ∼(( Σ + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1  )^-1ΣΣ)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )
       + 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·((Σ)- 2 ((Σ + κ_1 Z_1)^-1ΣΣ)) 
       ∼_(A) (1-α)^2 ( (( Σ + κ I )^-1Σ( Σ + κ I  )^-1ΣΣ)) 
       +  1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)· (1-α)^2 ·((Σ + κ I)^-1Σ (Σ + κ I)^-1ΣΣ) 
       + 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·((Σ)- 2(1-α) ( (Σ+ κ I)^-1ΣΣ)) 
       = (1-α)^2/1 - 1/N(Σ^2 (Σ + κ I)^-2)( (( Σ + κ I )^-1Σ( Σ + κ I  )^-1ΣΣ)) 
       + 1/N (1-α)(Σ^2 (Σ + κ_1 Z_1)^-2)/1 - 1/N (1-α)(Σ^2 (Σ + κ_1 Z_1)^-2)·((Σ)- 2(1-α) ( (Σ+ κ I)^-1ΣΣ)) 
       ∼ _(B)(1-α)^2/1 - 1/N(Σ^2 (Σ + κ I)^-2)( (( Σ + κ I )^-1Σ( Σ + κ I  )^-1ΣΣ)) 
       + (1-α) 1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)·((Σ)- 2(1-α) ( (Σ+ κ I)^-1ΣΣ))
 
 where (A) applies Lemma <ref>, Lemma <ref>, and (B) uses Lemma <ref> and Lemma <ref>. 






 §.§ Analysis of Term 3 (T3)



We show the following deterministic equivalent for term 3. 



Consider the setup of Lemma <ref> and assume the notation above. Let 1 =  (β_1 - β_2) β_1^T, and let κ = κ(λ, N, Σ). Then it holds that: 
 
    2 λ (1-α) ( (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_21)  
       ∼2 (1-α) κ/1 - 1/N(Σ^2 (Σ + κ I)^-2)((Σ + κ I)^-1Σ (Σ + κ I)^-1Σ1) 
       - 2 (1-α) 1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)·κ(  (Σ + κ I)^-1Σ1)
 


The analysis follows a similar structure to the analysis of (T2); we similarly unwrap the randomness in layers.  



Consider the setup of Lemma <ref> and assume the notation above. Assume < 1. Let Z_1 = α/1-αΣ̂_1 + /1-α I, and let κ_1 = κ(1, N(1-α), Z_1^-1/2Σ Z_1^-1/2). Then it holds that:
 
    2 λ (1-α)^2 ( (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 1) 
       ∼ 2 λκ_1/(1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ1)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ(Σ + κ_1 Z_1)^-1Σ )
       - 2 λκ_1/(1-α)·1/N (1-α)(Σ^2 (Σ + κ_1 Z_1)^-2)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ(Σ + κ_1 Z_1)^-1Σ )·(Σ(Σ + κ_1 Z_1)^-1Σ1).



By Claim <ref> we have that:

    2 λ (1-α) ( (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 1)    = 2 λ/(1-α)( (Σ̂_2  + Z_1 )^-1Σ(Σ̂_2  + Z_1 )^-1Σ̂_2 1) 
       ∼_(A) 2 λ/(1-α)(κ_1 ( (Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ1) - E )

where (A) follows from Lemma <ref> and Claim <ref>, and E is defined such that 

    E    :=1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )· (κ_1)^2 (( Σ  + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1 )^-1 Z_1  1).

and κ_1 = κ(λ, N(1-α), Z_1^-1/2Σ Z_1^-1/2). 

Note that:

    (κ_1)^2 ( ( Σ  + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1 )^-1 Z_1 1) 
       = κ_1 (( Σ  + κ_1 Z_1 )^-1Σ( Σ + κ_1 Z_1 )^-1 (κ_1 Z_1)  1) 
       =  κ_1 ( (Σ + κ_1 Z_1)^-1Σ( I - (Σ + κ_1 Z_1)^-1Σ) 1) 
       =  κ_1 (  (Σ + κ_1 Z_1)^-1Σ1) - κ_1 ((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1Σ1)


Moreover, note that:

    2 λκ_1 /(1-α)( (Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ1) 
       + 2 λ/(1-α)·1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·κ_1 ((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1Σ1) 
       = 2 λ/(1-α)((Σ + κ_1Z_1)^-1Σ (Σ + κ_1Z_1)^-1Σ1)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·κ_1.





Now we are ready to prove Lemma <ref>.


The statement follows trivially if α = 1. 
By Lemma <ref>, it holds that:
 
    2 λ (1-α)^2 ( (Σ̂ +  I)^-1Σ (Σ̂ +  I)^-1Σ̂_2 1) 
       ∼ 2 λκ_1/(1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ1)/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )
       - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·  2 λκ_1/(1-α)((Σ + κ_1 Z_1)^-1Σ1) 
       ∼_(A) 2 (1-α) κ((Σ + κ I)^-1Σ (Σ + κ I)^-1Σ1) 
       + 2 (1-α) κ1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)((Σ + κ I)^-1Σ (Σ + κ I)^-1Σ1) 
       - 2 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·κ(  (Σ + κ I)^-1Σ1) 
       = 2 (1-α) κ/1 - 1/N(Σ^2 (Σ + κ I)^-2)((Σ + κ I)^-1Σ (Σ + κ I)^-1Σ1) 
       - 2 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )/1 - 1/N (1-α)((Σ + κ_1 Z_1)^-1Σ (Σ + κ_1 Z_1)^-1Σ )·κ(  (Σ + κ I)^-1Σ1) 
       ∼_(B) 2 (1-α) κ/1 - 1/N(Σ^2 (Σ + κ I)^-2)((Σ + κ I)^-1Σ (Σ + κ I)^-1Σ1) 
       - 2 (1-α) 1/N(Σ^2 (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)·κ(  (Σ + κ I)^-1Σ1)
 
 where (A) applies Lemma <ref>, Lemma <ref>, and Lemma <ref>, and (B) uses Lemma <ref> and Lemma <ref>. 





 §.§ Proof of Lemma <ref>


Lemma <ref> follows from the sublemmas in this section.

We apply Claim <ref> to decompose the error in terms (T1), (T2), and (T3). We replace these terms with deterministic equivalents using Lemma <ref>, Lemma <ref>, and Lemma <ref>. The statement follows from adding these terms. 





 §.§ Reformulation of Lemma <ref> using assumptions from Section <ref>



Under the assumptions from Section <ref>, we show the following: 


Suppose that power scaling holds for the eigenvalues and alignment coefficients with scaling γ, δ > 0 and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Suppose that ∈ (0,1), and N ≥ 1. Let L_1^ := L_1^(β_1, β_2, , , N, α) be the deterministic equivalent from Lemma <ref>. Let κ = κ(λ, N, Σ) from Definition <ref>. Let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)]. Then it holds that:
  
    Q ·𝔼_[L_1^]    = κ^2 (1 - 2(1-α)^2 (1-ρ)) ∑_i=1^P i^-δ -1- γ/(i^-1-γ + κ)^2 + (1-α)^2 L^*(ρ) 
       + 2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + 2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ,

  where Q = 1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2. 



Before proving Lemma <ref>, we prove a number of sublemmas where we analyze each of the terms in Lemma <ref> using the assumptions from Section <ref>. In the proofs in this section, we use the notation F ≈ F' to denote that F = Θ(F') where the Θ is allowed to hide dependence on the scaling exponents γ and δ. Moreover let Σ = V Λ V^T be the eigendecomposition of Σ, where Λ is a diagonal matrix consisting of the eigenvalues. 




Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>. Let ν = min(2(1+γ), γ + δ). Then it holds that:

    𝔼_[T_1] := κ^2 ·(ΣΣ_κ^-2𝔼_[1])= κ^2  ∑_i=1^P i^-δ-1-γ/(i^-1-γ + κ)^2 .



 Observe that:

    (ΣΣ_κ^-2𝔼_[1])    = (Λ (Λ + κ I)^-2𝔼_[V^Tβ_1 β_1^T V])  
       = ∑_i=1^P i^-1-γ/(i^-1-γ + κ)^2·𝔼_[⟨β_1, v_i⟩^2]   
       = ∑_i=1^P i^-δ-1-γ/(i^-1-γ + κ)^2






Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>. Then it holds that:

    𝔼_[T_2] := (1-α)^2 ( (Σ_κ^-2Σ^3 𝔼_[] )) = 2 (1-α)^2 (1-ρ) ∑_i=1^P i^-δ - 3(1+γ)/(i^-1-γ + κ)^2.



First, we observe that 

    𝔼_[⟨β_1 - β_2, v_i⟩^2] = 𝔼_[⟨β_1 , v_i⟩^2] + 𝔼_[⟨β_2, v_i⟩^2] - 2 𝔼_[⟨β_1 , v_i⟩⟨β_2, v_i⟩]  = i^-δ + i^-δ - 2 ρ i^-δ = 2(1-ρ) i^-δ.
 It is easy to see that:

    (Σ_κ^-2Σ^3 𝔼_[] )    = (Λ^3 (Λ + κ I)^-2𝔼_[V^T (β_1 - β_2) (β_1 - β_2)^T V])  
       = ∑_i=1^P i^-3(1+γ)/(i^-1-γ + κ)^2·𝔼_[⟨β_1 - β_2, v_i⟩^2]   
       = 2 (1-ρ) ∑_i=1^P i^-δ - 3(1+γ)/(i^-1-γ + κ)^2.
 





Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>. Then it holds that:

    𝔼_[T_3] :=  2 (1-α) κ·(Σ_κ^-2Σ^2 1) =  2(1-α) κ (1-ρ) ∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)^2.



First, we observe that 

    𝔼_[⟨β_1 - β_2, v_i⟩⟨β_1, v_i⟩  ] = 𝔼_[⟨β_1 , v_i⟩^2] - 𝔼_[⟨β_1 , v_i⟩⟨β_2, v_i⟩]  = i^-δ - ρ i^-δ = (1-ρ) i^-δ.

Observe that:

    (Σ_κ^-2Σ^2 1)    = (Λ^2 (Λ + κ I)^-2𝔼_[V^T (β_1 - β_2) β_1^T V])  
       = ∑_i=1^P i^-2(1+γ)/(i^-1-γ + κ)^2·𝔼_[⟨β_1 - β_2, v_i⟩⟨β_1, v_i⟩ ]   
       = (1-ρ) ∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)^2.

This means that:

    𝔼_[T_3]    = 2(1-α) κ (1-ρ) ∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)^2.







Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>. Then it holds that:

    |𝔼_[T_4]|    := 2 κ (1-α) 1/N(Σ^2 Σ_κ ^-2) ·(Σ_κ^-1Σ𝔼_[1] ) 
       = 2 κ (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) (∑_i=1^P i^-δ-1-γ/i^-1-γ + κ)




First, we observe that 

    𝔼_[⟨β_1 - β_2, v_i⟩⟨β_1, v_i⟩ ] = 𝔼_[⟨β_1 , v_i⟩^2] - 𝔼_[⟨β_1 , v_i⟩⟨β_2, v_i⟩]  = i^-δ + - ρ i^-δ = (1-ρ) i^-δ.

Observe that:

    (Σ_κ^-1Σ𝔼_[1] )    = (Λ (Λ + κ I)^-1𝔼_[V^T (β_1 - β_2) β_1^T V])  
       = ∑_i=1^P i^-1-γ/i^-1-γ + κ·𝔼_[⟨β_1 - β_2, v_i⟩⟨β_1, v_i⟩]   
       = (1-ρ) ∑_i=1^P i^-δ-1-γ/i^-1-γ + κ.


Now, apply Lemma <ref>, we see that:

    |𝔼_[T_4]|    := 2 κ (1-α) 1/N(Σ^2 Σ_κ ^-2) ·(Σ_κ^-1Σ1) 
       =_(A) 2 κ (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) (∑_i=1^P i^-δ-1-γ/i^-1-γ + κ)

where (A) follows from Lemma <ref>.




Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>, and similarly let

    𝔼_[T_5]    := (1-α) 1/N(Σ^2 Σ_κ ^-2) ·((Σ𝔼_[]  )- 2 (1-α) ( Σ_κ^-1Σ^2 𝔼_[]   ) ) 
       = 2 (1-α) (1-ρ) 1/N( ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·(∑_i=1^P i^-δ - 1-γ - 2 (1-α) ·∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)).




First, we observe that 

    𝔼_[⟨β_1 - β_2, v_i⟩^2] = 𝔼_[⟨β_1 , v_i⟩^2] + 𝔼_[⟨β_2, v_i⟩^2] - 2 𝔼_[⟨β_1 , v_i⟩⟨β_2, v_i⟩]  = i^-δ + i^-δ - 2 ρ i^-δ = 2(1-ρ) i^-δ.


Now, observe that:

    𝔼_[T_5]    := (1-α) 1/N(Σ^2 Σ_κ ^-2) ·((Σ𝔼_[]  )- 2 (1-α) ( Σ_κ^-1Σ^2 𝔼_[]  ) ) 
       = (1-α) 1/N(Σ^2 Σ_κ ^-2) ·((Λ𝔼_[V^T (β_1 - β_2) (β_1 - β_2)^T V]  ) ) 
       - (1-α) 1/N(Σ^2 Σ_κ ^-2) ·(2 (1-α) ( (Λ + κ I)^-1Λ^2 𝔼_[V^T (β_1 - β_2) (β_1 - β_2)^T V]  ) ) 
       = (1-α) 1/N(Σ^2 Σ_κ ^-2) ·(∑_i=1^P i^-1-γ⟨β_1 - β_2, v_i⟩^2 - 2 (1-α) ·∑_i=1^P i^-2-2γ/(i^-1-γ + κ)⟨β_1 - β_2, v_i⟩^2 ) 
       = 2 (1-α) (1-ρ) 1/N(Σ^2 Σ_κ ^-2) ·(∑_i=1^P i^-δ - 1-γ - 2 (1-α) ·∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)) 
       =_(A) 2 (1-α) (1-ρ) 1/N( ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·(∑_i=1^P i^-δ - 1-γ - 2 (1-α) ·∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)).

where (A) uses Lemma <ref>.




The proofs of these sublemmas use the following fact.


  Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>. Then it holds that:
  
    (Σ^2 (Σ + κ I)^-2) = ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2.



We see that:

    (1-α) 1/N(Σ^2 Σ_κ ^-2)    = (1-α) 1/N(V Λ^2 (Λ + κ I)^-2 V^T) 
       = (1-α) 1/N(Λ^2 (Λ + κ I)^-2) 
       = ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2.




Now, we are ready to prove Lemma <ref>.

By Lemma <ref>, we know: 

    Q = 1 - 1/N(Σ^2 (Σ + κ I)^-2)= 1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2.

Moreover, we have that: 
     
    Q ·𝔼_[L_1^]    =_(A)𝔼_[T_1 + T_2 + T_3 + T_4 + T_5] 
       =_(B)κ^2  ∑_i=1^P i^-δ - 1- γ/(i^-1-γ + κ)^2 + 2 (1-α)^2 (1-ρ) ∑_i=1^P i^-δ - 3 (1+γ)/(i^-1-γ + κ)^2
       + 2κ (1-ρ) (1-α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       - 2κ (1-ρ)  (1-α) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2)   (∑_i=1^P i^-δ - 1-γ/i^-1-γ + κ) 
       + 2 (1-α) (1-ρ) 1/N( ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·(∑_i=1^P i^-δ - 1-γ - 2 (1-α) ·∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)).

  where (A) follows from Lemma <ref>, and (B) follows from Lemmas <ref>-<ref>. 


By Claim <ref>, we know that:

    L^*(ρ) = 2 (1-ρ) ∑_i=1^P i^-δ-1-γ= 2 (1-ρ) ∑_i=1^P i^-δ-3(1+γ)/(i^-1-γ)^2.

This means that:

    L^*(ρ) - 2 (1-ρ) ∑_i=1^P i^-δ - 3 (1+γ)/(i^-1-γ + κ)^2
       =  2 (1-ρ) ∑_i=1^P (i^-δ-3(1+γ)/(i^-1-γ)^2 - i^-δ - 3 (1+γ)/(i^-1-γ + κ)^2) 
       = 2 (1-ρ) ∑_i=1^P (i^-δ-3(1+γ)· ((i^-1-γ + κ)^2 - (i^-1-γ)^2)/(i^-1-γ)^2 · (i^-1-γ + κ)^2)  
       = 2 κ^2 (1-ρ) ∑_i=1^P (i^-δ-3(1+γ)/(i^-1-γ)^2 · (i^-1-γ + κ)^2)  + 4 κ (1-ρ) ∑_i=1^P (i^-δ-3(1+γ)· i^-1-γ/(i^-1-γ)^2 · (i^-1-γ + κ)^2) 
       = 2 κ^2 (1-ρ) ∑_i=1^P (i^-δ-1-γ/(i^-1-γ + κ)^2)  + 4 κ (1-ρ) ∑_i=1^P (i^-δ-2(1+γ)/(i^-1-γ + κ)^2)



Applying this and some other algebraic manipulations, we obtain that:     
  
    Q · L_1^   = κ^2 (1 - 2(1-α)^2 (1-ρ)) ∑_i=1^P i^-δ - 1-γ/(i^-1-γ + κ)^2 + (1-α)^2 L^*(ρ) 
       + 2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       - 2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2)   (∑_i=1^P i^-δ - 1-γ - ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ) 
       + 2 (1-α) (1-ρ) 1/N( ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·(∑_i=1^P i^-δ - 1-γ - 2 (1-α) ·∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)) 
       = κ^2 (1 - 2(1-α)^2 (1-ρ)) ∑_i=1^P i^-δ - γ/(i^-1-γ + κ)^2 + (1-α)^2 L^*(ρ) 
       + 2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + 2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ.







 §.§ Proof of Theorem <ref>


We now prove Theorem <ref>. In the proof, we again use the notation F ≈ F' to denote F = Θ(F'). The main ingredient is Lemma <ref>, coupled with the auxiliary calculations in Appendix <ref>. 


The proof boils down to three steps: (1) obtaining an exact expression, (2) obtaining an up-to-constants asymptotic expression in terms of κ and Q, and (3) substituting in κ and Q.



  
Step 1: Exact expression.
We apply Lemma <ref> to see that: 
  
    Q · L_1^   = κ^2 (1 - 2(1-α)^2 (1-ρ)) ∑_i=1^P i^-δ - 1-γ/(i^-1-γ + κ)^2 + (1-α)^2 L^*(ρ) 
       + 2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + 2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ,

where Q = 1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2, where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)], and where κ = κ(Σ, N, λ) as defined in Definition <ref>.



  
Step 2: Asymptotic expression in terms of κ and Q. We show that 
    Q · L_1^≈κ^/1+γ + (1-α)^2 (1-ρ) + 
    (1-α) (1-ρ) κ^-1/1+γ/N.


We analyze this expression term-by-term and repeatedly apply Lemma <ref>. We see that:

    κ^2 (1 - 2(1-α)^2 (1-ρ)) ∑_i=1^P i^-δ - 1- γ/(i^-1-γ + κ)^2≈_(A)κ^/1+γ (1 - 2(1-α)^2 (1-ρ)) ≈_(B)κ^/1+γ,

where (A) uses Lemma <ref> and (B) uses that α≥ 0.5. Moreover, we observe that:

    (1-α)^2 L^*(ρ) ≈_(C) (1-α)^2 (1-ρ),

where (C) uses Claim <ref>. Moreover, we see that:

    2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2   ≈_(D) (1-α) (1-ρ) (1 - 2 (1-α))  max( κ, κ^δ + γ/1+γ) 
       =_(E) O((1-α) √(1-ρ)max( κ, κ^δ + γ/2(1+γ))) 
       = O( √((1-α)^2 (1-ρ) ·κ^min(2(1+γ), γ + δ)/1+γ)) 
       =_(F) O( κ^min(2(1+γ), γ + δ)/1+γ + (1-α)^2 (1-ρ) ) 
       = O( κ^/1+γ + (1-α)^2 (1-ρ) )

where (D) uses Lemma <ref>, (E) uses that 1-ρ≤ 1 and that κ = O(1) (which follows from Lemma <ref> and the assumption that λ∈ (0,1)) and (F) follows from AM-GM. Finally, observe that: 

    2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       ≈ (1 - 2(1-α)) · (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       ≈_(G) (1 - 2(1-α)) · 
    (1-α) (1-ρ) κ^-1/1+γ/N

where (G) uses Lemma <ref> twice. 

Putting this all together, we see that:

    Q · L_1^≈κ^/1+γ + (1-α)^2 (1-ρ) + (1 - 2(1-α)) · 
    (1-α) (1-ρ) κ^-1/1+γ/N.


We split into two cases based on α. When α≥ 0.75, we observe that 

    (1 - 2(1-α)) · 
    (1-α) (1-ρ) κ^-1/1+γ/N≈ (1-α) (1-ρ) κ^-1/1+γ/N,
 and when α∈ [0.5, 0.75], we observe that 

    (1 - 2(1-α)) · 
    (1-α) (1-ρ) κ^-1/1+γ/N = O( (1-α) (1-ρ) κ^-1/1+γ/N)
 and 

    (1-α)^2 (1-ρ) ≈_(H) (1-α) (1-ρ) κ^-1/1+γ/N

where (H) follows from the fact that κ = Ω(N^-1-γ) by Lemma <ref>. Altogether, this implies that:

    Q · L_1^≈κ^/1+γ + (1-α)^2 (1-ρ) + 
    (1-α) (1-ρ) κ^-1/1+γ/N,

as desired.



  
Step 2: Substitute in κ and Q. Finally, we apply Lemma <ref> to see that:

    Q^-1 = (1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2)^-1 = Θ(1).

We apply Lemma <ref> to see that 

    κ = κ(Σ, N, Σ)  = max(N^-1-γ, λ).

Plugging this into the expression derived in Step 2, we obtain the desired expression. 







 §.§  Proof of Corollary <ref>


We prove Corollary <ref> using Theorem <ref>.

We apply Theorem <ref> to see that:

    𝔼_[L_1^] = Θ( max(λ^/1+γ, N^-)_finite data error + (1-α)^2 · (1 - ρ)_mixture error +   (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ)
    _overfitting error).

We split into three cases: N ≤ (1-α)^-1/(1-ρ)^-1/, (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-2+/ (1-ρ)^-1/, and N ≥ (1-α)^-2+/ (1-ρ)^-1/. 



 

  
Case 1: N ≤ (1-α)^-1/(1-ρ)^-1/. We observe that the finite data error dominates regardless of . This is because the condition implies that 
 
    max(λ^/1+γ, N^-) ≥ (1-α)(1-ρ),

 which dominates both the mixture error and the overfitting error. 



  
Case 2: (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-2+/ (1-ρ)^-1/.  We show that the finite error term and overfitting error dominate. Let Ñ = min(λ^-1/1+γ, N). We can bound the sum of the finite data error and the overfitting error as:
 
    max(λ^/1+γ, N^-) + (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ)    =  Ñ^- + (1-α) (1-ρ) Ñ/N.

 Taking a derivative (and verifying the second order condition), we see that this expression is minimized when:
 
    ·Ñ^- - 1 = (1-α) (1-ρ)/N

 which solves to:
 
    Ñ = Θ(((1-α) (1-ρ)/N)^-1/1+).

 The lower bound on N guarantees that:
 
    Ñ = Θ(((1-α) (1-ρ)/N)^-1/1+) = O (((1-α)^1 + 1/ (1-ρ)^1 + 1/)^-1/1+)= O ((1-α)^-1/ (1-ρ)^-1/) = O(N)

 which ensures that Ñ can be achieved by some choice of λ. In particular, we can take = Θ(((1-α) (1-ρ)/N)^1+γ/ + 1). 

The resulting sum of the finite error and the overfitting error is:
 
    max(λ^/1+γ, N^-) + (1-α) (
     min(λ^-1/1+γ, N)/N) = Θ(((1-α) (1-ρ)/N)^/ + 1).


The upper bound on N guarantees that this dominates the mixture error:

    Θ(((1-α) (1-ρ)/N)^/ + 1) = Ω(((1-α)^1 + 2+/ (1-ρ)^1 + 1/)^/ + 1) = Ω((1-α)^2 (1-ρ))

as desired. 



  
Case 3: N ≥ (1-α)^-2+/ (1-ρ)^-1/.
 We show that the mixture and the overfitting error terms dominate. First, we observe that the sum of the mixture error and the finite data error is:
 
    (1-α)^2 (1-ρ) + (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ) = Θ( (1-α)(1-ρ) (1 - α + min(λ^-1/1+γ, N)/N) ).

This is minimized by taking = Θ((N(1-α))^-1-γ), which yields Θ((1-α)^2 (1-ρ)).

The upper bound on N and the setting of  guarantees that this term dominates the finite data error: 
 
    max(λ^/1+γ, N^-) = O((N(1-α))^-) ≤ O((1-α)^- (1-α)^2 +  (1-ρ) ) = O((1-α)^2 (1-ρ),

 as desired. 

  




 §.§ Proof of Theorem <ref>


We prove Theorem <ref>. 


Like the proof of Theorem <ref>, the proof boils down to three steps: (1) obtaining an exact expression, (2) obtaining an up-to-constants asymptotic expression in terms of κ, and (3) substituting in κ.



  
Step 1: Exact expression.
We first apply Lemma <ref> to obtain the precise loss:

    Q ·𝔼_[L_1^*(β_1, β_2, , λ_E, N, α_E)]     =κ^2 (1 - 2(1-α)^2 (1-ρ)) ∑_i=1^P i^-δ -1- γ/(i^-1-γ + κ)^2 + (1-α)^2 L^*(ρ) 
       +  2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + 2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ,

  where Q = 1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2 and where κ = κ(Σ, N, λ) as defined in Definition <ref>. 
  This can be written as: 

    𝔼_[L_1^*(β_1, β_2, , λ_E, N, α_E)] - (1-α)^2 L^*(ρ)   
       =Q^-1·κ^2 (1 - 2(1-α)^2 (1-ρ))  ∑_i=1^P i^-δ - 1- γ/(i^-1-γ   + κ)^2
       + Q^-1· 2κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1· 2 (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       + 1-Q/Q (1-α)^2 L^*(ρ).
  



  
Step 2: Asymptotic expression in terms of κ.
 We use the notation F ≈ F' to denote that F = Θ(F'). We obtain:
 
    𝔼_[L_1^*(β_1, β_2, , λ_E, N, α_E)] - (1-α)^2 L^*(ρ)   
       ≈_(A)κ^2 (1 - 2(1-α)^2 (1-ρ))  ∑_i=1^P i^-δ -1- γ/(i^-1-γ   + κ)^2
       + κ (1-ρ) (1-α) (1 - 2 (1-α)) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2(1-α))  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       + (1-Q) (1-α)^2 L^*(ρ) 
       ≈_(B)κ^2 ∑_i=1^P i^-δ - 1- γ/(i^-1-γ   + κ)^2 + κ (1-ρ) (1-α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       + (1-α)^2 L^*(ρ) ·1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2).
  
  where (A) uses that Q^-1 is a constant by Lemma <ref> and (B) uses that α≥ 0.75 and the definition of Q. Now, using the bounds from Lemma <ref>, and the bound from Claim <ref>, we obtain: 

    𝔼_[L_1^*(β_1, β_2, , λ_E, N, α_E)] - (1-α)^2 L^*(ρ)  
       ≈κ^min(2(1+γ), γ + δ)/1+γ  + (1-ρ) (1-α) max( κ, κ^γ + δ/1+γ) + (1-α) (1-ρ) κ^-1/1+γ/N  + κ^-1/1+γ/N (1-α)^2 (1-ρ) 
       ≈κ^/1+γ  + (1-ρ) (1-α) κ^'/1+γ + (1-α) (1-ρ) κ^-1/1+γ/N.
  



  
Step 3: Substituting in κ. Finally, we apply Lemma <ref> to see that 

    κ = κ(Σ, N, Σ)  = max(N^-1-γ, λ).
 Plugging this into the expression derived in Step 2, we obtain the desired expression. 






 §.§ Proof of Corollary <ref>


We prove Corollary <ref> using Theorem <ref>.

We apply Theorem <ref> to see that:

    𝔼_[L_1^ - L_1(β(α, 0))]  
       =  Θ( max(λ^/1+γ, N^-)_finite data error + (1-ρ) (1-α) max(λ^'/1+γ, N^-')_mixture finite data error +   (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ)
    _overfitting error).


We split into three cases: N ≤ (1-α)^-1/(1-ρ)^-1/, (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-'+1/ - '(1-ρ)^-'+1/ - ', and N ≥ (1-α)^-'+1/ - '(1-ρ)^-'+1/ - '. 



 

  
Case 1: N ≤ (1-α)^-1/(1-ρ)^-1/. We observe that the finite data error dominates regardless of . This is because the condition implies that 
 
    max(λ^/1+γ, N^-) ≥ (1-α)(1-ρ),

 which dominates both the mixture finite data error and the overfitting error. 



  
Case 2: (1-α)^-1/(1-ρ)^-1/≤ N ≤  (1-α)^-'+1/ - '(1-ρ)^-'+1/ - '.  We show that the finite error term and overfitting error dominate. Let Ñ = min(λ^-1/1+γ, N). We can bound the sum of the finite data error and the overfitting error as:
 
    max(λ^/1+γ, N^-) + (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ)    =  Ñ^- + (1-α) (1-ρ) Ñ/N.

 Taking a derivative (and verifying the second order condition), we see that this expression is minimized when:
 
    ·Ñ^- - 1 = (1-α) (1-ρ)/N

 which solves to:
 
    Ñ = Θ(((1-α) (1-ρ)/N)^-1/1+).

 The lower bound on N guarantees that:
 
    Ñ = Θ(((1-α) (1-ρ)/N)^-1/1+) = O (((1-α)^1 + 1/ (1-ρ)^1 + 1/)^-1/1+)= O ((1-α)^-1/ (1-ρ)^-1/) = O(N)

 which ensures that Ñ can be achieved by some choice of λ. In particular, we can take = Θ(((1-α) (1-ρ)/N)^1+γ/ + 1). 

The resulting sum of the finite error and the overfitting error is:
 
    max(λ^/1+γ, N^-) + (1-α) (
     min(λ^-1/1+γ, N)/N) = Θ(((1-α) (1-ρ)/N)^/ + 1).


The upper bound on N and the choice of λ guarantees that this dominates the mixture finite data error, as shown below: 

    (1-ρ) (1-α) max(λ^'/1+γ, N^-') 
       = Θ((1-ρ) (1-α) ((1-α) (1-ρ)/N)^'/ + 1)
       = Θ(((1-α) (1-ρ)/N)^/ + 1 (1-α) (1-ρ) ((1-α) (1-ρ)/N)^' - / + 1) 
       = Θ(((1-α) (1-ρ)/N)^/ + 1 (1-α)^'+1/ + 1 (1-ρ)^'+1/ + 1 N^ - '/ + 1) 
       = O(((1-α) (1-ρ)/N)^/ + 1 (1-α)^'+1/ + 1 (1-ρ)^'+1/ + 1 (1-α)^-'+1/ + 1 (1-ρ)^-'+1/ + 1) 
       =  O(((1-α) (1-ρ)/N)^/ + 1)

as desired. 




  
Case 3: N ≥ (1-α)^-'+1/ - '(1-ρ)^-'+1/ - '.
 We show that the mixture finite data error and the overfitting error terms dominate. First, we observe that the sum of the mixture error and the finite data error is:
 
    (1-ρ) (1-α) max(λ^'/1+γ, N^-') + (1-α) (
     min(λ^-1/1+γ, N)/N) 
    (1-ρ) 
       = Θ( (1-α)(1-ρ) (λ^'/1+γ + min(λ^-1/1+γ, N)/N) )

This is minimized by taking = Θ(N^-1+γ/'+1), which yields Θ((1-α) (1-ρ) N^-'/'+1).

The upper bound on N and the setting of  guarantees that this term dominates the finite data error: 

    max(λ^/1+γ, N^-)    = Θ(N^-/'+1) 
       ≤Θ((1-α) (1-ρ) N^-'/'+1 (1-α)^-1 (1-ρ)^-1 N^- - '/'+1) 
       = O((1-α) (1-ρ) N^-'/'+1 (1-α)^-1 (1-ρ)^-1 (1-α) (1-ρ) ) 
       = O((1-α) (1-ρ) N^-'/'+1)

as desired. 
  




 §.§ Auxiliary calculations under power scaling assumptions


We show the following auxiliary calculations which we use when analyzing the terms in Lemma <ref> under the power scaling assumptions. Throughout this section, we again use the notation F ≈ F' to denote that F = Θ(F').



Suppose that power-law scaling  holds for eigenvalues and alignment coefficients with scaling exponents γ, δ >0 and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Let κ = κ(λ, N, Σ) be defined according to Definition <ref>. Then the following holds:

    ∑_i=1^P i^-δ -1 - γ/(i^-1-γ +  κ)^2   ≈κ^-2κ^min(2(1+γ), γ + δ)/1+γ
    ∑_i=1^P i^-δ - 3(1+γ)/(i^-1-γ +  κ)^2   ≈ 1 
    ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ   ≈ 1 
    ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ + κ)^2   ≈max(1, κ^δ - 1/1+γ) 
    ∑_i=1^P i^-δ - 1 - γ/i^-1-γ + κ   ≈max(1, κ^δ - 1/1+γ) 
    ∑_i=1^P i^- 2 - 2 γ/(i^-1-γ + κ)^2   ≈κ^-1/1+γ
    ∑_i=1^P i^- 1 - γ/i^-1-γ + κ   ≈κ^-1/1+γ
    ∑_i=1^P i^-1 - γ/(i^-1-γ +  κ)^2   ≈κ^-2κ^γ/1+γ



To prove the first statement, observe that:

    ∑_i=1^P i^-δ-1-γ/(i^-1-γ + κ)^2   =  ∑_i ≤κ^-1/1+γi^-δ-1-γ/(i^-1-γ + κ)^2 + ∑_i ≥κ^-1/1+γi^-δ-1-γ/(i^-1-γ + κ)^2
       ≈∑_i ≤κ^-1/1+γ i^1+γ-δ + κ^-2∑_i ≥κ^-1/1+γ i^-δ-1-γ
       ≈max(1, κ^-2+γ-δ/1+γ) + κ^-2κ^δ+γ/1+γ
       = κ^-2max(κ^2, κ^γ+δ/1+γ) + κ^-2κ^δ+γ/1+γ
       ≈κ^-2max(κ^2, κ^γ+δ/1+γ) 
       ≈κ^-2κ^min(2(1+γ), γ + δ)/1+γ.


To prove the second statement, we use Lemma <ref> and the assumption that λ∈ (0,1) to see κ = Θ(max(λ, N^-1-γ)) = O(1). This means that 

    ∑_i=1^P i^-δ - 3(1+γ)/(i^-1-γ + κ)^2 = Ω(∑_i=1^P i^-δ - 3(1+γ)) = Ω(1).

Moreover, we see that:

    ∑_i=1^P i^-δ - 3(1+γ)/(i^-1-γ + κ)^2 = O (∑_i=1^P i^-δ - 3(1+γ)/(i^-1-γ)^2)= O (∑_i=1^P i^-δ - 1 -γ)) = Ω(1).


To prove the third statement, we use Lemma <ref> and the assumption that λ∈ (0,1) to see κ = Θ(max(λ, N^-1-γ)) = O(1). This means that 

    ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ = Ω(∑_i=1^P i^-δ - 2(1+γ)) = Ω(1).

Moreover, we see that:

    ∑_i=1^P i^-δ - 2(1+γ)/i^-1-γ + κ = O (∑_i=1^P i^-δ - 2(1+γ)/i^-1-γ) = O (∑_i=1^P i^-δ - 1  - γ) = O(1).




To prove the fourth statement, observe that:

    ∑_i=1^P i^-δ-2-2γ/(i^-1-γ + κ)^2   ≈∑_i ≤κ^-1/1+γi^-δ-2-2γ/(i^-1-γ + κ)^2 + ∑_i ≥κ^-1/1+γi^-δ-2-2γ/(i^-1-γ + κ)^2
       ≈∑_i ≤κ^-1/1+γ i^-δ +  κ^-2∑_i ≥κ^-1/1+γ i^-δ-2-2γ
       ≈max(1, κ^-1-δ/1+γ) + κ^-2κ^δ+1+2γ/1+γ
       ≈max(1, κ^δ-1/1+γ).


To prove the fifth statement, observe that:

    ∑_i=1^P i^-δ-1-γ/i^-1-γ + κ   = ∑_i ≤κ^-1/1+γi^-δ-1-γ/i^-1-γ + κ + ∑_i ≥κ^-1/1+γi^-δ-1-γ/i^-1-γ + κ
       ≈∑_i ≤κ^-1/1+γ i^-δ + κ^-1∑_i ≥κ^-1/1+γ i^-δ-1-γ
       ≈max(1, κ^-1-δ/1+γ) + κ^-1κ^δ+γ/1+γ
       ≈max(1, κ^δ-1/1+γ).


To prove the sixth statement, observe that:


    ∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2   =  ∑_i ≤κ^-1/1+γi^-2-2γ/(i^-1-γ + κ)^2 + ∑_i ≥κ^-1/1+γi^-2-2γ/(i^-1-γ + κ)^2
       ≈∑_i ≤κ^-1/1+γ 1 + κ^-2∑_i ≥κ^-1/1+γ i^-2-2γ
       ≈κ^-1/1+γ + κ^-2κ^1 + 2γ/1+γ
       ≈κ^-1/1+γ.


To prove the seventh statement, observe that:


    ∑_i=1^P i^-1-γ/i^-1-γ + κ   =  ∑_i ≤κ^-1/1+γi^-1-γ/i^-1-γ + κ + ∑_i ≥κ^-1/1+γi^-1-γ/i^-1-γ + κ
       ≈∑_i ≤κ^-1/1+γ 1 + κ^-1∑_i ≥κ^-1/1+γ i^-1-γ
       ≈κ^-1/1+γ + κ^-1κ^γ/1+γ
       ≈κ^-1/1+γ.


To prove the eighth statement, observe that:

    ∑_i=1^P i^-1-γ/(i^-1-γ + κ)^2   =  ∑_i ≤κ^-1/1+γi^-1-γ/(i^-1-γ + κ)^2 + ∑_i ≥κ^-1/1+γi^-δ-1-γ/(i^-1-γ + κ)^2
       ≈∑_i ≤κ^-1/1+γ i^1+γ + κ^-2∑_i ≥κ^-1/1+γ i^-1-γ
       ≈max(1, κ^-2+γ/1+γ) + κ^-2κ^γ/1+γ
       = κ^-2max(κ^2, κ^γ/1+γ) + κ^-2κ^γ/1+γ
       ≈κ^-2max(κ^2, κ^γ/1+γ) 
       ≈κ^-2κ^γ/1+γ






Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), suppose that P = ∞. Assume the notation from Lemma <ref>, and similarly let

    Q := 1 - 1/N(Σ^2 Σ_κ ^-2).

Then it holds that Q^-1 = Θ(1). 


Let Σ = V Λ V^T be the eigendecomposition of Σ, where Λ is a diagonal matrix consisting of the eigenvalues. By Definition <ref>, we see that:

    λ/κ + 1/N(ΣΣ_κ ^-1) = 1.

This implies that:

    Q    = 1- 1/N(ΣΣ_κ ^-1) + 1/N( (ΣΣ_κ ^-1) - (Σ^2 Σ_κ^-2) ) 
       = λ/κ + 1/N( (ΣΣ_κ ^-1) - (Σ^2 Σ_κ^-2) ).

Observe that:

    (ΣΣ_κ ^-1) - (Σ^2 Σ_κ ^-2)    =  (Λ (Λ + κ I)^-1) - (Λ^2 (Λ + κ I)^-2) 
       = ∑_i=1^P (i^-1-γ/i^-1-γ + κ - i^-2-γ/(i^-1-γ + κ)^2) 
       = κ∑_i=1^P i^-1-γ/(i^-1-γ + κ)^2.

This means that:

    Q    = λ/κ + κ/N∑_i=1^P i^-1-γ/(i^-1-γ + κ)^2
       ≈_(A)λ/κ + Θ((κ/Nκ^-2κ^γ/1+γ)) 
       =λ/κ +  Θ(κ^-1/1+γ/N).

where (A) uses Lemma <ref>. 



  
Case 1: κ = Θ(λ). In this case, we see that 

    Q = λ/κ +  Θ(κ^-1/1+γ/N) = Θ(1).

This means that  Q^-1 = Θ(1). 



  
Case 2: κ = Θ(N^-1-γ). In this case, we see that 

    Q = λ/κ +  Θ(κ^-1/1+γ/N) = Ω(κ^-1/1+γ/N) = Ω(1).

This means that  Q^-1 = Θ(1). 






Suppose that power-law scaling holds for the eigenvalues with scaling exponent γ, and suppose that P = ∞. Then it holds that κ(λ, M, Σ) = Θ(max(λ, M^-1-γ)). 


Let Σ = V Λ V^T be the eigendecomposition of Σ, where Λ is a diagonal matrix consisting of the eigenvalues. 
Observe that:

    ((Σ + κ I)^-1Σ)    = (Λ (Λ + κ I)^-1) 
       = ∑_i=1^P i^-1-γ/i^-1-γ + κ
       ≈_(A)κ^-1/1+γ.

where (A) follows from Lemma <ref>. Using Definition <ref>, we see that for κ = κ(λ, M, Σ), it holds that: 

    λ/κ + 1/MΘ(κ^-1-γ) = 1.

This implies that κ = Θ(max(λ, M^-1-γ)) as desired. 









§ MACHINERY FROM RANDOM MATRIX THEORY


In this section, we introduce machinery from random matrix theory that serves as the backbone for our analysis of multi-objective scaling laws in Appendix <ref>. In Appendix <ref>, we give a recap of known Marčenko-Pastur properties. In  Appendix <ref>, we use these known properties to derive random matrix theory results which are tailored to our analysis.  



 §.§ Recap of Marčenko-Pastur properties


We introduce Marčenko-Pastur properties, following the treatment in <cit.>. Informally speaking, Marčenko-Pastur laws show that a random matrix  (Σ̂ + λ I)^-1 (where Σ̂ is a sample covariance) behaves similarly to a deterministic matrix of the form (Σ̂ + κ I)^-1, where κ = κ(λ, M, Σ) is an effective regularizer. 

Deriving this formally requires placing several structural assumptions on number of data points N ≥ 1, the number of parameters P ≥ 1, the distribution , and the vectors β_1 and β_2. We adopt assumptions from <cit.> which guarantee that a Marčenko-Pastur law holds for Σ, and we further introduce a boundedness assumption for technical reasons. 


We assume that: (1) X ∼ takes the form X = Z Σ^1/2 where Z has bounded subgaussian i.i.d components with mean zero and unit variance, (2) N and P approach ∞ with P/N tending to γ > 0, (3) the spectral measure 1/P∑_i=1^P δ_λ_i of Σ converges to a probability measure with compact support, and Σ is invertible and bounded in operator norm, and (4) for j ∈{1,2}, the measure ∑_i=1^P ⟨ v_i, β_j ⟩^2 converges to a measure with bounded mass, and β_j has bounded ℓ_2 norm. 


The effective regularizer κ(λ, M, Σ) is defined as follows. 


For λ≥ 0, M ≥ 1, and a P-dimensional positive semidefinite matrix Σ with eigenvalues λ_i for 1 ≤ i ≤ P, the value κ(λ, M, Σ) is the unique value κ≥ 0 such that:

    λ/κ + 1/N∑_i=1^P λ_i/λ_i + κ = 1.



We are now ready to state the key random matrix theory results proven in <cit.>. Following <cit.>, the asymptotic equivalence notation u ∼ v means that u/v tends to 1 as N and P go to ∞.


Let Σ̂ = 1/M∑_i=1^M X_i X_i^T be the sample covariance matrix from M i.i.d. samples from X_1, …, X_M ∼. Let κ = κ(λ, N, Σ). Suppose that A and B have bounded operator norm. 
Then it holds that:

    ((Σ̂ + λ I)^-1 A )    ∼κ((Σ + κ I)^-1 A ) 
    κ^2  ((Σ̂ + λ I)^-1 A (Σ̂ + λ I)^-1 B )    ∼((Σ + κ I)^-1 A (Σ + κ I)^-1 B ) 
       + κ^2 1/N(A Σ (Σ + κ I)^-2)/1 - 1/N(Σ^2 (Σ + κ I)^-2)((Σ + κ I)^-1Σ (Σ + κ I)^-1 B ).



We note that the requirement that B has bounded operator norm in Lemma <ref> is what forces us to require that β_1 and β_2 are bounded. However, <cit.> showed that the norm can be unbounded in several real-world settings, and thus instead opt to assume a local Marčenko-Pastur law and derive scaling laws based on this assumption. We suspect it may be possible to derive our scaling law with an appropriate analogue of the local Marčenko-Pastur law, which would also have the added benefit of allowing one to relax other requirements in Assumption <ref> such as gaussianity. We view such an extension as an interesting direction for future work. 



 §.§ Useful random matrix theory facts


We derive several corollaries of Lemma <ref> tailored to random matrices that arise in our analysis of multi-objective scaling laws. 



Assume that  satisfies the Marčenko-Pastur property (Assumption <ref>). Let Z be a positive definite matrix such that Z^-1 has bounded operator norm, and let A be a matrix with bounded operator norm. Let Σ̂ = 1/M∑_i=1^M X_i X_i^T be the sample covariance matrix from M i.i.d. samples from X_1, …, X_M ∼. Then it holds that: 

    λ·((Σ̂  + λ Z)^-1 A) ∼κ·((Σ + κ Z)^-1 A).

If A also has bounded trace and Z has bounded operator norm, then it holds that: 

    (Σ̂ (Σ̂ + λ Z)^-1 A) ∼(Σ· (Σ + κ Z)^-1 A)

where κ = κ(λ, M, Z^-1/2Σ Z^-1/2). 



For (<ref>), observe that:

    λ·((Σ̂ + λ Z)^-1 A) 
        =  λ·(Z^-1/2 (Z^-1/2Σ̂ Z^-1/2  + λ I)^-1 Z^-1/2 A) 
       =  λ·((Z^-1/2Σ̂ Z^-1/2  + λ I)^-1 Z^-1/2 A Z^-1/2) 
       ∼_(A)κ·((Z^-1/2Σ Z^-1/2  + κ I)^-1 Z^-1/2 A Z^-1/2) 
       = κ·(Z^-1/2 (Z^-1/2Σ Z^-1/2  + κ I)^-1 Z^-1/2 A) 
       = κ·((Σ+ κ Z)^-1 A).

where (A) applies Lemma <ref> (using the fact that since A and Z^-1 have bounded operator norm, it holds that Z^-1/2 A Z^-1/2 has bounded operator norm). 

For (<ref>), observe that:

    (Σ̂ (Σ̂ + λ Z)^-1 A)    =_(A)((I - λ  Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2) A ) 
       =_(B)(A) - λ·(( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A Z^1/2) 
       ∼_(C)(A) - κ·(( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 A Z^1/2) 
       =_(D)((I - κ  Z^1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2) A ) 
       =_(E)(Σ (Σ + κ Z)^-1 A)

where (A) and (E) follows from Claim <ref>, (B) and (D) use the fact that (A) is bounded, and (C) follows from Lemma <ref> (using the fact that since A, Z, and Z^-1 have bounded operator norm, it holds that Z^-1/2 A Z^1/2 has bounded operator norm).






Assume that  satisfies the Marčenko-Pastur property (Assumption <ref>). Let Z be any positive definite matrix such that Z and Z^-1 have bounded operator norm, and let A and B have bounded operator norm. Let Σ̂ = 1/M∑_i=1^M X_i X_i^T be the sample covariance matrix from M i.i.d. samples from X_1, …, X_M ∼. Then it holds that:

    λ^2 ((Σ̂  + λ Z)^-1 A (Σ̂  + λ Z)^-1 B) 
       = λ^2  (Z^-1/2 (Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A Z^-1/2  (Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 B)  
       ∼κ^2 ((Σ  + κ Z)^-1 A (Σ  + κ Z)^-1 B) 
       + κ^21/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1  A)/1 - 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1Σ)((Σ  + κ Z)^-1Σ (Σ  + κ Z)^-1 B)

where κ = κ(λ, M, Z^-1/2Σ Z^-1/2). 



Let q = 1/M(Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-2 Z^-1/2 A Z^-1/2)/1 - 1/M(Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-2 Z^-1/2Σ Z^-1/2). 

Observe that: 

    λ^2 ((Σ̂  + λ Z)^-1 A (Σ̂  + λ Z)^-1 B) 
       λ^2 (Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 B)  
       = λ^2 (( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 B Z^-1/2)  
       ∼_(A)κ^2 (( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 A Z^-1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 B Z^-1/2)  
       + κ^2 q  (( Z^-1/2Σ  Z^-1/2 + κ I)^-1 Z^-1/2Σ  Z^-1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 B Z^-1/2) 
       = κ^2 (Z^-1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 A Z^-1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 B)  
       + κ^2 q  (Z^-1/2( Z^-1/2Σ  Z^-1/2 + κ I)^-1 Z^-1/2Σ  Z^-1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 B ) 
       = κ^2 ((Σ + κ Z )^-1 A (Σ + κ Z )^-1 B)  + q κ^2 ((Σ + κ Z )^-1Σ(Σ + κ Z )^-1 B ),

where (A) follows from Lemma <ref> (using the fact that since A, B, Z, and Z^-1 have bounded operator norm, it holds that Z^-1/2 A Z^1/2, Σ, and Z^-1/2 B Z^1/2 have bounded operator norm).


We can simplify q as follows: 

    q    = 1/M(Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-2 Z^-1/2 A Z^-1/2)/1 - 1/M(Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-2 Z^-1/2Σ Z^-1/2)
       = 1/M((Z^-1/2Σ Z^-1/2 + κ I)^-1 
     Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 A Z^-1/2)/1 - 1/M((Z^-1/2Σ Z^-1/2 + κ I)^-1 
     Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2Σ Z^-1/2)
       = 1/M(Z^-1/2(Z^-1/2Σ Z^-1/2 + κ I)^-1 
     Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2 A)/1 - 1/M(Z^-1/2(Z^-1/2Σ Z^-1/2 + κ I)^-1 
     Z^-1/2Σ Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2Σ)
       = 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1  A)/1 - 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1Σ).





Assume that  satisfies the Marčenko-Pastur property (Assumption <ref>). Let Z be any positive definite matrix such that Z and Z^-1 have bounded operator norm. Let A and B have bounded operator norm, and suppose also that (A B) is bounded. Let Σ̂ = 1/M∑_i=1^M X_i X_i^T be the sample covariance matrix from M i.i.d. samples from X_1, …, X_M ∼.  Then it holds that: 

    (Σ̂ (Σ̂ + λ Z)^-1 A (Σ̂ +  λ Z)^-1Σ̂ B) ∼(Σ (Σ + κ Z)^-1  A (Σ + κ Z)^-1Σ B) + E,

where:

    E    := 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1  A)/1 - 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1Σ)·κ^2 (( Σ  + κ Z )^-1Σ( Σ + κ Z )^-1 Z B Z ),

and κ = κ(λ, M, Z^-1/2Σ Z^-1/2). 



Observe that: 

    (Σ̂ (Σ̂ + λ Z)^-1  A (Σ̂ + λ Z)^-1Σ̂ B) 
       = (Σ̂ (Σ̂ + λ Z)^-1  A  (Σ̂ (Σ̂ + λ Z)^-1)^T B) 
       =_(A)((I - λ  Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2) A (I - λ  Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2)^T B ) 
       =_(B)(A B) - λ(A (Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2)^T B ) 
       - λ(Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A B ) 
       + λ^2 (Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A ( Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2)^T B )  
       = (A B) - λ(A Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^1/2 B ) 
       - λ(Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A B ) 
       + λ^2 (Z^1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^1/2  B )  
       = (A B) -  λ(( Σ̂  + λ Z )^-1  Z B A )_(1) - λ(( Σ̂ + λ Z )^-1 A B Z )_(2)
       + λ^2 ((Σ̂  + λ Z )^-1 A (Σ̂  + λ Z )^-1  Z B Z )_(3)

where (A) follows from Claim <ref>, (B) uses that (AB) is bounded,  

For term (1) and term (2), we apply Lemma <ref> to see that: 

    λ(( Σ̂  + λ Z )^-1  Z B A )     ∼κλ(( Σ + κ Z )^-1  Z B A ) 
    λ(( Σ̂ + λ Z )^-1 A B Z )   ∼κ(( Σ + κ Z )^-1 A B Z ).



For term (3), we apply Lemma <ref> to see that 

    λ^2 ((Σ̂  + λ Z )^-1 A (Σ̂  + λ Z )^-1  Z B Z )  
       ∼κ^2 (( Σ + κ Z )^-1 A ( Σ + κ Z )^-1 Z B Z )  
       + κ^2 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1  A)/1 - 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1Σ)((Σ  + κ Z)^-1Σ (Σ  + κ Z)^-1 Z B Z ) 
       ∼κ^2 (( Σ + κ Z )^-1 A ( Σ + κ Z )^-1 Z B Z )  + E



This means that: 

    (Σ̂ (Σ̂ + λ Z)^-1  A (Σ̂ + λ Z)^-1Σ̂)    ∼(A B) -  κ((Σ + κ Z )^-1  Z B A ) - κ(( Σ + κ Z )^-1 A B Z ) 
       + κ^2 ((Σ  + κ Z )^-1 A (Σ + κ Z )^-1  Z B Z ) + E 
       =_(C)(Σ(Σ + κ Z)^-1  A  (Σ + κ Z)^-1Σ B) + E,

where (C) uses an analogous analysis to the beginning of the proof. 






Assume that  satisfies the Marčenko-Pastur property (Assumption <ref>). Let Z be any positive definite matrix such that Z and Z^-1 have bounded operator norm, and let A and B have bounded operator norm. Let Σ̂ = 1/M∑_i=1^M X_i X_i^T be the sample covariance matrix from M i.i.d. samples from X_1, …, X_M ∼.  Then it holds that: 

    λ( (Σ̂ + λ Z)^-1 A (Σ̂ +  λ Z)^-1Σ̂  B ) ∼κ((Σ + κ Z)^-1  A (Σ + κ Z)^-1Σ  B )  - E,

where:

    E    := 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1  A)/1 - 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1Σ)·κ^2 (( Σ  + κ Z )^-1Σ( Σ + κ Z )^-1 Z B )

and κ = κ(λ, N, Z^-1/2Σ Z^-1/2). 


Observe that: 

    λ((Σ̂ + λ Z)^-1  A (Σ̂ + λ Z)^-1Σ̂  B ) 
       =_(A)λ(Z^-1/2(Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A  (I - λ  Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^1/2) B ) 
       = λ(Z^-1/2 (Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A B )  
       - λ^2 ( Z^-1/2( Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^-1/2 A Z^-1/2 (Z^-1/2Σ̂ Z^-1/2 + λ I)^-1 Z^1/2 B ) 
       = λ((Σ̂ + λ Z)^-1 A B  )_(1) - λ^2  (( Σ̂  + λ  Z )^-1 A  (Σ̂ + λ Z)^-1 Z B )_(2)

where (A) follows from Claim <ref>. 

For term (1), we apply Lemma <ref> see that:

    λ((Σ̂ + λ Z)^-1 A B )    ∼κ((Σ + κ Z)^-1 A B ).



For term (2), we apply Lemma <ref> to see that 

    λ^2  (( Σ̂  + λ  Z )^-1 A  (Σ̂ + λ Z)^-1 Z B  ) 
       ∼κ^2 (( Σ + κ Z )^-1 A ( Σ + κ Z )^-1 Z B )  
       + κ^2 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1  A)/1 - 1/M((Σ + κ Z)^-1Σ (Σ + κ Z)^-1Σ)((Σ  + κ Z)^-1Σ (Σ + κ Z)^-1 Z B  ) 
       ∼κ^2 (( Σ + κ Z )^-1 A ( Σ + κ Z )^-1 Z B )  + E.


This means that: 

    λ((Σ̂ + λ Z)^-1  A (Σ̂ + λ Z)^-1Σ̂  B ) 
       ∼κ((Σ + κ Z)^-1 A B )  + κ^2 (( Σ + κ Z )^-1 A ( Σ + κ Z )^-1 Z B )  - E 
       = κ(Z^-1/2 (Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2  A  (I - κ  Z^1/2( Z^-1/2Σ Z^-1/2 + κ I)^-1 Z^-1/2) B ) - E 
       =_(A)κ((Σ + κ Z)^-1  A (Σ + κ Z)^-1Σ  B )  - E,

where (A) uses an analogous analysis to the beginning of the proof. 



The proofs of these results relied on the following basic matrix fact.

 
Let A be any matrix and let B be any symmetric positive definite matrix. Then it holds that:

    A (A + λ B)^-1 = I - λ B^1/2( B^-1/2 A B^-1/2 + λ I )^-1 B^-1/2.



 Observe that:

    A (A + λ B)^-1
       = A B^-1/2( B^-1/2 A B^-1/2 + λ I)^-1 B^-1/2
       = B^1/2(B^-1/2 A B^-1/2) ( B^-1/2 A B^-1/2 + λ I)^-1 B^-1/2
       =  B^1/2(B^-1/2 A B^-1/2 + λ I ) ( B^-1/2 A B^-1/2 + λ I)^-1 B^-1/2 - B^1/2λ( B^-1/2 A B^-1/2 + λ I)^-1 B^-1/2
       =  I - λ  B^1/2( B^-1/2 A B^-1/2 + λ I)^-1 B^-1/2.






§ EXTENSION: MARKET-ENTRY THRESHOLD WITH RICHER FORM FOR L_2^*



In this section, we modify the safety requirement to take into account the impact of dataset size N and regularization parameter λ, and we extend our model and analysis of the market-entry threshold accordingly. We show that the characterization in Theorem <ref> directly applies to this setting, and we also show relaxed versions of Theorem <ref> and Theorem <ref>. Altogether, these extended results illustrate that our qualitative insights from Sections <ref>-<ref> hold more generally. 

We define a modified approximation of the safety violation L̃_2(β_1, β_2, , , N, α). This modified approximation is defined analogously to ^*(β_1, β_2, , , N, α). To formalize this, we define a deterministic equivalent L_2^ for the safety violation to be  

    L_2^(β_1, β_2, , , N, α) := L_1^(β_2, β_1, , , N, 1-α).

It follows from Lemma <ref> that L_2(β̂(α, λ, X)) ∼ L_2^(β_1, β_2, , , N, α): here, we use the fact that L_2(β̂(α, λ, X)) is distributed identically to L_1(β̂(1-α, λ, X)). Now, using this deterministic equivalent, we define L̃_2(β_1, β_2, , , N, α) = L_2^(β_1, β_2, , , N, α).  

Using this formulation of L̃_2, we define a modified market entry threshold where we replace all instances of original approximation L_2^* with the modified approximation L̃_2. In particular, a company C faces reputational damage if: 

    𝔼_(β_1, β_2) ∼L̃_2(β_1, β_2, , α_C) ≥τ_C.

The company selects ∈ [0.5,1] and ∈ (0,1) to maximize their performance subject to their safety constraint, as formalized by the following optimization program:[Unlike in Section <ref>, there might not exist ∈ [0.5,1] and ∈ (0,1) which satisfy the safety constraint, if N_C is too small.]

    (α̃_C, λ̃_C) = _∈ [0.5, 1], ∈ (0,1)𝔼_[^*(β_1, β_2, , , N_C, α)]  s.t. 𝔼_[L̃_2(β_1, β_2, , α)] ≤τ_C.

We define the modified market-entry threshold as follows. 


The modified market-entry threshold (, , , , )
is the minimum value of ∈ℤ_≥ 1 such that 𝔼_[^*(β_1, β_2, , λ̃_E, , α̃_E)] ≤𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)].  


In this section, we analyze the modified market entry threshold (,, , ,  ). We show an extension of Theorem <ref> (Appendix <ref>). We then derive a simplified version of the deterministic equivalent L_2^ (Appendix <ref>). Finally, we show a weakened extension of Theorem <ref> (Appendix <ref>) and a weakened extension of Theorem <ref> (Appendix <ref>). These weakened extensions derive upper bounds (rather than tight bounds) on the modified market entry threshold, and also assume that δ≤ 1. 



 §.§ Extension of Theorem <ref>

We study the market entry  threshold in the environment of Theorem <ref> where the incumbent has infinite data and the new company faces no safety constraint. We show that the modified  market entry threshold takes the same form as the market entry threshold in Theorem <ref>.  


Suppose that power-law scaling holds for the eigenvalues and alignment coefficients, with scaling exponents γ, δ > 0 and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. 
Suppose that the incumbent company has infinite data (i.e., = ∞), and that the entrant faces no constraint on their safety (i.e., = ∞). Suppose that the safety constraint  satisfies (<ref>). Then, it holds that:

    (∞, , ∞, , ) = Θ((√(L^*(ρ)) - √(min(, L^*(ρ))))^-2/),

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ), and where := min(2(1+γ), δ + γ). 


Theorem <ref> shows that the qualitative insights from Theorem <ref>—including that the new company can enter with finite data—readily extend to this setting.   

To prove Theorem <ref>, we build on the notation and analysis from Appendix <ref>. It suffices to show that each company C will select _C = _C and λ_C = λ̃_C. This follows trivially for the entrant C = E since they face no safety constraint, and there is no different between the two settings. The key ingredient of the proof is to compute _I and _I for the incumbent (i.e., an analogue of Lemma <ref> in Appendix <ref>). 

To do this, we first upper bound the following function of the safety loss and performance loss for general parameters  and .


For any α and , it holds that:

    √(𝔼_[L_1(β(α, λ))]) + √(𝔼_[L_2(β(α, λ))])≥√(𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T]).



Note that:

    T    := √(𝔼_[L_1(β(α, λ))]) + √(𝔼_[L_2(β(α, λ))])
       = √((β_1 - β(α, λ))^T Σ (β_1 - β(α, λ))) + √((β_2 - β(α, λ))^T Σ (β_2 - β(α, λ)))
       = √((λβ_1 + (1-α) Σ (β_1 - β_2))^T Σ (Σ + λ I)^-2 (λβ_1 + (1-α) Σ (β_1 - β_2)))
       + √((λβ_2 +  αΣ (β_2 - β_1))^T Σ (Σ + λ I)^-2 (λβ_2 +  αΣ (β_2 - β_1)))
       = √((λβ_1 + (1-α) Σ (β_1 - β_2))^T Σ (Σ + λ I)^-2 (λβ_1 + (1-α) Σ (β_1 - β_2)) )
       + √((-λβ_2 +  αΣ (β_1 - β_2))^T Σ (Σ + λ I)^-2 (-λβ_2 + αΣ (β_1 - β_2))).

Now note that for any PSD matrix Σ' and any distribution, note that the following triangle inequality holds: 

    √(𝔼[(X_1 + X_2)^T Σ' (X_1 + X_2)])≤√(𝔼[X_1^T Σ' X_1]) + √(𝔼[X_2^T Σ' X_2]).
 We apply this for X_1 = λβ_1 + (1-α) Σ (β_1 - β_2), X_2 = -λβ_2 +  αΣ (β_1 - β_2), and distribution . This means that we can lower bound: 

    T    ≥√(𝔼_[((Σ + λ I) (β_1 - β_2))^T Σ (Σ + λ I)^-2 ((Σ + λ I) (β_1 - β_2))])
       = √(𝔼_[(β_1 - β_2))^T Σ (β_1 - β_2))])

as desired. 
 
Now, we are ready to compute _I and _I for the incumbent. 


Let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T]. Suppose that = ∞, and suppose that the safety constraint  satisfies (<ref>). Then it holds that α_I =  √(min(, L^*(ρ))/L^*(ρ)), and _I = 0 is optimal for the incumbent. Moreover, it holds that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α̃_I)] = (√(L^*(ρ)) - √(min(L^*(ρ), )))^2.



First, we apply Lemma <ref> with N = ∞ to see that:

    𝔼_[L^*_1(β_1, β_2, , , ∞, α)] = 𝔼_[L_1(β(α, λ))]

and 

    𝔼_[L^*_2(β_1, β_2, , , ∞, α)] = 𝔼_[L_2(β(α, λ))].


Let α^* =√(min(, L^*(ρ))/L^*(ρ)). By the assumption in the lemma statement, we know that:

    α^* ≥√(𝔼_[^*(β_1, β_2, , 0.5)]/L^*(ρ)) = 0.5.

Observe that:

    √(𝔼_[ L_1(β(α^*, 0))]) + √(min(, L^*(ρ)))
       =√(𝔼_[ L_1(β(α^*, 0))]) + √(𝔼_[ L_2(β(α^*, 0))])
       = √((1-α^*)^2 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T]) + √( (α^*)^2 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T])
       = √(𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T])


We show that (α̃_I, _I) = (α^*, 0). Assume for sake of contradiction that (α, ) ≠ (α^*, 0) satisfies the safety constraint 𝔼_[L̃_2(β_1, β_2, , α)] ≤min(, L^*(ρ)) and achieves strictly better performance loss:

    𝔼_[^*(β_1, β_2, , , ∞, )] <  𝔼_[^*(β_1, β_2, , 0, ∞, ^*)].
 Then it would hold that:

    √(𝔼_[ L_1(β(, ))]) + √(𝔼_[ L_2(β(, ))])   < √(𝔼_[ L_1(β(α^*, 0))]) + √(min(, L^*(ρ)))
       = √(𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)^T]),

which contradicts Lemma <ref>.

To analyze the loss, note that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α̃_I)] 
       = 𝔼_[L_1(β(α̃_I, λ̃_I))] 
       = (1-α̃_I)^2 L^*(ρ) 
       = (√(L^*(ρ)) - √(min(L^*(ρ), )))^2

    






We now prove Theorem <ref>.  


We analyze (α̃_C, _C) first for the incumbent C = I and then for the entrant C = E. 



  
Analysis of the incumbent C = I.
By Lemma <ref>, we see that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α̃_I)] =  (√(L^*(ρ)) - √(min(, L^*(ρ))))^2.




  
Analysis of the entrant C = E. This analysis follows identically to the analogous case in the proof of Theorem <ref>, and we repeat the proof for completeness. Since the entrant faces no safety constraint, the entrant can choose any α∈ [0.5, 1]. We apply Corollary <ref> to see that:

    𝔼_[L^*_1(β_1, β_2, , _E, N, α_E)] = inf_α∈ [0.5, 1]inf_ > 0𝔼_[L^*_1(β_1, β_2, , , N, α)] = Θ(
    N^-),

which means that:

    ^*(∞, , ∞, , ) = Θ((√(L^*(ρ)) - √(min(, L^*(ρ)))^-2/)

as desired. 
We can further apply Claim <ref> to see that L^*(ρ) = Θ(1-ρ). 






 §.§ Bounds on the excess loss for safety


We bound the excess loss α^2 L^*(ρ)  - 𝔼_[L_2^]. We assume that α≥ 0.5 and we further assume that δ≤ 1. 


Suppose that power scaling holds for the eigenvalues and alignment coefficients with scaling γ > 0 and δ∈ (0,1], and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Suppose that α≥ 0.5, ∈ (0,1), and N ≥ 1. Let L_2^ :=  L_2^(β_1, β_2, , , N, α) be defined according to (<ref>). Let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)]. Then it holds that:

    α^2 L^*(ρ)  - 𝔼_[L_2^] = O( max(λ^/1 + γ, N^-) 
    
    )

and 

    𝔼_[L_2^] - α^2 L^*(ρ) = O( max(λ^/1 + γ, N^-) + (1-α) (1-ρ) min(λ^-1/1 + γ, N)/N),

where = min(2(1+γ), δ + γ) = δ + γ. 


To prove Lemma <ref>, we first simplify the deterministic equivalent L_2^(β_1, β_2, , , N, α) using the assumptions from Section <ref>. 


Suppose that power scaling holds for the eigenvalues and alignment coefficients with scaling γ, δ > 0 and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Suppose that ∈ (0,1), and N ≥ 1. Let L_2^ :=  L_2^(β_1, β_2, , , N, α) be defined according to (<ref>). Let κ = κ(λ, N, Σ) from Definition <ref>. Let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)]. Then it holds that:
  
    𝔼_[L_2^] - L^*(ρ)    = 
    Q^-1·κ^2 ∑_i=1^P i^-δ -1- γ/(i^-1-γ + κ)^2  + Q^-1 2κα (1-α) (1-ρ) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1 2 α (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       - 2 α^2 κ (1-ρ) ∑_i=1^P  i^-δ - 1 -γ/i^-1-γ + κ,

  where Q = 1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2. 


First, we apply  Lemma <ref>, coupled with the fact that L_2^(β_1, β_2, , , N, α) := L_1^(β_2, β_1, , , N, 1-α), to see that:

    Q ·𝔼_[L_2^]    = κ^2 (1 - 2 α^2 (1-ρ)) ∑_i=1^P i^-δ - 1- γ/(i^-1-γ + κ)^2 + α^2 L^*(ρ) 
       + 2κ (1-ρ) α (1 - 2  α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + 2 α (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2α)  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ,

   where Q = 1 - 1/N∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2. Using that (Q^-1 - 1) α^2 L^*(ρ) = Q^-11/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) 2 α^2 (1-ρ)  ( ∑_i=1^P i^-δ-1-γ), this means that:

    𝔼_[L_2^] -  α^2 L^*(ρ)    = Q^-11/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) 2 α^2 (1-ρ)  ( ∑_i=1^P i^-δ-1-γ) 
       + 
    Q^-1·κ^2 (1 - 2 α^2 (1-ρ)) ∑_i=1^P i^-δ - 1- γ/(i^-1-γ + κ)^2
       + Q^-1 2κ (1-ρ) α (1 - 2  α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1 2 α (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) · (1 - 2α)  ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ

By expanding some of these terms, we see that:

    𝔼_[L_2^] -  α^2 L^*(ρ)    = 
    Q^-1 2 α^2 (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P i^-δ-1-γ
       + Q^-1·κ^2 ∑_i=1^P i^-δ - 1-γ/(i^-1-γ + κ)^2 - Q^-12 α^2 (1-ρ) ·κ^2 ∑_i=1^P i^-δ -1- γ/(i^-1-γ + κ)^2
       + Q^-1 2κ (1-ρ) α (1 -  α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2 - Q^-1 2κ (1-ρ) α^2 ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1 2 α (1 - α)(1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       - Q^-1 2 α^2 (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ .


When we collect terms, we obtain: 

    𝔼_[L_2^] -  α^2 L^*(ρ) 
       = Q^-1·κ^2 ∑_i=1^P i^-δ - 1-γ/(i^-1-γ + κ)^2 + Q^-1 2κ (1-ρ) α (1 -  α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1 2 α (1 - α)(1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       - Q^-1 2κ (1-ρ) α^2 (∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2  + ∑_i=1^P κ· i^-δ -1- γ/(i^-1-γ + κ)^2) 
       + 
    Q^-1 2 α^2 (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·(∑_i=1^P i^-δ-1-γ - ∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ) 
       = Q^-1·κ^2 ∑_i=1^P i^-δ - 1-γ/(i^-1-γ + κ)^2 + Q^-1 2κ (1-ρ) α (1 -  α) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1 2 α (1 - α)(1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       - Q^-1 2κ (1-ρ) α^2 (∑_i=1^P i^-δ - 1 - γ/(i^-1-γ+κ)) 
       + 
    Q^-1 2 κα^2 (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·i^-δ - 1-γ/i^-1-γ + κ.

Combining the last two terms gives us the desired statement. 


Now, we are ready to prove Lemma <ref>.


For the first bound, we observe that:

    α^2 L^*(ρ) - 𝔼_[L_2^]  
       ≤_(A) 2 α^2 κ (1-ρ) ∑_i=1^P  i^-δ - 1 -γ/i^-1-γ + κ
       =_(B) O(α^2 (1-ρ) κ^min(1+γ, δ+γ)/1+γ) 
       =_(C) O(κ^/1+γ) 
       =_(D) O(max(λ^/1+γ, N^-) )

where (A) uses Lemma <ref>, (B) uses Lemma <ref>, (C) uses that δ≤ 1 and ρ∈ [0, 1), and (D) uses Lemma <ref>.

For the second bound, we observe that:

    𝔼_[L_2^] -  α^2 L^*(ρ) 
       ≤_(A)  
    Q^-1·κ^2 ∑_i=1^P i^-δ -1- γ/(i^-1-γ + κ)^2
       + Q^-1 2κα (1-α) (1-ρ) ∑_i=1^P i^-δ - 2(1+γ)/(i^-1-γ+κ)^2
       + Q^-1 2 α (1-α) (1-ρ) 1/N(∑_i=1^P i^-2-2γ/(i^-1-γ + κ)^2) ·∑_i=1^P  i^-δ - 2-2γ/i^-1-γ + κ
       =_(B)  
    O( κ^min(2(1+γ), γ + δ)/1+γ + α (1-α) (1-ρ) κ^min(1+γ, γ + δ)/1+γ + α (1-α) (1-ρ) κ^-1/1+γ/N) 
       =_(C)  
    O( κ^γ + δ/1+γ + (1-α) (1-ρ) κ^γ + δ/1+γ + (1-α) (1-ρ) κ^-1/1+γ/N) 
       = O( κ^γ + δ/1+γ + (1-α) (1-ρ) κ^-1/1+γ/N) 
       =_(D) O( max(λ^/1+γ, N^-) + (1-α) (1-ρ) min(λ^-1/1+γ, N)/N)

where (A) uses Lemma <ref>, (B) uses Lemma <ref> and Lemma <ref>, (C) uses that δ≤ 1 and α≥ 0.5, and (D) uses Lemma <ref>.





 §.§ Extension of Theorem <ref>




We next study the market entry  threshold in the environment of Theorem <ref> where the incumbent has finite data and the new company faces no safety constraint. We place the further assumption that δ≤ 1. We compute the following upper bound on the modified market entry threshold.



Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ > 0, δ∈ (0, 1] and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Assume that = ∞. Suppose that the safety constraint  satisfies (<ref>). Then we have that = (, , ∞, , ) satisfies: 

    := 
    
    O()     if ≤G̃_I^-1/2  (1-ρ)^-1/2
    
    O(^1/+1·G̃_I^-1/2(+1) (1-ρ)^-1/2(+1))      if G̃_I^-1/2  (1-ρ)^-1/2≤≤G̃_I^-1/2 - 1/(1-ρ)^1/2
    
    O(G̃_I^-1/)      if ≥G̃_I^-1/2 - 1/(1-ρ)^1/2,

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ), where α^* = √(min(, L^*(ρ))/L^*(ρ)), where α̃ := √((1-α^*) + (α^*)^2), where G̃_I = (1-α̃)^2 (1-ρ), and where = min(2(1+γ), γ + δ) = γ + δ.  


Theorem <ref> shows that the key qualitative finding from Theorem <ref>—that the new company can enter with = o() data as long as the incumbent's dataset size is sufficiently large—readily extends to this setting. We note that the bound in Theorem <ref> and the bound in Theorem <ref> take slightly different forms: the term G_I = (√(L^*(ρ))- √(min(L^*(ρ), )))^2 = Θ((1-α^*)^2 (1-ρ)) is replaced by G̃_I = (1-α̃)^2(1-ρ). We expect some of these differences arise because the bound in Theorem <ref> is not tight, rather than fundamental distinctions between the two settings. Proving a tight bound on the modified market entry threshold is an interesting direction for future work. 

To prove this, we compute a lower bound on the incumbent's loss 𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)]. 


Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ > 0, δ∈ (0, 1] and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Assume that = ∞. Suppose that the safety constraint  satisfies (<ref>). 
Then we have that: 

    𝔼_[L^*_1(β_1, β_2, , _I, , α̃_I)] 
       =  Ω( ^-)     if ≤G̃_I^-1/2 (1-ρ)^-1/2
    Ω(^-/+1·G̃_I^/2(+1) (1-ρ)^/2(+1))      if  G̃_I^-1/2 (1-ρ)^-1/2≤≤G̃_I^-1/2 - 1/(1-ρ)^1/2
    Ω(G̃_I)      if  ≥G̃_I^-1/2 - 1/(1-ρ)^1/2.

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ), where α^* = √(min(, L^*(ρ))/L^*(ρ)), where α̃ := √((1-α^*) + (α^*)^2), where G̃_I = (1-α̃)^2 (1-ρ)
and where = min(2(1+γ), γ + δ) = γ + δ.  


By Corollary <ref> and Lemma <ref>, we know that:

    𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)]  = Ω(κ^/1+γ) = Ω(max(λ^/1+γ, ^-)).

Let C_δ, γ be an implicit constant[We need to introduce an implicit constant because of O() is permitted to hide constants that depend on δ and γ.] such that:

    𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)]  ≥ C_δ, γmax(λ^/1+γ, ^-)

By Lemma <ref>, there also exists an implicit constant C'_δ, γ  such that:

    α^2 L^*(ρ) - 𝔼_[L_2^(β_1, β_2, , λ, , α)] ≤ C'_δ, γmax(λ^/1+γ, ^-).


We now split into two cases: (1) C'_δ, γ/C_δ, γ𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)] ≥ (1-α^*)L^*(ρ), and (2)  C'_δ, γ/C_δ, γ𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)] ≤ (1-α^*)L^*(ρ). 



  
Case 1: C'_δ, γ/C_δ, γ𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)] ≥ (1-α^*)L^*(ρ). It follows from (<ref>) that: 

    𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)]  ≥ C_δ, γmax(λ^/1+γ, ^-) ≥ C_δ, γ^-.
 
Using the condition for this case, this implies that:

    ≤(1/C_δ, γ𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)])^-1/
       ≤(1/C'_δ, γ (1-α^*) L^*(ρ) )^-1/
       = O(((1-α̃) (1-ρ) )^-1/) 
       = O(G̃_I^-1/2 (1-ρ)^-1/2 ).

This proves that  is up to constants within the first branch of the expression in the lemma statement. Since the bound in the lemma statement only changes by constants (that depend on δ and γ) between the first branch and second branch, this proves the desired expression for this case.



  
Case 2: C'_δ, γ/C_δ, γ𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)]  ≤ (1-α^*)L^*(ρ). Note that α^* = √(min(, L^*(ρ))/L^*(ρ)) is the mixture parameter that achieves the safety constraint in the infinite-data ridgeless setting. The incumbent's safety constraint means that: 

    𝔼_[L_2^(β_1, β_2, , λ̃_I, , α̃_I)] ≤ (α^*)^2 L^*(ρ).

By (<ref>), this implies that 

    (α̃_I)^2 L^*(ρ) ≤ C'_δ, γ·max(λ^δ+ γ/1+γ, ^-δ-γ) + (α^*)^2 L^*(ρ).

Now, applying (<ref>) and the assumption for this case, we see that:

    (α̃_I)^2 L^*(ρ)    ≤C'_δ, γ/C_δ, γ·𝔼_[^*(β_1, β_2, , λ̃_I, , α̃_I)]  + (α^*)^2 L^*(ρ)   
       ≤ (1-α^*)L^*(ρ) + (α^*)^2 L^*(ρ).

This implies that:

    α̃_I ≤√((1-α^*) + (α^*)^2).
 Let α̃ := √((1-α^*) + (α^*)^2). Plugging this into Corollary <ref>, we see that:

    𝔼_[L^*_1(β_1, β_2, , _I, , α̃_I)] 
       ≥inf_α∈[0.5, α̃]inf_ > 0𝔼_[L^*_1(β_1, β_2, , ,  , α)]  
       = Θ(
    inf_ > 0𝔼_[L^*_1(β_1, β_2, Σ, ,  , α̃)] ) 
       = Θ(^-)     if ≤ (1-α̃ )^-1/(1-ρ)^-1/
    Θ((/(1-α̃ )(1-ρ))^-/ + 1)     if  (1-α̃ )^-1/(1-ρ)^-1/≤≤  (1-α̃ )^-2+/ (1-ρ)^-1/
    Θ((1-α̃ )^2(1-ρ))     if ≥ (1-α̃ )^-2+/ (1-ρ)^-1/,
    
       = Θ( ^-)     if ≤G̃_I^-1/2 (1-ρ)^-1/2
    Θ(^-/+1·G̃_I^/2(+1) (1-ρ)^/2(+1))      if G̃_I^-1/2 (1-ρ)^-1/2≤≤G̃_I^-1/2 - 1/(1-ρ)^1/2
    Θ(G̃_I)      if ≥G̃_I^-1/2 - 1/(1-ρ)^1/2.

The statement follows in this case. 


We are now ready to prove Theorem <ref>.


We analyze (α̃_C, _C) first for the incumbent C = I and then for the entrant C = E. Like in the theorem statement, let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β_2)] = Θ(1 - ρ) (Claim <ref>) and G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and = min(2(1+γ), δ + γ).



  
Analysis of the incumbent C = I. 
We apply Lemma <ref> to see that: 

    𝔼_[L^*_1(β_1, β_2, , _I, , α̃_I)] 
       = Ω( ^-)     if ≤G̃_I^-1/2 (1-ρ)^-1/2
    Ω(^-/+1·G̃_I^/2(+1) (1-ρ)^/2(+1))      if G̃_I^-1/2 (1-ρ)^-1/2≤≤G̃_I^-1/2 - 1/(1-ρ)^1/2
    Ω(G̃_I)      if ≥G̃_I^-1/2 - 1/(1-ρ)^1/2.
    .




  
Analysis of the entrant C = E. Since the entrant faces no safety constraint, the entrant can choose any α∈ [0.5, 1].  We apply Corollary <ref> to see that:

    𝔼_[L^*_1(β_1, β_2, , _E, N, α̃_E)] = inf_α∈ [0.5, 1]inf_ > 0𝔼_[L^*_1(β_1, β_2, , , N, α)] = Θ(
    N^-),

which means that:

    ^*(, , ∞, , ) = 
    O()     if ≤G̃_I^-1/2 (1-ρ)^-1/2
    
    O(^1/+1·G̃_I^-1/2(+1) (1-ρ)^-1/2(+1))      if G̃_I^-1/2 (1-ρ)^-1/2≤≤G̃_I^-1/2 - 1/(1-ρ)^1/2
    
    O(G̃_I^-1/)      if ≥G̃_I^-1/2 - 1/(1-ρ)^1/2

as desired.  






 §.§ Extension of Theorem <ref>



We next study the market entry  threshold in the environment of Theorem <ref> where the incumbent has infinite data and the new company faces a nontrivial safety constraint. We place the further assumption that δ≤ 1. We compute the following upper bound on the modified market entry threshold.



Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ > 0, δ∈ (0,1], and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Suppose that the safety constraints  and  satisfy (<ref>). 
Then it holds that = (∞, , , , ) satisfies: 

    := 
    O(max(D̃^-1/, D̃^- + 1/( G_E^1/2 (1-ρ)^1/2 + 1/2 G_I - 1/2 G_E )  ) ),

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β)] = Θ(1 - ρ), where = min(2(1+γ), δ + γ) = δ + γ, where 
G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 and G_E := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and where:  

    D̃ := α^*_E · (G_I - G_E) - (G_I - G_E)^2/4 · L^*(ρ) .
 



Theorem <ref> shows that the key qualitative finding from Theorem <ref>—that the new company can enter with finite data, as long as they face a strictly weaker safety constraint than the incumbent company—readily extends to this setting. We note that the bound in Theorem <ref> and the bound in Theorem <ref> take slightly different forms. Some of these differences are superficial: while the bound in Theorem <ref> contains two—rather than three—regimes, the third regime in Theorem <ref> does not exist in the case where δ≤ 1. Other differences are more substantial: for example, the bound in Theorem <ref> scales with D̃ while the bound in Theorem <ref> scales with D. However, we expect some of this difference arises because the bound in Theorem <ref> is not tight, rather than fundamental distinctions between the two settings. Proving a tight bound on the modified market entry threshold is an interesting direction for future work. 


We compute an upper bound on the number of data points  that the new company needs to achieve at most loss (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 on performance.


Suppose that the power-law scaling holds for the eigenvalues and alignment coefficients with scaling exponents γ > 0, δ∈ (0, 1] and correlation coefficient ρ∈ [0, 1), and suppose that P = ∞. Suppose that the safety constraints  and  satisfy (<ref>). For sufficiently large constant C_δ, γ, if 

    ≥ 
    C_δ, γ·max(D̃^-1/, D̃^- + 1/( G_E^1/2 (1-ρ)^1/2 + 1/2 G_I - 1/2 G_E )  ),

then it holds that: 

    𝔼_[^*(β_1, β_2, , _E, , α̃_E)] ≤ G_I,

where L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β)] = Θ(1 - ρ), where = min(2(1+γ), δ + γ) = δ + γ, where 
G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 and G_E := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and where:  

    D̃ := α^*_E · (G_I - G_E) - (G_I - G_E)^2/4 · L^*(ρ) .
 


It suffices to construct α̃ and λ̃ such that 

    𝔼_[L̃_2(β_1, β_2, , , , α̃)] ≤
 and 

    𝔼_[^*(β_1, β_2, , , , α̃)] ≤ G_I

for = Ω(max(D̃^-1/, D̃^- + 1/( G_E^1/2 (1-ρ)^1/2 + 1/2 G_I - 1/2 G_E )  )). 

To define α̃ and , it is inconvenient to work with the following intermediate quantities. Let α^*_E = (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 and let α^*_I = (√(L^*(ρ)) - √(min(, L^*(ρ))))^2. We define an error function: 

    f(, α, λ) := max(λ^/1 + γ, ^-) + (1-α) (1-ρ) min(λ^-1/1 + γ, )/

We define:

    α̃ := α^*_E + 1/2 (1 - α^*_E)^2  - 1/2 (1 - α^*_I)^2 = α^*_I + α^*_E - α^*_I/2.

and 

    := inf_∈ (0,1) f(, α̃, λ).

At these values of α̃ and  and under the condition on , observe that:

    f(, α̃, )    = Θ(max(^-, (/(1-α̃)(1-ρ))^-/+1) ) 
       = Θ(max(^-, (/G_E^1/2 (1-ρ)^1/2 + 1/2G_I + 1/2 G_E)^-/+1) ) 
       = O(D̃),

where the implicit constant can be reduced by increasing the implicit constant on . 

The remainder of the analysis boils down to showing that 𝔼_[L̃_2(β_1, β_2, , , , α̃)] ≤ and 𝔼_[^*(β_1, β_2, , , , α̃)] ≤ G_I. To show this, we first derive an error function and bound these losses in terms of the error function.




  
Bounding 𝔼_[L̃_2(β_1, β_2, , , , α̃)] ≤. Observe that:

    𝔼_[L̃_2(β_1, β_2, , , , α̃)] 
       =_(A)α̃^2 L^*(ρ) + O( max(λ^/1 + γ, ^-) + (1-α) (1-ρ) min(λ^-1/1 + γ, )/) 
       = (α^*_E + 1/2 (1-α^*_E)^2 - 1/2 (1-α^*_I)^2) L^*(ρ) + O(f(, α̃)) 
       ≤((α^*_E)^2 L^*(ρ) + ((1-α^*_I)^2 - (1-α^*_E)^2)^2/4 - α^*_E ((1-α^*_I)^2 - (1-α^*_E)^2)  ) L^*(ρ) + D̃
       =  + (G_I - G_E)^2/4 · L^*(ρ) - α^*_E(G_I - G_E) α^*_E · (G_I - G_E) - (G_I - G_E)^2/4 · L^*(ρ)
       =

where (A) follows from Lemma <ref>. This gives us the desired bound.  



  
Bounding 𝔼_[^*(β_1, β_2, , , , α̃)].
Observe that: 

    𝔼_[^*(β_1, β_2, , , , α̃)] 
       =_(A) (1-α̃)^2 L^*(ρ) + O( max(λ^/1 + γ, ^-) + (1-α) (1-ρ) min(λ^-1/1 + γ, )/) 
       ≤ (1- α^*_E - 1/2 (1-α^*_E)^2 + 1/2 (1-α^*_I)^2)^2 L^*(ρ) + O(f(, α̃)) 
       ≤((1-α^*_E)^2 + ((1-α^*_I)^2 - (1-α^*_E)^2)^2/4 - (1-α^*_E) ((1-α^*_I)^2 - (1-α^*_E)^2) ) L^*(ρ) + D̃
       ≤ 
    G_E + (G_I - G_E) (1-α^*_E) + (G_I - G_E)^2/4 L^*(ρ)  + α^*_E · (G_I - G_E) - (G_I - G_E)^2/4 · L^*(ρ)
       = G_I.

where (A) uses Theorem <ref>, coupled with the fact that δ≤ 1 (which means that ' =, so the mixture finite data error is subsumed by the finite data error) and coupled with Lemma <ref>. This gives us the desired bound. 





We are now ready to prove Theorem <ref>. 





We analyze (α̃_C, _C) first for the incumbent C = I and then for the entrant C = E. Like in the theorem statement, let L^*(ρ) = 𝔼_[(β_1 - β_2)^T Σ (β_1 - β)] = Θ(1 - ρ), let = min(2(1+γ), δ + γ) = δ + γ, let 
G_I := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2 and G_E := (√(L^*(ρ)) - √(min(, L^*(ρ))))^2, and let:  

    D̃ := α^*_E · (G_I - G_E) - (G_I - G_E)^2/4 · L^*(ρ).
 



  
Analysis of the incumbent C = I.
To compute α̃_I and _I, we apply Lemma <ref>. 
The assumption ≥𝔼_[(β_1, β_2, Σ, 0.5)] in the lemma statement can be rewritten as ≥ 0.25 L^*(ρ), which guarantees the assumptions in Lemma <ref> are satisfied. By Lemma <ref>, we see that:

    𝔼_[L^*_1(β_1, β_2, , _I, ∞, α̃_I)] =  (√(L^*(ρ)) - √(min(, L^*(ρ)))^2 = G_I.





  
Analysis of the entrant C = E. 
We apply Lemma <ref> to see 
for sufficiently large constant C_δ, γ, if 

    ≥ 
    C_δ, γ·max(D̃^-1/, D̃^- + 1/( G_E^1/2 (1-ρ)^1/2 + 1/2 G_I - 1/2 G_E )  ),

then it holds that: 

    𝔼_[^*(β_1, β_2, , _E, , α̃_E)] ≤ G_I =  𝔼_[L^*_1(β_1, β_2, , _I, ∞, α̃_I)].

This means that:

    = O( max(D̃^-1/, D̃^- + 1/( G_E^1/2 (1-ρ)^1/2 + 1/2 G_I - 1/2 G_E )  ))

as desired. 

