An online system provides video recommendations to a target user of the online system as a supplement to videos provided to the target user that were posted by the user's connections in the online system. The recommended videos are selected from publicly available video content and are likely to be of interest to the target user. The online system has video candidate generators that select video candidates based on a variety of selection criteria. The selected video candidates are filtered to identify inappropriate content or videos that the target user has already viewed for elimination from candidacy. The filtered video candidates are ranked based on weights of features of the video candidates. Based on the ranking, the online system selects videos above a threshold as recommendations to the target user.