Abstract Take a prime power q , an integer $$n\ge 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , and a coordinate subspace $$S\subseteq GF(q)^n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>G</mml:mi> <mml:mi>F</mml:mi> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>q</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:math> over the Galois field GF ( q ). One can associate with S an n -partite n -uniform clutter $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> , where every part has size q and there is a bijection between the vectors in S and the members of $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> . In this paper, we determine when the clutter $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> is ideal , a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly, the characterization differs depending on whether q is 2, 4, a higher power of 2, or otherwise. Each characterization uses crucially that idealness is a minor-closed property : first the list of excluded minors is identified, and only then is the global structure determined. A key insight is that idealness of $$\mathcal {C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>C</mml:mi> </mml:math> depends solely on the underlying matroid of S . Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence, we prove the Replication and $$\tau =2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>τ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> Conjectures for this class of clutters.

Abstract When faced with multiple minima of an inner-level convex optimization problem, the convex bilevel optimization problem selects an optimal solution which also minimizes an auxiliary outer-level convex objective of interest. Bilevel optimization requires a different approach compared to single-level optimization problems since the set of minimizers for the inner-level objective is not given explicitly. In this paper, we propose a new projection-free conditional gradient method for convex bilevel optimization which requires only a linear optimization oracle over the base domain. We establish $$O(t^{-1/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> convergence rate guarantees for our method in terms of both inner- and outer-level objectives, and demonstrate how additional assumptions such as quadratic growth and strong convexity result in accelerated rates of up to $$O(t^{-1})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and $$O(t^{-2/3})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msup> <mml:mi>t</mml:mi> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>2</mml:mn> <mml:mo>/</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for inner- and outer-levels respectively. Lastly, we conduct a numerical study to demonstrate the performance of our method.