New safety concerns have arisen with the growth of machine learning, necessitating mitigation efforts to ensure algorithms adhere to trustworthiness standards. In this dissertation, we study problems where safety constraints are potentially unknown and are strictly enforced. In the first part of the dissertation, we study social network polarization as a form of unsafe outcome. In this setting, a learner must provide useful recommendations to a social network of users while preventing bias and polarization amongst the users - complex emergent phenomena based on network dynamics. We generalize established models of opinion formation in economic theory and mathematical sociology [Degroot [1974, Friedkin and Johnsen [1990]] to account for cognitive biases [Lord et al. [1979]] and the presence of a recommender system. Using this model, we define bias as opinion shift from initial opinions, and polarization as opinion shift from mean opinions. We develop algorithms perform well, while controlling bias and polarization through an indirect safety constraint leveraging network properties. To this end, we use tools from online learning literature to show that it is possible to design an algorithm to aggregate recommendation or predictions in a way that ensures that it is non-polarizing (or non-biasing) and also has vanishing regret w.r.t. to be best non-polarizing (or non-biasing) mixture of base recommenders. We also provide an efficient version of our aggregation algorithm that ensures non-biasedness under mild assumptions on our opinion dynamic model. In the second part of the dissertation, we study the broader problem of online learning where the sequence of actions played by the learner must adhere to an unknown safety constraint at every round. The goal is to minimize regret with respect to the best safe action in hindsight while simultaneously satisfying the safety constraint with high probability on each round. We provide a general meta-algorithm that leverages an online regression oracle to estimate the unknown safety constraint, and converts the predictions of an online learning oracle to predictions that adhere to the unknown safety constraint. On the theoretical side, our algorithm's regret can be bounded by the regret of the online regression and online learning oracles, the eluder dimension of the model class containing the unknown safety constraint, and a novel complexity measure that characterizes the difficulty of safe learning. We complement our result with an asymptotic lower bound that shows that the aforementioned complexity measure is necessary. When the constraints are linear, we instantiate our result to provide a the first algorithm with $\sqrt{T}$ regret using a scaling transformation that balances optimistic exploration with pessimistic constraint satisfaction.