Descriptions may be stale. Consult the linked Lean sources.
Batched
Polar Matrix Optimization
We consider minimizing a differentiable, possibly nonconvex function
, where
are nonnegative integers. Its gradient is -Lipschitz from the spectral norm to the
nuclear norm, with , and a
given starting matrix has
objective gap at most
above a global lower bound. The oracle returns unbiased stochastic
gradients using independent, identically distributed samples, with
rowwise standard deviations summing to at most in a fixed orthonormal basis.
Batched polar updates must produce a random output satisfying , where is the nuclear norm, , and expectation
includes sampling and algorithm randomness.
The optimization problem is
Equip the matrix space with the Frobenius inner product and its norm ; gradients are taken with
respect to this inner product. Write for the induced
Euclidean operator norm, also called the spectral norm. Its dual under
the Frobenius pairing is the nuclear norm: The algorithm receives , and ; the objective and the oracle’s
distributional model are accessible only through queries.
Our assumptions:
Assumption 1 (Spectral smoothness). The function
is Fréchet differentiable
everywhere, and
Assumption 2 (Lower bound and initial gap). There
exists such
that
Assumption 3 (Unbiased oracle with a row variance
profile). Let be a probability
measure on a measurable sample space . The oracle is specified by a
jointly measurable map . For every , the random matrix is Bochner integrable for , and There exist a fixed orthonormal basis of and numbers with For every
and , the vector belongs to and satisfies At call , a query receives , where the measurable sample
variables are
mutually independent with common law . Algorithm randomness is independent
of the entire sample sequence.
Our formulation is algorithm-specific: we analyze batched polar
updates. Define the polar direction as the minimum-Frobenius-norm
maximizer of the linear objective over the spectral unit ball: The second minimizer is unique, including at
rank-deficient . The method
chooses a constant step size , a batch size , and an integer from its inputs. Starting at the
given , it makes queries at each , for , and follows These query and update rules must hold for every
possible sequence of oracle replies. A measurable index , drawn from the algorithm’s randomness
independently of the samples, is uniform on . After oracle calls, the output is The output remains after any additional calls. The call
count includes the batch at ,
although the output is selected from .
Let be the joint law of the
algorithm randomness and the sample sequence. The output must be
measurable, its gradient’s nuclear norm must be integrable under , and the required accuracy is