I think exceptions are OK in this case.
Just make sure to shortcircuit and eliminate the exceptions you can:
private static bool IsValidRegex(string pattern)
{
if (string.IsNullOrWhiteSpace(pattern)) return false;
try
{
Regex.Match("", pattern);
}
catch (ArgumentException)
{
return false;
}
return true;
}