  We study computational aspects of algorithmic replicability, a notion of
stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell [2022].
Motivated by a recent line of work that established strong statistical
connections between replicability and other notions of learnability such as
online learning, private learning, and SQ learning, we aim to understand better
the computational connections between replicability and these learning
paradigms. Our first result shows that there is a concept class that is
efficiently replicably PAC learnable, but, under standard cryptographic
assumptions, no efficient online learner exists for this class. Subsequently,
we design an efficient replicable learner for PAC learning parities when the
marginal distribution is far from uniform, making progress on a question posed
by Impagliazzo et al. [2022]. To obtain this result, we design a replicable
lifting framework inspired by Blanc, Lange, Malik, and Tan [2023] that
transforms in a black-box manner efficient replicable PAC learners under the
uniform marginal distribution over the Boolean hypercube to replicable PAC
learners under any marginal distribution, with sample and time complexity that
depends on a certain measure of the complexity of the distribution. Finally, we
show that any pure DP learner can be transformed to a replicable one in time
polynomial in the accuracy, confidence parameters and exponential in the
representation dimension of the underlying hypothesis class.
