Ordinary least squares and its variations (e.g., ridge regression or constrained least squares) have been studied extensively in the literature, with most of the results primarily focusing on the upper bounds. Many variations of our problem were previously considered in the literature (e.g., fixed-design regression, distributional assumptions different from boundedness or performance metrics that differ from the excess risk); see [1]} for a detailed comparison of different setups. For comprehensive surveys of existing work, we refer to [2]}, [3]}, [4]}, [5]} and the books [6]}, [7]}, [8]}. The lower bound (REF ) is due to [1]}, and it is the tightest lower bound in the literature that covers the setting considered in our work. The best known upper bound in such a setting is of the form given in (REF ); the gap between (REF ) and (REF ) is currently not addressed in the literature.
